Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп, страница 2

При записи символьных атомовобычно можно использовать спецзнаки (*, = и др.), регистр же букв неважен: так, B5 и b5 – это два варианта записи одного и того же атома B5.Символьные атомы используются как для записи обрабатываемыхсписков, так и в качестве имён переменных и функций.5Среди множества атомов базового Лиспа константами являются:все числовые атомы;символьные атомы T и NIL, обозначающие соответственнологические значения истина и ложь; а атом NIL также обозначаетпустой список.Ключевым понятием языка Лисп является список – рекурсивнаяструктура, которая может быть описана следующими БНФ(металингвистическими формулами Бэкуса-Наура):список ::= ( последовательность_элементов ) | пустой списокпоследовательность_элементов ::= элемент |элемент └─┘ последовательность_элементовэлемент ::= атом | списокпустой список ::= () | NILВ приведённых БНФ знак └─┘ обозначает пробел.

Пробелы используются вкачестве разделителей элементов списка. Другими разделителямиэлементов являются круглые скобки, при этом расположенные рядом соскобками пробелы могут быть опущены. Примеры списков языка Лисп:(BETA 56 (9))()((С ()) NIL 81 (ЕЕ В С))((((Т))))Таким образом, лисповский список может содержать в качествесвоих элементов атомы и другие, вложенные списки. В каждом спискеможет быть произвольное количество элементов. Количество уровнейвложенности списков также не ограничивается. Первый уровень элементовсписка, открывающийся внешней круглой скобкой, называется верхним.Глубиной списка считается максимальное количество вложенных парскобок.

Так, на верхнем уровне списка (BETA 56 (9)) находятся триэлемента: символьный атом BETA, число 56 и вложенный список (9), аглубина этого списка равна 2.Единственной константой составного типа является пустой список(), который может быть записан и как атом NIL, обе эти записиэквивалентны. Отметим, что уникальной особенностью этой константыявляется её принадлежность одновременно и к атомам, и к спискам.Программа на языке Лисп записывается в виде последовательностиатомов и списков, т.е. программа и данные имеют одинаковый синтаксис.Точнее, лисп-программа представляет собой последовательность форм, аформа, или вычислимое выражение – это атом или список, который можновычислить и получить значение. Далее для указания связи форм с ихзначениями будем использовать запись видаформа => значение .6Вычисление программы реализует лисп-интерпретатор, которыйсчитывает очередную входящую в программу форму, вычисляет её ивыводит полученный результат (атом или список).Важным является вопрос: какие атомы и списки вычислимы (т.е.являются формами).

Охарактеризуем три самых распространённых случаявычислимых выражений: константа, переменная со значением иобращение к функции.1) Любая константа представляет собой вычислимое выражение,значением которого является она сама. Например,для чисел:72 => 72для символьных атомов:t => T() => NILNIL => NILЗаметим, что при выводе атомов лисп-интерпретатор используетобычно заглавные (прописные) буквы, а атом NIL применяется какканоническая запись пустого списка.2) Символьный атом вычислим только тогда, когда он представляетсобой имя переменной, точнее – имя формального параметра(аргумента) некоторой функции, и этот параметр имеет значение,например:x => (B C D).3) Список можно вычислить, если он представляет собой обращение кфункции, или функциональный вызов: (f e1 e2 … en),где f – символьный атом, имя вызываемой функции,а e1, e2, …, en – аргументы этой функции, n≥0.n - число аргументов функции.В случае n=0 имеем вызов функции без аргументов: (f).

Обычноe1, e2, …, en являются вычислимыми выражениями и вычисляютсяпоследовательно слева направо.Таким образом, если в процессе работы лисп-интерпретаторатребуется вычислить некоторый список, то первым элементом этогосписка должно быть имя функции. Если это не так, лисп-интерпретаторсообщает об ошибке и прерывает вычисление текущего выраженияпрограммы.Вместо общепринятой в математике записи обращений к функциямвида f(x,y) в Лиспе используется нотация, при которой имя функциистоит не перед аргументными скобками, а внутри них, вместе саргументами, которые разделяются уже не запятыми, а пробелами:(f x y).

Именно за счёт этого достигается синтаксическое единообразиепрограммы и данных.7Функции Лиспа обычно делятся на:•встроенные, или стандартные, которые могут применяться безопределения;•определяемые пользователем в его программе.Другое важное в Лиспе деление функций на классы учитываетколичество и вычислимость аргументов функции. Различают: обычные функции (их большинство); особые, или специальные функции.Обычная функция имеет строго фиксированное число аргументов, ипри вычислении её значения интерпретатор сначала вычисляет значения еёаргументов, а уже затем функция применяется к вычисленным значениям.У особой функции нарушается хотя бы одно из двух указанныхтребований, т.е. у неё может быть произвольное количество аргументови/или некоторые её аргументы могут не вычисляться.Поскольку возможны вложенные функциональные обращения, кпримеру: (f1 (f2 x) (f4 (f3 y))) ,существенен порядок их вычисления.

