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

Эта функция будет иметь два аргумента – применяемуюоперацию F и исходный список X, т.е. будет функционалом. ОпределимFList как обычную функцию с вычисляемыми аргументами, поэтому приее вызове с нужными нам операциями последние должны квотироваться:(FList 'add1 X) и (FList 'sub1 X). Эти два функциональныхвызова должны быть эквивалентны соответственно вызовам функций(Аdd1List X) и (Sub1List X), в частности:(FList 'add1 '(5 17 0 3)) => (6 18 1 4)(FList 'sub1 '(5 17 0 3)) => (4 16 -1 2)Кажущееся очевидным определение FList, получающееся из Add1Listзаменой конкретной операции на формальный параметр F:(defun FList (F X)(cond ((null X) NIL)(T (cons (F (car X)) (FList F (cdr X))))))всё же неверно, и в этом легко убедиться, попробовав вычислить(FList 'add1 X) или (FList 'sub1 X).Причинаошибкисвязанасособенностьювычисленийфункциональных вызовов в языке Лисп. Любой вычислимый в Лиспесписок должен иметь в качестве своего первого элемента либо символьныйатом – имя функции (встроенной или уже определённой), либо лямбдавыражение, определяющее некоторую безымянную функцию.

Инымисловами, первый элемент вычисляемого списка (функционального вызова)никогда не вычисляется, он должен быть задан явно. В случае, когдапервый элемент – это атом (имя функции), лисп-интерпретатор используетсвязанное с этим символьным атомом определяющее выражение функции.Поэтому при вычислении тела функции FList, точнее, привычислении выражения (F (car X)) символ F будет трактоваться какимя функции, а такая функция не была определена. Чтобы исправитьошибку, необходимо при вычислении этого выражения использоватьвместо символа F его значение как фактического параметра. Применяявстроенную функцию eval, это можно сделать, например, так:(defun FList (F X)(cond ((null X) NIL)63(T (cons (eval (list F (list 'quote (car X))))(FList F (cdr X))))))При вычислении первого аргумента функции cons сначала формируетсясписок-обращение к нужной функции F (за счёт первого вычисленияфункцией eval своего аргумента), а затем сформированное обращениевычисляется (за счёт второго вычисления функцией eval своегоаргумента).

Чтобы при этом аргумент функции F не вычислялся дважды, входе первого этапа вычислений строится форма для его последующегоквотирования:(list 'quote(car X)) => (quote первый_элемент_X)).Функции add1 и sub1 являются встроенными в диалекте MuLisp,но их нет в Common Lisp. Однако и в этом диалекте легко применитьсозданный функционал, используя вместо имени функции еёопределяющее выражение:(FList '(lambda(x)(+ x 1)) '(5 17 0 3)) => (6 18 1 4)(FList '(lambda(x)(- x 1)) '(5 17 0 3)) =>(4 16 -1 2)При вычислении первого аргумента этих вызовов будет получено лямбдавыражение, которое будет использовано в теле функционала FListвместо формального параметра F.Таким образом, функциональный аргумент функционала FListвычисляется, и его значением должно быть либо имя функции от одногоаргумента (вычисляемого), либо её определяющее выражение:(FList 'list '(5 17 0 3)) => ((5)(17)(0)(3))(FList '(lambda(X)(cons X NIL)) '(5 17 0 3))=> ((5)(17)(0)(3))Рассмотренная нами функция FList встроена во многие диалектыЛиспа (в том числе – в MuLisp и Common Lisp) под именем mapcar.

Вбольшинстве диалектов есть целый набор встроенных функционалов,облегчающих программирование, включая создание и применение новыхфункционалов.3.2. Встроенные функционалыВстроенные функционалы обычно включают группу применяющих игруппу отображающих функционалов.Применяющиефункционалыпозволяютприменитьсвойфункциональный аргумент (функцию) к заданным её аргументам.Функционал apply является обычной функцией с двумявычисляемыми аргументами, обращение к ней имеет вид: (apply F L),64где F – функциональный аргумент и L – список: L =>(p1 … pn), n≥0,рассматриваемый как список фактических параметров для F.

Значениефункционала – результат применения F к этим фактическим параметрам,например: (apply '* '(2 5)) => 10(apply 'cons '(2 (5))) => (2 5)(apply 'list '(A B)) => (A B)(apply 'apply '(* (2 5))) => 10Отметим, что в приведённых примерах квотирование функциональногоаргумента является обязательным, поскольку функционал applyвычисляет значения всех своих аргументов.

Это вычислениедействительно необходимо в случаях, когда функциональный аргумент неможет быть задан непосредственно, поскольку не известен заранее иопределяется в ходе вычислений.Функционал funcall – особая функция с вычисляемымиаргументами, обращение к ней: (funcall F e1 … en), n≥0. Еёдействие аналогично apply, отличие состоит в том, что аргументыприменяемой функции F задаются не списком, а по отдельности.Например:(funcall '* 2 5) => 10(funcall 'cdr '((B) A)) => (A)(funcall 'list '(A B)) => ((A B))(funcall 'apply 'list '(A B)) => (A B)Поскольку функционал apply – обычная функция, он может бытьреализован на основе базового набора встроенных функций Лиспа ифункции defun по схеме:(apply F Е) ≡ (eval (list F '(car Е) '(cadr Е) … ))Его определение:(defun apply(F L)(eval (cons F (Qu L))))(defun Qu(L) ;вспомогательная функция квотирования(cond ((null L) NIL)(T (cons (list 'quote (car L))(Qu (cdr L))))))В этом определении используется Qu – вспомогательная функцияквотирования (блокировки вычисления) всех аргументов функции F, т.к.их число заранее неизвестно.В отличие от apply, функционал funcall может иметьпроизвольное количество аргументов (это особая функция), и для егореализации по схеме:(funcall F e1 … en) ≡ (eval (list F 'e1 'e2 … 'en))65требуются уже дополнительные средства определения особых функций,которые будут рассмотрены в дальнейшем.В группу отображающих функционалов входят функции mapcar иmaplist.

Их имена имеют префикс map (mapping – отображение),поскольку их действие – отображение списка-аргумента в списокрезультат за счёт применения заданной функции к элементам исходногосписка.Обращение к mapcar обычно имеет вид: (mapcar F L), приэтом оба аргумента вычисляются. В этом случае функционалпоследовательно применяет свой функциональный аргумент F (функциюот одного аргумента) к элементам списка L, которые извлекаются из Lфункцией-селектором car (поэтому имя car входит в имя функционала),и возвращает список из полученных значений. Схематично результатможет быть записан как((F (car L)) (F (cadr L)) (F (caddr L)) …).Покажем на примерах действие этого функционала (напомним,функция length вычисляет количество элементов на верхнем уровнесвоего списка-аргумента):(mapcar 'length '((A B) (C) (D E ()))) => (2 1 3)(mapcar 'list '(A S D F)) => ((A)(S)(D)(F))Описанныйфункционалmapcarможетзапрограммирован на основе функционала funcall:бытьлегко(defun mapcar (F L)(cond ((null L) NIL)(T (cons (funcall F (car L))(mapcar F (cdr L))))))Другой отображающий функционал maplist с обращением(maplist F L) последовательно применяет свой функциональныйаргумент F к списку-аргументу L и его хвостовым частям (полученным изL путём отбрасывания первого элемента, первых двух элементов и т.д.) ивозвращает список из вычисленных значений.

Как и mapcar, функционалmaplist является обычной функцией, вычисляющей свои аргументы.Схематично действие этого функционала можно записать как((F l) (F (cdr L)) (F (cddr L)) …)Приведём примеры его использования:(maplist 'reverse '(X Y Z)) => ((Z Y X) (Z Y) (Z))(maplist 'list '(A S D F))=> (((A S D F))((S D F))((D F))((F)))66Определение функционала maplist на основе funcall:(defun maplist (F L)(cond ((null L) NIL)(T (cons (funcall F L)(maplist F (cdr L))))))Без использования funcall этот функционал можно определить так:(defun maplist (F L)(cond ((null L) NIL)(T (cons (eval (cons F(cons (cons 'quote L)NIL)))(maplist F (cdr L))))))В общем случае функционалы mapcar и maplist допускаютфункциональный аргумент с числом параметров N≥1.

Вызовфункционалов имеет вид:(mapcar FN L1 L2 … LN) и(maplist FN L1 L2 … LN)где FN – функция от N аргументов. Функционал mapcar применяет этуфункцию к первым элементам списков L1 … LN, затем ко вторымэлементам и т.д. Функционал maplist применяет FN к спискам L1…LN,затем к (cdr L1)…(cdr LN), далее к (cddr L1)…(cddr LN) и т.д. Изполученных при этом значений составляется список, который являетсязначением функционалов. Например:(mapcar 'cons '(1 2 3) '((A)(S)(D))) =>((1 A)(2 S)(3 D))(mapcar 'list '(A S D) '(1 2 3) '(Z X C)) =>((A 1 Z)(S 2 X)(D 3 C))(maplist 'cons '(1 2 3) '(A S D)) =>(((1 2 3) A S D)((2 3) S D)((3) D))(maplist 'list '(A S D) '(1 2 3) '(Z X C)) =>(((A S D)(1 2 3)(Z X C))((S D)(2 3)(X C))((D)(3)(C)))3.3.

Замыкание функционального аргументаРассмотрим проблему, которая может возникнуть, если в качествефункционального аргумента берётся функция, в теле которой естьпеременные, не входящие в число её формальных параметров. Такойфункцией является, к примеру, функция с определяющим выражением(lambda (X) (cons L X)) .Именно такие переменные могут составлять проблему при вычислениях.Переменная называется свободной для некоторой функции, если онаиспользуется в теле этой функции, но не входит в число её формальных67параметров (аргументов), и называется связанной в противном случае.Одна и та же переменная может быть одновременно связанной для однойфункции, и свободной – для другой. Например, переменная L связана дляфункции Ex, но свободна для безымянной функции, используемой в телеEx как функциональный аргумент:(defun Ex (L Y)(funcall '(lambda (X)(cons L X)) Y))Действие Ex: (Ex '(1 2) '(A S)) => ((1 2) A S) .Рассмотрим подробнее вычисление функциональных аргументов сосвободными переменными.

Будем использовать данное ранее определениефункционала mapcar:(defun mapcar (F L)(cond ((null L) NIL)(T (cons (funcall F (car L))(mapcar F (cdr L))))))а также определение функции MapCons, которая использует mapcar длятого, чтобы образовать двухэлементные списки из заданного элемента L иэлементов заданного списка Z:(defun MapCons (L Z)(mapcar '(lambda (X) (list L X)) Z))Согласно этим определениям функций, при вызове MapCons ожидаетсярезультат: (MapCons 7 '(А(В)С)) => ((7 А) (7 (В)) (7 С))Однако реально в результате вычислений будет получено:(MapCons 7 '(А (В) С))=> (((А (В) С) А) (((В) С) (В)) ((С) С))Причина этого связана с переменной L, которая является связанной в телеmapcar и MapCons, но свободной в теле безымянной функции,являющейся фактическим аргументом mapcar.

Ясно, что значениесвободной переменной лямбда-выражения должно определяться внекотором внешнем выражении, причём это внешнее выражение можетфиксироваться либо статически (по записи определений функций) либодинамически (при их вычислении).Согласно принципу динамического связывания, при вычислениитела функции значение переменной L должно быть взято из ближайшейобъемлющей вычисляемой функции. Поясним полученный результатMapCons с помощью контекста вычисления, под которым будемпонимать набор зафиксированных связей вида имя-переменной = значение,например: {x=3; y=(U V); z=(NIL)}.

При динамическом связыванииимён с их значениями контекст формируется в ходе вычисленияфункциональной программы по следующим правилам:681. При вызове функции (F p1 … pk) , k≥1 каждый её фактическийпараметр pi при необходимости вычисляется в контексте вызова, послечего контекст пополняется связями вида xi=vi или xi=pi (xi –формальный параметр функции F, а vi – значение pi). Вычисляемостьпараметров зависит от вида функции (обычная или особая, невычисляющая свои аргументы).2. Если при пополнении вычислительного контекста имена xiформальных параметров уже встречаются в контексте вызова (т.евозникает коллизия имён), то старые связи вытесняются новыми(обычное решение проблемы коллизии имён в программировании:локальные связи замещают уже существующие).3.