Основы функционального программирования

Имена, определения и контексты

Разбить на страницы
Показывать лекцию целиком

Интерпретирующая система. Реализационное уточнение интерпретации

Эта глава предназначена для реализационного уточнения уже известных теоретических рассуждений. Ряд уточнений показан на примере, представляющем программу, которая определяет три функции UNION, INTERSECTION и MEMBER, а затем применяет эти функции к нескольким тестам [1]. На этом примере будут рассмотрены средства и методы, обеспечивающие удобочитаемость функциональных программ и удобство их развития при отладке. Как правило, удобство достигается включением в систему дополнительных функций для решения проблем, принципиальное решение которых уже обеспечено на уровне теории.

Функции UNION и INTERSECTION применяют к множествам, каждое множество представлено в виде списка атомов. Заметим, что все функции рекурсивны, а UNION и INTERSECTION используют MEMBER. Схематично работу этих функций можно выразить следующим образом:

member = lambda [a;x]
        [ null[x] >> Nil ]
        [ eq[a;car[x]] >> T ]
        [ T >> member[a;cdr[x]] ] 

union = lambda[x;y]
        [ null[x] >> y ]
        [ member[car[x];y] >> union[cdr[x];y] ]
        [ T >> cons[car[x];union[cdr[x];y]] ]

intersection = lambda [x;y]
        [ null[x] >> NIL ]
        [ member[car[x];y] >>
                   cons[car[x];intersection[cdr[x];y]] ]
        [ T >> intersection[cdr[x];y] ]

Определяя эти функции на Лиспе, мы используем дополнительную псевдо-функцию DEFUN, объединяющую эффекты LAMBDA и LABEL. Программа выглядит так:

(DEFUN MEMBER (A X)
   (COND
      ((NULL X) Nil) 
      ((EQ A (CAR X)) T)
      (T (MEMBER A (CDR X)) )
) ) 

(DEFUN UNION (X Y)
   (COND
      ((NULL X) Y)
      ((MEMBER (CAR X) Y) (UNION (CDR X) Y) )
      (T (CONS (CAR X) (UNION (CDR X) Y))) )) ) 
)  )

(DEFUN INTERSECTION (X Y)
    (COND
       ((NULL X) NIL)
       ((MEMBER (CAR X) Y) 
         (CONS (CAR X) (INTERSECTION (CDR X) Y)) )
       (T (INTERSECTION (CDR X) Y))
)  ) 

(INTERSECTION '(A1 A2 A3) '(A1 A3 A5)) 
(UNION '(X Y Z) '(U V W X))

Эта программа предлагает вычислить пять различных форм.

Первые три формы сводятся к применению псевдо-функции DEFUN.

Псевдо-функция — это функция, которая выполняется ради ее воздействия на систему, тогда как обычная функция — ради ее значения. DEFUN заставляет функции стать определенными и допустимыми в системе равноправно со встроенными функциями. Ее значение — имя определяемой функции, в данном случае — MEMBER, UNION, INTERSECTION. Более точно можно сказать, что полная область значения псевдо-функции DEFUN включает в себя некоторые доступные ей части системы, обеспечивающие хранение информации о функциональных объектах, а формальное ее значение — атом, символизирующий определение функции.

Значение четвертой формы — (A1 A3). Значение пятой формы — (Y Z C B D X). Анализ пути, по которому выполняется рекурсия, показывает, почему элементы множества появляются именно в таком порядке.

