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

Универсальная функция

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

Общий подход к обработке символьных выражений и представлению программ

Приведенные ранее описания и правила записи функций и выражений в этой лекции получат более строгое определение. Начнем с синтаксического обобщения. Представим результаты предыдущей лекции в виде простых БНФ (Формул Бекуса-Наура), позволяющих задать грамматику представления функций и значений в виде системы правил. Каждое правило отдельному понятию сопоставляет ( : : = ) варианты ( | ) его изображения:

Синтаксис данных в Лиспе сводится к правилам представления атомов и S-выражений, включая списки.

атом ::= БУКВА конец_атома

Это правило констатирует, что атомы начинаются с буквы.

конец_атома ::= пусто
          | БУКВА конец_атома
          | цифра конец_атома

Это правило констатирует, что после первой литеры в изображении атома могут быть как буквы, так и цифры.

В Лиспе атомы — это мельчайшие частицы. Их разложение по литерам не имеет смысла.

S-выражение ::= атом
         | (S-выражение . S-выражение)
         | (S-выражение ... )

Данное правило констатирует, что S-выражения — это или атомы, или узлы из пары S-выражений, или списки из S-выражений. (Три точки означают, что допустимо любое число вхождений предшествующего вида объектов, включая ни одного.)

Согласно такому правилу "()" есть допустимое S-выражение. Оно в языке Лисп по соглашению эквивалентно атому NIL.

Базовая система представления данных — точечная нотация, хотя на практике запись в виде списков удобнее. Любой список можно представить точечной нотацией:

() = NIL
(a . NIL) = (a)
- - - 
(a1 . ( ... (aK . NIL) ... )) = (a1 ... aK)

Такая единая структура данных оказалась вполне достаточной для представления сколь угодно сложных программ. Дальнейшее определение языка Лисп можно рассматривать как восходящий процесс генерации семантического каркаса, по ключевым позициям которого распределены семантические действия по обработке программ.

Другие правила представления данных нужны лишь при расширении и специализации лексики языка (числа, строки, имена особого вида и т.п.). Они не влияют ни на общий синтаксис языка, ни на строй его понятий, а лишь характеризуют разнообразие сферы его конкретных приложений.

Синтаксис программ является конкретизацией синтаксиса данных, а именно — выделением из класса S-выражений подкласса вычислимых выражений (форм), т.е. данных, имеющих смысл как выражения языка и приспособленных к вычислению. Внешне это выглядит как объявление объектов, заранее известных в языке, и представление разных форм, вычисление которых обладает определенной спецификой.

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

идентификатор ::= атом

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

Понятие "идентификатор" выделено для того, чтобы по мере развития определения атома не требовалось на все виды атомов искусственно распространять семантику вычислений. (Например, у Бекуса в его знаменитой статье про "бутылочное горлышко" рассматриваются числа как представление операций доступа [20].)

форма ::= константа
      | переменная
      | (функция аргумент ... )
      | (COND (форма форма) (форма форма) ... )

константа ::= (QUOTE S-выражение)
      | 'S-выражение

переменная ::= идентификатор

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

Таким образом, класс форм — это объединение класса переменных и подкласса списков, начинающихся с QUOTE, COND или с представления некоторой функции.

аргумент ::= форма

Форма — это выражение, которое может быть вычислено. Форма, представляющая собой константу, выдает эту константу как свое значение. В таком случае нет необходимости в вычислениях, независимо от вида константы. Константные значения могут быть любой сложности, включая вычислимые выражения. Чтобы избежать двусмысленности, предлагается константы изображать как результат специальной функции QUOTE, блокирующей вычисление. Представление констант с помощью QUOTE устанавливает границу, далее которой вычисление не идет. Использование апострофа "'" — просто сокращенное обозначение для удобства набора внешних форм. Константные значения аргументов характерны при тестировании и демонстрации программ.

Если форма представляет собой переменную, то ее значением должно быть S-выражение, связанное с этой переменной до момента вычисления формы. ( Динамическое связывание, в отличие от традиционного правила, требующего связывания к моменту описания формы, т.е. статическое связывание.)

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

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

Последняя ветвь определяет формат условного выражения. Согласно этому формату условное выражение строится из размещенных в двухэлементном списке синтаксически различимых позиций для пропозициональных термов и обычных форм. Двухэлементные списки из определения условного выражения рассматриваются как представление предиката и соответствующего ему S-выражения. Значение условного выражения определяется перебором предикатов по порядку, пока не найдется форма, значение которой отлично от NIL, что означает логическое значение "истина". Строго говоря, такая форма должна быть найдена непременно. Тогда вычисляется S-выражение, размещенное вторым элементом этого же двухэлементного списка. Остальные предикаты и формы условного выражения не вычисляют (логика Маккарти), их формальная корректность или определенность не влияют на существование результата.

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

функция ::= название
        | (LAMBDA список_переменных форма)
        | (LABEL название функция)

список_переменных ::= (переменная ... )

название ::= идентификатор

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

Таким образом, класс функций — это объединение класса назва-ний и подкласса трехэлементных списков, начинающихся с LAMBDA или LABEL.

Функция может быть представлена просто именем. В таком случае ее смысл должен быть заранее известен. Функция может быть введена с помощью лямбда-выражения, устанавливающего соответствие между аргументами функции и связанными переменными, упоминаемыми в теле ее определения (в определяющей ее форме). Форма из определения функции может включать переменные, не включенные в лямбда-список, — так называемые свободные переменные. Их значения должны устанавливаться на более внешнем уровне. Если функция рекурсивна, то следует объявить ее имя с помощью специальной функции LABEL. (Используемая в примерах DEFUN, по существу, совмещает эффекты LABEL и LAMBDA.)

форма ::= переменная
      | (QUOTE S-выражение)
      | (COND (форма форма) ... (форма форма))
      | (функция аргумент ... )

аргумент ::= форма

переменная ::= идентификатор

функция ::= название
      | (LAMBDA список_переменных форма)
      | (LABEL название функция)

список_переменных ::= (переменная ... )
название ::= идентификатор

идентификатор ::= атом
S-выражение ::= атом
      | (S-выражение . S-выражение)
      | (S-выражение ...)

атом ::= БУКВА конец_атома

конец_атома ::= пусто 
      | БУКВА конец_атома
      | цифра конец_атома

Универсальная функция

Интерпретация или универсальная функция — это функция, которая может вычислять значение любой формы, включая формы, сводимые к вычислению произвольной заданной функции, применяемой к аргументам, представленным в этой же форме, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, интерпретация будет повторяться бесконечно.)

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

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

  • атомарное выражение обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида x, elem, смысл которых зависит от контекста, в котором они вычисляются;
  • константы, представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение "истина";
  • условное выражение требует специального алгоритма для перебора предикатов и выбора нужной ветви. Например, интерпретация условного выражения
    (COND ((ATOM x) x)
        ((QUOTE T) (first (CAR x)) )
 )
    должна обеспечивать выбор ветви в зависимости от атомарности значения аргумента. Семантика чистого Лиспа не определяет значение условного выражения при отсутствии предиката со значением "истина". Но во многих реализациях и диалектах Лиспа такая ситуация не рассматривается как ошибка, а значением считается NIL. Иногда это придает условным выражениям лаконичность;
  • остальные формы выражений рассматриваются по общей схеме как список из функции и ее аргументов. Обычно аргументы вычисляются, а затем вычисленные значения передаются функции для интерпретации ее определения. Так обеспечивается возможность писать композиции функций. Например, в выражении (first (CAR x)) внутренняя функция CAR сначала получит в качестве своего аргумента значение переменной x, а потом свой результат передаст как аргумент более внешней функции first ;
  • если функция представлена своим названием, то среди названий различаются имена встроенных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенных в программе, например first. Для встроенных функций интерпретация сама "знает", как найти их значение по заданным аргументам, а для введенных в программе функций — использует их определение, которое находит по имени;
  • если функция построена с помощью лямбда-конструктора, то прежде чем ее применять, понадобится связывать переменные из лямбда-списка со значениями аргументов. Функция, использующая лямбда-выражение,
    (LAMBDA (x)
     (COND ((ATOM x) x)
            ((QUOTE T) (first (CAR x)) )
 )   )
    зависит от одного аргумента, значение которого должно быть связано с переменной x. В определении используется свободная функциональная переменная first, которая должна быть определена в более внешнем контексте;
  • если представление функции начинается с LABEL, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Например, предыдущее LAMBDA-определение безымянной функции становится рекурсивным, если его сделать вторым аргументом специальной функции LABEL, первый аргумент которой — fisrt, имя новой функции.
    (LABEL first
    (LAMBDA (x)
         (COND ((ATOM x) x)
              ((QUOTE T) (first (CAR x)) )
)   )   )
    •

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

  • обработка структур данных ( cons, car, cdr, atom, eq );
  • конструирование функциональных объектов ( lambda, label );
  • идентификация объектов (имена переменных и названия функций);
  • управление логикой вычислений и границей вычислимости (композиции, quote, cond, eval ).
    •

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

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

    Начнем с общих методов обработки S-выражений.

    AMONG — проверка, входит ли заданный атом в данное S-выражение.

    (DEFUN among (x y) 
    (COND 
      ((ATOM y) (EQ x y))
      ((among x (CAR y)) (QUOTE T))
      ((QUOTE T) (among x (CDR y) ))
)   )
(among 'A '(C (A B))) ; = T
(among 'A '(C D B))   ; = NIL

    Символ " ; " - начало примечания (до конца строки).

    EQUAL — предикат, проверяющий равенство двух S-выражений. Его значение "истина" для идентичных аргументов и "ложь" для различных. (Элементарный предикат EQ определен только для атомов.) Определение EQUAL иллюстрирует условное выражение внутри условного выражения (двухуровневое условное выражение и equalнаправленная рекурсия).

    (DEFUN equal (x y)
    (COND 
        ((ATOM x) (COND 
                           ((ATOM y) (EQ x y))
                           ((QUOTE T) (QUOTE NIL))
         )            )
        ((equal (CAR x)(CAR y))
      (equal (CDR x)(CDR y)) )

        ((QUOTE T) (QUOTE NIL) )
)   )
(equal '(A (B)) '(A (B))) ; = T
(equal '(A B) '(A . B))   ; = NIL

    SUBST — функция трех аргументов x, y, z, строящая результат замены S-выражением x всех вхождений y в S-выражение z.

    (DEFUN subst (x y z)
    (COND 
         ((equal y z) x)
         ((ATOM z) z)
         ((QUOTE T)(CONS 
                      (subst x y (CAR z)) 
                      (subst x y (CDR z))
                    )
         )
)   )
(subst '(x . A) 'B '((A . B) . C)) =  ((A x . A) . C)

    Использование equal в этом определении позволяет осуществлять подстановку и в более сложных случаях. Например, для редукции совпадающих хвостов подсписков:

    (subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) 
                     ; = ((A . x)     (E . x)     (F . x))

    NULL — предикат, отличающий пустой список от остальных S-выражений. Позволяет выяснять, когда список исчерпан. Принимает значение "истина" тогда и только тогда, когда его аргумент — NIL .

    (DEFUN null (x) 
    (COND 
        ((EQ x (QUOTE NIL)) (QUOTE T))
        ((QUOTE T) (QUOTE NIL))
)   )

    При необходимости можно компоненты точечной пары разместить в двухэлементном списке функцией PAIR_TO_LIST, и наоборот, из первых двух элементов списка построить точечную пару функцией LIST_TO_PAIR.

    (DEFUN pair_to_list (x)
     (CONS (CAR x) 
                (CONS (CDR x) NIL)) )
(pair_to_list '(A B))   ; = (A B)

(DEFUN list_to_pair (x)
      (CONS (CAR x) (CADR x)) ) 
(list_to_pair '(A B C))     ; = (A . B)

    По этим определениям видно, что списочная запись строится большим числом CONS, т.е. на нее расходуется больше памяти.

    Основные методы обработки списков

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

    APPEND — функция двух аргументов x и y, сцепляющая два списка в один.

    (DEFUN append (x y) 
   (COND 
       ((null x) y)
       ((QUOTE T)
         (CONS (CAR x) 
              (append (CDR x) y) 
         )
       )
)  )
(append '(A B) '(C D E))       ; = (A B C D E)

    MEMBER — функция двух аргументов x и y, выясняющая, встречается ли S-выражение x среди элементов списка y .

    (DEFUN member (x y)
    (COND 
        ((null y)  (QUOTE NIL) )
        ((equal x (CAR y)) (QUOTE T) )
        ((QUOTE T) (member x (CDR y)) )
)   )
(member '(a) '(b (a) d))      ; = T
(member 'a '(b (a) d))        ; = NIL

    PAIRLIS — функция аргументов x, y, al строит список пар соответствующих элементов из списков x и y и присоединяет их к списку al. Полученный список пар, похожий на таблицу с двумя столбцами, называется ассоциативным списком или ассоциативной таблицей. Такой список может использоваться для связывания имен переменных и функций при организации вычислений интерпретатором.

    (DEFUN pairlis (x y al)
    (COND 
        ((null x) al)
        ((QUOTE T) (CONS 
                             (CONS (CAR x)(CAR Y) )
                             (pairlis (CDR x)(CDR y)al) 
        )              )
)   )
(pairlis '(A B C) 
           '(u t  v)   
           '((D . y)(E . y)) )
; = ((C . v)(B . t)( A . u) (D . y)(E . y))

    ASSOC — функция двух аргументов, x и al. Если al — ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения по таблице, реализованной в форме ассоциативного списка .

    (DEFUN assoc (x al)
    (COND 
        ((equal x (CAAR al)) (CAR al) )
        ((QUOTE T) (assoc x (CDR al)) )
)   )

    Частичная функция — рассчитана на наличие ассоциации.

    (assoc 'B '((A . (m n))
                (B . (CAR x)) 
                (C . w) 
	(B . (QUOTE T)) )
)
     ; = (B . (CAR x))

    SUBLIS — функция двух аргументов al и y, предполагается, что первый из аргументов AL устроен как ассоциативный список вида ((u1 . v1) ... (uK . vK)), где u есть атомы, а второй аргумент Y — любое S-выражение. Действие sublis заключается в обработке Y, такой, что вхождения переменных Ui, связанные в ассоциативном списке со значениями Vi, заменяются на эти значения. Другими словами в S-выражении Y вхождения переменных U заменяются на соответствующие им V из списка пар AL. Вводим вспомогательную функцию SUB2, обрабатывающую атомарные S-выражения, а затем — полное определение SUBLIS:

    (DEFUN sub2 (al z)
   (COND 
        ((null al) z)
        ((equal (CAAR al) z) (CDAR al) )
        ((QUOTE T) (sub2 (CDR al)  z) )
)  )

(DEFUN sublis (al y)
     (COND 
        ((ATOM y) (sub2 al y))
        ((QUOTE T)(CONS 
                            (sublis al (CAR y)) 
                            (sublis al (CDR y))
)    )  )               ) 

(sublis '((x . Шекспир)
            (y . (Ромео и Джульетта)) )
          '(x написал трагедию y) )
; = (Шекспир написал трагедию (Ромео и Джульетта))

    INSERT — вставка z перед вхождением ключа x в список al .

    (DEFUN insert (al x z)
      (COND 
         ((null al) NIL)
         ((equal (CAR al) x) (CONS z al) )
         ((QUOTE T) (CONS (CAR al) 
                                     (insert (CDR al) x z) ))
)    )
(insert '(a b c) 'b 's) = (a s b c)

    ASSIGN — модель присваивания переменным, хранящим значения в ассоциативном списке . Замена связанного с данной переменной в первой паре значения на новое заданное значение. Если пары не было вообще, то новую пару из переменной и ее значения помещаем в конец а-списка, чтобы она могла работать как глобальная.

    (DEFUN assign (x v al) 
     (COND 
        ((Null al) (CONS(CONS x v) NIL ) )
        ((equal x (CAAR al)) (CONS(CONS x v)
                                                (CDR al)) )
        ((QUOTE T) (CONS (CAR al)
                                    (assign x v (CDR al)) ))
   )
)

(assign 'a 111 '((a . 1)(b . 2)(a . 3)))
                ; = ((a . 111)(b . 2)(a . 3))

(assign 'a 111 '((c . 1)(b . 2)(a . 3)))
                ; = ((c . 1)(b . 2)(a . 111))

(assign 'a 111 '((c . 1)(d . 3))) 
            ; =     ((c . 1)(d . 3) (a . 111))

    REVERSE — обращение списка — два варианта, второй с накапливающим параметром и вспомогательной функцией :

    (DEFUN reverse (m) 
     (COND ((null m) NIL)
	(T (append(reverse(CDR m))
                                (list(CAR m)) )) 
)   )

(DEFUN reverse (m) (rev m NIL))
(DEFUN rev (m n)
    (COND ((null m)N)
               (T (rev(CDR m)
                         (CONS (CAR m) n))
)   )          )

    Определение универсальной функции

    Универсальная функция EVAL, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к вычислению функции, имеющей значение на списке аргументов из этой же формы, то данное значение и является результатом функции eval.

    (EVAL '(fn arg1 ... argK))
; = результат применения fn к аргументам arg1, ..., argK.

    Явное определение универсальной функции позволяет достичь четкости механизмов обработки Лисп-программ.

    (EVAL '((LAMBDA (x y) (CONS (CAR x) y)) 
                '(A B) '(C D) ))
; = (A C D)

    Вводим две важные функции EVAL-А и APPLY для обработки форм и обращения к функциям, соответственно. Пусть каждая из этих функций использует ассоциативный список для хранения связанных имен — значений переменных и определений функций.

    Сначала этот список пуст.

    Вернемся к синтаксической сводке вычислимых форм.

    форма ::= переменная
             | (QUOTE S-выражение)
             | (COND (форма форма) ... (форма форма))
             | (функция аргумент ...)

аргумент ::= форма

переменная ::= идентификатор

функция ::= название
                 | (LAMBDA список_переменных форма)
                 | (LABEL название функция)
список_переменных ::= (переменная ... )

название ::= идентификатор

идентификатор ::= атом

    Ветвям этой сводки будут соответствовать ветви универсальной функции:

    Кроме того работа с идентификаторами использует ассоциативный список для хранения связанных имен - значений переменных и определений функций.

    (DEFUN EVAL (e) (eval-a e '((NIL . NIL)(T . T))))

    Вспомогательная функция APPLY понадобилась для выделения обращений к функциям. Вспомогательная функция EVAL-A понадобилась, чтобы для EVAL завести накапливающий параметр — ассоциативный список , в котором будут храниться связи имен переменных с их значениями и названий функций с их определениями. Здесь его значение ((NIL . NIL)(T . T)) обеспечивает, что атомы NIL и T обозначают сами себя.

    (DEFUN eval-a(e a)
    (COND
        ((ATOM e) (CDR(assoc e a)) )
        ((EQ (CAR e) 'QUOTE) (cadr e))
        ((EQ (CAR e) 'COND) (evcon (CDR e) a))
        ( T (apply (CAR e) (evlis (CDR e) a) a) )
)   )

(defun apply (fn x a)
   (COND 
       ((ATOM fn)

            (COND
               ((EQ fn 'CAR) (caar x))
               ((EQ fn 'CDR) (cdar x))
               ((EQ fn 'CONS) (CONS (CAR x)(cadr x)) )
               ((EQ fn 'ATOM) (ATOM (CAR x)) )
               ((EQ fn 'EQ) (EQ (CAR x)(cadr x)) )
               (T (apply (eval-a fn a) x a))
       )    )
   
     ((EQ (CAR fn)'LAMBDA) (eval-a (caddr fn) 
                                        (pairlis (cadr fn) x a) ))
     ((EQ (CAR fn) 'LABEL) (apply (caddr fn) x 
                                       (CONS(CONS(cadr fn) (caddr fn)) a)
)  ) )                             )

    ASSOC и PAIRLIS уже определены ранее.

    (DEFUN evcon (c a) 
    (COND 
       ((eval-a (caar c) a) (eval-a (cadar c) a) )
       ( T (evcon (CDR c) a) ) 
)  )

    (Не допускается отсутствие истинного предиката, т.е. пустого C.)

    (DEFUN evlis (m a)
   (COND
       ((null m) NIL )
       ( T (CONS(eval-a (CAR m) a) 
                     (evlis(CDR m) a) 
)  )  )    )

    При

    (DEFUN EVAL (e) (eval-a e ObList ))

    определения функций могут накапливаться в системной переменной ObList, то есть работать как глобальные определения. ObList обязательно должна содержать глобальное определение встроенной константы "NIL", можно и сразу разместить в ней константу "T", выполняющую роль значения "истина".

    Поясним ряд пунктов этих определений.

    Аргумент EVAL — форма. Если она — атом, то этот атом может быть только именем переменной, а значение переменной должно уже находиться в ассоциативном списке.

    Если CAR от формы — QUOTE, то она представляет собой константу, значение которой выделяется как CADR от нее самой.

    Если CAR от формы — COND, то форма — условное выражение. Вводим вспомогательную функцию EVCON (определение ее будет дано ниже), которая обеспечивает вычисление предикатов (пропозициональных термов) по порядку и выбор формы, соответствующей первому предикату, принимающему значение "истина". Эта форма передается EVAL для дальнейших вычислений.

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

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

    Первый аргумент APPLY — функция. Если она — атом, то существует две возможности. Атом может представлять одну из элементарных функций (CAR CDR CONS ATOM EQ). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом — название ранее заданного определения функции. Определение можно найти в ассоциативном списке , подобно вычислению переменной.

    Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными, а тело определения (форма из лямбда-выражения) передается как аргумент функции EVAL-A для дальнейшей обработки.

    Если функция начинается с LABEL, то ее название и определение соединяются в пару, и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов APPLY, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке — в нем уже размещено определение имени функции. Поскольку определение размещается "наверху" стека, оно становится доступным для всех последующих использований, то есть работает как локальный объект. Глобальные объекты, которые обеспечиваются псевдо-функцией DEFUN, устроены немного иначе, что будет рассмотрено в лекциях 5 и 6.

    Определение универсальной функции является важным шагом, показывающим одновременно и механизмы реализации функциональных языков, и технику функционального программирования на любом языке. Пока еще не описаны многие другие особенности языка Лисп и функционального программирования, которые будут рассмотрены позднее. Но все они будут увязаны в единую картину, основа которой согласуется с этим определением.

  • В строгой теории аппликативного программирования все функции следует определять всякий раз, когда они используются. На практике это неудобно. Реальные системы имеют большой запас встроенных функций (более тысячи в Clisp-е), известных языку, и возможность присоединения такого количества новых функций, какое понадобится. Во многих реализациях Лиспа все элементарные функции вырабатывают результат и на списках, и на атомах, но его смысл зависит от системных решений, что может создавать трудности при переносе программ на другие системы. Базисный предикат EQ всегда имеет значение, но смысл его на неатомарных аргументах будет более ясен после знакомства со структурами данных, используемыми для представления списков в машине.
  • В чистом языке Лисп базисные функции CAR и CDR не определены для атомарных аргументов. Такие функции, имеющие осмысленный результат не на всех значениях естественной области определения, называют частичными. Отладка и применение частичных функций требует большего контроля, чем работа с тотальными, всюду определенными функциями. Во многих реализациях функциональных языков программирования все функции всегда вырабатывают значение. При необходимости каждый существенный класс объектов пополняется значением класса ERROR, символизирующим исключительные ситуации.
  • Для функциональных языков характерно большое разнообразие условных форм, конструкций выбора, ветвлений и циклов, практически без ограничений на их комбинирование. Форма COND выбрана для начального знакомства как наиболее общая. За редким исключением в Лиспе нет необходимости писать в условных выражениях (QUOTE T) или (QUOTE NIL). Вместо них используются встроенные константы T и NIL, соответственно.
  • В реальных системах функционального программирования обычно поддерживается работа с целыми, дробными и вещественными числами в предельно широком диапазоне, а также работа с битовыми и текстовыми строками. Такие данные, как и атомы, являются минимальными объектами при обработке информации, но отличаются от атомов тем, что их смысл задан непосредственно их собственным представлением. Их понимание не требует ассоциаций или связывания. Поэтому и константы такого вида не нуждаются в префиксе в виде апострофа.
    •

    Приведенное выше самоопределение Лисп-интерпретации является концептуальным минимумом, обеспечивающим постепенность восприятия более сложных особенностей специфики функционального программирования, а также методов реализации языков и систем программирования, которые будут иллюстрироваться в дальнейшем. Они будут введены как расширения или уточнения чистого определения универсальной функции.

    Предикаты и истинность в Лиспе

    Хотя формальное правило записи программ вычислений в виде S-выражения предписывает, что константа Т — это (QUOTE T), было оговорено, что в системе всегда пишется Т. Кроме того, NIL оказался удобнее, чем атом F, встречавшийся в начальных предложениях по Лиспу аналог значения FALSE. Программист может либо принять это правило на веру, либо изучить следующие уточнения.

    В Лисп есть два атомных символа, которые представляют истину и ложь, соответственно. Эти два атома — T и NIL. Данные символы — действительные значения всех предикатов в системе. Главная причина в удобстве кодирования. Во многих случаях достаточно отличать произвольное значение от пустого списка. Если атомы T и F имеют значение T и NIL, соответственно, то символы T и F в качестве константных предикатов могут работать, потому что:

    (eval-a T '((NIL . NIL)(T . T) (F . NIL)))    ; = T
(eval-a NIL'((NIL . NIL)(T . T) (F . NIL)))  ; = NIL
(eval-a F '((NIL . NIL)(T . T) (F . NIL)))    ; = NIL

    Формы (QUOTE T) и (QUOTE NIL) будут также работать, потому что:

    (EVAL (QUOTE T) )     ; = T
(EVAL (QUOTE NIL) )  ; = NIL

    Но

    (EVAL (QUOTE F)NIL)  ; = F

    Это неправильно, отлично от NIL, и поэтому (QUOTE F) не будет работать как представление ложного значения в системе.

    Заметим, что

    (EVAL  T )    ; = T
(EVAL NIL )  ; = NIL 
(EVAL F)      ; = NIL

    будет работать в силу причин, которые объясняются в лекции 6.

    Формального различия между функцией и предикатом в Лиспе не существует. Предикат может быть определен как функция со значениями либо T либо NIL. Это верно для всех предикатов системы. Можно использовать форму, не являющуюся предикатом там, где требуется предикат: предикатная позиция условного выражения или аргумент логической операции. Семантически любое S-выражение, отличное от NIL, будет рассматриваться в таком случае как истинное. Первое следствие из этого — предикат NULL и логическое отрицание NOT идентичны. Второе — то, что (QUOTE T) или (QUOTE Х) практически эквивалентны Т как константные предикаты.

    Предикат EQ ведет себя следующим образом:

  • Если его аргументы различны, значением EQ является NIL.
  • Если оба его аргументы являются одним и тем же атомом, то значение — Т.
  • Если значения одинаковы, но не атомы, то его значение T или NIL в зависимости от того, идентично ли представление аргументов в памяти.
  • Значение EQ всегда T или NIL. Оно никогда не бывает не определено, даже если аргументы неправильные.
    •

    Универсальная функция — это джин, выпущенный из бутылки, т.к. потенциал такой функции ограничен лишь способностями нашего воображения. Пока рассмотрены лишь простейшие, самые очевидные следствия из возможности явно применять и уточнять механизмы символьного представления и определения функций, такие как использование накапливающих параметров, связывание обозначений по схеме знак-смысл в ассоциативном списке как имен переменных со значениями, так и названий функций с определениями, а также применение вспомогательных функций для достижения прозрачности определений. Эти возможности имеют место в любом языке высокого уровня. Но попутно выполнено достаточно строгое построение совершенно формальной математической системы, называемой "Элементарный ЛИСП". Составляющие этой формальной системы следующие:

  • Множество символов, называемых S-выражениями.
  • Система функциональных обозначений для основных понятий, необходимых при программировании обработки S-выражений.
  • Формальное представление функциональных обозначений в виде S-выражений.
  • Универсальная функция (записанная в виде S-выражения), интерпретирующая обращение произвольной функции, записанной как S-выражение, к ее аргументам.
  • Система базовых функций, обеспечивающих техническую поддержку обработки S-выражений, и специальных функций, обеспечивающих управление вычислениями.
    •

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

    Страницы:

    Общий подход к обработке символьных выражений и представлению программ

    Приведенные ранее описания и правила записи функций и выражений в этой лекции получат более строгое определение. Начнем с синтаксического обобщения. Представим результаты предыдущей лекции в виде простых БНФ (Формул Бекуса-Наура), позволяющих задать грамматику представления функций и значений в виде системы правил. Каждое правило отдельному понятию сопоставляет ( : : = ) варианты ( | ) его изображения:

    Синтаксис данных в Лиспе сводится к правилам представления атомов и S-выражений, включая списки.

    атом ::= БУКВА конец_атома

    Это правило констатирует, что атомы начинаются с буквы.

    конец_атома ::= пусто
          | БУКВА конец_атома
          | цифра конец_атома

    Это правило констатирует, что после первой литеры в изображении атома могут быть как буквы, так и цифры.

    В Лиспе атомы — это мельчайшие частицы. Их разложение по литерам не имеет смысла.

    S-выражение ::= атом
         | (S-выражение . S-выражение)
         | (S-выражение ... )

    Данное правило констатирует, что S-выражения — это или атомы, или узлы из пары S-выражений, или списки из S-выражений. (Три точки означают, что допустимо любое число вхождений предшествующего вида объектов, включая ни одного.)

    Согласно такому правилу "()" есть допустимое S-выражение. Оно в языке Лисп по соглашению эквивалентно атому NIL.

    Базовая система представления данных — точечная нотация, хотя на практике запись в виде списков удобнее. Любой список можно представить точечной нотацией:

    () = NIL
(a . NIL) = (a)
- - - 
(a1 . ( ... (aK . NIL) ... )) = (a1 ... aK)

    Такая единая структура данных оказалась вполне достаточной для представления сколь угодно сложных программ. Дальнейшее определение языка Лисп можно рассматривать как восходящий процесс генерации семантического каркаса, по ключевым позициям которого распределены семантические действия по обработке программ.

    Другие правила представления данных нужны лишь при расширении и специализации лексики языка (числа, строки, имена особого вида и т.п.). Они не влияют ни на общий синтаксис языка, ни на строй его понятий, а лишь характеризуют разнообразие сферы его конкретных приложений.

    Синтаксис программ является конкретизацией синтаксиса данных, а именно — выделением из класса S-выражений подкласса вычислимых выражений (форм), т.е. данных, имеющих смысл как выражения языка и приспособленных к вычислению. Внешне это выглядит как объявление объектов, заранее известных в языке, и представление разных форм, вычисление которых обладает определенной спецификой.

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

    идентификатор ::= атом

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

    Понятие "идентификатор" выделено для того, чтобы по мере развития определения атома не требовалось на все виды атомов искусственно распространять семантику вычислений. (Например, у Бекуса в его знаменитой статье про "бутылочное горлышко" рассматриваются числа как представление операций доступа [20].)

    форма ::= константа
      | переменная
      | (функция аргумент ... )
      | (COND (форма форма) (форма форма) ... )

константа ::= (QUOTE S-выражение)
      | 'S-выражение

переменная ::= идентификатор

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

    Таким образом, класс форм — это объединение класса переменных и подкласса списков, начинающихся с QUOTE, COND или с представления некоторой функции.

    аргумент ::= форма

    Форма — это выражение, которое может быть вычислено. Форма, представляющая собой константу, выдает эту константу как свое значение. В таком случае нет необходимости в вычислениях, независимо от вида константы. Константные значения могут быть любой сложности, включая вычислимые выражения. Чтобы избежать двусмысленности, предлагается константы изображать как результат специальной функции QUOTE, блокирующей вычисление. Представление констант с помощью QUOTE устанавливает границу, далее которой вычисление не идет. Использование апострофа "'" — просто сокращенное обозначение для удобства набора внешних форм. Константные значения аргументов характерны при тестировании и демонстрации программ.

    Если форма представляет собой переменную, то ее значением должно быть S-выражение, связанное с этой переменной до момента вычисления формы. ( Динамическое связывание, в отличие от традиционного правила, требующего связывания к моменту описания формы, т.е. статическое связывание.)

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

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

    Последняя ветвь определяет формат условного выражения. Согласно этому формату условное выражение строится из размещенных в двухэлементном списке синтаксически различимых позиций для пропозициональных термов и обычных форм. Двухэлементные списки из определения условного выражения рассматриваются как представление предиката и соответствующего ему S-выражения. Значение условного выражения определяется перебором предикатов по порядку, пока не найдется форма, значение которой отлично от NIL, что означает логическое значение "истина". Строго говоря, такая форма должна быть найдена непременно. Тогда вычисляется S-выражение, размещенное вторым элементом этого же двухэлементного списка. Остальные предикаты и формы условного выражения не вычисляют (логика Маккарти), их формальная корректность или определенность не влияют на существование результата.

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

    функция ::= название
        | (LAMBDA список_переменных форма)
        | (LABEL название функция)

список_переменных ::= (переменная ... )

название ::= идентификатор

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

    Таким образом, класс функций — это объединение класса назва-ний и подкласса трехэлементных списков, начинающихся с LAMBDA или LABEL.

    Функция может быть представлена просто именем. В таком случае ее смысл должен быть заранее известен. Функция может быть введена с помощью лямбда-выражения, устанавливающего соответствие между аргументами функции и связанными переменными, упоминаемыми в теле ее определения (в определяющей ее форме). Форма из определения функции может включать переменные, не включенные в лямбда-список, — так называемые свободные переменные. Их значения должны устанавливаться на более внешнем уровне. Если функция рекурсивна, то следует объявить ее имя с помощью специальной функции LABEL. (Используемая в примерах DEFUN, по существу, совмещает эффекты LABEL и LAMBDA.)

    форма ::= переменная
      | (QUOTE S-выражение)
      | (COND (форма форма) ... (форма форма))
      | (функция аргумент ... )

аргумент ::= форма

переменная ::= идентификатор

функция ::= название
      | (LAMBDA список_переменных форма)
      | (LABEL название функция)

список_переменных ::= (переменная ... )
название ::= идентификатор

идентификатор ::= атом
S-выражение ::= атом
      | (S-выражение . S-выражение)
      | (S-выражение ...)

атом ::= БУКВА конец_атома

конец_атома ::= пусто 
      | БУКВА конец_атома
      | цифра конец_атома

    Универсальная функция

    Интерпретация или универсальная функция — это функция, которая может вычислять значение любой формы, включая формы, сводимые к вычислению произвольной заданной функции, применяемой к аргументам, представленным в этой же форме, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, интерпретация будет повторяться бесконечно.)

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

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

  • атомарное выражение обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида x, elem, смысл которых зависит от контекста, в котором они вычисляются;
  • константы, представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение "истина";
  • условное выражение требует специального алгоритма для перебора предикатов и выбора нужной ветви. Например, интерпретация условного выражения
    (COND ((ATOM x) x)
        ((QUOTE T) (first (CAR x)) )
 )
    должна обеспечивать выбор ветви в зависимости от атомарности значения аргумента. Семантика чистого Лиспа не определяет значение условного выражения при отсутствии предиката со значением "истина". Но во многих реализациях и диалектах Лиспа такая ситуация не рассматривается как ошибка, а значением считается NIL. Иногда это придает условным выражениям лаконичность;
  • остальные формы выражений рассматриваются по общей схеме как список из функции и ее аргументов. Обычно аргументы вычисляются, а затем вычисленные значения передаются функции для интерпретации ее определения. Так обеспечивается возможность писать композиции функций. Например, в выражении (first (CAR x)) внутренняя функция CAR сначала получит в качестве своего аргумента значение переменной x, а потом свой результат передаст как аргумент более внешней функции first ;
  • если функция представлена своим названием, то среди названий различаются имена встроенных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенных в программе, например first. Для встроенных функций интерпретация сама "знает", как найти их значение по заданным аргументам, а для введенных в программе функций — использует их определение, которое находит по имени;
  • если функция построена с помощью лямбда-конструктора, то прежде чем ее применять, понадобится связывать переменные из лямбда-списка со значениями аргументов. Функция, использующая лямбда-выражение,
    (LAMBDA (x)
     (COND ((ATOM x) x)
            ((QUOTE T) (first (CAR x)) )
 )   )
    зависит от одного аргумента, значение которого должно быть связано с переменной x. В определении используется свободная функциональная переменная first, которая должна быть определена в более внешнем контексте;
  • если представление функции начинается с LABEL, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Например, предыдущее LAMBDA-определение безымянной функции становится рекурсивным, если его сделать вторым аргументом специальной функции LABEL, первый аргумент которой — fisrt, имя новой функции.
    (LABEL first
    (LAMBDA (x)
         (COND ((ATOM x) x)
              ((QUOTE T) (first (CAR x)) )
)   )   )
    •

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

  • обработка структур данных ( cons, car, cdr, atom, eq );
  • конструирование функциональных объектов ( lambda, label );
  • идентификация объектов (имена переменных и названия функций);
  • управление логикой вычислений и границей вычислимости (композиции, quote, cond, eval ).
    •

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

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

    Начнем с общих методов обработки S-выражений.

    AMONG — проверка, входит ли заданный атом в данное S-выражение.

    (DEFUN among (x y) 
    (COND 
      ((ATOM y) (EQ x y))
      ((among x (CAR y)) (QUOTE T))
      ((QUOTE T) (among x (CDR y) ))
)   )
(among 'A '(C (A B))) ; = T
(among 'A '(C D B))   ; = NIL

    Символ " ; " - начало примечания (до конца строки).

    EQUAL — предикат, проверяющий равенство двух S-выражений. Его значение "истина" для идентичных аргументов и "ложь" для различных. (Элементарный предикат EQ определен только для атомов.) Определение EQUAL иллюстрирует условное выражение внутри условного выражения (двухуровневое условное выражение и equalнаправленная рекурсия).

    (DEFUN equal (x y)
    (COND 
        ((ATOM x) (COND 
                           ((ATOM y) (EQ x y))
                           ((QUOTE T) (QUOTE NIL))
         )            )
        ((equal (CAR x)(CAR y))
      (equal (CDR x)(CDR y)) )

        ((QUOTE T) (QUOTE NIL) )
)   )
(equal '(A (B)) '(A (B))) ; = T
(equal '(A B) '(A . B))   ; = NIL

    SUBST — функция трех аргументов x, y, z, строящая результат замены S-выражением x всех вхождений y в S-выражение z.

    (DEFUN subst (x y z)
    (COND 
         ((equal y z) x)
         ((ATOM z) z)
         ((QUOTE T)(CONS 
                      (subst x y (CAR z)) 
                      (subst x y (CDR z))
                    )
         )
)   )
(subst '(x . A) 'B '((A . B) . C)) =  ((A x . A) . C)

    Использование equal в этом определении позволяет осуществлять подстановку и в более сложных случаях. Например, для редукции совпадающих хвостов подсписков:

    (subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) 
                     ; = ((A . x)     (E . x)     (F . x))

    NULL — предикат, отличающий пустой список от остальных S-выражений. Позволяет выяснять, когда список исчерпан. Принимает значение "истина" тогда и только тогда, когда его аргумент — NIL .

    (DEFUN null (x) 
    (COND 
        ((EQ x (QUOTE NIL)) (QUOTE T))
        ((QUOTE T) (QUOTE NIL))
)   )

    При необходимости можно компоненты точечной пары разместить в двухэлементном списке функцией PAIR_TO_LIST, и наоборот, из первых двух элементов списка построить точечную пару функцией LIST_TO_PAIR.

    (DEFUN pair_to_list (x)
     (CONS (CAR x) 
                (CONS (CDR x) NIL)) )
(pair_to_list '(A B))   ; = (A B)

(DEFUN list_to_pair (x)
      (CONS (CAR x) (CADR x)) ) 
(list_to_pair '(A B C))     ; = (A . B)

    По этим определениям видно, что списочная запись строится большим числом CONS, т.е. на нее расходуется больше памяти.

    Основные методы обработки списков

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

    APPEND — функция двух аргументов x и y, сцепляющая два списка в один.

    (DEFUN append (x y) 
   (COND 
       ((null x) y)
       ((QUOTE T)
         (CONS (CAR x) 
              (append (CDR x) y) 
         )
       )
)  )
(append '(A B) '(C D E))       ; = (A B C D E)

    MEMBER — функция двух аргументов x и y, выясняющая, встречается ли S-выражение x среди элементов списка y .

    (DEFUN member (x y)
    (COND 
        ((null y)  (QUOTE NIL) )
        ((equal x (CAR y)) (QUOTE T) )
        ((QUOTE T) (member x (CDR y)) )
)   )
(member '(a) '(b (a) d))      ; = T
(member 'a '(b (a) d))        ; = NIL

    PAIRLIS — функция аргументов x, y, al строит список пар соответствующих элементов из списков x и y и присоединяет их к списку al. Полученный список пар, похожий на таблицу с двумя столбцами, называется ассоциативным списком или ассоциативной таблицей. Такой список может использоваться для связывания имен переменных и функций при организации вычислений интерпретатором.

    (DEFUN pairlis (x y al)
    (COND 
        ((null x) al)
        ((QUOTE T) (CONS 
                             (CONS (CAR x)(CAR Y) )
                             (pairlis (CDR x)(CDR y)al) 
        )              )
)   )
(pairlis '(A B C) 
           '(u t  v)   
           '((D . y)(E . y)) )
; = ((C . v)(B . t)( A . u) (D . y)(E . y))

    ASSOC — функция двух аргументов, x и al. Если al — ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения по таблице, реализованной в форме ассоциативного списка .

    (DEFUN assoc (x al)
    (COND 
        ((equal x (CAAR al)) (CAR al) )
        ((QUOTE T) (assoc x (CDR al)) )
)   )

    Частичная функция — рассчитана на наличие ассоциации.

    (assoc 'B '((A . (m n))
                (B . (CAR x)) 
                (C . w) 
	(B . (QUOTE T)) )
)
     ; = (B . (CAR x))

    SUBLIS — функция двух аргументов al и y, предполагается, что первый из аргументов AL устроен как ассоциативный список вида ((u1 . v1) ... (uK . vK)), где u есть атомы, а второй аргумент Y — любое S-выражение. Действие sublis заключается в обработке Y, такой, что вхождения переменных Ui, связанные в ассоциативном списке со значениями Vi, заменяются на эти значения. Другими словами в S-выражении Y вхождения переменных U заменяются на соответствующие им V из списка пар AL. Вводим вспомогательную функцию SUB2, обрабатывающую атомарные S-выражения, а затем — полное определение SUBLIS:

    (DEFUN sub2 (al z)
   (COND 
        ((null al) z)
        ((equal (CAAR al) z) (CDAR al) )
        ((QUOTE T) (sub2 (CDR al)  z) )
)  )

(DEFUN sublis (al y)
     (COND 
        ((ATOM y) (sub2 al y))
        ((QUOTE T)(CONS 
                            (sublis al (CAR y)) 
                            (sublis al (CDR y))
)    )  )               ) 

(sublis '((x . Шекспир)
            (y . (Ромео и Джульетта)) )
          '(x написал трагедию y) )
; = (Шекспир написал трагедию (Ромео и Джульетта))

    INSERT — вставка z перед вхождением ключа x в список al .

    (DEFUN insert (al x z)
      (COND 
         ((null al) NIL)
         ((equal (CAR al) x) (CONS z al) )
         ((QUOTE T) (CONS (CAR al) 
                                     (insert (CDR al) x z) ))
)    )
(insert '(a b c) 'b 's) = (a s b c)

    ASSIGN — модель присваивания переменным, хранящим значения в ассоциативном списке . Замена связанного с данной переменной в первой паре значения на новое заданное значение. Если пары не было вообще, то новую пару из переменной и ее значения помещаем в конец а-списка, чтобы она могла работать как глобальная.

    (DEFUN assign (x v al) 
     (COND 
        ((Null al) (CONS(CONS x v) NIL ) )
        ((equal x (CAAR al)) (CONS(CONS x v)
                                                (CDR al)) )
        ((QUOTE T) (CONS (CAR al)
                                    (assign x v (CDR al)) ))
   )
)

(assign 'a 111 '((a . 1)(b . 2)(a . 3)))
                ; = ((a . 111)(b . 2)(a . 3))

(assign 'a 111 '((c . 1)(b . 2)(a . 3)))
                ; = ((c . 1)(b . 2)(a . 111))

(assign 'a 111 '((c . 1)(d . 3))) 
            ; =     ((c . 1)(d . 3) (a . 111))

    REVERSE — обращение списка — два варианта, второй с накапливающим параметром и вспомогательной функцией :

    (DEFUN reverse (m) 
     (COND ((null m) NIL)
	(T (append(reverse(CDR m))
                                (list(CAR m)) )) 
)   )

(DEFUN reverse (m) (rev m NIL))
(DEFUN rev (m n)
    (COND ((null m)N)
               (T (rev(CDR m)
                         (CONS (CAR m) n))
)   )          )

    Определение универсальной функции

    Универсальная функция EVAL, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к вычислению функции, имеющей значение на списке аргументов из этой же формы, то данное значение и является результатом функции eval.

    (EVAL '(fn arg1 ... argK))
; = результат применения fn к аргументам arg1, ..., argK.

    Явное определение универсальной функции позволяет достичь четкости механизмов обработки Лисп-программ.

    (EVAL '((LAMBDA (x y) (CONS (CAR x) y)) 
                '(A B) '(C D) ))
; = (A C D)

    Вводим две важные функции EVAL-А и APPLY для обработки форм и обращения к функциям, соответственно. Пусть каждая из этих функций использует ассоциативный список для хранения связанных имен — значений переменных и определений функций.

    Сначала этот список пуст.

    Вернемся к синтаксической сводке вычислимых форм.

    форма ::= переменная
             | (QUOTE S-выражение)
             | (COND (форма форма) ... (форма форма))
             | (функция аргумент ...)

аргумент ::= форма

переменная ::= идентификатор

функция ::= название
                 | (LAMBDA список_переменных форма)
                 | (LABEL название функция)
список_переменных ::= (переменная ... )

название ::= идентификатор

идентификатор ::= атом

    Ветвям этой сводки будут соответствовать ветви универсальной функции:

    Кроме того работа с идентификаторами использует ассоциативный список для хранения связанных имен - значений переменных и определений функций.

    (DEFUN EVAL (e) (eval-a e '((NIL . NIL)(T . T))))

    Вспомогательная функция APPLY понадобилась для выделения обращений к функциям. Вспомогательная функция EVAL-A понадобилась, чтобы для EVAL завести накапливающий параметр — ассоциативный список , в котором будут храниться связи имен переменных с их значениями и названий функций с их определениями. Здесь его значение ((NIL . NIL)(T . T)) обеспечивает, что атомы NIL и T обозначают сами себя.

    (DEFUN eval-a(e a)
    (COND
        ((ATOM e) (CDR(assoc e a)) )
        ((EQ (CAR e) 'QUOTE) (cadr e))
        ((EQ (CAR e) 'COND) (evcon (CDR e) a))
        ( T (apply (CAR e) (evlis (CDR e) a) a) )
)   )

(defun apply (fn x a)
   (COND 
       ((ATOM fn)

            (COND
               ((EQ fn 'CAR) (caar x))
               ((EQ fn 'CDR) (cdar x))
               ((EQ fn 'CONS) (CONS (CAR x)(cadr x)) )
               ((EQ fn 'ATOM) (ATOM (CAR x)) )
               ((EQ fn 'EQ) (EQ (CAR x)(cadr x)) )
               (T (apply (eval-a fn a) x a))
       )    )
   
     ((EQ (CAR fn)'LAMBDA) (eval-a (caddr fn) 
                                        (pairlis (cadr fn) x a) ))
     ((EQ (CAR fn) 'LABEL) (apply (caddr fn) x 
                                       (CONS(CONS(cadr fn) (caddr fn)) a)
)  ) )                             )

    ASSOC и PAIRLIS уже определены ранее.

    (DEFUN evcon (c a) 
    (COND 
       ((eval-a (caar c) a) (eval-a (cadar c) a) )
       ( T (evcon (CDR c) a) ) 
)  )

    (Не допускается отсутствие истинного предиката, т.е. пустого C.)

    (DEFUN evlis (m a)
   (COND
       ((null m) NIL )
       ( T (CONS(eval-a (CAR m) a) 
                     (evlis(CDR m) a) 
)  )  )    )

    При

    (DEFUN EVAL (e) (eval-a e ObList ))

    определения функций могут накапливаться в системной переменной ObList, то есть работать как глобальные определения. ObList обязательно должна содержать глобальное определение встроенной константы "NIL", можно и сразу разместить в ней константу "T", выполняющую роль значения "истина".

    Поясним ряд пунктов этих определений.

    Аргумент EVAL — форма. Если она — атом, то этот атом может быть только именем переменной, а значение переменной должно уже находиться в ассоциативном списке.

    Если CAR от формы — QUOTE, то она представляет собой константу, значение которой выделяется как CADR от нее самой.

    Если CAR от формы — COND, то форма — условное выражение. Вводим вспомогательную функцию EVCON (определение ее будет дано ниже), которая обеспечивает вычисление предикатов (пропозициональных термов) по порядку и выбор формы, соответствующей первому предикату, принимающему значение "истина". Эта форма передается EVAL для дальнейших вычислений.

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

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

    Первый аргумент APPLY — функция. Если она — атом, то существует две возможности. Атом может представлять одну из элементарных функций (CAR CDR CONS ATOM EQ). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом — название ранее заданного определения функции. Определение можно найти в ассоциативном списке , подобно вычислению переменной.

    Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными, а тело определения (форма из лямбда-выражения) передается как аргумент функции EVAL-A для дальнейшей обработки.

    Если функция начинается с LABEL, то ее название и определение соединяются в пару, и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов APPLY, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке — в нем уже размещено определение имени функции. Поскольку определение размещается "наверху" стека, оно становится доступным для всех последующих использований, то есть работает как локальный объект. Глобальные объекты, которые обеспечиваются псевдо-функцией DEFUN, устроены немного иначе, что будет рассмотрено в лекциях 5 и 6.

    Определение универсальной функции является важным шагом, показывающим одновременно и механизмы реализации функциональных языков, и технику функционального программирования на любом языке. Пока еще не описаны многие другие особенности языка Лисп и функционального программирования, которые будут рассмотрены позднее. Но все они будут увязаны в единую картину, основа которой согласуется с этим определением.

  • В строгой теории аппликативного программирования все функции следует определять всякий раз, когда они используются. На практике это неудобно. Реальные системы имеют большой запас встроенных функций (более тысячи в Clisp-е), известных языку, и возможность присоединения такого количества новых функций, какое понадобится. Во многих реализациях Лиспа все элементарные функции вырабатывают результат и на списках, и на атомах, но его смысл зависит от системных решений, что может создавать трудности при переносе программ на другие системы. Базисный предикат EQ всегда имеет значение, но смысл его на неатомарных аргументах будет более ясен после знакомства со структурами данных, используемыми для представления списков в машине.
  • В чистом языке Лисп базисные функции CAR и CDR не определены для атомарных аргументов. Такие функции, имеющие осмысленный результат не на всех значениях естественной области определения, называют частичными. Отладка и применение частичных функций требует большего контроля, чем работа с тотальными, всюду определенными функциями. Во многих реализациях функциональных языков программирования все функции всегда вырабатывают значение. При необходимости каждый существенный класс объектов пополняется значением класса ERROR, символизирующим исключительные ситуации.
  • Для функциональных языков характерно большое разнообразие условных форм, конструкций выбора, ветвлений и циклов, практически без ограничений на их комбинирование. Форма COND выбрана для начального знакомства как наиболее общая. За редким исключением в Лиспе нет необходимости писать в условных выражениях (QUOTE T) или (QUOTE NIL). Вместо них используются встроенные константы T и NIL, соответственно.
  • В реальных системах функционального программирования обычно поддерживается работа с целыми, дробными и вещественными числами в предельно широком диапазоне, а также работа с битовыми и текстовыми строками. Такие данные, как и атомы, являются минимальными объектами при обработке информации, но отличаются от атомов тем, что их смысл задан непосредственно их собственным представлением. Их понимание не требует ассоциаций или связывания. Поэтому и константы такого вида не нуждаются в префиксе в виде апострофа.
    •

    Приведенное выше самоопределение Лисп-интерпретации является концептуальным минимумом, обеспечивающим постепенность восприятия более сложных особенностей специфики функционального программирования, а также методов реализации языков и систем программирования, которые будут иллюстрироваться в дальнейшем. Они будут введены как расширения или уточнения чистого определения универсальной функции.

    Предикаты и истинность в Лиспе

    Хотя формальное правило записи программ вычислений в виде S-выражения предписывает, что константа Т — это (QUOTE T), было оговорено, что в системе всегда пишется Т. Кроме того, NIL оказался удобнее, чем атом F, встречавшийся в начальных предложениях по Лиспу аналог значения FALSE. Программист может либо принять это правило на веру, либо изучить следующие уточнения.

    В Лисп есть два атомных символа, которые представляют истину и ложь, соответственно. Эти два атома — T и NIL. Данные символы — действительные значения всех предикатов в системе. Главная причина в удобстве кодирования. Во многих случаях достаточно отличать произвольное значение от пустого списка. Если атомы T и F имеют значение T и NIL, соответственно, то символы T и F в качестве константных предикатов могут работать, потому что:

    (eval-a T '((NIL . NIL)(T . T) (F . NIL)))    ; = T
(eval-a NIL'((NIL . NIL)(T . T) (F . NIL)))  ; = NIL
(eval-a F '((NIL . NIL)(T . T) (F . NIL)))    ; = NIL

    Формы (QUOTE T) и (QUOTE NIL) будут также работать, потому что:

    (EVAL (QUOTE T) )     ; = T
(EVAL (QUOTE NIL) )  ; = NIL

    Но

    (EVAL (QUOTE F)NIL)  ; = F

    Это неправильно, отлично от NIL, и поэтому (QUOTE F) не будет работать как представление ложного значения в системе.

    Заметим, что

    (EVAL  T )    ; = T
(EVAL NIL )  ; = NIL 
(EVAL F)      ; = NIL

    будет работать в силу причин, которые объясняются в лекции 6.

    Формального различия между функцией и предикатом в Лиспе не существует. Предикат может быть определен как функция со значениями либо T либо NIL. Это верно для всех предикатов системы. Можно использовать форму, не являющуюся предикатом там, где требуется предикат: предикатная позиция условного выражения или аргумент логической операции. Семантически любое S-выражение, отличное от NIL, будет рассматриваться в таком случае как истинное. Первое следствие из этого — предикат NULL и логическое отрицание NOT идентичны. Второе — то, что (QUOTE T) или (QUOTE Х) практически эквивалентны Т как константные предикаты.

    Предикат EQ ведет себя следующим образом:

  • Если его аргументы различны, значением EQ является NIL.
  • Если оба его аргументы являются одним и тем же атомом, то значение — Т.
  • Если значения одинаковы, но не атомы, то его значение T или NIL в зависимости от того, идентично ли представление аргументов в памяти.
  • Значение EQ всегда T или NIL. Оно никогда не бывает не определено, даже если аргументы неправильные.
    •

    Универсальная функция — это джин, выпущенный из бутылки, т.к. потенциал такой функции ограничен лишь способностями нашего воображения. Пока рассмотрены лишь простейшие, самые очевидные следствия из возможности явно применять и уточнять механизмы символьного представления и определения функций, такие как использование накапливающих параметров, связывание обозначений по схеме знак-смысл в ассоциативном списке как имен переменных со значениями, так и названий функций с определениями, а также применение вспомогательных функций для достижения прозрачности определений. Эти возможности имеют место в любом языке высокого уровня. Но попутно выполнено достаточно строгое построение совершенно формальной математической системы, называемой "Элементарный ЛИСП". Составляющие этой формальной системы следующие:

  • Множество символов, называемых S-выражениями.
  • Система функциональных обозначений для основных понятий, необходимых при программировании обработки S-выражений.
  • Формальное представление функциональных обозначений в виде S-выражений.
  • Универсальная функция (записанная в виде S-выражения), интерпретирующая обращение произвольной функции, записанной как S-выражение, к ее аргументам.
  • Система базовых функций, обеспечивающих техническую поддержку обработки S-выражений, и специальных функций, обеспечивающих управление вычислениями.
    •

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

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