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

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

Описание файла

PDF-файл из архива "Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп", который расположен в категории "книги и методические указания". Всё это находится в предмете "искусственный интеллект" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 13 страницы из PDF

По окончании вычисления тела функции из текущего вычислительногоконтекста удаляются введённые связи вида 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). Плохо то, что значение этой безымянной функцииможет меняться в зависимости от вычислительного контекста, в которомона используется, что противоречит идее строгой функциональности.Контекст определения функции часто называют статическим, вотличие от формируемого динамически контекста вычисления.Рассмотренная проблема определения контекста при вычислениисвободных переменных функционального аргумента получила название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).

Свежие статьи
Популярно сейчас