Элементарный Лисп

Точечная нотация

Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования S-выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.

Бинарный узел, содержащий пару атомов   ATOM1 и ATOM2, можно представить в виде S-выражения вида:

( ATOM1 . ATOM2 )

Если вместо атомов   ATOM1, ATOM2 рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то получим множество всех возможных S-выражений. Можно сказать, что S-выражение — это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Все сложные данные выстраиваются из одинаково устроенных блоков — бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.

ATOM
(A . B)
(C . (A . B))
((A . B) . C)
((A . B) . (D . C))
((A . B) . (D . (C . E)))

Любое S-выражение может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.

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

Точечная нотация точнее, чем списки, представляет логику хранения данных в памяти и доступа к компонентам структур данных, но для непосредственного представления и обработки символьных выражений она оказалась менее удобной. Практически сразу была предложена более лаконичная запись наиболее употребимого подкласса S-выражений в виде списков произвольной длины вида (A B C D E F G H ). В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом   NIL, символизирующий завершение списка.

Атом NIL, рассматриваемый как представление пустого списка   (), играет роль ограничителя в любом списке. Одноэлементный список   (A) идентичен S-выражению   (A . NIL). Список   (A1 A2 ... Ak) может быть представлен как S-выражение вида:

(A1 . (A2 . ( ... . (Ak . NIL) ... ))).

В памяти это фактически одна и та же структура данных. (Запятая в качестве разделителя элементов списка в первых реализациях Лиспа поддерживалась, но не прижилась. Пробел оказался удобнее.)

Для многошагового доступа к отдельным элементам такой структуры удобно пользоваться мнемоничными обозначениями композиций из многократных CAR-CDR. Имена таких композиций устроены как цепочки из "a" или "d", задающие маршрут движения из шагов CAR и CDR, соответственно, расположенный между "c" и "r". Указанные таким способом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. в порядке, обратном записи.

Основные понятия: программа, функции и выражения

Гипотезу об универсальности символьных данных, прежде всего, следует проверить при выборе представления форм, возникающих при написании программы и ее основного конструктива — переменных, констант, выражений, определений, ветвлений, вызовов функций:

1) Самая простая форма выражения — это переменная. Она может быть представлена как атом .

X
Y
n
Variablel
LongSong

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

(функция аргумент1 аргумент2 ... )

Обычно S-выражение — это или атом, или список ; значит, неатомарное S-выражение можно понимать как вызов функции, если все остальные понятия свести к применению некоторых функциональных объектов.

Теперь можно записывать формы для получения результатов операций из таблиц 2.1 и 2.2 в виде списков:

(ATOM NIL)
(CONS NIL NIL)
((LAMBDA (Y X) (CONS X Y)) NIL(ATOM NIL)) 
		;= (T)
((LAMBDA (X Y) (CONS X Y)) NIL(ATOM NIL)) 
		;= (() . T)

";" - начало строчного комментария. Последние два примера показывают роль порядка аргументов функции, задаваемого с помощью специального LAMBDA-конструктора.

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

Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций LABEL (отсутствует в Common Lisp), первый аргумент которого — имя функции, второй — собственно именуемое определение функции . Формальным результатом LABEL является ее первый аргумент, который становится объектом другой категории. Он меняет свой статус — теперь это имя новой функции.

(LABEL третий	;               ; имя новой функции
     (LAMBDA (x)	;	; параметры функции
         (CAR (CDR (CDR x)))     ; тело функции
 )   )

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

4) Композиции функций можно строить с помощью вложенных скобок.

(функция1 (функция2 аргумент21 аргумент22 ... )
                   аргумент2 ... )

Приведенные правила ничего не говорят ни о природе данных и функций, ни о порядке вычисления аргументов и композиций функций. Речь идет исключительно о форме — внешнем виде списков, используемых для записи программы. Такая синтаксическая оболочка, в которой еще не конкретизированы операции над данными, является общей спецификацией реализационной основы для определения аппликативных систем, допускающих специализацию практически в любом направлении. Можно сказать, что Лисп является аппликативной системой, специализированной для обработки списков или S-выражений. (Язык функционального программирования Sisal [11] специализирован для обработки многомерных векторов и организации параллельных процессов, выполняемых на суперкомпьютерах.)