Вычисление начинается с самойвнешней функции, в данном примере – с функции f1. Если она обычная,то сначала необходимо вычислить вложенные функциональные вызовы,задающие значения её аргументов – обращения к функциям f2 и f4. Всвою очередь для вычисления значения функции f4 (если она обычная)требуетсяпредварительновычислитьзначениефункцииf3.Функциональные вызовы, находящиеся на одном уровне, вычисляютсяобычно слева направо: сначала f2, затем f4. Вычисление вложенныхфункциональных вызовов завершается в соответствии с их иерархией, т.е.в первую очередь вычисляется самое вложенное обращение, а впоследнюю – самое внешнее. Особые функции могут нарушать этотстандартный порядок. Таким образом, если в приведённом примере всефункции f1, f2, f3 и f4 – обычные, то они вычисляются в следующемпорядке: f2, f3, f4, f1.1.2.

Базовый набор функцийБазовый набор включает 8 встроенных функций Лиспа. Первые трифункции являются обычными и реализуют основные операции надсписками: две функции для расщепления и одна для построения списка.Функция car от одного аргумента возвращает первый элементсписка, являющегося значением её аргумента.8Функция cdr возвращает хвост списка, являющегося значением еёединственного аргумента (хвостом, или остатком списка является списокбез своего первого элемента).Функция cons от двух аргументов с обращением(cons e1 e2)строит новый список, первым элементом которого является значениепервого аргумента е1, а хвостом – значение второго аргумента е2.

По сути,эта функция включает заданный элемент (значение выражения е1) вначало списка, являющегося значением е2.Приведём примеры работы этих функций. Будем считать, чтопеременная x имеет значение (GAMMA (15)), а переменная y имеетзначение (TETA):x => (GAMMA (15))y => (TETA)Тогда(car x) => GAMMA(cdr x) => ((15))(cdr y) => NIL(car (cdr x)) => (15)(car(car(cdr x))) => 15(cons x y) => ((GAMMA (15)) TETA)(cons y ()) => ((TETA))Заметим, что функция-конструктор cons (сокращение от англ.construct) реализует обратное действие по отношению к car и cdr.

Будемсчитать пока, что вторым аргументом cons должен быть список. Что жекасается области определения функций car и cdr, то, несмотря на то, чтов ряде диалектов Лиспа (например, в MuLisp) они работают и для атомов,будем считать, что значением их аргумента должен быть непустой список(это обеспечит их правильную работу во всех диалектах).Имена функций car и cdr происходят из самой ранней реализацииЛиспа, в которой использовались специальные регистры: адресный идекрементный, и имена были даны как сокращения названий Contents ofAddress Register и Contents of Decrement Register.

Современные диалектыЛиспа обычно допускают для функций car и cdr мнемоничныесинонимичные названия: first и rest соответственно.Следующие две функции базового набора являются предикатами, т.е.функциями, вычисляющими логическое значение T или NIL в зависимостиот наличия определённых свойств у своих аргументов. Обе эти функции –обычные.Функция atom вырабатывает значение T, если значением еёединственного аргумента является атом (числовой или символьный).

Впротивном случае возвращается NIL.9Функция-предикат eq (сокращение от англ. equal) проверяетсовпадение двух своих аргументов-атомов, вырабатывая значение T, когда:1) значением одного из аргументов является атом, и одновременно2) значения аргументов равны (идентичны).В ином случае значением функции eq является NIL. Будем считать, чтокогда оба аргумента функции eq – списки, её результат неопределён.Кроме того, поскольку одно и то же число может быть записано разнымиспособами (например, +6 и 6), функция eq корректно осуществляетсравнение только символьных атомов, а для проверки равенства чиселслужит обычно другая встроенная функция.Приведём примеры работы рассмотренных функций-предикатов,используя прежнее значение переменной x:x => (GAMMA (15))(atom NIL) => T(atom T) => T(atom x) => NIL(atom ()) => T(atom (cdr (cdr x))) => T(eq (atom 5) T) => T(eq (car x)(cdr x)) => NILШестая функция базового набора – особая функция quote, котораяв качестве своего значения выдаёт сам аргумент, не вычисляя его:(quote e) => eПо сути, эта функция блокирует вычисление своего аргумента (англ.