Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 14
Текст из файла (страница 14)
Плохо то, что значение этой безымянной функцииможет меняться в зависимости от вычислительного контекста, в которомона используется, что противоречит идее строгой функциональности.Контекст определения функции часто называют статическим, вотличие от формируемого динамически контекста вычисления.Рассмотренная проблема определения контекста при вычислениисвободных переменных функционального аргумента получила названиеfunarg-проблемы, или проблемы функционального аргумента. Онавозникает, когда сочетаются два условия: В качестве функционального аргумента используется функция сосвободными переменными.69 В контексте определения функции и в контексте вызова этой функциииспользуются одинаковые имена для обозначения двух разныхлисповских выражений, т.е.
возникает конфликт имён.Существуют два возможных пути решения этой проблемы:1) Исключить конфликты имён путём использования для свободныхпеременных функций особых экзотических имён, которые не могутвстретиться в других функциях (*****1 и т.п.). Тем самым решениепроблемы фактически возлагается на программиста, который долженотслеживать использование имён в программе.2) Применить так называемое замыкание функционального аргумента[15, c. 112]. Можно считать, что замыкание – это лямбда-выражение(функциональный аргумент) вместе с некоторой частью контекста егоопределения – той, что фиксирует связи его свободных переменных.Вычисление замыкания отложено на момент вызова функциональногоаргумента.В диалекте MuLisp (а также в ранних диалектах Лиспа) замыканиеотсутствует, поэтому возможен только первый из приведённых путейрешения проблемы функционального аргумента.В диалекте Common Lisp для замыкания функционального аргументавстроена специальная форма (function F), где F – определяющеевыражение функции.
Эту форму часто называют функциональнойблокировкой, поскольку она аналогична по действию функции quote, ноне просто квотирует аргумент, а как бы замыкает значения используемыхв функциональном аргументе F свободных переменных, фиксируя ихзначения из контекста его определения. Функциональную блокировкуможно записывать короче, с помощью двух знаков #':(function F) ≡ #'FДля получения правильного вычисления MapCons на базе CommonLisp необходимо заменить в её определении при записи функциональногоаргумента функционала mapcar простую блокировку (quote или ') нафункциональную (function или #'):(defun MapCons (L Z)(mapcar (function(lambda (X) (list L X))) Z))Тогда при вычислении mapcar всегда для L будет браться в качествезначения фактический аргумент функции MapCons. В нашем конкретномслучае будет установлен следующий контекст для mapcar (замыканиепоказано квадратными скобками):mapcar: {F = [(lambda (X)(cons X L)); {L=7}];L = (A (B) C) ; Z = (A (B) C)}В итоге: (MapCons 7 '(А (В) С)) => ((7 А)(7 (В))(7 С)).70Особенностью диалекта Common Lisp является необходимостьприменения формы function для лямбда-выражений при любом ихиспользовании в качестве функционального аргумента встроенныхфункционалов, даже когда в них нет свободных переменных.
Поэтому втаких случаях вызов встроенных функционалов в этих двух диалектахразличается:; вызов встроенных функционалов в MuLisp(apply '(lambda (x) (+ 2 x)) '(3)) => 5(funcall '(lambda (x) (+ 2 x)) 3) => 5(mapcar '(lambda(y)(* y 2)) '(1 2 3)) => (2 4 6)(maplist '(lambda(v)v)'(X Y Z)) => ((X Y Z)(Y Z)(Z)); вызов встроенных функционалов в Common Lisp(apply #'(lambda (x) (+ 2 x)) '(3)) => 5(funcall #'(lambda (x) (+ 2 x)) 3) => 5(mapcar #'(lambda(y)(* y 2)) '(1 2 3)) => (2 4 6)(maplist #'(lambda(v)v)'(X Y Z)) => ((X Y Z)(Y Z)(Z))Как уже отмечалось ранее, в Common Lisp для переменныхпрограммы по умолчанию действует статическое (лексическое)связывание, согласно которому значения переменных в ходе вычисленийопределяются исходя из контекста их определения.
В то же время в этомдиалекте есть средство (defvar имя_переменной), устанавливающеедля заданной переменной динамическое связывание.3.4. Применение функционаловРассмотрим примеры определения и использования различныхфункционалов.
При их программировании в случае необходимости будемприменять функциональную блокировку function (#') и указыватьразличие решений в диалектах MuLisp и в Common Lisp.Первый пример – функционал SubstIf с тремя аргументами:(SubstIf Z F S), который на всех уровнях списочного выражения S(S-выражения) заменяет на значение Z те элементы выражения, длякоторых одноместный предикат F принимает истинное значение. Вкачестве результата SubstIf выдаёт модифицированное таким образомсписочное выражение, например:(SubstIf '* 'null '(A (B ()) ())) => (A (B *) *)(SubstIf '(NUM) 'numberp '(6 (C 8 A) (7) B))=> ((NUM) (C (NUM) A) ((NUM)) B))Определение этого функционала с использованием funcall:71(defun SubstIf(Z F S)(cond ((null S) NIL)((funcall F (car S))(cons Z (SubstIf Z F (cdr S))))((atom (car S))(cons (car S)(SubstIf Z F (cdr S))))(T (cons (SubstIf Z F (car S))(SubstIf Z F (cdr S)))) ))Первая ветвь функции служит для завершения рекурсии, вторая –для проверки нужного свойства (предикат F) первого элементаобрабатываемого списочного выражения и его замене в случаеположительной проверки.
После этой замены рекурсивно продолжаетсяобработка остальных элементов выражения, также как и на третьей ветви,в случае атомарности первого элемента. Параллельная рекурсия впоследней ветви обеспечивает обработку списочного выражения вширь ивглубь в случае отрицательных проверок предыдущих ветвей.Рассмотрим теперь довольно мощный функционал reduce,встроенный в ряд диалектов языка Лисп и позволяющий выразить большоечисло сложных операций обработки списков. Он реализует редукцию, илисвёртку заданного списка, которая может трактоваться по-разному.В диалекте MuLisp функционал reduce выполняет следующеепреобразование исходного списка L=>(e1 e2 … en) с использованиемзначения A и бинарной операции-функции F:(reduce F L A) ≡ (F(…(F(F A e1) e2))…en)Например: (reduce 'list '(1 2 3) 0) => (((0 1) 2) 3)(reduce '+ '(1 2 3 4) 0) => 10 ;сумма чисел(reduce '* '(1 2 3 4) 1) =>24 ;их произведениеОпределим этот функционал на основе функционала funcall:(defun ReduceL (F L A)(cond ((null L) A)(T (ReduceL F (cdr L)(funcall F A (car L))))))и покажем его применение в задаче слияния двух упорядоченных списковчисел.
Пусть есть функция Insert от двух аргументов:(defun Insert (N L)(cond((null L)(cons N NIL));вставка в конец списка((<= N (car L))(cons N L)); условие вставки(T (cons (car L) ;место вставки ищется дальше(Insert N (cdr L) ) )) ))72которая вставляет заданное число N в упорядоченный по неубываниюсписок чисел L с сохранением упорядоченности:(Insert 5 '(1 3 8 10)) => (1 3 5 8 10)Эту функцию можно использовать вместе с ReduceL для компактногопрограммирования функции Merge слияния двух упорядоченных списковчисел в один упорядоченный список:(defun Merge(X Y) (ReduceL 'Insert X Y))(Merge '(1 3 5 8) '(2 6 8 10)) => (1 2 3 5 6 8 8 10)Другой пример использования функционала ReduceL – поискмаксимума в списке чисел на базе функции Max вычисления максимумадвух чисел:(defun Max(X Y) (cond((> X Y) X) (T Y)))(defun MaxList(L) (ReduceL 'Max (cdr L) (car L)))(MaxList '(-6 4 -82 2 94 -3)) => 94В ряде случаев полезен другой вариант редукции (свёртки) списка,при котором (reduce F L A) для списка L=>(e1 … en), выражения Aи бинарной функции F означает(reduce F L A) ≡ (F e1 (F e2 … (F en A) … )).Например: (reduce 'list '(1 2 3) 0) => (1 (2 (3 0)))Соответствующее определение функционала:(defun ReduceR (F L A)(cond ((null L) A)(T (funcall F (car L)(ReduceR F (cdr L) A)))))В этом определении выражение A фигурирует уже как второйоперанд редуцирующей операции F, а в качестве её первого операндаберутся очередные элементы списка L, начиная с конца списка.
На основетакой редукции легко определить многие функции, в частности:(ReduceR 'cons X ()) ≡ (copy X)(ReduceR 'cons X Y) ≡ (append X Y)Также как и ReduceL, функционал ReduceR применим для слияния двухупорядоченных списков чисел и поиска максимума в списке чисел(отличие – в направлении обработки списка L):(defun Merge(X Y) (ReduceR 'Insert X Y))(defun MaxList(L) (ReduceR 'Max (cdr L) (car L)))Рассмотренные варианты (ReduceL и ReduceR) функционалаreduce часто называются левой и правой свёрткой. Отметим, что в случае73коммутативности и ассоциативности бинарной операции F их действиеодинаково:(ReduceL F L A)= (ReduceR F L A).В диалекте Common Lisp реализованный функционал reduce можетвыполнять оба варианта редукции за счёт использования так называемыхключевых параметров. Первый ключевой параметр initial-valueзадаёт значение A, а второй параметр from-end используется дляуказания направления свёртки:(ReduceL F L A) ≡ ( reduce F L :initial-value A),(ReduceR F L A) ≡(reduce F L :initial-value A :from-end T).Примеры использования этого функционала в Common Lisp:(reduce 'list '(1 2 3) :initial-value 0)=> (((0 1) 2) 3)(reduce 'list '(1 2 3) :initial-value 0 :from-end T)=> (1 (2 (3 0)))Покажем теперь применение функционалов на примере задачипостроения декартова произведения двух множеств, представленныходноуровневыми списками атомов:(Decart '(A B C) '(D E))=> ((A D)(A E)(B D)(B E)(C D)(C E))Будем записывать решения этой задачи для диалекта Common Lisp,решения же для MuLisp получаются заменой функциональной блокировки#' на обычную блокировку ', а также исключением в вызове reduceимени ключевого параметра :initial-value.Сначала составим функцию Decart1 с использованием обычнойтехники рекурсивного программирования: эта функция будет выполнятьпроход по элементам первого списка, обращаясь с очередным егоэлементом-атомом к вспомогательной функции Dec для формированиявсех кортежей-пар с этим элементом.(defun Decart1 (M1 M2)(cond ((null M1) NIL)(T (append (Dec (car M1) M2)(Decart1 (cdr M1) M2) )) ))(defun Dec (A M) ;вспомогательная функция(cond ((null M) NIL)(T (cons (list A (car M))(Dec A (cdr M)))) ))74Функция Dec формирует декартово произведение одноэлементногомножества (заданного атомом-значением параметра A) и множества M,например:(Dec 'С '(D E)) => ((С D)(С E)).Обе приведённые функции сами по себе рекурсивны, в дополнениеDecart1 вызывает Dec, а она выполняет проход по списку-множествуM2 (это внутренний цикл по отношению к внешнему циклу прохода посписку M1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