В этом примере продемонстрировано несколько элементарных правил написания функциональных программ, сложившихся при реализации интерпретатора Лисп 1.5 в дополнение к идеализированным правилам, сформулированным в строгой теории Лиспа. (С точностью до разницы между EVALQUOTE — EVAL.)

  • Программа состоит из последовательности вычисляемых форм. Если форма список, то ее первый элемент интерпретируется как функция. Остальные элементы списка — аргументы для этой функции. Они вычисляются с помощью EVAL, а функция применяется к ним с помощью APPLY, и полученное значение выводится как результат программы.
  • Особого формата для записи программ не существует. Границы строк игнорируются. Формат программы, включая идентификацию, выбран просто для удобства чтения.
  • Любое число пробелов и концов строк можно разместить в любой точке программы, но не внутри атома.
  • Не используются (QUOTE T), (QUOTE NIL). Вместо них применяется T, NIL, что влечет за собой соответствующее изменение определения EVAL.
  • Атомы должны начинаться с букв, чтобы их можно было легко отличать от чисел.
  • Может использоваться точечная нотация. Любое число пробелов перед или после точки, свыше одного, будет игнорироваться (один пробел нужен обязательно при соседстве с атомом).
  • Точечные пары могут появляться как элементы списка, и списки могут быть элементами точечных пар.
    ((A . B) X (C . (E F D)))
    — допустимое S-выражение. Оно может быть записано как
    ((A . B) . ( X . ((C . (E . ( F . (D . Nil)))) . Nil)))
    или
    ((A . B) X (C E F D))
  • Форма типа (A B C . D) есть сокращение для (A . ( B . ( C . D) )). Любая другая расстановка точек на одном уровне есть ошибка, например (A. B C).
  • Набор основных функций предоставляется системой. Другие функции могут быть введены программистом. Порядок введения функций не имеет значения. Любая функция может использоваться в определении другой функции.

    Вывод S-выражений на печать и в файлы выполняет псевдо-функция PRINT, чтение данных обеспечивает псевдо-функция READ. Программа из файла может быть загружена псевдо-функцией LOAD.

    (LOAD 'TEST.LST)

(PRINT (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) )
(PRINT (UNION '(X Y Z) '(U V W X)) )
(PRINT (UNION (READ) '(1 2 3 4)) )
; объединение вводимого списка со списком
; '(1 2 3 4)
    •

    Именование значений и подвыражений

    Переменные

    Переменная — это символ, который используется для представления аргумента функции.

    Таким образом, возвращаясь к Дж.Маккарти [1]:

    "Можно написать "a + b, где a = 341 и b = 216". В такой ситуации не может быть недоразумений, и все согласятся, что ответ есть 557. Чтобы получить этот результат, необходимо заменить переменные фактическими значениями, и затем сложить два числа (на арифмометре, например).

    Одна из причин, по которой в этом случае не возникает недоразумений, состоит в том, что "a" и "b" не есть приемлемые входы для арифмометра, и следовательно, очевидно, что они только представляют фактические аргументы. При символьных вычислениях ситуация может быть более сложной. Атом может быть как переменной, так и фактическим аргументом. К дальнейшему усложнению приводит то обстоятельство, что некоторые из аргументов могут быть переменными, вычисляемыми внутри вызова другой функции. В таких случаях интуитивный подход может подвести. Для эффективного программирования в функциональном стиле необходимо более точное понимание формализмов.

    Чтобы не обескураживать читателей, следует заметить, что здесь ничего принципиально нового нет. Все, что сейчас рассматривается, может быть логически выведено из правил представления программ в виде S-выражений или из определения универсальных функций eval/apply, и является их непосредственным следствием, возможно, не вполне очевидным.

    Любой формализм для переменных сводится к лямбда-обозначению. Часть интерпретатора, которая при вычислении функций связывает переменные, называется APPLY. Когда APPLY встречает функцию, начинающуюся с LAMBDA, список переменных попарно связывается со списком аргументов и добавляется к началу а-списка. При вычислении функции могут быть обнаружены переменные. Они вычисляются поиском в а-списке. Если переменная встречается несколько раз, то используется последнее или самое новое значение. Часть интерпретатора, которая делает это, называется EVAL. Проиллюстрируем данное рассуждение на примере. Предположим, что интерпретатор получает следующее S-выражение:

    ((LAMBDA (X Y) (CONS X Y)) 'A 'B)

    Функция: ((LAMBDA (X Y) (CONS X Y)) 'A 'B)

    Аргументы: (A B)

    EVAL через EVAL-A передает эти аргументы функции APPLY. (См. лек. 3).

    (APPLY #'(LAMBDA (X Y) (CONS X Y)) '(A B) Nil )

    APPLY свяжет переменные и передаст функцию и удлинившийся а-список EVAL для вычисления.

    (EVAL  '(CONS X Y) ' ((X . A) (Y . B) . Nil))

    EVAL вычисляет переменные и сразу передает их консолидации - функции CONS, строящей из них бинарный узел.

    (Cons 'A 'B) = (A . B)

    EVAL вычисляет переменные и сразу передает их консолидации, строящей из них бинарный узел.

    Реальный интерпретатор пропускает один шаг, требуемый формальным определением универсальных функций".

    На практике сложилась традиция включать в систему функционального программирования специальные функции, обеспечивающие иерархию контекстов, в которых переменные обладают определенным значением. Для Clisp это LET и LET *.

    LET сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения.

    (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)) )      ; значений из контекста
    )   )  ; завершение контекста LET 
)

    LET * — сопоставляет локальным переменным взаимосвязанные выражения. Она позволяет дозировать сложность именуемых подвыражений.

    (DEFUN MEMBER (a x)
      (LET* ( (N-X (NULL x))
	(a-x (CAR x))
	(d-x (CDR x))
	(e-car (EQ a a-x))
              ) ; список локально именованных выражений

         (COND (N-X Nil)                   ; использование
                    (E-CAR T)                 ; именованных
                    (T (MEMBER A D-X))  ; выражений
      )  )   ; выход из контекста именованных выражений
)

    (Эквивалентность с точностью до побочного эффекта.)

    Глобальные переменные можно объявить с помощью специальной функции DEFPARAMETER.

    (DEFPARAMETER GLOB '(a b c))

    Значение такой переменной доступно в любом контексте, оно может быть переопределено. Возможно оттеснение одноименными локальными переменными с восстановлением при выходе из соответствующих контекстов. При выполнении кода программ:

    (LET ((GLOB 12))(PRINT GLOB))
(PRINT GLOB)

    напечатано будет:

    12
(A B C)

    Константы

    Дж.Маккарти обращает внимание [1]:"Иногда говорят, что константы представляют сами себя, в противоположность переменным, представляющим что-то другое. Это не вполне точно, поскольку обычно константы представляют как a, b, c, ..., а переменные как x, y, z, ... — но и то, и другое выглядит как атом. Удобнее говорить, что одна переменная ближе к константам, чем другая, если она связана на более высоком уровне и ее значение изменяется не столь часто.

    Обычно переменная считается связанной в области действия лямбда-конструктора функции, который связывает переменную внутри тела определения функции путем размещения пары из имени и значения в начале а-списка. В том случае, когда переменная всегда имеет определенное значение независимо от текущего состояния а-списка, она будет называться константой. Такую неизменяемую связь можно установить, помещая пару (a . v) в конец a-списка. Но в реальных системах это организовано с помощью так называемого списка свойств атома, являющегося представлением переменной. Каждый атом имеет свой p-список (property list), доступный через хэш-таблицу идентификаторов, что действует эффективнее, чем a-список. С каждым атомом связана специальная структура данных, в которой размещается имя атома, его значение, определение функции, представляемой этим же атомом, и список произвольных свойств, помеченных индикаторами. При вычислении переменных EVAL исследует эту структуру до выполнения поиска в а-списке. Такое устройство переменных не позволяет им служить в а-списке".

    Константы могут быть заданы программистом. В системе Clisp чтобы переменная X стала обозначением для (A B C D), надо воспользоваться псевдо-функцией DEFCONSTANT.

    (DefConstant X '(A B C D))

    Особый интерес представляет тип констант, которые всегда обозначают себя, Nil — пример такой константы. Такие константы как T, Nil и другие самоопределимые константы (числа, строки) не могут использоваться в качестве переменных. Cмысл чисел и строк не может быть изменен с помощью DEFCONSTANT.

    Функции

    Ситуация, когда атом обозначает функцию, реализационно подобна той, в которой атом обозначает аргумент. Если функция рекурсивна, то ей надо дать имя. Теоретически это делается с помощью формы LABEL, которая связывает название с определением функции в ассоциативном списке (а-списке). Название связано с определением функции точно так же, как переменная связана со своим значением. На практике LABEL используется редко. Удобнее связывать название с определением другим способом. Это делается путем размещения определения функции в списке свойств атома ( р-список ), символизирующего ее название. Выполняет данную операцию псевдо-функция DEFUN, описанная в начале этой лекции. Когда APPLY интерпретирует функцию, представленную атомом, она исследует р-список до поиска в а-списке. Таким образом, DEFUN будет опережать LABEL.

    Тот факт, что большинство функций — константы, определенные программистом, а не переменные, изменяемые программой, вызван отнюдь не каким-либо недостатком функционального программирования. Напротив, он указывает на потенциал подхода, который мы не научились использовать лучшим образом. (Работы по теории компиляции, оптимизации и верификации программ, смешанным вычислениям, суперпрограммированию и т.п. активно используют средства функционального программирования.)

    Системы функционального программирования обеспечивают возможность манипулирования функциональными переменными так же, как и обычными. Но организуется это с помощью ряда специальных функций, осуществляющих переход от символов, изображающих функции, к функциональным объектам, представленным этими символами. Такой переход может быть реализован в рамках любого языка программирования, но на Лиспе он выглядит естественно и поддерживается в любой Лисп-системе. Рассмотрим средства Clisp, обеспечивающие структурирование функциональных объектов.

    LABELS — позволяет из списка определений функций формировать контекст, в котором вычисляются выражения.

    FLET — специальная функция, позволяющая вводить локальные нерекурсивные функции.

    DEFUN — позволяет вводить новые определения на текущем уровне.

    (LABELS ( (INTERSECTION (x y)

                 (LET* ( (N-X (NULL x))
                           (MEM-CAR (MEMBER (CAR x) y))
                           (INT #'INTERSECTION) 
                         ) ; конец списка локальных выражений let*

                     (FLET ((F-TAIL (FN sx sy) 
                                      (APPLY FN (LIST (CDR sx) sy)) )
                             (CONS-F-TAIL (FN sx sy)
                                   (CONS (CAR sx) 
                                            (APPLY FN (LIST (CDR sx) sy)) 
                             ))    ) ; конец списка нерекурсивных функций FLET

      (COND (N-X NIL)                                     ; выражение, использующее 
                 (MEM-CAR (cons-f-tail INT x y) )    ; локальные определения функций
                 (T (f-tail INT x y)) )                       ; из контекстов FLET  и
                                                                    ; LABELS 
                     ) ; выход из контекста FLET
                 ) ;  выход из контекста LET*
            )  ; завершено определение INTERSECTION
          )  ; конец списка локальных рекурсивных функций

  (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-выражений закодированы как замкнутые машинные подпрограммы. Такая функция будет иметь особый индикатор в списке свойств с указателем, который позволяет интерпретатору связаться с подпрограммой. Существует три случая, в которых низкоуровневая подпрограмма может быть включена в систему:

  • Подпрограмма закодирована внутри Лисп-системы.
  • Функция кодируется пользователем вручную на языке типа ассемблера.
  • Функция сначала определяется с помощью S-выражения, затем транслируется компилятором. Компилированные функции могут выполняться в 2100 раз быстрее, чем интерпретироваться.
    •

    Специальные формы

    Обычно EVAL вычисляет аргументы функций до применения к ним функций с помощью APPLY. Таким образом, если EVAL задано (CONS X Y), то сначала вычисляются X и Y, а потом над полученными значениями работает CONS. Но если EVAL задано (QUOTE X), то X не будет вычисляться. QUOTE — специальная форма, которая препятствует вычислению своих аргументов.

    Специальная форма отличается от других функций двумя свойствами. Ее аргументы не вычисляются, пока она сама не просмотрит свои аргументы. COND, например, имеет свой особый способ вычисления аргументов с использованием EVCON. Второе отличие заключается в том, что специальные формы могут иметь неограниченное число аргументов.

    Неподвижная точка и самоприменимость функций

    Возможность использования безымянных определений функций не вполне очевидна для вспомогательных рекурсивных функций, так как их имена нужны в их собственных определениях. Но при необходимости и определение рекурсивной функции можно привести к форме, не зависящей от ее имени. Такие имена формально работают как связанные переменные, т.е. их смысл не зависит от имени — нечто вроде местоимения. Это позволяет выполнять систематическую замену названия функции на другие символы или выражения.

    Пример (предложен В.А. Потапенко).

    Преобразуем определение факториала в самоприменимую безымянную форму.

    Для этого нужно:

  • преобразовать исходное определение в самоприменимую форму;
  • избавиться от собственного имени функции.
    •

    Традиционное определение факториала:

    (DEFUN N! (n)
   (COND
      ((EQ n 0) 1)
      (T (* n (N! (- n 1))))     ; Факториал

   ; Выход из рекурсии
 
; Рекурсивный виток с редукцией аргумента
) )   ; и умножением на результат предыдущего витка

    Строим самоприменимое определение факториала:

    (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))))) ))   ; функция

   (LAMBDA (f n )
      (COND ((EQ n 0)1) (T (* n (apply f (list f 
         (- n 1))))) ))   ;первый аргумент — f 
   5   ; второй аргумент — 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 )

    Сокращаем совпадающие подфункции и получаем форму, в которой основные содержательные компоненты локализованы:

    ((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, связано с реализационным различием структурного представления данных и представляемых ими функций.

    Программы для Лисп-интерпретатора.

    Цель этой части — помочь избежать некоторых общих ошибок при отладке программ.

    (CAR '(A B)) = (CAR (QUOTE(A B))

    Функция: CAR

    Аргументы: ((A B))

    Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает, т.к. APPLY подается список аргументов.

    Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.

    (CONS 'A '(B . C))

    Функция: CONS

    Аргументы: (A (B . C))

    Результат (A . (B . C)) программа печати выведет как (A B . C)

    ((CAR (QUOTE (A . B))) CDR (QUOTE (C . D)))

    Функция: CONS

    Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))

    Значением такого вычисления будет

    ((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))

    Скорее всего, это совсем не то, чего ожидал новичок. Он рассчитывал вместо (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 . D))))

    Решения этого примера показывают, что грань между функциями и данными достаточно условна — одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.

    Страницы:

    Интерпретирующая система. Реализационное уточнение интерпретации

    Эта глава предназначена для реализационного уточнения уже известных теоретических рассуждений. Ряд уточнений показан на примере, представляющем программу, которая определяет три функции UNION, INTERSECTION и MEMBER, а затем применяет эти функции к нескольким тестам [1]. На этом примере будут рассмотрены средства и методы, обеспечивающие удобочитаемость функциональных программ и удобство их развития при отладке. Как правило, удобство достигается включением в систему дополнительных функций для решения проблем, принципиальное решение которых уже обеспечено на уровне теории.

    Функции UNION и INTERSECTION применяют к множествам, каждое множество представлено в виде списка атомов. Заметим, что все функции рекурсивны, а UNION и INTERSECTION используют MEMBER. Схематично работу этих функций можно выразить следующим образом:

    member = lambda [a;x]
        [ null[x] >> Nil ]
        [ eq[a;car[x]] >> T ]
        [ T >> member[a;cdr[x]] ] 

