globalf5-240972240972 (850810), страница 16
Текст из файла (страница 16)
ГородняяОсновы функционального программирования) ; конец списка локальных рекурсивных функций(DEFUN UNION (x y)(LET ( (a-x (CAR x))(d-x (CDR x)))(COND ((NULL x) y)((MEMBER a-x y) (UNION d-x y) )(T (CONS a-x (UNION d-x y)) )) ) ) ; завершено определение на текущем уровне(INTERSECTION '(A1 A2 A3) '(A1 A3 A5))(UNION '(X Y Z) '(U V W X))) ; выход из контекста LABELSФункции на машинном языке (низкоуровневые)Некоторые функции вместо определений с помощью S-выраженийзакодированы как замкнутые машинные подпрограммы. Такая функциябудет иметь особый индикатор в списке свойств с указателем, которыйпозволяет интерпретатору связаться с подпрограммой.
Существует трислучая, в которых низкоуровневая подпрограмма может быть включена всистему:1. Подпрограмма закодирована внутри Лисп-системы.2. Функция кодируется пользователем вручную на языке типаассемблера.3. Функция сначала определяется с помощью S-выражения, затемтранслируется компилятором. Компилированные функции могутвыполняться в 2100 раз быстрее, чем интерпретироваться.Специальные формыОбычно EVAL вычисляет аргументы функций до применения к нимфункций с помощью APPLY.
Таким образом, если EVAL задано (CONSX Y), то сначала вычисляются X и Y, а потом над полученными101Л.В. ГородняяОсновы функционального программированиязначениями работает CONS. Но если EVAL задано (QUOTE X), то X небудет вычисляться. QUOTE — специальная форма, которая препятствуетвычислению своих аргументов.Специальная форма отличается от других функций двумя свойствами.Ее аргументы не вычисляются, пока она сама не просмотрит своиаргументы. COND, например, имеет свой особый способ вычисленияаргументов с использованием EVCON.
Второе отличие заключается втом, что специальные формы могут иметь неограниченное числоаргументов.Неподвижная точка и самоприменимость функцийВозможность использования безымянных определений функций невполне очевидна для вспомогательных рекурсивных функций, так каких имена нужны в их собственных определениях. Но принеобходимости и определение рекурсивной функции можно привести кформе, не зависящей от ее имени.
Такие имена формально работают каксвязанные переменные, т.е. их смысл не зависит от имени — нечтовроде местоимения. Это позволяет выполнять систематическую заменуназвания функции на другие символы или выражения.Пример (предложен В.А. Потапенко).Преобразуем определение факториала в самоприменимую безымяннуюформу.Для этого нужно:преобразовать исходное определение в самоприменимую форму;избавиться от собственного имени функции.Традиционное определение факториала:(DEFUN N! (n)(COND((EQ n 0) 1)(T (* n (N! (- n 1)))); Факториал102Л.В.
ГородняяОсновы функционального программирования; Выход из рекурсии; Рекурсивный виток с редукцией аргумента) ) ; и умножением на результат предыдущего виткаСтроим самоприменимое определение факториала:(DEFUN N!_self (f n) ; Обобщенная функция,; равносильная факториалу при f = N!_self(COND ((EQ n 0)1)(T (* n (APPLY f (list f (- n 1))))); применение функции f; к списку из уменьшенного аргумента))Использовать это определение можно следующим образом:(N!_self #'N!_self 3) ; = 6 =или(APPLY 'N!_self '(N!_self 4)) ; = 24 =При таких аргументах оно эквивалентно исходному определениюфакториала. Теперь избавимся от названия функции:((LAMBDA (f n ); безымянная функция, равносильная факториалу; при f = N!_self(COND ((EQ n 0)1)(T (* n ( f (list f (- n 1)))))))Использовать это определение можно в следующей форме:((LAMBDA (f n )(COND ((EQ n 0)1) (T (* n (apply f (list f(- n 1))))) )) ; функция103Л.В.
ГородняяОсновы функционального программирования(LAMBDA (f n )(COND ((EQ n 0)1) (T (* n (apply f (list f(- n 1))))) )) ;первый аргумент — f5 ; второй аргумент — n) ; = 120 - результат самоприменения факториалаили(APPLY#'(LAMBDA (f n )(COND ((EQ n 0)1)(T (* n (apply f (list f(- n 1))))) ) ) ; функция'((LAMBDA (f n )(COND ((EQ n 0)1) (T (* n (apply f (list f(- n 1))))) ))6 ) ; список аргументов)) ; = 720Можно записать этот текст программы (код) без дублированияопределения функции:(LAMBDA (n)( (LAMBDA (f) (APPLY f (list f n))))#'(LAMBDA (f n ) (COND ((EQ n 0)1) (T (* n(APPLY f (list f (- n 1)))) ) ); внутренняя функция f) ))И использовать полученное определение следующим образом:((LAMBDA (n)((LAMBDA (f) (APPLY f (list f n)))#'(LAMBDA (f n ) (COND ((EQ n 0)1) (T (* n(APPLY f (list f (- n 1)))))) ) )) 5 ) ; = 120 )Сокращаем совпадающие подфункции и получаем форму, в которойосновные содержательные компоненты локализованы:104Л.В. ГородняяОсновы функционального программирования((LAMBDA (n) (flet ((afl (f n)(apply f (list f n)) ))((LAMBDA (f) (afl f n))#'(LAMBDA (f n ) (COND ((EQ n 0)1) (T (* n(afl f (- n 1)))))))))6 ) ; = 720)Таким образом, определение рекурсивной функции можнопреобразовать к безымянной форме.
Техника эквивалентныхпреобразований позволяет поддерживать целостность системыфункций втягиванием безымянных вспомогательных функций внутрьтела основного определения. Верно и обратное: любую конструкцию излямбда-выражений можно преобразовать в систему отдельныхфункций.Такое, пусть не самое понятное, определение позволяет получитьбольше, чем просто скорость исполнения кода и его переносимость.Техника функциональных определений и их преобразований позволяетрассматривать решение задачи с той точки зрения, с какой это удобнопри постановке задачи, с естественной степенью подробности, гибкостии мобильности.Специальная функция FUNCTION (#') обеспечивает доступ кфункциональному объекту, связанному с атомом, а функция FUNCALLобеспечивает применение функции к произвольному числу ееаргументов.(FUNCALL F a1 a2 ...
) = (APPLY F (list a1 a2 ...))Разрастание числа функций, манипулирующих применением функций вязыке Clisp, связано с реализационным различием структурногопредставления данных и представляемых ими функций.Программы для Лисп-интерпретатора.105Л.В. ГородняяОсновы функционального программированияЦель этой части — помочь избежать некоторых общих ошибок приотладке программ.(CAR '(A B)) = (CAR (QUOTE(A B))Пример 5.2.Функция: CARАргументы: ((A B))Значение есть A. Заметим, что интерпретатор ожидает списокаргументов.
Единственным аргументом для CAR является (A B).Добавочная пара скобок возникает, т.к. APPLY подается списокаргументов.Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Этокорректно, но не является необходимым.(CONS 'A '(B . C))Пример 5.3.Функция: CONSАргументы: (A (B . C))Результат (A . (B . C)) программа печати выведет как (A B .C)((CAR (QUOTE (A . B))) CDR (QUOTE (C . D)))Пример 5.4.Функция: CONSАргументы: ((CAR (QUOTE (A .
B))) (CDR (QUOTE (C .D))))Значением такого вычисления будет((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))106Л.В. ГородняяОсновы функционального программированияСкорее всего, это совсем не то, чего ожидал новичок. Он рассчитывалвместо (CAR (QUOTE (A . B)) получить A и увидеть (A . D) вкачестве итогового значения CONS.
Интерпретатор настроен не насписок уже готовых значений аргументов, а на список выражений,которые будут вычисляться до вызова функции. Кроме очевидногостирания апострофов(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))) )ниже приведены еще три правильных способа записи нужной формы.Первый состоит в том, что CAR и CDR части функции задаются спомощью LAMBDA в определении функции. Второй заключается впереносе CONS в аргументы и вычислении их с помощью EVAL припустом а-списке. Третий — в принудительном выполненииконстантных действий в представлении аргументов.((LAMBDA (X Y) (CONS (CAR X) (CDR Y)))'(A .
B) '(C . D))Функция: (LAMBDA (X Y) (CONS (CAR X) (CDR Y)))Аргументы: ((A . B)(C . D))(EVAL '(CONS (CAR (QUOTE (A . B)))(CDR (QUOTE (C . D)))) Nil)Функция: EVALАргументы: ((CONS (CAR (QUOTE (A . B))) (CDR (QUOTE(C . D)))) Nil)Значением того и другого является (A .
D)((LAMBDA (X Y) (CONS (EVAL X)(EVAL Y))) '(CAR (QUOTE (A . B)))'(CDR (QUOTE (C . D))) )Функция: (LAMBDA (X Y) (CONS (EVAL X) (EVAL Y)))Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C .107Л.В. ГородняяОсновы функционального программированияD))))Решения этого примера показывают, что грань между функциями иданными достаточно условна — одни и те же вычисления можноосуществить при разном распределении промежуточных вычисленийвнутри выражения, передвигая эту грань.108Л.В.
ГородняяОсновы функционального программированияСвойства атомов и категории функцийМетоды расширения функциональных построений применены длямоделированияпривычногооператорно-процедурногостиляпрограммирования и техники работы с глобальными определениями.Демонстрируется еще один важный метод — обобщение базовой схемыобработки символьных выражений и представленных с их помощьюфункциональных форм на основе списков свойств атомов. В результатеможно собирать и специализировать функционально полноеопределение гибкого и расширяемого интерпретатора для языкапрограммирования на примере Лиспа, написанном на Лиспе. Акцентна возможности варьирования семантики функций и пополнениясемантического базиса с целью автоматизации выполненныхпостроений в процессе исследования границ класса решаемых задач иконкретизации методов их решения.Prog-выражения и циклыПротивопоставление функционального и императивного стилейпрограммирования порой напоминает войну остроконечников ступоконечниками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
