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

Проиллюстрируемпроцесс преобразования на примере выражения (X & (Y V TRUE)),используя вышеописанную технику переписывания:0)1)2)3)4)5)(TranOp: X=(X & (Y V TRUE)))(TranExpr: X=(X & (Y V TRUE)))(list 'AND (TranOp: X=X)(TranOp: X=(Y V TRUE)))(list 'AND 'X (TranOp: X=(Y V TRUE)))(list 'AND 'X (TranExpr: X=(Y V TRUE)))(list 'AND 'X (list 'OR (TranOp: X=Y)(TranOp: X=TRUE)))6) (list 'AND 'X (list 'OR 'Y (TranOp: X=TRUE)))7) (list 'AND 'X (list 'OR 'Y 'T))8) (list 'AND 'X '(OR Y T))=> (AND X (OR Y T))Видно, что функции TranOp и TranExpr реализуют рекурсивнуюобработку логического выражения, однако ни та, ни другая несоответствует определению прямой рекурсии, поскольку в их телахотсутствует вызов их самих. Значит, необходимо уточнить определениерекурсивной функции с учетом динамики вычислений.Функция называется рекурсивной, если в процессе вычисления еётела может возникнуть обращение к ней самой.

Это определение ужеохватывает и случаи косвенной рекурсии, подобные рассмотреннымфункциям TranOp и TranExpr: первая функция в процессе вычисленийобращается ко второй, а она, в свою очередь – к первой. Вообще говоря,может быть более сложная цепочка вызовов, включающая большееколичество взаимосвязанных функций.При косвенной рекурсии вызывающие друг друга функции частоназывают взаимно рекурсивными.2.3. Параллельная рекурсияПараллельная рекурсия относится к прямой рекурсии, нопредставляет более сложный (чем простая рекурсия) её вид.

Она обычновозникает, когда необходим анализ и обработка всех уровней некоторогосписочного выражения, как в ранее приведённой функции Copy.Рассмотрим этот вид рекурсии на примере построения функциипредиката MemberS от двух аргументов A и L. Функция определяет,содержится ли атом, являющийся значением аргумента A, в списочномвыражении, являющемся значением L, хотя бы на одном из его уровней, ивырабатывает соответственно T или NIL:46(MemberS 'S '(A (X K) M (Z (D S)) V)) => T(MemberS 'Y '(A (X K) M (Z (D S)) V)) => NILЭта функция обобщает действие ранее рассмотренной функции Member,проверяющей вхождение только на верхнем уровне списочноговыражения.Необходимый рекурсивный просмотр списка проще организовать наоснове определения S-выражения.

Согласно нему, следует рассмотреть дваслучая для S-выражения – атом и точечную пару. В случае атома его надопроверить на равенство значению A, а в случае точечной пары –продолжать поиск в выражениях, являющихся левой и правой частью этойпары (они получаются соответственно функциями car и cdr). Такимобразом, просмотр исходного списочного выражения проводится дополучения очередного его атома (лист бинарного дерева, представляющегообрабатываемое S-выражение). Следует также учесть, что атом-значение Aвходит в точечную пару, если он входит либо в левую, либо в правую еёчасть (в левое или правое поддерево). Соответствующее определение:(defun MemberS (A L)(cond((atom L)(eql A L)) ; дошли до атома(T(or(MemberS A(car L));поиск в левом поддереве(MemberS A(cdr L));поиск в правом поддереве)) ))Отметим, что структура тела этой функции соответствуетрекурсивной структуре обрабатываемого S-выражения: две её ветвисоответствуют атому и точечной паре, причём во второй ветви находятсясразу два рекурсивных вызова (аргументы функции or).

Говорят, чтоимеет место параллельная рекурсия, если в теле определяемой функциисодержится вызов некоторой функции, не менее двух аргументов которойявляются рекурсивными вызовами определяемой функции. В такихслучаях говорят также, что рекурсия проводится и вширь, и вглубьсписочного выражения.Покажем ход вычисления функции MemberS, используя техникупереписывания:0) (MemberS: A=S, L=(A (Z (D S)) V))1) (or (MemberS: A=S, L=A)(MemberS: A=S, L=((Z(D S))V)))2) (or NIL (MemberS: A=S, L=((Z(D S))V))3) (MemberS: A=S, L=((Z(D S))V)4) (or (MemberS: A=S,L=(Z(D S)))(MemberS: A=S, L=(V)))5) (or (or (Members: A=S, L=Z)(Members: A=S, L=((D S))))(MemberS: A=S, L=(V)))476) (or (or NIL (MemberS: A=S, L=((D S))))(MemberS: A=S, L=(V)))7) (or (MemberS: A=S, L=((D S))))(MemberS: A=S, L=(V))8) (or (or(MemberS: A=S, L=(D S))(MemberS: A=S, L=()))(MemberS: A=S, L=(V)))9) (or (or(or(MemberS: A=S, L=D)(MemberS: A=S, L=(S)))(MemberS: A=S, L=()))(MemberS: A=S, L=(V)))10) (or (or(or NIL (MemberS: A=S, L=(S)))(MemberS: A=S, L=()))(Member: A=S, L=(v)))11) (or (or(MemberS: A=S,L=(S))) (MemberS: A=S, L=()))(MemberS: A=S, L=(V)))12) (or (or(or(MemberS: A=S, L=S)(MemberS: A=S, L=()))(MemberS: A=S, L=())) (MemberS: A=S, L=(V)))13) (or (or(or T (MemberS: A=S, L=()))(MemberS: A=S, L=()))(MemberS: A=S, L=(V)))14) (or (or T (MemberS: A=S, L=()))(MemberS: A=S, L=(V)))15) (or T (MemberS: A=S, L=(V)))=> TВ рассмотренной задаче можно было бы обойтись без параллельнойрекурсии, если поместить проверку поддеревьев на разные ветви функции:(defun MemberS (A L)(cond ((atom L)(eql A L))((MemberS A (car L)) )((MemberS A (cdr L)) )))Возможен и другой вариант решения этой задачи – на основерекурсивного определения лисповского списка, а не S-выражения:(defun MemberSL (A L)(cond ((null L) NIL) ;случай пустого списка((atom (car L)) ;анализ 1-го элемента L(cond ((eql (car L) A) T)(T (MemberSL A (cdr L)) )))((MemberSL A (car L))((MemberSL A (cdr L)) )) ))В этом варианте на второй ветви тела функции выполняется анализпервого элемента списка L, и поэтому нужна дополнительная (первая)ветвь, на которой проверяется непустота списка L.