union = lambda[x;y]
        [ null[x] >> y ]
        [ member[car[x];y] >> union[cdr[x];y] ]
        [ T >> cons[car[x];union[cdr[x];y]] ]

intersection = lambda [x;y]
        [ null[x] >> NIL ]
        [ member[car[x];y] >>
                   cons[car[x];intersection[cdr[x];y]] ]
        [ T >> intersection[cdr[x];y] ]

    Определяя эти функции на Лиспе, мы используем дополнительную псевдо-функцию DEFUN, объединяющую эффекты LAMBDA и LABEL. Программа выглядит так:

    (DEFUN MEMBER (A X)
   (COND
      ((NULL X) Nil) 
      ((EQ A (CAR X)) T)
      (T (MEMBER A (CDR X)) )
) ) 

(DEFUN UNION (X Y)
   (COND
      ((NULL X) Y)
      ((MEMBER (CAR X) Y) (UNION (CDR X) Y) )
      (T (CONS (CAR X) (UNION (CDR X) Y))) )) ) 
)  )

(DEFUN INTERSECTION (X Y)
    (COND
       ((NULL X) NIL)
       ((MEMBER (CAR X) Y) 
         (CONS (CAR X) (INTERSECTION (CDR X) Y)) )
       (T (INTERSECTION (CDR X) Y))
)  ) 

(INTERSECTION '(A1 A2 A3) '(A1 A3 A5)) 
(UNION '(X Y Z) '(U V W X))

    Эта программа предлагает вычислить пять различных форм.

    Первые три формы сводятся к применению псевдо-функции DEFUN.

    Псевдо-функция — это функция, которая выполняется ради ее воздействия на систему, тогда как обычная функция — ради ее значения. DEFUN заставляет функции стать определенными и допустимыми в системе равноправно со встроенными функциями. Ее значение — имя определяемой функции, в данном случае — MEMBER, UNION, INTERSECTION. Более точно можно сказать, что полная область значения псевдо-функции DEFUN включает в себя некоторые доступные ей части системы, обеспечивающие хранение информации о функциональных объектах, а формальное ее значение — атом, символизирующий определение функции.

    Значение четвертой формы — (A1 A3). Значение пятой формы — (Y Z C B D X). Анализ пути, по которому выполняется рекурсия, показывает, почему элементы множества появляются именно в таком порядке.

    В этом примере продемонстрировано несколько элементарных правил написания функциональных программ, сложившихся при реализации интерпретатора Лисп 1.5 в дополнение к идеализированным правилам, сформулированным в строгой теории Лиспа. (С точностью до разницы между EVALQUOTE — EVAL.)

  • Программа состоит из последовательности вычисляемых форм. Если форма список, то ее первый элемент интерпретируется как функция. Остальные элементы списка — аргументы для этой функции. Они вычисляются с помощью EVAL, а функция применяется к ним с помощью APPLY, и полученное значение выводится как результат программы.
  • Особого формата для записи программ не существует. Границы строк игнорируются. Формат программы, включая идентификацию, выбран просто для удобства чтения.
  • Любое число пробелов и концов строк можно разместить в любой точке программы, но не внутри атома.
  • Не используются (QUOTE T), (QUOTE NIL). Вместо них применяется T, NIL, что влечет за собой соответствующее изменение определения EVAL.
  • Атомы должны начинаться с букв, чтобы их можно было легко отличать от чисел.
  • Может использоваться точечная нотация. Любое число пробелов перед или после точки, свыше одного, будет игнорироваться (один пробел нужен обязательно при соседстве с атомом).
  • Точечные пары могут появляться как элементы списка, и списки могут быть элементами точечных пар.
    ((A . B) X (C . (E F D)))
    — допустимое S-выражение. Оно может быть записано как
    ((A . B) . ( X . ((C . (E . ( F . (D . Nil)))) . Nil)))
    или
    ((A . B) X (C E F D))
  • Форма типа (A B C . D) есть сокращение для (A . ( B . ( C . D) )). Любая другая расстановка точек на одном уровне есть ошибка, например (A. B C).
  • Набор основных функций предоставляется системой. Другие функции могут быть введены программистом. Порядок введения функций не имеет значения. Любая функция может использоваться в определении другой функции.

    Вывод S-выражений на печать и в файлы выполняет псевдо-функция PRINT, чтение данных обеспечивает псевдо-функция READ. Программа из файла может быть загружена псевдо-функцией LOAD.

    (LOAD 'TEST.LST)

(PRINT (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) )
(PRINT (UNION '(X Y Z) '(U V W X)) )
(PRINT (UNION (READ) '(1 2 3 4)) )
; объединение вводимого списка со списком
; '(1 2 3 4)
    •

    Именование значений и подвыражений

    Переменные

    Переменная — это символ, который используется для представления аргумента функции.

    Таким образом, возвращаясь к Дж.Маккарти [1]:

    "Можно написать "a + b, где a = 341 и b = 216". В такой ситуации не может быть недоразумений, и все согласятся, что ответ есть 557. Чтобы получить этот результат, необходимо заменить переменные фактическими значениями, и затем сложить два числа (на арифмометре, например).

    Одна из причин, по которой в этом случае не возникает недоразумений, состоит в том, что "a" и "b" не есть приемлемые входы для арифмометра, и следовательно, очевидно, что они только представляют фактические аргументы. При символьных вычислениях ситуация может быть более сложной. Атом может быть как переменной, так и фактическим аргументом. К дальнейшему усложнению приводит то обстоятельство, что некоторые из аргументов могут быть переменными, вычисляемыми внутри вызова другой функции. В таких случаях интуитивный подход может подвести. Для эффективного программирования в функциональном стиле необходимо более точное понимание формализмов.

    Чтобы не обескураживать читателей, следует заметить, что здесь ничего принципиально нового нет. Все, что сейчас рассматривается, может быть логически выведено из правил представления программ в виде S-выражений или из определения универсальных функций eval/apply, и является их непосредственным следствием, возможно, не вполне очевидным.

    Любой формализм для переменных сводится к лямбда-обозначению. Часть интерпретатора, которая при вычислении функций связывает переменные, называется APPLY. Когда APPLY встречает функцию, начинающуюся с LAMBDA, список переменных попарно связывается со списком аргументов и добавляется к началу а-списка. При вычислении функции могут быть обнаружены переменные. Они вычисляются поиском в а-списке. Если переменная встречается несколько раз, то используется последнее или самое новое значение. Часть интерпретатора, которая делает это, называется EVAL. Проиллюстрируем данное рассуждение на примере. Предположим, что интерпретатор получает следующее S-выражение:

    ((LAMBDA (X Y) (CONS X Y)) 'A 'B)

    Функция: ((LAMBDA (X Y) (CONS X Y)) 'A 'B)

    Аргументы: (A B)

    EVAL через EVAL-A передает эти аргументы функции APPLY. (См. лек. 3).

    (APPLY #'(LAMBDA (X Y) (CONS X Y)) '(A B) Nil )

    APPLY свяжет переменные и передаст функцию и удлинившийся а-список EVAL для вычисления.

    (EVAL  '(CONS X Y) ' ((X . A) (Y . B) . Nil))

    EVAL вычисляет переменные и сразу передает их консолидации - функции CONS, строящей из них бинарный узел.

    (Cons 'A 'B) = (A . B)

    EVAL вычисляет переменные и сразу передает их консолидации, строящей из них бинарный узел.

    Реальный интерпретатор пропускает один шаг, требуемый формальным определением универсальных функций".

    На практике сложилась традиция включать в систему функционального программирования специальные функции, обеспечивающие иерархию контекстов, в которых переменные обладают определенным значением. Для Clisp это LET и LET *.

    LET сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения.

    (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)) )      ; значений из контекста
    )   )  ; завершение контекста LET 
)

    LET * — сопоставляет локальным переменным взаимосвязанные выражения. Она позволяет дозировать сложность именуемых подвыражений.

    (DEFUN MEMBER (a x)
      (LET* ( (N-X (NULL x))
	(a-x (CAR x))
	(d-x (CDR x))
	(e-car (EQ a a-x))
              ) ; список локально именованных выражений

         (COND (N-X Nil)                   ; использование
                    (E-CAR T)                 ; именованных
                    (T (MEMBER A D-X))  ; выражений
      )  )   ; выход из контекста именованных выражений
)

    (Эквивалентность с точностью до побочного эффекта.)

    Глобальные переменные можно объявить с помощью специальной функции DEFPARAMETER.

    (DEFPARAMETER GLOB '(a b c))

    Значение такой переменной доступно в любом контексте, оно может быть переопределено. Возможно оттеснение одноименными локальными переменными с восстановлением при выходе из соответствующих контекстов. При выполнении кода программ:

    (LET ((GLOB 12))(PRINT GLOB))
(PRINT GLOB)

    напечатано будет:

    12
(A B C)

    Константы

    Дж.Маккарти обращает внимание [1]:"Иногда говорят, что константы представляют сами себя, в противоположность переменным, представляющим что-то другое. Это не вполне точно, поскольку обычно константы представляют как a, b, c, ..., а переменные как x, y, z, ... — но и то, и другое выглядит как атом. Удобнее говорить, что одна переменная ближе к константам, чем другая, если она связана на более высоком уровне и ее значение изменяется не столь часто.

    Обычно переменная считается связанной в области действия лямбда-конструктора функции, который связывает переменную внутри тела определения функции путем размещения пары из имени и значения в начале а-списка. В том случае, когда переменная всегда имеет определенное значение независимо от текущего состояния а-списка, она будет называться константой. Такую неизменяемую связь можно установить, помещая пару (a . v) в конец a-списка. Но в реальных системах это организовано с помощью так называемого списка свойств атома, являющегося представлением переменной. Каждый атом имеет свой p-список (property list), доступный через хэш-таблицу идентификаторов, что действует эффективнее, чем a-список. С каждым атомом связана специальная структура данных, в которой размещается имя атома, его значение, определение функции, представляемой этим же атомом, и список произвольных свойств, помеченных индикаторами. При вычислении переменных EVAL исследует эту структуру до выполнения поиска в а-списке. Такое устройство переменных не позволяет им служить в а-списке".

    Константы могут быть заданы программистом. В системе Clisp чтобы переменная X стала обозначением для (A B C D), надо воспользоваться псевдо-функцией DEFCONSTANT.

    (DefConstant X '(A B C D))

    Особый интерес представляет тип констант, которые всегда обозначают себя, Nil — пример такой константы. Такие константы как T, Nil и другие самоопределимые константы (числа, строки) не могут использоваться в качестве переменных. Cмысл чисел и строк не может быть изменен с помощью DEFCONSTANT.

    Функции

    Ситуация, когда атом обозначает функцию, реализационно подобна той, в которой атом обозначает аргумент. Если функция рекурсивна, то ей надо дать имя. Теоретически это делается с помощью формы LABEL, которая связывает название с определением функции в ассоциативном списке (а-списке). Название связано с определением функции точно так же, как переменная связана со своим значением. На практике LABEL используется редко. Удобнее связывать название с определением другим способом. Это делается путем размещения определения функции в списке свойств атома ( р-список ), символизирующего ее название. Выполняет данную операцию псевдо-функция DEFUN, описанная в начале этой лекции. Когда APPLY интерпретирует функцию, представленную атомом, она исследует р-список до поиска в а-списке. Таким образом, DEFUN будет опережать LABEL.

    Тот факт, что большинство функций — константы, определенные программистом, а не переменные, изменяемые программой, вызван отнюдь не каким-либо недостатком функционального программирования. Напротив, он указывает на потенциал подхода, который мы не научились использовать лучшим образом. (Работы по теории компиляции, оптимизации и верификации программ, смешанным вычислениям, суперпрограммированию и т.п. активно используют средства функционального программирования.)

    Системы функционального программирования обеспечивают возможность манипулирования функциональными переменными так же, как и обычными. Но организуется это с помощью ряда специальных функций, осуществляющих переход от символов, изображающих функции, к функциональным объектам, представленным этими символами. Такой переход может быть реализован в рамках любого языка программирования, но на Лиспе он выглядит естественно и поддерживается в любой Лисп-системе. Рассмотрим средства Clisp, обеспечивающие структурирование функциональных объектов.

    LABELS — позволяет из списка определений функций формировать контекст, в котором вычисляются выражения.

    FLET — специальная функция, позволяющая вводить локальные нерекурсивные функции.

    DEFUN — позволяет вводить новые определения на текущем уровне.

    (LABELS ( (INTERSECTION (x y)

                 (LET* ( (N-X (NULL x))
                           (MEM-CAR (MEMBER (CAR x) y))
                           (INT #'INTERSECTION) 
                         ) ; конец списка локальных выражений let*

                     (FLET ((F-TAIL (FN sx sy) 
                                      (APPLY FN (LIST (CDR sx) sy)) )
                             (CONS-F-TAIL (FN sx sy)
                                   (CONS (CAR sx) 
                                            (APPLY FN (LIST (CDR sx) sy)) 
                             ))    ) ; конец списка нерекурсивных функций FLET

      (COND (N-X NIL)                                     ; выражение, использующее 
                 (MEM-CAR (cons-f-tail INT x y) )    ; локальные определения функций
                 (T (f-tail INT x y)) )                       ; из контекстов FLET  и
                                                                    ; LABELS 
                     ) ; выход из контекста FLET
                 ) ;  выход из контекста LET*
            )  ; завершено определение INTERSECTION
          )  ; конец списка локальных рекурсивных функций

  (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-выражений закодированы как замкнутые машинные подпрограммы. Такая функция будет иметь особый индикатор в списке свойств с указателем, который позволяет интерпретатору связаться с подпрограммой. Существует три случая, в которых низкоуровневая подпрограмма может быть включена в систему:

  • Подпрограмма закодирована внутри Лисп-системы.
  • Функция кодируется пользователем вручную на языке типа ассемблера.
  • Функция сначала определяется с помощью S-выражения, затем транслируется компилятором. Компилированные функции могут выполняться в 2100 раз быстрее, чем интерпретироваться.
    •

    Специальные формы

    Обычно EVAL вычисляет аргументы функций до применения к ним функций с помощью APPLY. Таким образом, если EVAL задано (CONS X Y), то сначала вычисляются X и Y, а потом над полученными значениями работает CONS. Но если EVAL задано (QUOTE X), то X не будет вычисляться. QUOTE — специальная форма, которая препятствует вычислению своих аргументов.

    Специальная форма отличается от других функций двумя свойствами. Ее аргументы не вычисляются, пока она сама не просмотрит свои аргументы. COND, например, имеет свой особый способ вычисления аргументов с использованием EVCON. Второе отличие заключается в том, что специальные формы могут иметь неограниченное число аргументов.

    Неподвижная точка и самоприменимость функций

    Возможность использования безымянных определений функций не вполне очевидна для вспомогательных рекурсивных функций, так как их имена нужны в их собственных определениях. Но при необходимости и определение рекурсивной функции можно привести к форме, не зависящей от ее имени. Такие имена формально работают как связанные переменные, т.е. их смысл не зависит от имени — нечто вроде местоимения. Это позволяет выполнять систематическую замену названия функции на другие символы или выражения.

    Пример (предложен В.А. Потапенко).

    Преобразуем определение факториала в самоприменимую безымянную форму.

    Для этого нужно:

  • преобразовать исходное определение в самоприменимую форму;
  • избавиться от собственного имени функции.
    •

    Традиционное определение факториала:

    (DEFUN N! (n)
   (COND
      ((EQ n 0) 1)
      (T (* n (N! (- n 1))))     ; Факториал

   ; Выход из рекурсии
 
; Рекурсивный виток с редукцией аргумента
) )   ; и умножением на результат предыдущего витка

    Строим самоприменимое определение факториала:

    (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))))) ))   ; функция

   (LAMBDA (f n )
      (COND ((EQ n 0)1) (T (* n (apply f (list f 
         (- n 1))))) ))   ;первый аргумент — f 
   5   ; второй аргумент — 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 )

    Сокращаем совпадающие подфункции и получаем форму, в которой основные содержательные компоненты локализованы:

    ((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, связано с реализационным различием структурного представления данных и представляемых ими функций.

    Программы для Лисп-интерпретатора.

    Цель этой части — помочь избежать некоторых общих ошибок при отладке программ.

    (CAR '(A B)) = (CAR (QUOTE(A B))

    Функция: CAR

    Аргументы: ((A B))

    Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает, т.к. APPLY подается список аргументов.

    Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.

    (CONS 'A '(B . C))

    Функция: CONS

    Аргументы: (A (B . C))

    Результат (A . (B . C)) программа печати выведет как (A B . C)

    ((CAR (QUOTE (A . B))) CDR (QUOTE (C . D)))

    Функция: CONS

    Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))

    Значением такого вычисления будет

    ((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))

    Скорее всего, это совсем не то, чего ожидал новичок. Он рассчитывал вместо (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 . D))))

    Решения этого примера показывают, что грань между функциями и данными достаточно условна — одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^