Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 5

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

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

Определение языкаТеперь можем датьпрограммирования.-болееточноеопределениеЛиспакакязыкаСинтаксис ЛиспаСемантика ЛиспаНакопительные параметрыВспомогательные функцииНачнем с синтаксического обобщения.Определение языка программирования обычно начинают с синтаксическихформул, называемых БНФ (формулы Бекуса-Наура). Определение таких формулсводится к следующим положениям:••••Язык характеризуется набором определяемых понятий.Каждому понятию соответствует набор вариантов синтаксических формул.Каждый вариант – это последовательность элементов.Элемент – это или терминальный символ или синтаксическое понятие –нетерминальный символ.Синтаксис данных в Лиспе сводится к правилам представления атомов и Sвыражений.<атом> ::= <БУКВА> <конец_атома><конец_атома> ::= <пусто>| <БУКВА> <конец_атома>| <число> <конец_атома>В Лиспе атомы - это мельчайшие частицы.

Их разложение по литерам не имеет смысла.<S-выражение> ::= <атом>| (<S-выражение> . <S-выражение>)| (<S-выражение> ... )По этому правилу S-выражения - это или атомы, или узлы из пары S-выражений,или списки из S-выражений./Три точки означают, что допустимо любое число вхождений предшествующеговида объектов, включая ни одного./30Символ «;» - начало комментария до конца строки.Т.о. “()” есть допустимое S-выражение.

Оно в языке Лисп по соглашениюэквивалентно атому Nil.Базовая система представления данных - точечная нотация, хотя на практикезапись в виде списков удобнее. Любой список можно представить точечнойнотацией:() = Nil(a . Nil) = (a)--(a1 . ( ... (aK . Nil) ... )) = (a1 ... aK)Такая единая структура данных оказалась вполне достаточной для представлениясколь угодно сложных программ. Дальнейшее определение языка Лиспа можнорассматривать как восходящий процесс генерации семантического каркаса, поключевым позициям которого распределены семантические действия пообработке программ.Другие правила представления данных нужны лишь при расширении испециализации лексики языка (числа, строки, имена особого вида и т.п.). Они невлияют ни на общий синтаксис языка, ни на строй его понятий, а лишьхарактеризуют разнообразие сферы его конкретных приложений.Синтаксис программ в Лиспе внешне на отличается от синтаксиса данных.Просто выделяем вычислимые выражения (формы), т.е.

данные,приспособленные к вычислению. Внешне это выглядит как объявление объектов,заранее известных в языке, и представление разных форм, вычисление которыхобладает определенной спецификой.Выполнение программына Лиспе устроено как интерпретация данных,представляющих выражения, имеющие значение. Ниже приведены синтаксическиеправила для обычных конструкций, к которым относятся идентификаторы,переменные, константы, аргументы, формы и функции.<идентификатор> ::= <атом>Идентификатор - это атомы, используемые при именовании неоднократноиспользуемых объектов программы - функций и переменных. Предполагается, чтообъекты размещаются в памяти так, что по идентификатору их можно найти.31<форма> ::= <константа>| <переменная>| (<функция> <аргумент> ...

>)| (COND (<форма> <форма>) (<форма> <форма>) ... )<константа> ::= (QOUTE <S-выражение>)| '<S-выражение><переменная> ::= <идентификатор>Переменная - это идентификатор, имеющий многократно используемое значение,ранее вычисленное в подходящем контексте.

Подразумевается, что одна и та жепеременная в разных контекстах может иметь разные значения.Форма - это выражение, которое может быть вычислено. Формами являютсяпеременные и списки, начинающиеся с QUOTE, COND или с представлениянекоторой функции.<аргумент> ::= <форма>Если форма представляет собой константу, то нет необходимости в вычислениях,независимо от вида константы. Константные значения, могут быть любойсложности, включая вычислимые выражения.Константы изображаются спомощью специальной функции QUOTE, блокирующей вычисление.Представление констант с помощью QOUTE устанавливает границу, далее которойвычисление не идет.

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

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

Строго говоря, такая форма должна найтись непременно.Тогда вычисляется S-выражение, размещенное вторым элементом этого жедвухэлементного списка. Остальные предикаты и формы условного выраженияне вычисляют (логика Мак-Карти), их формальная корректность илиопределенность не влияют на существование результата.Разница между предикатами и обычными формами заключается лишь в трактовкеих результатов. Любая форма может выполнить роль предиката.<функция> ::= <название>| (LAMBDA <список_переменных> <форма>)| (DEFUN <название> <функция>)<список_переменных> ::= (<переменная> ... )<название> = <идентификатор>Название - это идентификатор, определение которого хранится в памяти, но ономожет не подвергаться влиянию контекста вычислений.Таким образом, функция - это или название, или трехэлементный список,начинающийся с LAMBDA или DEFUN.Функция может быть представлена просто именем.

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

Некоторые из них пригодятся приопределении интерпретатора.Начнем с общих методов обработки S-выражений.AMONG – проверка входит ли заданный атом в данное S-выражение.33(DEFUN among (x y) (COND((ATOM y) (EQ x y))((among x (CAR y)) (QUOTE T))((QUOTE T) (among x (CDR y) ))))EQUAL - предикат, проверяющий равенство двух S-выражений. Его значение"истина" для идентичных аргументов и "ложь" для различных. (Элементарныйпредикат EQ определен только для атомов.) Определение 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))))При желании можно дать название этой функции по-русски:(DEFUN равно_ли (x y) (equal x y))SUBST - функция трех аргументов x, y, z, строящая результатвыражением x всех вхождений атома y в S-выражение z.замены S-(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))))))34(subst '(x .