Этих правил достаточно, чтобы более ясно выписать основные тождества Лиспа, формально характеризующие элементарные функции CAR, CDR, CONS, ATOM, EQ над S-выражениями:

(CAR (CONS x y))       ; = x
(CDR (CONS x y))       ; = y
(ATOM (CONS x y))     ; = NIL
(CONS (CAR x) (CDR x))  ; = x - для неатомарных x.
(EQ x x)                 ; = T - если x атом
(EQ x y)                 ; = NIL - если x и y различимы

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

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

(SET 'PI 3.1415926)

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

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

(QUOTE A)                       ;константа атом A 
(QUOTE (A B C) )             ;константа список (A B C) 
(ATOM (QUOTE A))           ;= T — аргумент предиката - атом A   
(ATOM (QUOTE (A B C)))  ; = Nil — аргумент предиката - список (A B C)
(ATOM A)                        ;— значение не определено

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

Можно сказать, что функция QUOTE выполняет в древовидной структуре программы роль помеченного контейнера. С ее помощью любое выражение может быть заключено в контейнер, а контейнер помечен указанием, что вычислять его содержимое не следует. Потом, при выполнении функции QUOTE, пометка и контейнер исчезают, и выражение может обрабатываться по общей схеме. Например: (третий (QUOTE (A B C))) — применение функции "третий" к значению, не требующему вычисления.

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

Ветвление   (условное выражение) характеризуется тем, что ход процесса зависит от некоторых предикатов (условий), причем условия следует сгруппировать в общий комплект и соотнести с подходящими ветвями. Такую организацию процесса вычисления обеспечивает специальная функция   COND (condition), аргументами которой являются двухэлементные списки, содержащие предикаты и соответствующие им выражения. Аргументов может быть сколько угодно, а обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента, и вычисляется его значение, которое и считается значением всего условного выражения .

(COND (p1 e1) (p2 e2) ... (pk ek) )

pi - предикаты для выбора ветви,

ei - ветви условного выражения

Каждый предикат   pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.

Обычное условное выражение   (if Predicate Then Else) или (если Predicate то Then иначе Else) может быть представлено с помощью функции COND следующим образом:

(COND (Predicate Then)(T Else))

Разумеется, можно повышать наглядность подбором геометрии текста:

(COND
       (Predicate Then)
       (T Else)
 )

(COND
      ((EQ (CAR x) (QUOTE A))  (CONS (QUOTE B) (CDR x)) )
      (T x)
 )

Атом   T представляет тождественную истину. Значение всего условного выражения получается путем замены первого элемента из значения переменной   x на B в том случае, если (CAR x) совпадает с A

Содержательно функции QUOTE, COND, LAMBDA образуют базовый комплект средств управления программами и процессами, поддерживающий стиль программирования, идеологически близкий структурному программированию [18].

Такие специальные функции   QUOTE, COND, LAMBDA существенно отличаются от элементарных функций   CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычные функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции. Специальные функции не требуют такой предварительной обработки параметров. Они сами могут выполнять все необходимое, используя представление фактических параметров в виде S-выражений.

Рекурсивные функции: определение и исполнение

8) Определения могут быть рекурсивными.

На практике такие определения обычно имеют глобальные имена, задаваемые с помощью функции DEFUN, о которой еще будет речь в конце этой лекции. Сейчас теоретически можно ограничиться конструктором локальных функций LABEL, которую мы вводим здесь для учебных целей (в системе GNU Clisp его нет, но для него проще определение интерпретатора, которое будем строить в следующей лекции).

Как правило, рекурсивные вызовы функций должны быть заданы в комплекте с нерекурсивными ветвями процесса. Основное применение условных выражений — рекурсивные определения функций .

(LABEL премьер          ;имя локальной функции
     (LAMBDA (x)          ;определение функции
          (COND ((ATOM x) x)
                      (T (премьер (CAR x)))
 )    )   )

