Введение в язык Лисп — различия между версиями

Материал из ТХАБ.РФ
Перейти к: навигация, поиск
(Новая страница: «'''Очень краткое введение в язык Лисп''' == Обращение к читателю.== Честно говоря, автор перв…»)
 
м (Обращение к читателю.)
 
Строка 1: Строка 1:
 
'''Очень краткое введение в язык Лисп'''
 
'''Очень краткое введение в язык Лисп'''
== Обращение к читателю.==
+
=== Обращение к читателю ===
 
Честно говоря, автор первоначально не планировал излагать в этом руководстве основы Лиспа. Однако, изучив литературу, изданную по Лиспу на русском языке, автор вынужден признать, что она весьма немногочисленна, а последняя книга по Лиспу издана почти 20 лет назад. Получается, что читатель, не знакомый с Лиспом, вынужден либо искать библиографические редкости, либо что-то качать из Интернета.
 
Честно говоря, автор первоначально не планировал излагать в этом руководстве основы Лиспа. Однако, изучив литературу, изданную по Лиспу на русском языке, автор вынужден признать, что она весьма немногочисленна, а последняя книга по Лиспу издана почти 20 лет назад. Получается, что читатель, не знакомый с Лиспом, вынужден либо искать библиографические редкости, либо что-то качать из Интернета.
  
Строка 10: Строка 10:
  
 
В заключение, автор просит извинения у искушенного читателя (если он сюда забредет!) за навязчивое объяснение элементарных вещей...
 
В заключение, автор просит извинения у искушенного читателя (если он сюда забредет!) за навязчивое объяснение элементарных вещей...
 +
 +
== Лисп-машина ==
 +
 +
Любой язык программирования предназначен для кодирования команд, которые выполняет компьютер. Результатом выполнения команд является все то, ради чего человек использует вычислительную технику (обработка текста, графика, звук, расчеты и т.д.). Процессор компьютера, как правило, умеет исполнять только элементарные команды. Поэтому команды, написанные человеком, обычно преобразуются (транслируются) в команды процессора. Возможен и другой подход, при котором программа на языке программирования не преобразуется в команды процессора, а поступает на вход программы-исполнителя (интерпретируется).
 +
 +
Именно так работает Лисп.
 +
 +
Будем далее называть программу, исполняющую команды Лиспа, Лисп-машиной. В ранних версиях Лиспа взаимодействие с пользователем было построено на принципе "запрос - ответ". В настоящее время Лисп-машина может быть реализована и как диалоговая, и как пакетная. Последнее означает, что программа Лисп-машины стартует, считывает команды из какого-либо источника (например, из файла), выполняет эти команды, и завершается. Для изучения языка Лисп важно то, что программа на языке Лисп состоит из команд, которые исполняются Лисп-машиной.
 +
 +
== Алфавит языка Лисп ==
 +
 +
Алфавит языка Лисп включает в себя заглавные и строчные латинские буквы, цифры и все специальные знаки, которые есть на клавиатуре. Буквы национальных языков традиционно в алфавит не входят, хотя нет никаких особых запретов на этот счет. В частности, в алфавит HomeLisp входят все русские строчные и заглавные буквы.
 +
 +
Среди всех символов алфавита выделяются следующие 6 символов, которые используются особым образом: это пробел, точка, открывающая и закрывающая КРУГЛЫЕ скобки, апостроф и двойная кавычка. Остальные символы, в общем, "равноправны".
 +
 +
== Атомы ==
 +
Из алфавитных символов Лиспа строятся все его конструкции. Простейшей из этих конструкций является атом. Атом - это произвольная строка алфавитных символов, за исключением:
 +
 +
отдельно стоящей точки
 +
 +
отдельно стоящей левой или правой скобок или групп левых или правых скобок (за исключением открывающей и закрывающей скобки, стоящих подряд)
 +
 +
отдельно стоящего пробела или группы пробелов
 +
 +
отдельно стоящего апострофа или двойной кавычки
 +
 +
Строка символов, изображающая атом, не может содержать пробела и круглых скобок, но может содержать точку. Кроме того, имеется ограничение на использование двойной кавычки внутри строки, изображающей атом.
 +
 +
Среди всех мыслимых атомов Лиспа сразу выделим четыре специальные группы атомов:
 +
 +
Десятичные числа - это атомы, которые представляют собой корректное изображение десятичного числа (целого или с дробной частью; в качестве разделителя целой и дробной части используется точка).
 +
 +
Шестнадцатеричные (битовые) константы представляются атомами вида: &Hnnnn, где nnnn - от одного до восьми символов из набора:
 +
 +
  0 1 2 3 4 5 6 7 8 9 A B C D E F a b c d e f 
 +
 +
Строки - это атомы, первый и последний символ которых - двойная кавычка. Между этими кавычками могут располагаться все символы алфавита (включая пробелы и скобки).
 +
 +
Атомы Nil и T. Эти атомы (особенно Nil) используются для разнообразных целей.
 +
 +
Ниже приводится таблица, иллюстрирующая правила построения атомов Лиспа.
 +
Строка Что это
 +
Abc Это обычный атом
 +
1Abc И это - тоже атом (хотя имя и начинается с цифры)
 +
Q$W И это - тоже атом (хотя имя и содержит знак доллара)
 +
123 Это атом - число
 +
-12.3 И это атом - число
 +
6.02E+23 И это атом - число
 +
A.A Это атом
 +
A A А это - не атом. Пробел в имени недопустим!
 +
