Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 13
Текст из файла (страница 13)
Вбольшинстве диалектов есть целый набор встроенных функционалов,облегчающих программирование, включая создание и применение новыхфункционалов.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.
По окончании вычисления тела функции из текущего вычислительногоконтекста удаляются введённые связи вида xi=vi или xi=pi, т.е.восстанавливается контекст вызова.Вернёмся к примеру вычисления функции MapCons. При её вызовеустанавливается контекстMapCons: {L = 7; Z = (A (B) C) },а при вызове в теле MapCons вложенного mapcar добавляются связи иновая связь для L вытесняет более старую:mapcar: {F = (lambda (X)(cons X L));L = (A (B) C); Z = (A (B) C)} .Поэтому при вычислении в теле mapcar обращения к функции F и будетвзято последнее, новое значение L, а не прежнее 7, и в итоге получитсярезультат (((А (В) С) А) (((В) С) (В)) ((С) С)) .Таким образом, проблема заключается в том, что по правиламвычисления будет взято последнее значение L – по месту вызова функцииF, т.е. динамически, а подразумевалось (при определении функций) братьстатически, по месту записи лямбда-выражения (функциональногоаргумента mapcar).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
