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

количество элементов на верхнем уровне:(Length '(A (5 6) D)) => 3.22Ясно, что для этого необходимо организовать проход по верхнемууровню списка-аргумента с одновременным подсчётом числа егоэлементов. Из функций базового набора для реализации прохода подходятлишь функции car и cdr.

В рассматриваемой задаче достаточноиспользовать функцию cdr, вырабатывающую хвост списка – еёпоследовательное применение и будет означать движение по верхнемууровню списка. Ясно, что применять cdr следует до тех пор, пока списокне закончится, т.е. не станет пустым. Для подсчета длины будемиспользовать следующее правило: длина списка равна длине его хвоста,увеличенной на 1. Очевидно, что длина пустого списка равна нулю.

Такимобразом, получаем функцию, телом которой служит условное выражение сдвумя ветвями:(defun Length (L)(cond ((null L) 0)(T (+ 1 (Length (cdr L))) )))Вторая ветвь функции содержит рекурсивный вызов, а первая –условие выхода из рекурсии (равенство аргумента функции пустомусписку). Ветви рекурсивной функции, не содержащие рекурсивныхвызовов и определяющие условия завершения рекурсии, называютсяэлементарными. Обычно элементарные ветви предшествуют ветвям срекурсивными вызовами.В данном решении задачи рекурсивные вычисления обязательнозакончатся, поскольку с каждым рекурсивным вызовом функции Lengthсписок-аргумент становится на один элемент короче, и по исчерпанииэлементов списка проработает первая, элементарная ветвь функции.Для понимания хода вычисления рекурсивной функции полезнотрассировать её вычисление для конкретных значений аргументов. Лиспинтерпретатор для выполнения рекурсивных вызовов использует стек, вкотором запоминаются ещё необработанные вызовы (отложенныевычисления).

Ниже схематично показано изменение содержимого стека входе вычисления вызова Length с аргументом (А (5 6) D):(Length: L=(A (5 6) D) )=> 3→ (+ 1 (Length: L=((5 6) D) ))=> 3 ↑→ (+ 1 (Length: L=(D) ))=> 2 ↑→ (+ 1 (Length: L=() ) ) => 1 ↑└────=>0────┘Первоначально в стеке находится исходное обращение к функцииLength, с помощью знака = указано значение её формального параметраL. Затем в стек поочередно заносятся функциональные вызовы,получаемые в результате работы второй ветви функции Length.

Каждое23записываемое в стек выражение – это вызов функции сложения саргументом-вызовом Length при новом значении её параметра L. Внашем изображении стека эти вызовы записываются на очередной строке,и стоящая слева от них стрелка → означает занесение их в стек. Дляформального параметра L в каждом вызове Length указывается еголокальное значение.Стек растёт до тех пор, пока в него не попадёт выражение,содержащее вызов Length с аргументом, равным NIL. Это выражениеможно сразу вычислить (проработает элементарная ветвь функции,вычисляющая длину пустого списка) и убрать его из стека. Вычисленноезначение используется для вычисления предыдущего записанного в стеквыражения.

Так последовательно, в обратном порядке выполняютсяотложенные в стек функциональные вызовы, и вычисленные при этомзначения передаются для вычисления других отложенных в стеквыражений. В нашем схематическом изображении эта передачапоказывается стрелкой ↑, стоящей справа от вычисленных значений. Этотпроцесс заканчивается, когда стек пуст и вычислено значение исходногообращения к функции Length.Отметим, что при заполнении стека новые локальные связипеременной-параметра L отменяют на время старые, но старые связивосстанавливаются лисп-интерпретатором тогда, когда вычислениявозвращаются к соответствующему функциональному вызову.В качестве следующей задачи запрограммируем функцию-предикатMember от двух аргументов А и L: (Member А L).

Функция проверяет,входит ли аргумент-атом А в заданный список L на верхнем его уровне, ивырабатывает по результатам этой проверки значение T или NIL:(Member 'Q '(Е (C) Q В)) => T(Member 'Q '(Е (C) В)) => NILОба аргумента функции вычисляются. Будем предполагать, что значениеаргумента А всегда есть символьный атом, в то же время список L можетсодержать на верхнем уровне неатомарные элементы.Как и в предыдущей задаче, требуется последовательный просмотрсписка, однако теперь необходимо ещё сравнение очередного элементасписка с заданным атомом. Проход по списку опять можно организовать спомощью функции cdr, тогда очередной элемент списка может бытьполучен обращением к функции car.

Сравнение этого элемента созначением аргумента А реализует функция eq (она требует обязательнойатомарности только одного своего аргумента). Поскольку возможны дваразных исхода сравнения, необходимы две ветви функции: если найденатом A, то следует завершить вычисление функции со значением T, если24же результат сравнения отрицателен, то необходимо рекурсивнопродолжать поиск атома А (в хвосте списка L). Если же в процессерекурсивных вызовов список L стал пуст, это означает, что искомого атоманет в этом списке, и значение функции должно быть равно NIL.Получающееся таким образом определение функции:(defun Member (А L)(cond ((null L) NIL)((eq A (car L)) T)(T (Member A (cdr L)) )))Эта функция имеет три ветви, из них две первые – элементарные,порядок всех ветвей строго определён.

Первая ветвь работает в том случае,когда список L пуст, и не может быть переставлена со второй, так какфункция car должна иметь непустой аргумент-список. Завершаемостьрекурсивных вычислений гарантируется тем, что рекурсивный вызовпроисходит с более простым аргументом.Схематично покажем процесс рекурсивных вычислений в стеке:(Member: A=Q, L=(Е (C) Q B) )=> T→ (Member: A=Q, L=((C) Q B) )=> T ↑→ (Member: A=Q, L=(Q B)) => T ↑Заметим, что во многих реализациях Лиспа (в том числе в MuLisp иCommonLisp) есть встроенная функция member, отличающаяся отзапрограммированной нами тем, что если атом-значение параметра Австречается в списке L, то функция в качестве своего значения выдаётчасть списка, начинающуюся с этого атома:(member 'Q '(Е (C) Q В)) => (Q В) .Такая особенность позволяет использовать member и как предикат, и какфункцию поиска нужного подсписка.

Для её реализации во второй ветвиприведённого выше определения функции надо заменить атом T напеременную L.Ещё одна задача – построение рекурсивной функции Append отдвух аргументов-списков L1 и L2. Функция соединяет (сливает)элементы верхнего уровня обоих списков в один список, например:(Append '(Q R T) '(K M)) => (Q R T K M)(Append '(B (A)) '((C C) () D))=> (B (A) (C C) NIL D)Действие Append иногда называют конкатенацией списков. Врезультате должен быть построен новый список, на верхнем уровнекоторого находятся сначала элементы верхнего уровня первого списка, а25затем – элементы верхнего уровня второго списка, причём в той жепоследовательности, что и в исходных списках. Поскольку в базовомнаборе функций Лиспа есть только одна встроенная функция cons,формирующая новый список, то для решения нашей задачи придётсяпоследовательно её использовать, каждый раз отщепляя очереднойэлемент от одного из списков-аргументов (например, от первого) иприсоединяя его к другому при помощи cons.

Этот процесс надозакончить, когда первый список-аргумент станет пустым (при этомзначением функции будет второй список).Определённая таким образом функция имеет две ветви:(defun Append(L1 L2)(cond ((null L1) L2)(T (cons (car L1)(Append (cdr L1) L2)))))Ключевым при программировании рекурсивной ветви являетсяправильный порядок вызовов функций, согласно следующей идее:результат слияния двух списков есть результат присоединения первогоэлемента первого списка-аргумента к списку, получающемуся в результатерекурсивного слияния хвоста первого списка со вторым списком.Рассмотрим вычисление вызова функции Append в стеке:(Append: L1=(Q R T), L2= (K M) )=> (Q R T K M)→(cons 'Q(Append: L1=(R T), L2=(K M)))=>(Q R T K M)↑→(cons 'R(Append: L1=(T), L2=(K M) )) =>(R T K M)↑→(cons 'T(Append: L1=(),L2=(K M))) =>(T K M)↑└───────=>(K M)─────┘Видно, что реальное присоединение элементов первого списка ко второмусписку откладывается до тех пор, пока не проработает элементарная ветвьфункции.

Тогда будет вычислено выражение, положенное в стекпоследним (в нём подчеркнуто вычисленное по элементарной ветвиобращение к Append и показано полученное значение), и начнётсяпоочередное вычисление предыдущих отложенных функциональныхвызовов. Результирующий список (Q R T K M) последовательностроится, начиная с присоединения T (последнего элемента первогосписка-аргумента) к началу второго списка.Если же поменять в рекурсивной ветви определения функцииAppend порядок вызовов функций cons и Append, то получим функциюRevAppend:26(defun RevAppend(L1 L2)(cond ((null L1) L2)(T (RevAppend (cdr L1)(cons (car L1) L2)) )))Эта функция при соединении списков будет менять порядокследования элементов первого списка на противоположный:(RevAppend '(Q R T) '(K M)) => (T R Q K M) .В этом можно убедиться, проследив вычисление функции в стеке:(RevAppend: L1=(Q R T), L2= (K M))=> (T→(RevAppend: L1=(R T), L2=(Q K M)) => (T→(RevAppend: L1=(T), L2=(R Q K M)) => (T→(RevAppend: L1=(), L2=(T R Q K M))=>(TRRRRQQQQKKKKM)M)↑M)↑M)↑Рассмотренная функция Аppend является встроенной в диалектахCommon Lisp и MuLisp.1.6.

S-выраженияОсновной лисповской структурой данных является так называемоеS-выражение, обобщающее понятие списка и атома:S-выражение ::= атом | (S-выражение └─┘.└─┘S-выражение)Как и ранее, знак └─┘ в приведённой БНФ обозначает пробел.В простейшем случае лисповское выражение – это атом, а в болеесложном – списочная структура, или точечная пара, соединяющая дваS-выражения. Как и введённое ранее понятие лисповского списка, понятиеS-выражения определяется рекурсивно и допускает произвольноеколичество вложений точечных пар друг в друга, например:((Т . К) . NIL)((А . В) .(С . (А .

Е )))В общем случае разделяющая точка в точечной паре должна бытьвыделена пробелами слева и справа, чтобы не слиться со стоящим слеваили справа атомом (т.к. обычно точка допускается в именах атомов). Еслиже слева или справа от точки стоит скобка, то соответствующий пробелможет быть опущен.Для S-выражений функции базового набора car, cdr и consопределены следующим образом.

Пусть значением формы Е являетсяS-выражение (v1 . v2), а v1 и v2 – некоторые S-выражения:Е => (v1 . v2) ,тогда(car Е) => v1 , (cdr Е) => v2 .27Если S-выражения e1 и e2 имеют значения v1 и v2 соответственно:e1 => v1 ,e2 => v2 ,то(cons e1 e2) => (v1 . v2) .Таким образом, аргументами функции cons могут быть произвольныелисповские выражения, в том числе – атомы.Поскольку S-выражение – обобщение понятий атома и списка, вселисповские списки можно записать как S-выражения, используя точечнуюзапись.