Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп, страница 4

Значением этойформы является имя определяемой функции:(defun f (x1 x2 … xk) e) => F,k≥0Однако основное действие функции defun – связывание с именем fлямбда-выражения (lambda (x1 … xk) e), что означает определениеновой функции с именем f и указанным определяющим выражением. Вдальнейшем можно обращаться к этой функции с фактическими(f p1 … pk), что будет означатьпараметрами p1, …, pk :вычисление лямбда-вызова ((lambda (x1 … xk) e) p1 … pk),т.е. имя функции при вычислении функционального вызова заменяется еёопределяющим выражением.Приведём пример определения и использования функции List2,образующей список из значений двух своих аргументов:(defun List2 (x y) (cons x (cons y ()))) => LIST2(List2 '(A) 'B) => ((A) B)(List2 'Y 'X) => (Y X)(List2 T '(С (Е))) => (T (С (Е)))Действие List2 сводится к вложенным вызовам функции cons, причёмвторой аргумент внутреннего вызова cons – пустой список, служащийосновой формирования результирующего списка.Ещё один пример – определение функции InsNew, вставляющейатом NEW после первого элемента своего аргумента-списка (на верхнемего уровне):(defun InsNew(x)(cons(car x)(cons 'NEW (cdr x)))) => INSNEW(InsNew '(F (T E ())С)) => (F NEW (T E NIL) С)Эта функция фактически строит новый список, состоящий из первогоэлемента исходного списка, атома NEW и хвоста исходного списка.Кроме рассмотренного способа обращения к функции defun обычнодопускается и такое обращение:(defun f (lambda (x1 … xk) e)) .При этом способе (являющимся исторически первым) более явно виднасвязь имени f функции с её определяющим выражением.

Однако гораздочаще используется упрощённая запись, когда исключены внешние скобкилямбда-выражения и атом lambda.16Во многих диалектах Лиспа есть встроенная особая функция let,обращение к которой является ничем иным, как другой формой записилямбда-вызова:(let ((x1 p1)(x2 p2)…(xn pn)) e)≡((lambda (x1 … xn) e) p1 … pn) .В конструкции let формальные и фактические параметры сгруппированыпопарно и помещены в начало, а её вычисление происходит таким жеобразом, как и вычисление соответствующего ей лямбда-вызова.Например:(let ((x 'A) (y 3)) (cond (x) (y)))=> AЧаще всего эта конструкция используется для сокращения вычислений вслучаях, когда некоторое выражение надо вычислить и использоватьнесколько раз.

К примеру, следующее условное выражение:(cond ((atom (F1 x))(F1 x))((eq x (F2 y))(F3 (F2 y)))(T (F3 x) ))в котором дважды вычисляется (F1 x) и (F2 y), можно переписать сиспользованием let, исключив повторные вычисления:(let ((x1 (F1 x))(y2 (F2 y)))(cond ((atom x1) x1)((eq x y2) (F3 y2))(T (F3 x) )))Подытожим возможные случаи вычислимости лисповского списка.Лисповский список является функциональным вызовом только в двухслучаях: Первый случай – обращение к функции по имени: (f e1 … ek),k≥0; этот случай включает обращение к функции let. Второй случай – лямбда-вызов, или обращение к безымяннойфункции: (λ e1 … ek), где λ – лямбда-выражение, k≥0.Подчеркнём, что первый элемент списка-вызова функции не вычисляетсялисп-интерпретатором, он представляет собой либо явно заданное имяфункции, либо явно заданное определяющее выражение функции.1.4. Встроенные функцииДля практического программирования на Лиспе требуется болееширокий набор встроенных функций.

Различные диалекты Лиспавключают разное количество встроенных функций – от несколькихдесятков до нескольких сотен. Однако количество не столь важно,17поскольку большинство из них может быть запрограммировано на основеописанного выше базового набора лисп-функций и функции defun.Опишем ряд встроенных функций Лиспа, существующих вбольшинстве диалектов и широко применяемых как вспомогательные припрограммировании более сложных задач обработки списков.

В случае,когда эти функции могут быть легко запрограммированы на основебазового набора, мы приводим их определения.Описываемые функции сгруппированы по своему назначению.Большинство из них являются обычными, поэтому вид функции явнооговаривается только для особых функций.Функции обработки списковК этой группе относятся 28 обычных функций от одного аргументаcaar, cadr, cdar, cddr, caaar, caadr, …, cdddar, cddddr, действиекоторых эквивалентно определённой суперпозиции функций car и cdr.Эти суперпозиции позволяют, в частности, выбирать некоторый элемент снужного уровня списка-аргумента.

Например, функция caddr выбираетиз списка-аргумента третий элемент верхнего уровня, а функция caаdr –первый элемент списка, стоящего вторым на верхнем уровне:(caddr '(Р (С Е) В ())) => В ,(caadr '(Р (С Е) В ())) => С .Функция cddr выдаёт список без двух первых элементов верхнего уровня:(cddr '(Р (С Е) В ())) => (B NIL)Их определения: (defun caddr (x) (car (cdr (cdr x))))(defun caаdr (x) (car (cаr (cdr x))))(defun cddr (x) (cdr (cdr x)))Укажем общий вид имени функции-суперпозиции: c{[a|d]}r , гдефигурные скобки обозначают повторение, а в квадратных скобках указаныповторяющиеся буквы. Между буквами c и r имени может быть не болеечетырёх букв a и d.

Последовательность a и d в имени функциисоответствует порядку следования car и cdr в эквивалентнойсуперпозиции. Предполагается, что список-аргумент у всех функцийсуперпозиций содержит необходимое число элементов.В группу функций обработки списков входит также частоиспользуемая функция-конструктор list, составляющая список иззначений своих аргументов.

Эта функция относится к особым, поскольку унеё может быть произвольное число аргументов, но при этом всеаргументы вычисляются. Например:(list '(NUM К) () 'C) => ((NUM К) NIL C)18(list '(В) 'А) => ((В) А)Отметим, что в отличие от функции cons, результат функции listсимметричен относительно аргументов:но(list '(А) '(В)) => ((А)(В)) ,(cons '(А) '(В)) => ((А) В).Для любого фиксированного количества аргументов определитьфункцию list на основе базового набора и функции defun легко (см.пример функции List2 из предыдущего раздела), однако дляорганизации произвольного количества аргументов необходимыспециальные средства определения особых функций.Арифметические функцииЭти функции выполняют операции сложения, вычитания, умноженияи деления чисел и обозначаются общепринятым образом: + - * /.Операции + и * обычно определены для произвольного количествааргументов (от одного и более).

Операции – и / определены для двух иодного аргумента, в последнем случае они означают соответственноизменение знака числа-аргумента на противоположный и вычислениеобратной величины. Например:(+(*(((/12 -67 34) => -211 2 3 4) => 24-15 -3) => -12-56) => 56-12 3) => -4Заметим, что в случае операции деления результат может быть различен вразных диалектах Лиспа:(/ -12 5) => -2.4 в MuLisp и -12/5 в Common Lisp,(/ 4) => 0.25 в MuLisp и 1/4 в Common Lisp,т.е. когда результат деления целых чисел не является целым, в CommonLisp он записывается как рациональное число.Часто полезны встроенные в MuLisp функции add1 и sub1прибавления и вычитания единицы:(add1 23) => 24(sub1 23) => 22, (add1 -15) => -14, (sub1 -15) => -16Эти функции можно определить следующим образом:(defun add1 (x) (+ x 1))(defun sub1 (x) (- x 1)) .19Арифметические предикатыВсе эти функции имеют два вычисляемых аргумента, значениямикоторых должны быть числа.

Предикаты вырабатывают логическоезначение T или NIL, в зависимости от выполнения проверяемого условия:= (равенство чисел), /= (неравенство), < (меньше), > (больше), <= (небольше), >= (не меньше). Например:(= 1/4 0.25) => T(/= 1/4 (- 0.3 0.05)) => NIL(< 7 (+ 12 3)) => T(<= 7 (+ -12 3)) => NILАрифметический предикат evenp от одного числового аргументавозвращает T, если значение его аргумента является чётным числом, и NILв противном случае.

Примеры его использования:(evenp 25) => NIL(evenp (+ -15 -3)) => TОтметим, что для сравнения атомов-чисел применяется функция =, ане eq (поскольку запись одного числа может варьироваться). В случае,когда заранее неизвестно, какими будут сравниваемые атомы –символьными или числовыми, удобна функция-предикат eql, встроеннаяв MuLisp. Её можно определить следующим образом:(defun eql (x y)(cond ((numberp x)(cond ((numberp y)(= x y))(T NIL)))(T (eq x y))))Предикаты типаОдна из самых часто используемых функций в Лиспе – предикатnull, который вырабатывает атом T, если значение его аргумента – NIL,и атом NIL в противном случае.

Приведём определение и примериспользования этого предиката:(defun null (x) (eq x NIL))(null '(М)) => NIL(null (cdr '(М))) => TФункция-предикат listp выдаёт значение T, если значением еёаргумента является список, и NIL в противном случае.(listp 'А ) => NIL(listp (car '((А)) )) => T(listp (caar '((А)))) => NIL20Отметим, что в случае пустого списка listp вырабатывает значение T:(listp (cdr '((a)))) => TФункция listp может быть определена на основе базового наборавстроенных лисп-функций:(defun listp (x)(cond ((eq x NIL))((atom x) NIL)(T)))Предикат numberp вырабатывает T, если значение его аргумента –числовой атом, и NIL в противном случае.

Парный к нему встроенныйпредикат symbolp выдаёт T, если значением его аргумента являетсясимвольный атом, и NIL в противном случае:(numberp (car '(12 A S))) => T(numberp (cadr '(12 A S))) => NIL(symbolp (car '(12 A S))) => NIL(symbolp (cadr '(12 A S))) => T(symbolp '(12 A S)) => NIL(numberp '(12 A S)) => NIL(symbolp ()) => TЛогические функцииК логическим функциям-предикатам относят логическое отрицаниеnot, конъюнкцию and и дизъюнкцию or. Первая из этих функцийявляется обычной, а другие две – особыми, поскольку допускаютпроизвольное количество аргументов, которые не всегда вычисляются.Логическое отрицание not вырабатывает соответственно:(not NIL) => T и(not T) => NILи может быть определено функцией(defun not (x) (eq x NIL)) .Фактически действие этой функции эквивалентно действию функцииnull, работающей не только с логическими значениями T и NIL, но и спроизвольными лисповскими выражениями.

Поэтому, например:(not '(B ())) => NILТем самым, определение функции not соответствует лисповскомурасширенному пониманию логического значения истина. Заметим, что дваразных имени not и null для фактически одной функции удобны для еёиспользования в разных контекстах.21Две другие встроенные логические функции также используютрасширенное понимание истинного значения.Вызов функции and, реализующей конъюнкцию, имеет вид(and e1 e2 … en), n≥0.При вычислении этого функционального обращения последовательнослева направо вычисляются аргументы функции ei – до тех пор, пока невстретится значение, равное NIL.

В этом случае вычисление прерывается изначение функции равно NIL. Если же были вычислены все значения ei иоказалось, что все они отличны от NIL, то результирующим значениемфункции and будет значение последнего выражения en .Вызов функции-дизъюнкции имеет вид (or e1 e2 … en), n≥0.При выполнении вызова последовательно вычисляются аргументы ei(слева направо) – до тех пор, пока не встретится значение ei, отличное отNIL. В этом случае вычисление прерывается и значение функции равнозначению этого ei.

Если же вычислены значения всех аргументов ei, иоказалось, что они равны NIL, то результирующее значение функцииравно NIL.При n=0 значения функций: (and)=>T, (or)=>NIL.Приведём примеры вычислений этих функций:(and (atom T)(= 1 23)(eq 'A 'B)) => NIL(and (< 12 56) (atom 'Z) '(A S)) => (A S)(or (eq 'A 'B) (atom 'Y) ()) => Т(or (eq 'A 'B) 'Y '(T R)) => Y(or (atom '(Y V)) () (eq 'A 'B)) => NILТаким образом, значение функции and и or не обязательно равно Т илиNIL, а может быть произвольным атомом или списочным выражением.1.5.

Рекурсивные функцииРекурсия – мощный механизм вычислений, поддерживаемыйинтерпретатором языка Лисп. Примем за рабочее следующее определение:функция называется рекурсивной, если в её теле содержится хотя бы однообращение к ней самой. Рассмотрим несколько задач на программированиерекурсивных функций, используя для этого в основном базовый наборвстроенных функций Лиспа.В качестве первой задачи определим функцию Length (встроена вMulLisp и CommonLisp), вычисляющую длину своего аргумента-списка,т.е.