Новая функция "премьер" выбирает первый атом из любого данного. Если x является атомом, то он является результатом, иначе функцию "премьер" следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь, выбираемая по тождественно истинному значению встроенной константы   T.

Определение функции "премьер" рекурсивно. Эта функция действительно работает в терминах самой себя. Важно, что для любого S-выражения существует некоторое число применений функции CAR, после которого из этого S-выражения выделится какой-нибудь атом, следовательно, процесс вычисления функции всегда определен, детерминирован и завершится за конечное число шагов. Можно сказать, что для определенности рекурсивной функции следует формулировать условие ее завершения.

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

((LABEL премьер  
       (LAMBDA (x)
            (COND ((ATOM x) x)
	       (T (премьер (CAR x)))
  )    )    )    ; объявлена локальная функция "премьер"
        (QUOTE ((A . B) . C) )  ; дан аргумент локальной функции
)   ; завершено выражение с локальной функцией

LABEL вырабатывает представление функции, которое тут же может быть применено к аргументу. При этом LABEL дает имена обычным функциям, поэтому фактический параметр функции "премьер" будет вычислен до того, как начнет работать ее определение, и переменная x получит значение ((A . B) . C)).

x = ((A . B) . C))

(T (премьер (CAR x))) )

Условные выражения не менее удобны и для численных расчетов:

(LABEL Абс 
     (LAMBDA (x)
            (COND
                ((< x 0 ) (- x))
                (T x) 
 )   )      )

(LABEL Факториал 
     (LAMBDA (N)
         (COND
             ((= N 0 ) 1 )
             (T ( * N (Факториал (- N 1 ))) ) 
 )   )   )

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

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

(+ 1 2 3 4) = 10

(LABEL НОД 
     (LAMBDA (x y)
          (COND
                ((< x y) (НОД y x))
                ((= (остаток y x ) 0 ) x )
                (T (НОД (остаток y x) x )) 
 )   )    )

Подробное изложение теории функций, определяемых рекурсивными выражениями, можно найти у многих математиков, например [19].

По мнению Дж. Маккарти, даже математики, включая логиков, термин "функция" используют не вполне аккуратно, применяя его к формулам вида "x + y^2" с уверенностью, что читатель, слушатель или собеседник правильно поймет, о чем идет речь. Автоматическая обработка данных, символизирующих функции, требует более точного различия между функциями и формами их применения. Для этих целей выработана система обозначений, известная как "лямбда-исчисление", которую предложил Алонсо Черч в работах по исследованию понятия "функция". Соответствующие рассуждения поясняются в книге по Lisp 1.5 [1] на простом примере (неофициальный перевод):

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

(DEFUN третий  ; имя новой функции
           (x)	       ; параметры функции
           (CAR (CDR (CDR x )))   ; тело функции
 )

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

(третий (QUOTE (A B C)) ) ; — применение новой функции

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

(DEFUN премьер (x)
    (COND ((ATOM x) x)
             (T (премьер (CAR x)) ) 
 )  )

Собственно механизм связывания пока определен не был. Функция DEFUN использует лямбда-конструктор, чтобы представление функции получалось более естественно и использовалось как единая конструкция. Фактически LABEL и DEFUN реализуют аналог тождества:

премьер = (LAMBDA (x) (COND ((ATOM x) x)
                                             (T (премьер (CAR x)) ) ))

Роль локального связывания имени и определения функции в Лиспе выполняет специальная функция LABEL. Если EF — определение, а NF — его имя, то (LABEL NF EF) — функция, знающая свое имя NF. В форме (DEFUN премьер (x) (COND((ATOM x) x) (T (премьер (CAR x))) )) используется x — связанное имя переменной, а "премьер" — связанное имя функции, доступное программе.

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

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

Базис элементарного Лиспа образуют пять функций над S-выражениями, CAR, CDR, CONS, ATOM, EQ, и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, LABEL.

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

Формально для перехода к самостоятельным упражнениям нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями: