Определение языка программирования

Начнем с синтаксического обобщения.

Определение языка программирования обычно начинают с синтаксических формул, называемых БНФ ( формулы Бекуса-Наура ). Определение таких формул сводится к следующим положениям:

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

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

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

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

<S-выражение> ::= <атом>
         | (<S-выражение> . <S-выражение>)  ; пара
         | (<S-выражение> ... )             ; список

По этому правилу S-выражения - это или атомы, или узлы из пары S-выражений, или списки из S-выражений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если форма представляет собой константу, то нет необходимости в вычислениях, независимо от вида константы. Константные значения, могут быть любой сложности, включая вычислимые выражения, но в данный момент они не вычисляются. Константы изображаются с помощью специальной функции QUOTE, блокирующей вычисление. Представление констант с помощью QUOTE устанавливает границу, далее которой вычисление не идет. Использование апострофа (') - просто сокращенное обозначение для удобства набора текста. Константные значения аргументов характерны при тестировании и демонстрации программ.

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

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

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

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

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

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

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

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

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

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

Функция может быть представлена просто именем. В таком случае ее смысл должен быть заранее известен. Например, встроенные функции CAR, CDR и т.д.

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

Общий механизм вычисления форм будет позднее определен как универсальная функция 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 '( B . A )  )

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

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

(equal '( A B ) '( A . B))
(equal '( A B ) '( A . (B . Nil)) )

При желании можно дать название этой функции по-русски:

(DEFUN равно_ли  (x y)  (equal x y))

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)
(subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) ;= ((A . x)(E . x)(F . x))

Символ " ; " - начало комментария.

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

(DEFUN Подстановка (x y z) (subst x y z))
(Подстановка '(x . A) 'B '((A . B) . C))        ;= ((A . (x . A)) . C)

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

(DEFUN null (x) (COND 
            ((EQ x (QUOTE Nil)) (QUOTE T))
            ((QUOTE T)  (QUOTE Nil))
          )
)
( null '() )

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

(DEFUN pair_to_list  (x)  (CONS (CAR x) (CONS (CDR x) Nil)) )
( pair_to_list  '( A . B ) )

(DEFUN list_to_pair  (x)  (CONS (CAR x) (CADR x)) )
(list_to_pair  '( 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) C))
(member ' (A) '( B (A) C))

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)))       ;= ((A . u)(B . t)(C . v)(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))

Упражнение 5.1: Введите функции с именами – Пусто, Пара_в_список, Список_в_пару, входит_ли, Соединение, Элемент, Связывание, Ассоциация, Ряд_подстановок, Вставка, Присваивание, как аналоги вышеприведенных функций.

Упражнение 5.2: Напишите определение функции REVERSE – обращение списка, т.е. перечисление его элементов в обратном порядке.

Ответ:

(defun reverse (m) 
       (cond ((null m) NIL)
          (T (append(reverse(cdr m)) 
                     (list(car m))         ))       ))

Теперь посмотрим ее вариант как пример использования накапливающих параметров и вспомогательных функций:.

(defun rev (m n) 
      (cond ((null m) N)
               (T  (rev(cdr m) (cons (car m) n)))      )) 

(defun reverse (m) (rev m Nil)   )

Такое определение экономнее расходует память.

Выводы: