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

Этот проход можно реализовать без вспомогательнойфункции, используя функционал mapcar. Получим таким образом болеекороткое и простое решение:(defun Decart2 (M1 M2)(cond((null M1) NIL)(T (append(mapcar#'(lambda(Z)(list(car M1)Z))M2) ; M2 - второй аргумент mapcar(Decart2 (cdr M1) M2) )) ))На первый взгляд кажется, что и проход по элементам списка M1(внешний цикл) можно реализовать аналогичным образом на базе mapcar:(defun Decart3 (M1 M2)(mapcar #'(lambda (Y)(mapcar #'(lambda (Z) (list Y Z))M2 ))M1 ))Однако это не совсем верно, поскольку в итоговом списке-произведенииполучаются лишние скобки:(Decart3 '(A B C) '(D E)) =>(((A D)(A E))((B D)(B E))((C D)(C E)))Причина ошибки в том, что в функциях Decart_1 и Decart_2 длясоединенияпромежуточныхсписков-результатов(декартовыхпроизведений элементов-атомов из M1 со вторым множеством M2)применялась функция append, а функционал mapcar использует для ихсоединения функцию cons.Один из возможных способов исправления этой ошибки –ликвидировать возникшие лишние скобки, обратившись дополнительно ккакой-либо функции, например, к встроенному функционалу reduce(пригоден любой из двух вариантов редукции):(defun Decart4 (M1 M2)(reduce 'append (Decart3 M1 M2):initial-value NIL))75Однако более удачным представляется решение, в котором прислиянии списков, полученных внутренним mapcar, лишние скобки простоне образуются.

Для этого потребуется определить новый функционалMapАppend – аналог mapcar, который соединяет результаты применениясвоего аргумента-функции F к элементам списка L с помощью функцииappend:(defun MapАppend (F L)(cond ((null L) NIL)(T (append (funcall F (car L))(MapАppend F (cdr L) )) )) )Пример обращения к этому функционалу:(МapАppend #'(lambda (Y)(list Y 'W)) '(5 9 3))=> (5 W 9 W 3 W)Заменяя теперь в функции Decart3 внешнее обращение к mapcarна МapАppend, получаем короткое и верное решение исходной задачи,демонстрирующее выразительную мощность функционалов:(defun Decart5 (M1 M2)(Мapappend #'(lambda (Y)(mapcar #'(lambda (Z)(list Y Z))М2 ))М1 ))На основе аналогичных рассуждений построим функциюформирования всех подмножеств заданного множества (булеан заданногомножества) с помощью встроенных функционалов.

Назовём эту функциюSubsets. Как и в предыдущей задаче построения декартова произведениямножеств, исходное множество задаётся как одноэлементный списокатомов, а результирующий список является уже списком списковподмножеств. Порядок элементов в исходном и в итоговом списке неважен, важно однако, что в обоих списках нет повторяющихся элементов.Пример вызова функции Subsets и её определение для диалектаCommon Lisp:(Subsets '(A S D)) =>(NIL (A) (S) (S A) (D) (D A) (D S) (D S A));определение Subsets для Common Lisp(defun Subsets(M)(reduce #'(lambda (X Y)(append X(mapcar #'(lambda(Z)(cons Y Z)) X)))M :initial-value '(NIL) ))76Идея решения заключается в последовательном рассмотрении элементовисходного списка.

При этом на каждом шаге для очередного элемента наоснове уже построенных подмножеств строится группа новыхподмножеств, получающаяся вставкой этого элемента в каждое изимеющихся подмножеств. Полученная группа новых подмножествобъединяется функцией append с подмножествами предыдущего шага.Таким образом, количество построенных подмножеств после каждого шагаувеличивается вдвое, а общее количество подмножеств заданногомножества – 2N, где N – количество элементов-атомов в этом множестве.На первом шаге множество построенных подмножеств состоит изединственного пустого множества, обозначаемого NIL (третий аргументфункционала reduce – (NIL)).Как и для функций Decart из предыдущей задачи, для полученияопределения Subsets в диалекте MuLisp необходима замена вприведённом определении функциональной блокировки #' на обычнуюблокировку ', а также исключение в вызове функционала reduce имениключевого параметра :initial-value.В заключение, для дополнительной иллюстрации отличий впрограммировании функционалов в диалектах MuLisp и Common Lispрассмотрим вновь задачу определения функционала mapcar – теперьуже на основе функционала maplist.

В Common Lisp решение этойзадачи получается достаточно просто:;определение Мapcar на основе Мaplist для Common Lisp(defun Мapcar(F L)(maplist #'(lambda(X)(funcall F (car X))) L))В MuLisp функциональная блокировка отсутствует, а заменить её напростое квотирование в данном случае нельзя, т.к. в лямбда-выражениивместо формального параметра F необходимо брать его конкретныезначения. Поэтому в решении для MuLisp нужное лямбда-выражениестроится в ходе вычислений:;определение Мapcar на основе Мaplist для MuLisp(defun Мapcar(F L)(maplist (list 'lambda '(X) (list F '(car X))) L))3.5. Функционалы с функциональным значениемАналогично тому, как функция может быть аргументом другойфункции, она может быть и результатом (значением) функции, т.е.функция высшего порядка может иметь функциональное значение.Следующий пример показывает определение такой функции:77; определение функции Increment для языка Common Lisp(defun Increment (N) #'(lambda (Z) (+ Z N)) ))Значением функционала Increment является определяющеевыражение безымянной функции (лямбда-выражение) от одногоаргумента, которая добавляет к своему аргументу некоторое значение N(это свободная переменная в теле возвращаемой функции).В данном определении функционала Increment использованафункциональная блокировка function (или #'), которая кромеквотирования лямбда-выражения выполняет также связывание свободнойдля этого лямбда-выражения переменной N со значением аргументафункции Increment, что позволяет затем использовать такое замкнутоелямбда-выражение в качестве функционального аргумента другихфункционалов.Определение функционала Increment в диалекте MuLisp, безсредств встроенного замыкания, опять сложнее:; определение функции Increment для языка MuLisp(defun Increment (N)(list 'lambda '(Z) (list '+ 'Z N)))Это определение основано на следующей идее: чтобы вернуть функцию,увеличивающую свой аргумент на заданное число, необходимо построитьи вернуть лямбда-выражение, в котором вместо N уже будет подставленозаданное в качестве аргумента функции Increment значение.Различие двух приведённых определений функции Incrementобусловлено разными видами связывания переменных с их значениями,реализованными в диалектах MuLisp (динамическое связывание) иCommon Lisp (статическое связывание), а также наличием в Common Lispфункциональной блокировки – встроенной формы function (или #').Последнее существенно при программировании именно функционалов сфункциональным значением, поэтому далее для таких функционалов даёмдва определения – для MuLisp и для Common Lisp, а примерывозвращаемых значений этих функционалов приводим только для MuLisp.При разных N функционал Increment в MuLisp выдаёт в качествесвоего значения разные лямбда-выражения – безымянные функции сразными приращениями своего аргумента, например:(Increment 2) =>(LAMBDA (Z) (+ Z 2))(Increment 10) =>(LAMBDA (Z) (+ Z 10))В обоих диалектах функционал Increment можно использовать вдругих функционалах:78(mapcar (Increment 2) '(1 8 15)) => (3 10 17)(funcall (Increment 10) 5) => 15Приведём теперь определениефункциональным значением:функцииTwice,такжес; определение функции Twice для языка Common Lisp(defun Twice (F)(function (lambda (X) (funcall F (funcall F X))))); определение функции Twice для языка MuLisp(defun Twice (F)(list 'lambda '(X)(list 'funcall (list 'quote F)(list 'funcall (list 'quote F) 'X))))У функции Twice не только функциональное значение, но ифункциональный аргумент.

Результат её вычисления – определяющеевыражение функции, дважды применяющей заданную функцию F отодного аргумента. Например:(Twice 'list) =>(LAMBDA (X)(FUNCALL (QUOTE LIST)(FUNCALL (QUOTE LIST) X)))(mapcar(Twice 'list)'(5 7 8)) => (((5)) ((7)) ((8)))(funcall (Twice (Increment 3)) 5)) => 11Ещё один функционал Composition с функциональнымиаргументами и значением выполняет композицию F•G двух заданныхфункций (порядок применения F и G соответствует общепринятому):; определение функции Composition для Common Lisp(defun Composition (F G)(function (lambda (X)(funcall G (funcall F X)))) ); определение функции Composition для языка MuLisp(defun Composition (F G)(list 'lambda '(X)(list 'funcall (list 'quote G)(list 'funcall (list 'quote F) 'X))))Примеры применения этого функционала:(funcall (Composition (Increment 5) 'list) 7) => (12)(Composition (Increment 5) 'list) =>(LAMBDA (X)(FUNCALL (QUOTE LIST)(FUNCALL (QUOTE (LAMBDA (Z)(+ Z 5))) X)));возвращаемое лямбда-выражение приведено для MuLisp794.

Дополнительные возможностиОписанное в предыдущих разделах функциональное подмножествоязыка Лисп достаточно для программирования многих задач обработкисимвольных данных. Рассматриваемые в данном разделе средстварасширяют возможности языка и могут изучаться по мере необходимости.4.1.Список свойств атомаКак уже отмечалось ранее, с любым символьным атомом(идентификатором) в Лиспе могут быть связаны следующие значения: еговнешнее имя, его значение как параметра некоторой функции,функциональное значение и список свойств атома.