В итоге получаетсяболее длинное и более сложное для понимания определение.48Ещё один пример параллельной рекурсии, которую можнопреобразовать в простую – это функция Equal, проверяющая равенстводвух произвольных S-выражений и выдающая соответственно T или NIL:(Equal '(A (S) D) '(A (S) D)) => T(Equal '(A . B) '(A . B)) => T(Equal '(R T) '(Q R T)) => NILЕё определение с учётом структуры S-выражений:(defun Equal (X Y)(cond ((atom X)(eql X Y))((atom Y) NIL)(T (and (Equal (car X)(car Y))(Equal (cdr X)(cdr Y)) )))Основная идея проверки – одновременный проход по списочнымвыражениям X и Y вместе со сравнением соответствующих их частей.

Наветвях функции последовательно рассматриваются все возможные случаи(Х – атом; Х не атом, а Y – атом; Х и Y – не атомы). Как и в функцииMemberS, для сравнения атомов используется встроенная функция eql,реализующая сравнение как символьных, так и числовых атомов. Заметим,что можно упростить последнюю ветвь cond, записав в качестве условияэтой ветви первый аргумент функции and, а в качестве вычисляемоговыражения – второй аргумент.Рассмотрим теперь задачу, в которой нельзя обойтись безпараллельнойрекурсии.ЗапрограммируемфункциюNumber,подсчитывающую общее количество атомов в произвольном списочномвыражении:(Number '((A (X K) M ()(Z (D S)) V)) => 8Для программирования подсчёта атомов на базе определенияS-выражения желательно сформулировать действие этой функции втерминах бинарного дерева, представляющего обрабатываемое списочноевыражение. Ясно, что должен вестись подсчёт листьев этого дерева,однако остаётся вопрос, учитывать ли при этом атомы NIL (они могутвстречаться как в левых, так и в правых листьях дерева).

Для простотыбудем считать, что функция не будет учитывать атомы NIL. Поэтому вопределении функции Number кроме двух ветвей, соответствующих двумслучаям S-выражения (атом и точечная пара), появляется дополнительная,первая ветвь, соответствующая атомам NIL.Таким образом, вторая ветвь тела функции учитывает атомы,отличные от NIL, а на рекурсивной ветви суммируется число атомов влевом и правом поддереве:49(defun Number (X)(cond ((null X) 0)((atom X) 1)(T (+ (Number (car X))(Number (cdr X)) )) ))Покажем процесс вычисления вызова функции Number:0)1)2)3)4)5)6)7)8)9)10)11)12)13)14)15)16)17)18)(Number: X=(A (X K) M ()) )(+(Number: X=A)(Number: X=((X K) M ()) ) )(+ 1 (Number: X=((X K) M ()) ) )(+ 1 (+ (Number: X=(X K) ) (Number: X=(M ()) )))(+ 1 (+ (+ (Number: X=X)(Number: X=(K) ))(Number: X=(M ()) )))(+ 1(+(+ 1 (Number: X=(K) ))(Number: X=(M ()) )))(+ 1 (+ (+ 1 (+ (Number: X=K)(Number: X=() )))(Number: X=(M ()) )))(+ 1 (+ (+ 1 (+ 1 (Number: X=() )))(Number: X=(M ()) )))(+ 1 (+ (+ 1 (+ 1 0))(Number: X=(M ()) )))(+ 1 (+ (+ 1 1)(Number: X=(M ()) )))(+ 1 (+ 2 (Number: X=(M ()) )))(+ 1 (+ 2 (+ (Number: X=M)(Number: X=(()) ))))(+ 1 (+ 2 (+ 1 (Number: X=(()) ))))(+ 1 (+ 2 (+ 1 (+ (Number: X=() )(Number: X=() )))))(+ 1 (+ 2 (+ 1 (+ 0 (Number: X=() )))))(+ 1 (+ 2 (+ 1 (+ 0 0))))(+ 1 (+ 2 (+ 1 0)))(+ 1 (+ 2 1))(+ 1 3)=> 4Так же, как и в случае с функцией MemberS, данное решение,основанное на рекурсивном определении S-выражения, проще и понятнеерешения, полученного на основе определения лисповского списка, вкотором отдельно анализируются случаи с первым элементом списка:(defun NumberL (X)(cond ((null X) 0)((null (car X)) (NumberL (cdr X)))((atom (car X)) (+ 1 (NumberL (cdr X))))(T (+ (NumberL (car X))(NumberL (cdr X)) )) ))50Таким образом, при решении задач, требующих полного просмотрасписочного выражения, опора на рекурсивное определение S-выраженияприводит обычно к более простым и понятным функциям.2.4.