A( И это - не атом. Скобки в имени недопустимы!
 +
A'B И это - не атом. Апостроф в имени недопустим!
 +
() Как ни странно, это - атом. Почему, будет ясно из дальнейшего.
 +
"Проба пера" Это - атом-строка. Внутри строки пробелы вполне допустимы
 +
"Проба "пера"" Это - не атом. Кавычки, стоящие внутри строки, при записи должны удваиваться.
 +
"Проба ""пера""" Теперь верно.
 +
"Проба 'пера'" Можно и так. Апостроф внутри строки - обычный символ.
 +
&HFFFFFF Это - атом-битовая шкала.
 +
&H1122334455667788 Это - просто атом (а не битовая шкала, как могло бы показаться; слишком много цифр)
 +
Автор надеется, что читатель вполне уяснил правила составления имен атомов.
 +
 +
== Точечные пары - "молекулы" Лиспа.
 +
Точечная пара - это конструкция следующего вида: левая скобка, ноль или более пробелов, атом или точечная пара, один или более пробелов, точка, один или более пробелов, атом или точечная пара, ноль или более пробелов, правая скобка. Другими словами, точечную пару можно представить следующим образом:
 +
 +
 +
(Нечто . Нечто)
 +
 +
 +
Здесь Нечто - это атом или точечная пара. Схема построения точечных пар иллюстрируется таблицей, в которой представлены все типы точечных пар, а также приведены ошибочные построения.
 +
Строка Что это
 +
(a . b) Это правильная точечная пара.
 +
((1 . 2) . b) Это тоже правильная точечная пара.
 +
((1 . 2) . (3 . 4)) И это тоже правильная точечная пара.
 +
(x . (y . z)) И это...
 +
(1 .) А вот это - не точечная пара. После точки до скобки должен стоять атом или точечная пара.
 +
( . 2) И это - тоже не точечная пара. После скобки до точки должен стоять атом или точечная пара.
 +
(1 . 2 Не точечная пара. Скобки должны быть сбалансированы.
 +
(name . "Анатолий") Это снова правильная точечная пара.
 +
Следует обратить внимание на то, что образование точечной пары - это бинарная операция. Запись вида:
 +
 +
( A . B . C)
 +
 +
бессмысленна (по крайней мере, в HomeLisp). Однако, две следующие записи представляют собой корректные точечные пары:
 +
 +
(A . (B . C))
 +
 +
((A . B) . C)
 +
В первой из приведенных выше точечных пар, пара (B . C) является составной частью пары (A . (B . C)). Будем говорить, что пара (B . C) вложена в пару (A . (B . C)).
 +
 +
Введем важное определение: часть точечной пары, расположенную между левой скобкой и точкой будем называть A-частью или А-компонентой. Соответственно, часть пары, расположенную между точкой и правой скобкой будем называть D-частью или D-компонентой.
 +
 +
Что можно сказать о конструкции (1.2)? Здесь точка не отделена пробелами от окружения, а является частью атома 1.2 . Несмотря на внешнее сходство с точечной парой, эта конструкция не соответствует данному выше формальному определению. Мы еще вернемся к этой конструкции при рассмотрении списков, и вскроем ее истиную природу!
 +
 +
== S-выражения. ==
 +
Атом или точечная пара называются S-выражением. В "мире Лиспа" нет ничего, кроме S-выражений; S-выражениями являются и программы и данные. В памяти компьютера все конструкции, кроме атомов, хранятся и обрабатываются в виде точечных пар.
 +
 +
== Cписки.==
 +
Точечная пара - универсальный способ построения агрегатов из атомов. Однако, точечная запись не очень удобна для человека: в ней слишком много скобок и точек. Было предложено правило, позволяющее записывать S-выражения практически без точек и с использованием значительно меньшего количества скобок.
 +
 +
Этих правил всего два:
 +
 +
Цепочки  . Nil  просто удаляем;
 +
 +
Цепочки  . (  удаляем вместе с соответствующей закрывающей скобкой.
 +
 +
Рассмотрим применение этих правил к записи S-выражения:
 +
 +
 +
(A . (B . (C . Nil)))
 +
 +
 +
На приведенном ниже рисунке показана последовательность упрощений:
 +
 +
 +
 +
Использование описанных правил упрощения привело к тому, что большая часть S-выражений в Лиспе записывается в чисто скобочной нотации и называется списками.
 +
 +
Можно дать такое определение списка. Список - это такая точечная пара, в записи которой после применения правил упрощения не остается точек.
 +
 +
Вот эквивалентное определение. Список - эта точечная пара (состоящая, возможно, из атомов и других точечных пар), удовлетворяющая условию: D-частью всех вложенных точечных пар может быть либо точечная пара, либо специальный атом Nil.
 +
 +
Можно сказать, что список - это конструкция следующего вида: левая скобка, ноль или более пробелов, группа из нуля или более атомов или списков, разделенная цепочками из одного или более пробелов, ноль или более пробелов и правая скобка.
 +
 +
Это последнее определение обычно и приводится в курсах Лиспа. Оно, разумеется, правильно, но не следует забывать, что все S-выражения хранятся в памяти компьютера в виде точечных пар. Точечная запись "незримо присутствует" при работе Лисп-системы (а иногда и неожиданно проявляется; такой пример будет приведен ниже).
 +
 +
Еще раз следует отметить, что всякий список может быть представлен в точечной записи, но не всякая точечная пара является списком. В ряде случаев правила упрощения, приведенные выше, могут сделать точечную запись даже менее наглядной. Вот пример на эту тему: точечная пара ((a . b) . (c . d)) после применения правил упрощения превращается в малонаглядную запись: ((a . b) c . d). Исходная запись этой точечной пары нагляднее упрощенной. К счастью, такие конструкции в реальных программах почти не встречаются.
 +
 +
Для представления списка в точечной записи существует достаточно простое правило. В соответствии с последним определением, любой список может быть представлен в виде:
 +
 +
 +
( Нечто-1    Нечто-2    Нечто-3    ...)
 +
 +
 +
где Нечто - атом или список, а многоточие означает повторение. Легко убедиться, что эквивалентной точечной формой такого представления будет:
 +
 +
 +
( Нечто-1    .  ( Нечто-2    .  ( Нечто-3    .    ... . Nil) . Nil) . Nil )
 +
 +
 +
Далее подобному преобразованию следует подвергнуть каждое "Нечто", при условии, что это "Нечто" - список, а не атом. Ниже приводится последовательность преобразований позволяющая получить для списка ((A B) (C D) E F) эквивалентную точечную форму. При этом красным цветом выделены добавляемые точки и скобки на очередном шаге преобразования.
 +
 +
 +
 +
 +
Вот несколько примеров списков в точечной и списковой записи:
 +
 +
Списковая запись Точечная запись
 +
(A) (A . Nil)
 +
(A B C) (A . (B . (C . Nil)))
 +
(A (B C) (E F)) (A . ((B . (C . Nil)) . ((E . (F . Nil)) . Nil)))
 +
Снова вернемся к рассмотрению конструкции (1.2). Она полностью соответствует определению списка из одного элемента - атома 1.2 (и, следовательно, является на самом деле точечной парой (1.2 . Nil) !).
 +
 +
В заключение дадим еще три важных определения.
 +
 +
Конструкция () соответствует определению списка. Такой список называется пустым списком. В Лиспе принято считать, что пустой список эквивалентен атому Nil.
 +
 +
Первый элемент списка (он может, в свою очередь, быть атомом или списком) называется головой списка.
 +
 +
Часть списка, за исключением головы называется хвостом списка. Если кроме головы список не содержит других элементов, то хвост такого списка есть пустой список.
 +
 +
== Внутреннее представление списков.==
 +
Оперативная память, в которой хранятся S-выражения, обычно делится на две больших области: список объектов и область списочных ячеек.
 +
 +
В списке объектов хранятся атомы. Каждый атом занимает блок памяти переменного размера. В этом блоке хранится символьное изображение атома и ряд его дополнительных характеристик.
 +
 +
Область списочных ячеек состоит из блоков фиксированного размера. Каждая списочная ячейка хранит два адреса, которые по историческим причинам называются А-указатель и D-указатель. Эти адреса могут указывать как на атомы (т.е. хранить адреса областей из списка объектов), так и на другие списочные ячейки.
 +
 +
Для наглядного изображения списков существуют уже устоявшаяся традиция. Списочная ячейка предствляется прямоугольником, разделеным вертикальной линией на две равные части. В левой части хранится A-указатель, в правой - D-указатель. Атомы изображаются символами (буквами или цифрами). Теперь можно сказать, что точечная пара (A . B) - это одна списочная ячейка, в A-указателе которой находится адрес атома A, а в D-указателе - адрес атома B.
 +
 +
Графически точечную пару изображают так:
 +
 +
 +
или так:
 +
 +
А как можно представить графически список (A)? Поскольку список (A) есть точечная пара (A . Nil), то графическое изображение строится сразу:
 +
 +
 +
Не представляет труда построить графическое изображение и более сложных списков. Так, например, список (A B C D) устроен так:
 +
 +
 +
 +
Полезно соотнести это представление с точечной записью списка (A B C D), которое имеет вид (A . (B . (C . (D . Nil)))). Вот еще один пример внутреннего представленния списка более сложной структуры. Список ((A B) (C D)) хранится в памяти в следующем виде:
 +
 +
 +
 +
Автор надеется, что читатель уяснил преимущества графического представления списочных структур. Надо заметить, что с помощью прямоугольников и стрелок можно изобразить S-выражения, которые невозможно записать в скобочной нотации. Речь идет о циклических списках. Вот пример такого выражения:
 +
 +
 +
 +
Как видно из рисунка, S-выражение состоит из двух списочных ячеек и двух атомов. В D-указателе второй списковой ячейки содержится указатель на первую списковую ячейку. Записать это S-выражение в скобочной записи нельзя, но его можно создать (с помощью функций RPLACA и RPLACD; автор счел нецелесообразным описывать эти функции в элементарном введении в Лисп...)
 +
 +
Говоря о внутреннем представлении S-выражений, следует добавить, что каждый атом уникален. Даже если в каком-либо списке атом A встречается многократно, в списке объектов он представлен в единственном экземпляре (т.е. во всех списочных ячейках из которых исходят стрелки, указывающие на атом A, будет содержаться один и тот же адрес).
 +
 +
В обращении к читателю было сказано, что синтаксис S-выражений на первых порах проще всего представлять, как формальную знаковую систему. Начиная с этого момента, читатель может смотреть на S-выражения не как на формальные конструкции из букв и скобок, а как на реальные структуры данных, хранящиеся в памяти компьютера.
 +
 +
== Взаимодействие с Лисп-машиной - вычисление значений.
 +
Лисп-машина читает входящие команды, имеющие вид S-выражений, вычисляет значение каждого из введеных выражений, и выводит результат. Значением S-выражения является, разумеется, тоже S-выражение. (Кроме S-выражений в мире Лиспа ничего нет!) Побочным эффектом вычисления входящих S-выражений является изменение состояния Лисп-машины.
 +
 +
Вычисление значения выполняется по следующим формальным правилам:
 +
 +
Если входное S-выражение является атомом то:
 +
 +
- для атомов T и Nil их значением является сами атомы T и Nil соответственно;
 +
 +
- для атомов, представляющих корректное изображение числа, строки или битовой шкалы значением также является сам атом. Такие атомы (Nil, T, числа, строки и битовые шкалы) будем далее называть самоопределенными.
 +
 +
- все прочие атомы могут иметь значением S-выражение, которое было присвоено атому вызовом функций SET, SETQ или CSETQ. Если атому не было присвоено значения перечисленными выше функциями, то такой атом не имеет значения.
 +
 +
Если входное S-выражение является списком, и голова списка представляет собой атом, то этот атом рассматривается как имя функции, а оставшаяся часть списка (хвост списка) - как список параметров этой функции. Если соответствующая функция существует в системе, а список параметров корректен, то функция вычисляется. Результат вычисления и есть значение исходного S-выражения. Будем называть функцию, задаваемую головой S-выражения, ведущей функцией S-выражения.
 +
 +
Если входное S-выражение является списком, но голова списка представляет собой список, то этот список рассматривается как т.н. лямбда-выражение. Лямбда выражение задает безымянную функцию. Хвост исходного S-выражения задает список параметров этой безымянной функции. Разумеется, лямбда-выражение составляется по строгим правилам, которые будут описаны ниже. Если голова списка не является корректным лямбда-выражением, то вычисление завершается ошибкой.
 +
 +
Все остальные S-выражения значений не имеют. Попытка вычисления таких выражений вызывает ошибку.
 +
 +
В частности, если головой списка является число, строка, битовая шкала или список (не являющийся лямбда-выражением), то ведущая функция заведомо не существует и не может быть вычислена.
 +
 +
S-выражения, которые имеют значения, называются формами.
 +
 +
== Вычисление значений функций Лиспа.==
 +
 +
Что означает "вычислить функцию"? Это означает по S-выражениям - параметрам получить результирующее S-выражение. Процесс вычисления зависит от типа функции. А функции бывают следующих типов:
 +
 +
Встроенные в ядро Лиспа функции, реализованные в машинных кодах (или на языке реализации ядра Лиспа). Будем далее называть такие функции функциями типа SUBR (от Subroutine - подпрограмма);
 +
 +
Реализованные на языке Лисп. Будем далее называть такие функции функциями типа EXPR (от Expression - выражение);
 +
 +
Вызовы функций типа SUBR и типа EXPR не отличаются по форме и выглядят следующим образом:
 +
 +
 +
(Функция Аргумент1 Аргумент2 ... Аргументn)
 +
Многоточие здесь означает повторение. Каждый из аргументов может быть атомом или списоком. Функция "знает" сколько аргументов ей требуется. Если количество аргументов оказывается больше или меньше необходимого, возникает ошибка вычисления функции и выдается соответствующее сообщение. Бывают функции с переменным числом аргументов, а бывают и функции без аргументов. Обращение к такой функции выглядит так:
 +
 +
(Функция)
 +
В математике широко применяется конструкция "функция от функции". Например, запись F(G(x)) означает вычисление G(x), а затем вычисление функции F, с аргументом, равным G(x). Как записать эту конструкцию в обозначениях Лиспа? Очевидно, что запись:
 +
 +
(F G X)
 +
абсолютно неверна. Эта запись означает вычисление функции F с двумя аргументами: первый - G второй X! Более логично было бы записать конструкцию F(G(x)) в виде:
 +
 +
(F (G X))
 +
 +
Эта запись логична хотя бы потому, что здесь у функции F, как и положено один аргумент - список (G X). Если Лисп-машина, прежде чем вычислять значение функции F, сначала вычислит значение функции G (т.е. значение выражения (G X)) и заменит в выражении (F (G X)) список (G X) этим значением, то последующее вычисление функции F даст нужный результат.
 +
 +
Именно так Лисп-машина и поступает!
 +
 +
Вычисление выражения общего вида:
 +
 +
(F А1 А2 ... Аn)
 +
выполняется следующим образом. Вычисляется каждый аргумент. Если аргумент - атом, берется значение атома; если аргумент список - вычисляется соответствующая функция. После чего в исходном списке каждый аргумент заменяется своим значением. На заключительном этапе вычисляется значение функции F. Естественно, что в случае, когда какой-либо из аргументов является вызовом функции, то описанный выше процесс применяется к его вычислению точно так же.
 +
 +
Рассмотрим, например, вычисление следующего S-выражения:
 +
 +
 +
(F (G 1 2 (H "q" "p")) (I 12 -1))
 +
Вычисление будет проходить через следующие этапы:
 +
 +
Вычисляется первый аргумент функции F - S-выражение (G 1 2 (H "q" "P")). Это выражение, в свою очередь, является вызовом функции G с аргументами 1 2 и (H "q" "P"). Значением атома 1 является сам атом 1, а значением атома 2 является сам атом 2. А вот значение S-выражения (H "q" "p") нужно вычислять.
 +
 +
S-выражение (H "q" "p") является вызовом функции H с двумя аргументами "q" и "p". Значением атома "q" является сам атом "q", а значением атома "p" является сам атом "p". Далее вычисляется значение функции H с двумя аргументами "p" и "q". Предположим, что это значение равно S-выражению Рез_Н. Таким образом, первый аргумент исходного вызова функции F принимает вид (G 1 2 Рез_Н). Это выражение вычисляется, предположим, что результат вычисления равен Рез_G.
 +
 +
Далее исходное выражение приобретает вид (F Рез_G (I 12 -1)). Первый аргумент вызова функции F вычислен. Вычисляется второй аргумент. Значение второго аргумента равно значению функции I с двумя аргументами: 1 и 2. Предположим, что это значение равно Рез_I.
 +
 +
Теперь исходное выражение приобрело вид: (F Рез_G Рез_I). Вычисляется значение функции F с заданными аргументами. Это значение и есть значение исходного S-выражения (F (G 1 2 Рез_Н) (I 12 -1))
 +
 +
== Проблема вычисляемых аргументов. Классификация функций Лиспа.==
 +
Но как быть в том случае, когда некоторой функции требуется не значения аргументов, а сами аргументы? Предположим, есть функция, возвращающая сумму элементов числового списка. Пусть имя этой функции - SUMLIST. Тогда вызов (SUMLIST (1 2 3 4 5)) должен вернуть атом 15. Однако, в соответствии с написанным выше, Лисп сделает попытку вычислить значение списка (1 2 3 4 5), что, в свою очередь, повлечет за собой попытку вычисления значения функции 1 со списком аргументов (2 3 4 5). Это, естественно, вызовет ошибку.
 +
 +
Получается, что никакой функции Лиспа принципиально нельзя передать параметр вида (1 2 3 4 5)?
 +
 +
Разумеется, это не так. Отмеченная проблема решается в Лиспе двумя способами: введением специального класса функций, которые не вычисляют свои аргументы, а также выборочным использованием функции QUOTE, о чем будет сказано ниже.
 +
 +
В Лиспе есть класс встроенных функций, которые не вычисляют значения своих аргументов, а используют сами аргументы. Встроенные функции, вычисляющие значения аргументов, называются функциями класса SUBR, а встроенные функции, НЕ вычисляющие значения некоторых или всех аргументов, называются функциями класса FSUBR.
 +
 +
Соответственно, функции, написанные на Лиспе, тоже могут не вычислять значения своих аргументов. Функции, написанные на Лиспе и вычисляющие значения аргументов, называются функциями класса EXPR, а функции, написанные на Лиспе и НЕ вычисляющие значения некоторых или всех аргументов, называются функциями класса FEXPR.
 +
 +
Чтобы классификация функций Лиспа стала полностью завершенной, следует добавить, что существует еще один класс функций - MACRO. Эти функции ближе всего к функциям FEXPR, - они тоже не вычисляют значения своих аргументов. Однако вычисление функций типа MACRO имеет особенность, которая позволяет выделить эти функции в отдельный класс (он будет рассмотрен ниже).
 +
 +
В целом, классификация функций Лиспа может быть изображена следующим рисунком:
 +
 +
 +
 +
== Диалог с Лисп-машиной.==
 +
Большинство Лисп-машин работают по "телетайпному" принципу: пользователь вводит S-выражение, Лисп-вычисляет и выводит ответ (тоже, естественно, S-выражение). Простейшим примером такого диалога может служить консольное окно Windows (или UNIX/LINUX). В HomeLisp пользователь вводит S-выражение в область ввода и получает ответ в области вывода. Подробности диалога описаны в здесь. Введенное выражение дублируется в области вывода, поэтому область вывода содержит полный протокол диалога с пользователем.
 +
 +
Важно отметить следующее: если вычисление введенного завершено с ошибкой, то HomeLisp возвращает в качестве результата специальный атом ERRSTATE (ведь результат должен быть тоже S-выражением!). Если вычисления результата заняли слишком много времени, происходит принудительная остановка Лисп-машины и в качестве результата возвращается специальный атом BRKSTATE
 +
 +
Кроме того, некоторые функции могут что-то выводить в область вывода. Эта информация выводится перед результирующим S-выражением.
 +
 +
Ниже приводится пример взаимодействия с Лисп-машиной. Ответ Лисп-машины предваряется набором символов "==>".
 +
 +
_ver
 +
 +
==> "HomeLisp Вер. 1.11.1 (Файфель Б.Л.)"
 +
 +
Здесь пользователь ввел имя атома _ver (версия ядра) и получил ответ.
 +
 +
== Блокировка вычисления - функция QUOTE.==
 +
Функция QUOTE принимает ровно один аргумент и возвращает S-выражение, совпадающее с аргументом. Основное назначение функции QUOTE - выборочная блокировка вычисления аргументов при вызове функций класса SUBR и EXPR.
 +
 +
Понятно, что сама функция QUOTE должна принадлежать к классу FSUBR, - она не вычисляет значение своего аргумента, а возвращает сам аргумент.
 +
 +
Выше был приведен пример функции SUMLIST, вычисляющей сумму элементов списка, заданного единственным аргументом. Если функция SUMLIST принадлежит к классу EXPR или SUBR, то попытка вычислить (SUMLIST (1 2 3 4 5)) вызовет ошибку. Ведь сначала будет предпринята попытка вычислить значение списка (1 2 3 4 5), а это S-выражение не имеет значения. А вот вызов (SUMLIST (QUOTE (1 2 3 4 5))) не вызовет ошибки, ведь сначала будет вычислено значение (QUOTE (1 2 3 4 5)), результат вычисления равен (1 2 3 4 5). Этот результат без повторного вычисления будет передан на вход функции SUMLIST, которая вычислит сумму.
 +
 +
Ниже приводится пример использования функции QUOTE. Предполагается, что функция SUMLIST имеется в системе, принадлежит к классу EXPR или SUBR (т.е. вычисляет свои аргументы).
 +
 +
(sumlist (1 2 3))
 +
 +
Не найдена функция 1
 +
==> ERRSTATE
 +
 +
(sumlist (quote (1 2 3)))
 +
 +
==> 6
 +
 +
По уже укоренившейся традиции вместо того, чтобы писать:
 +
 +
== (QUOTE Нечто) ==
 +
допустимо писать:
 +
'Нечто
 +
 +
Далее в этом разделе будет употребляться именно такая запись. Следует обратить внимание на то, что скобки перед апострофом не ставятся.
 +
 +
На жаргоне лисперов, употребление апострофа называется квотированием. Квотировать выражение - значит поставить перед ним апостроф. Понятно, что квотировать аргументы функций класса SUBR/EXPR необходимо только в случае, когда требуется блокировать вычисление значения. Когда же аргументом является самоопределенный атом, то квотирование не требуется (хотя и не приведет к ошибке, а только чуть удлинит вычисления).
 +
 +
== Присвоение значений атомам. Функции SET, SETQ и CSETQ.==
  
 
== Ссылки ==
 
== Ссылки ==

Текущая версия на 22:29, 3 июня 2020

Очень краткое введение в язык Лисп

Обращение к читателю

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

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

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

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

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

Лисп-машина

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

Именно так работает Лисп.

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

Алфавит языка Лисп

Алфавит языка Лисп включает в себя заглавные и строчные латинские буквы, цифры и все специальные знаки, которые есть на клавиатуре. Буквы национальных языков традиционно в алфавит не входят, хотя нет никаких особых запретов на этот счет. В частности, в алфавит HomeLisp входят все русские строчные и заглавные буквы.

Среди всех символов алфавита выделяются следующие 6 символов, которые используются особым образом: это пробел, точка, открывающая и закрывающая КРУГЛЫЕ скобки, апостроф и двойная кавычка. Остальные символы, в общем, "равноправны".

Атомы

Из алфавитных символов Лиспа строятся все его конструкции. Простейшей из этих конструкций является атом. Атом - это произвольная строка алфавитных символов, за исключением:

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

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

Среди всех мыслимых атомов Лиспа сразу выделим четыре специальные группы атомов:

Десятичные числа - это атомы, которые представляют собой корректное изображение десятичного числа (целого или с дробной частью; в качестве разделителя целой и дробной части используется точка).
Шестнадцатеричные (битовые) константы представляются атомами вида: &Hnnnn, где nnnn - от одного до восьми символов из набора:
 0 1 2 3 4 5 6 7 8 9 A B C D E F a b c d e f  
Строки - это атомы, первый и последний символ которых - двойная кавычка. Между этими кавычками могут располагаться все символы алфавита (включая пробелы и скобки).
Атомы Nil и T. Эти атомы (особенно Nil) используются для разнообразных целей.

Ниже приводится таблица, иллюстрирующая правила построения атомов Лиспа. Строка Что это Abc Это обычный атом 1Abc И это - тоже атом (хотя имя и начинается с цифры) Q$W И это - тоже атом (хотя имя и содержит знак доллара) 123 Это атом - число -12.3 И это атом - число 6.02E+23 И это атом - число A.A Это атом A A А это - не атом. Пробел в имени недопустим! A( И это - не атом. Скобки в имени недопустимы! A'B И это - не атом. Апостроф в имени недопустим! () Как ни странно, это - атом. Почему, будет ясно из дальнейшего. "Проба пера" Это - атом-строка. Внутри строки пробелы вполне допустимы "Проба "пера"" Это - не атом. Кавычки, стоящие внутри строки, при записи должны удваиваться. "Проба ""пера""" Теперь верно. "Проба 'пера'" Можно и так. Апостроф внутри строки - обычный символ. &HFFFFFF Это - атом-битовая шкала. &H1122334455667788 Это - просто атом (а не битовая шкала, как могло бы показаться; слишком много цифр) Автор надеется, что читатель вполне уяснил правила составления имен атомов.

== Точечные пары - "молекулы" Лиспа. Точечная пара - это конструкция следующего вида: левая скобка, ноль или более пробелов, атом или точечная пара, один или более пробелов, точка, один или более пробелов, атом или точечная пара, ноль или более пробелов, правая скобка. Другими словами, точечную пару можно представить следующим образом:


(Нечто . Нечто)


Здесь Нечто - это атом или точечная пара. Схема построения точечных пар иллюстрируется таблицей, в которой представлены все типы точечных пар, а также приведены ошибочные построения. Строка Что это (a . b) Это правильная точечная пара. ((1 . 2) . b) Это тоже правильная точечная пара. ((1 . 2) . (3 . 4)) И это тоже правильная точечная пара. (x . (y . z)) И это... (1 .) А вот это - не точечная пара. После точки до скобки должен стоять атом или точечная пара. ( . 2) И это - тоже не точечная пара. После скобки до точки должен стоять атом или точечная пара. (1 . 2 Не точечная пара. Скобки должны быть сбалансированы. (name . "Анатолий") Это снова правильная точечная пара. Следует обратить внимание на то, что образование точечной пары - это бинарная операция. Запись вида:

( A . B . C)

бессмысленна (по крайней мере, в HomeLisp). Однако, две следующие записи представляют собой корректные точечные пары:

(A . (B . C))

((A . B) . C) В первой из приведенных выше точечных пар, пара (B . C) является составной частью пары (A . (B . C)). Будем говорить, что пара (B . C) вложена в пару (A . (B . C)).

Введем важное определение: часть точечной пары, расположенную между левой скобкой и точкой будем называть A-частью или А-компонентой. Соответственно, часть пары, расположенную между точкой и правой скобкой будем называть D-частью или D-компонентой.

Что можно сказать о конструкции (1.2)? Здесь точка не отделена пробелами от окружения, а является частью атома 1.2 . Несмотря на внешнее сходство с точечной парой, эта конструкция не соответствует данному выше формальному определению. Мы еще вернемся к этой конструкции при рассмотрении списков, и вскроем ее истиную природу!

S-выражения.

Атом или точечная пара называются S-выражением. В "мире Лиспа" нет ничего, кроме S-выражений; S-выражениями являются и программы и данные. В памяти компьютера все конструкции, кроме атомов, хранятся и обрабатываются в виде точечных пар.

Cписки.

Точечная пара - универсальный способ построения агрегатов из атомов. Однако, точечная запись не очень удобна для человека: в ней слишком много скобок и точек. Было предложено правило, позволяющее записывать S-выражения практически без точек и с использованием значительно меньшего количества скобок.

Этих правил всего два:

Цепочки  . Nil  просто удаляем;
Цепочки  . (  удаляем вместе с соответствующей закрывающей скобкой.

Рассмотрим применение этих правил к записи S-выражения:


(A . (B . (C . Nil)))


На приведенном ниже рисунке показана последовательность упрощений:


Использование описанных правил упрощения привело к тому, что большая часть S-выражений в Лиспе записывается в чисто скобочной нотации и называется списками.

Можно дать такое определение списка. Список - это такая точечная пара, в записи которой после применения правил упрощения не остается точек.

Вот эквивалентное определение. Список - эта точечная пара (состоящая, возможно, из атомов и других точечных пар), удовлетворяющая условию: D-частью всех вложенных точечных пар может быть либо точечная пара, либо специальный атом Nil.

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

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

Еще раз следует отметить, что всякий список может быть представлен в точечной записи, но не всякая точечная пара является списком. В ряде случаев правила упрощения, приведенные выше, могут сделать точечную запись даже менее наглядной. Вот пример на эту тему: точечная пара ((a . b) . (c . d)) после применения правил упрощения превращается в малонаглядную запись: ((a . b) c . d). Исходная запись этой точечной пары нагляднее упрощенной. К счастью, такие конструкции в реальных программах почти не встречаются.

Для представления списка в точечной записи существует достаточно простое правило. В соответствии с последним определением, любой список может быть представлен в виде:


( Нечто-1 Нечто-2 Нечто-3 ...)


где Нечто - атом или список, а многоточие означает повторение. Легко убедиться, что эквивалентной точечной формой такого представления будет:


( Нечто-1 . ( Нечто-2 . ( Нечто-3 . ... . Nil) . Nil) . Nil )


Далее подобному преобразованию следует подвергнуть каждое "Нечто", при условии, что это "Нечто" - список, а не атом. Ниже приводится последовательность преобразований позволяющая получить для списка ((A B) (C D) E F) эквивалентную точечную форму. При этом красным цветом выделены добавляемые точки и скобки на очередном шаге преобразования.



Вот несколько примеров списков в точечной и списковой записи:

Списковая запись Точечная запись (A) (A . Nil) (A B C) (A . (B . (C . Nil))) (A (B C) (E F)) (A . ((B . (C . Nil)) . ((E . (F . Nil)) . Nil))) Снова вернемся к рассмотрению конструкции (1.2). Она полностью соответствует определению списка из одного элемента - атома 1.2 (и, следовательно, является на самом деле точечной парой (1.2 . Nil) !).

В заключение дадим еще три важных определения.

Конструкция () соответствует определению списка. Такой список называется пустым списком. В Лиспе принято считать, что пустой список эквивалентен атому Nil.
Первый элемент списка (он может, в свою очередь, быть атомом или списком) называется головой списка.
Часть списка, за исключением головы называется хвостом списка. Если кроме головы список не содержит других элементов, то хвост такого списка есть пустой список.

Внутреннее представление списков.

Оперативная память, в которой хранятся S-выражения, обычно делится на две больших области: список объектов и область списочных ячеек.

В списке объектов хранятся атомы. Каждый атом занимает блок памяти переменного размера. В этом блоке хранится символьное изображение атома и ряд его дополнительных характеристик.

Область списочных ячеек состоит из блоков фиксированного размера. Каждая списочная ячейка хранит два адреса, которые по историческим причинам называются А-указатель и D-указатель. Эти адреса могут указывать как на атомы (т.е. хранить адреса областей из списка объектов), так и на другие списочные ячейки.

Для наглядного изображения списков существуют уже устоявшаяся традиция. Списочная ячейка предствляется прямоугольником, разделеным вертикальной линией на две равные части. В левой части хранится A-указатель, в правой - D-указатель. Атомы изображаются символами (буквами или цифрами). Теперь можно сказать, что точечная пара (A . B) - это одна списочная ячейка, в A-указателе которой находится адрес атома A, а в D-указателе - адрес атома B.

Графически точечную пару изображают так:


или так:

А как можно представить графически список (A)? Поскольку список (A) есть точечная пара (A . Nil), то графическое изображение строится сразу:


Не представляет труда построить графическое изображение и более сложных списков. Так, например, список (A B C D) устроен так:


Полезно соотнести это представление с точечной записью списка (A B C D), которое имеет вид (A . (B . (C . (D . Nil)))). Вот еще один пример внутреннего представленния списка более сложной структуры. Список ((A B) (C D)) хранится в памяти в следующем виде:


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


Как видно из рисунка, S-выражение состоит из двух списочных ячеек и двух атомов. В D-указателе второй списковой ячейки содержится указатель на первую списковую ячейку. Записать это S-выражение в скобочной записи нельзя, но его можно создать (с помощью функций RPLACA и RPLACD; автор счел нецелесообразным описывать эти функции в элементарном введении в Лисп...)

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

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

== Взаимодействие с Лисп-машиной - вычисление значений. Лисп-машина читает входящие команды, имеющие вид S-выражений, вычисляет значение каждого из введеных выражений, и выводит результат. Значением S-выражения является, разумеется, тоже S-выражение. (Кроме S-выражений в мире Лиспа ничего нет!) Побочным эффектом вычисления входящих S-выражений является изменение состояния Лисп-машины.

Вычисление значения выполняется по следующим формальным правилам:

Если входное S-выражение является атомом то:

- для атомов T и Nil их значением является сами атомы T и Nil соответственно;

- для атомов, представляющих корректное изображение числа, строки или битовой шкалы значением также является сам атом. Такие атомы (Nil, T, числа, строки и битовые шкалы) будем далее называть самоопределенными.

- все прочие атомы могут иметь значением S-выражение, которое было присвоено атому вызовом функций SET, SETQ или CSETQ. Если атому не было присвоено значения перечисленными выше функциями, то такой атом не имеет значения.

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

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

S-выражения, которые имеют значения, называются формами.

Вычисление значений функций Лиспа.

Что означает "вычислить функцию"? Это означает по S-выражениям - параметрам получить результирующее S-выражение. Процесс вычисления зависит от типа функции. А функции бывают следующих типов:

Встроенные в ядро Лиспа функции, реализованные в машинных кодах (или на языке реализации ядра Лиспа). Будем далее называть такие функции функциями типа SUBR (от Subroutine - подпрограмма);
Реализованные на языке Лисп. Будем далее называть такие функции функциями типа EXPR (от Expression - выражение);

Вызовы функций типа SUBR и типа EXPR не отличаются по форме и выглядят следующим образом:


(Функция Аргумент1 Аргумент2 ... Аргументn) Многоточие здесь означает повторение. Каждый из аргументов может быть атомом или списоком. Функция "знает" сколько аргументов ей требуется. Если количество аргументов оказывается больше или меньше необходимого, возникает ошибка вычисления функции и выдается соответствующее сообщение. Бывают функции с переменным числом аргументов, а бывают и функции без аргументов. Обращение к такой функции выглядит так:

(Функция) В математике широко применяется конструкция "функция от функции". Например, запись F(G(x)) означает вычисление G(x), а затем вычисление функции F, с аргументом, равным G(x). Как записать эту конструкцию в обозначениях Лиспа? Очевидно, что запись:

(F G X) абсолютно неверна. Эта запись означает вычисление функции F с двумя аргументами: первый - G второй X! Более логично было бы записать конструкцию F(G(x)) в виде:

(F (G X))

Эта запись логична хотя бы потому, что здесь у функции F, как и положено один аргумент - список (G X). Если Лисп-машина, прежде чем вычислять значение функции F, сначала вычислит значение функции G (т.е. значение выражения (G X)) и заменит в выражении (F (G X)) список (G X) этим значением, то последующее вычисление функции F даст нужный результат.

Именно так Лисп-машина и поступает!

Вычисление выражения общего вида:

(F А1 А2 ... Аn) выполняется следующим образом. Вычисляется каждый аргумент. Если аргумент - атом, берется значение атома; если аргумент список - вычисляется соответствующая функция. После чего в исходном списке каждый аргумент заменяется своим значением. На заключительном этапе вычисляется значение функции F. Естественно, что в случае, когда какой-либо из аргументов является вызовом функции, то описанный выше процесс применяется к его вычислению точно так же.

Рассмотрим, например, вычисление следующего S-выражения:


(F (G 1 2 (H "q" "p")) (I 12 -1)) Вычисление будет проходить через следующие этапы:

Вычисляется первый аргумент функции F - S-выражение (G 1 2 (H "q" "P")). Это выражение, в свою очередь, является вызовом функции G с аргументами 1 2 и (H "q" "P"). Значением атома 1 является сам атом 1, а значением атома 2 является сам атом 2. А вот значение S-выражения (H "q" "p") нужно вычислять.
S-выражение (H "q" "p") является вызовом функции H с двумя аргументами "q" и "p". Значением атома "q" является сам атом "q", а значением атома "p" является сам атом "p". Далее вычисляется значение функции H с двумя аргументами "p" и "q". Предположим, что это значение равно S-выражению Рез_Н. Таким образом, первый аргумент исходного вызова функции F принимает вид (G 1 2 Рез_Н). Это выражение вычисляется, предположим, что результат вычисления равен Рез_G.
Далее исходное выражение приобретает вид (F Рез_G (I 12 -1)). Первый аргумент вызова функции F вычислен. Вычисляется второй аргумент. Значение второго аргумента равно значению функции I с двумя аргументами: 1 и 2. Предположим, что это значение равно Рез_I.
Теперь исходное выражение приобрело вид: (F Рез_G Рез_I). Вычисляется значение функции F с заданными аргументами. Это значение и есть значение исходного S-выражения (F (G 1 2 Рез_Н) (I 12 -1))

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

Но как быть в том случае, когда некоторой функции требуется не значения аргументов, а сами аргументы? Предположим, есть функция, возвращающая сумму элементов числового списка. Пусть имя этой функции - SUMLIST. Тогда вызов (SUMLIST (1 2 3 4 5)) должен вернуть атом 15. Однако, в соответствии с написанным выше, Лисп сделает попытку вычислить значение списка (1 2 3 4 5), что, в свою очередь, повлечет за собой попытку вычисления значения функции 1 со списком аргументов (2 3 4 5). Это, естественно, вызовет ошибку.

Получается, что никакой функции Лиспа принципиально нельзя передать параметр вида (1 2 3 4 5)?

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

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

Соответственно, функции, написанные на Лиспе, тоже могут не вычислять значения своих аргументов. Функции, написанные на Лиспе и вычисляющие значения аргументов, называются функциями класса EXPR, а функции, написанные на Лиспе и НЕ вычисляющие значения некоторых или всех аргументов, называются функциями класса FEXPR.

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

В целом, классификация функций Лиспа может быть изображена следующим рисунком:


Диалог с Лисп-машиной.

Большинство Лисп-машин работают по "телетайпному" принципу: пользователь вводит S-выражение, Лисп-вычисляет и выводит ответ (тоже, естественно, S-выражение). Простейшим примером такого диалога может служить консольное окно Windows (или UNIX/LINUX). В HomeLisp пользователь вводит S-выражение в область ввода и получает ответ в области вывода. Подробности диалога описаны в здесь. Введенное выражение дублируется в области вывода, поэтому область вывода содержит полный протокол диалога с пользователем.

Важно отметить следующее: если вычисление введенного завершено с ошибкой, то HomeLisp возвращает в качестве результата специальный атом ERRSTATE (ведь результат должен быть тоже S-выражением!). Если вычисления результата заняли слишком много времени, происходит принудительная остановка Лисп-машины и в качестве результата возвращается специальный атом BRKSTATE

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

Ниже приводится пример взаимодействия с Лисп-машиной. Ответ Лисп-машины предваряется набором символов "==>".

_ver

==> "HomeLisp Вер. 1.11.1 (Файфель Б.Л.)"

Здесь пользователь ввел имя атома _ver (версия ядра) и получил ответ.

Блокировка вычисления - функция QUOTE.

Функция QUOTE принимает ровно один аргумент и возвращает S-выражение, совпадающее с аргументом. Основное назначение функции QUOTE - выборочная блокировка вычисления аргументов при вызове функций класса SUBR и EXPR.

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

Выше был приведен пример функции SUMLIST, вычисляющей сумму элементов списка, заданного единственным аргументом. Если функция SUMLIST принадлежит к классу EXPR или SUBR, то попытка вычислить (SUMLIST (1 2 3 4 5)) вызовет ошибку. Ведь сначала будет предпринята попытка вычислить значение списка (1 2 3 4 5), а это S-выражение не имеет значения. А вот вызов (SUMLIST (QUOTE (1 2 3 4 5))) не вызовет ошибки, ведь сначала будет вычислено значение (QUOTE (1 2 3 4 5)), результат вычисления равен (1 2 3 4 5). Этот результат без повторного вычисления будет передан на вход функции SUMLIST, которая вычислит сумму.

Ниже приводится пример использования функции QUOTE. Предполагается, что функция SUMLIST имеется в системе, принадлежит к классу EXPR или SUBR (т.е. вычисляет свои аргументы).

(sumlist (1 2 3))

Не найдена функция 1 ==> ERRSTATE

(sumlist (quote (1 2 3)))

==> 6

По уже укоренившейся традиции вместо того, чтобы писать:

(QUOTE Нечто)

допустимо писать: 'Нечто

Далее в этом разделе будет употребляться именно такая запись. Следует обратить внимание на то, что скобки перед апострофом не ставятся.

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

Присвоение значений атомам. Функции SET, SETQ и CSETQ.

Ссылки