Накапливающий параметрТипичным приёмом функционального программирования являетсявведение и использование функции с дополнительным аргументом,выполняющим роль накапливающего параметра.Рассмотрим задачу одновременного подсчёта суммы и произведениянескольких чисел. Эти числа задаются как элементы входного списка, арезультатом вычисления должна быть списочная пара (S . P),состоящая из суммы S этих чисел и их произведения P. Например:(SumPr '(12 4 3 10)) => (29 . 1440)Одним из решений этой задачи является функция SumPr1:(defun SumPr1 (X)(cond((null X) (cons 0 1))(T(cons(+ (car X) (car (SumPr1 (cdr X))))(* (car X) (cdr (SumPr1 (cdr X))))))))На элементарной ветви этой функции строится точечная пара изсуммы и произведения, соответствующих пустому списку чисел.

Вовторой ветви для пересчёта этой точечной пары используется параллельнаярекурсия. Очевидна неэффективность этого решения: дважды вычисляетсявыражение (car X), а также дважды вычисляется одно и то жерекурсивное обращение к SumPr1 – такое дублирование рекурсивныхвызовов функции даёт экспоненциальный эффект, увеличивая общее числорекурсивных вызовов с n (длина исходного списка) до 2n.Дублирования можно избежать, если сохранять промежуточныерезультаты вычисления – для этого необходимо завести дополнительнуюфункцию или же использовать эквивалентную, но более удобную напрактике конструкцию let, которая вводит локальные переменные длявычисляемых выражений. В нашем случае в let нужны две переменные:Y – для значения (car X), и Z – для вычисленного рекурсивногообращения.