APR Jun Jul 24 2006 2008 2009 11 captures 26 Mar 05 - 24 Jun 08

Close Help

Краткие сведения о языках Лисп и Плэнер

Язык программирования Лисп

К числу основных особенностей языка Лисп относится то, что программой является несколько определенных пользователем функций. С точки зрения синтаксиса лисп-функция, как и обрабатываемые ею данные, представляет собой так называемое S-выражение. В простейшем случае S-выражением является атом (идентификатор или число), в более сложном - список, т.е. последовательность элементов, разделенных обычно пробелом и заключенных в круглые скобки. Лисповские списки имеют рекурсивную структуру: элементом списка может быть произвольное S-выражение - как атом, так и список , например: (1() (a b (c)) class).

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

(f a₁ a₂ ... a_n), где f - имя функции, а a_i - ее аргументы (n≥0). Программа на Лиспе представляет собой последовательность таких форм, и ее выполнение заключается в их вычислении.

В большинстве версий языка Лисп имеется много встроенных (стандартных) функций, на основе которых составляется программа. Ниже кратко описаны некоторые из них - те, что использованы в предыдущих разделах пособия. Все они есть в наиболее известных версиях Лиспа, таких как Common Lisp и MuLisp. [Семенов М.Ю. Язык Лисп для персональных ЭВМ. - М.: Издательство МГУ, 1989.]

Определение новых функций

Для этого служит встроенная функция defun, к которой возможны следующие (равноценные) обращения:

(defun f (lambda (v₁ v₂ ... v_n) e))

или (defun f (v₁ v₂ ... v_n) e).

Вычисление функции defun в качестве побочного эффекта приводит к появлению в программе новой функции с именем f ; v_i - формальные параметры новой функции (n≥0), а e - форма, зависящая от v_i. Заметим, что таким образом определяется обычная лисп-функция, т.е. функция с фиксированным количеством аргументов, которые всегда вычисляются при обращении к ней.

При последующем обращении к этой уже определенной функции

(f a₁ a₂ ... a_n)

сначала вычисляются аргументы (фактические параметры) a_i, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, и далее вычисляется форма e при этих значениях переменных v_i, после чего эти переменные уничтожаются. Значением данной формы становится значение функции f при аргументах a_i.

Операции над списками

(car l)

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

(cdr l)

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

Кроме этих двух функций-селекторов элементов списка часто используются функции, являющиеся их суперпозициями. Имена всех таких функций начинаются на букву c, а заканчиваются на букву r, между ними же может стоять произвольная комбинация из не более чем 5 букв a и d, например,

(cadar l)≡(car(cdr(car l))) .

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

(nth n l)

Значением аргумента n должно быть положительное целое число (обозначим его N), а значением аргумента l - список. Значением функции является N-й от начала элемент этого списка.

(last l)

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

(cons e l)

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

(append l₁ l₂)

Эта функция осуществляет слияние (конкатенацию) двух списков, являющихся значением двух ее аргументов.

(list e₁ e₂ ... e_n )

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

Арифметические функции

(add1 n)

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

(sub1 n)

Значением аргумента должно быть число, функция вычитает из него 1 и выдает результат в качестве своего значения.

(+ n₁ n₂)

Значениями обоих аргументов функции должны быть числа, результат вычисления функции - их сумма.

(- n₁ n₂)

Значениями аргументов должны быть числа, значение функции - их разность.

(length l)

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

(mod n₁ n₂)

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

(rem n₁ n₂)

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

Предикаты

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

(null e)

Эта функция проверяет, является ли значение ее аргумента пустым списком: если да, то значение функции равно T, иначе - ().

(eq e₁ e₂)

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

(eql e₁ e₂)

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

(equal e₁ e₂)

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

(neq e₁ e₂)

Аналог, но значения аргументов сравниваются на "не равно".

(member a l)

Функция производит поиск атома, являющегося значением первого ее аргумента, в списке (на верхнем его уровне), являющемся вторым аргументом. В случае успеха поиска значение функции равно T, иначе - ().

(gt n₁ n₂) или (> n₁ n₂)

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

(lt n₁ n₂) или (< n₁ n₂)

Аналог, но числа сравниваются на "меньше".

Логические функции

Так называются три функции, реализующие основные логические операции.

(not e)

Эта функция, реализующая "отрицание", является дубликатом функции null: если значение аргумента равно () ("ложь"), то функция выдает результат T ("истина"), а при любом другом значении аргумента выдает результат ().

(and e₁ e₂ ... e_k) (k≥1)

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

(or e₁ e₂ ... e_k) (k≥1)

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

К числу логических функций можно отнести и лисповское условное выражение:

[cond (p₁ e_1,1 e_1,2 ... e_1,k1) ... (p_n e_n,1 e_n,2 ... e_n,kn)] (n≥1, k_i≥1)

Функция cond последовательно вычисляет первые элементы своих аргументов - обращения к предикатам p_i. Если все они имеют значение () ("ложь"), тогда функция заканчивает свою работу с этим же значением. Но если был обнаружен предикат p_i, значение которого отлично от (), т.е. он имеет значение "истина", тогда функция cond уже не будет рассматривать остальные предикаты, а последовательно вычислит формы e_i,j из этого i-го аргумента и со значением последнего из них закончит свою работу. Заметим, что поскольку значения предыдущих форм из этого аргумента нигде не запоминаются, то в качестве этих форм имеет смысл использовать только такие, которые имеют побочный эффект, например, обращение к функции присвоения значения.

Специальные функции

(quote e) или 'e

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

(gensym)

Функция генерации уникальных атомов, при каждом обращении к ней вычисляет (образует) новый атом-идентификатор. Этот идентификатор получается склеиванием специального префикса и очередного целого числа. Префикс и целое число, от которого начинается нумерация генерируемых атомов, могут быть установлены заранее, как например, в языке MuLisp:

(setq *gensym-prefix* 'S) (setq *gensym-count* 2).

После этого функция gensym будет последовательно выдавать атомы

S2, S3, S4, ... .

Блочная и связанные с ней функции

(prog (v₁ v₂ ... v_n) e₁ e₂ ... e_k) (n≥0, k≥1)

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

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

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

(setq v e)

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

(pop v₁ v₂)

Обоими аргументами должны быть имена переменных, существующих в данный момент, причем переменная v₂ должна иметь значение и им должен быть непустой список. Функция "расщепляет" этот список на две части - на его первый элемент, который присваивается переменной v₁, и на его "хвост" (без первого элемента), который становится новым значением переменной v₂. Значением самой функции является...

(push е v)

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

(return e)

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

(go e)

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

Язык программирования Плэнер

В языке Плэнер программа и обрабатываемые ею данные записываются в виде выражений, к которым относятся: атомы (идентификаторы и числа), обращения к переменным, состоящие из префикса и имени переменной (например, .X) и списки, т.е. последовательности выражений заключенные в круглые, квадратные или угловые скобки (например, [elem 1 (a b c)]).

Некоторые выражения можно вычислять, получая в результате значения (ими являются выражения); такие выражения называются формами. К ним относятся: атомы (значение атома - сам атом), обращения к переменным с префиксом "." (значением является текущее значение переменной), списки в круглых скобках (значением является список из значений элементов исходного списка) и обращения к функциям, имеющие вид [f a₁ a₂ ... a_n], где f - имя функции, а a_i - ее аргументы.

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

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

Определение новых функций

Для определения новой функции следует обратиться к встроенной функции define:

[define f dexp]

Вычисление функции define в качестве побочного эффекта приводит к появлению в программе новой функции с именем f и т.н. определяющим выражением dexp, которое должно иметь вид

(lambda (v₁ v₂ ... v_n) e) (n≥0)

где v_i - формальные параметры новой функции, а e - форма, зависящая от v_i.

При последующем обращении к этой новой функции

[f a₁ a₂ ... a_n]

сначала вычисляются аргументы (фактические параметры) a_i, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, и далее вычисляется форма e при этих значениях переменных v_i, после чего эти переменные уничтожаются. Значение данной формы становится значением функции f при аргументах a_i.

Операции над списками

[elem n e]

Значением аргумента n должно быть ненулевое целое число (обозначим его N), а значением второго аргумента - список (L) с любыми скобками. Значением функции является N-й от начала элемент списка L, если N>0, или |N|-й от конца элемент этого списка, если N<0. В случае, когда в качестве n явно указано число, имя функции в обращении можно опустить; например, [1 .X] - это сокращение от [elem 1 .X], т.е. выделяется первый от начала элемент списка, являющего значением переменной X.

Если требуется вычислить список в круглых скобках

(e₁ e₂ ... e_n) (n≥0)

т.е. если он рассматривается как форма, то все его элементы должны быть формами. Значением такого списка является список (с круглыми скобками) из значений его элементов. Например, если переменная X имеет значение (a b), то значением списка (.X c [-1 .X]) является список ((a b) c b).

В таких списках можно использовать т.н. сегментные формы, к которым относятся сегментные обращения к переменным (с префиксом "!.", например: !.X) и сегментные обращения к функциям (в угловых скобках, например: <elem 5 .X>). Сегментная форма вычисляется как обычная (простая) форма, но затем у ее значения, если это список, отбрасываются внешние скобки, и полученная таким образом последовательность элементов поставляется вместо сегментной формы. Например, если переменная X имеет значение (a (b c)), тогда:

значение (5 .X ()) равно (5 (a (b c)) ())

значение (5 !.X ()) равно (5 a (b c) ())

значение (!.X !.X) равно (a (b c) a (b c))

Арифметические функции

[+ n₁ n₂ ... n_k] (k≥2)

Значениями аргументов должны быть числа. Результат вычисления функции - их сумма.

[- n₁ n₂]

Значениями обоих аргументов должны быть числа. Значение функции - их разность.

[max n₁ n₂ ... n_k] (k≥2)

Значениями аргументов должны быть числа. Результат вычисления функции - их максимум.

[min n₁ n₂ ... n_k] (k≥2)

Значениями аргументов должны быть числа. Результат вычисления функции - их минимум.

Предикаты

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

[num e]

Эта функция-предикат проверяет, является ли числом значение ее аргумента. Если да, то значение функции равно T ("истина"), иначе - () ("ложь").

[empty e]

Функция проверяет, является ли значение ее аргумента пустым списком (с любыми скобками). Если да, то значение функции равно T, иначе - ().

[eq e₁ e₂]

Функция сравнивает значения своих аргументов. Если они равны, то значение функции равно T, иначе - ().

[neq e₁ e₂]

Аналог, но значения аргументов сравниваются на "не равно".

[gt n₁ n₂]

Значениями аргументов должны быть числа. Если первое из них больше второго, то значение функции равно T, иначе - ().

[ge n₁ n₂]

Аналог, но числа сравниваются на "больше или равно".

[lt n₁ n₂]

Аналог, но числа сравниваются на "меньше".

[hasval v]

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

Логические функции

Так называются функции, реализующие логические операции.

[not e]

Это "отрицание": если значение аргумента равно () ("ложь"), то функция выдает результат T ("истина"), а при любом другом значении аргумента выдает результат ().

[and e₁ e₂ ... e_k] (k≥2)

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

[or e₁ e₂ ... e_k] (k≥1)

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

[cond (p₁ e_1,1 e_1,2 ... e_1,k1) ... (p_n e_n,1 e_n,2 ... e_n,kn)] (n≥1, k_i≥1)

Это "условное выражение". Функция последовательно вычисляет первые элементы своих аргументов - предикаты p_i. Если все они имеют значение () ("ложь"), тогда функция заканчивает свою работу с этим же значением. Но если нашелся предикат p_i, значение которого отлично от (), т.е. имеет значение "истина", тогда функция уже не будет рассматривать остальные предикаты, а последовательно вычислит формы e_i,j из этого i-го аргумента и со значением последнего из них закончит свою работу. Замечание: значения предыдущих форм из этого аргумента нигде не запоминаются, поэтому в качестве этих форм имеет смысл использовать только такие, которые имеют побочный эффект, например, меняют значения переменных.

Блочная и связанные с ней функции

[prog (v₁ v₂ ... v_n) e₁ e₂ ... e_k] (n≥0, k≥1)

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

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

[set v e]

Это аналог оператора присваивания. Сначала вычисляются оба аргумента, причем значением аргумента v должно быть имя переменной, существующей в данный момент. Функция присваивает этой переменной новое значение - значение аргумента e. Это же значение является значением функции set, но оно, как правило, не используется.

[fin v₁ v₂]

Значением обоих аргументов должны быть имена переменных (обозначим их V1 и V2), существующих в данный момент, причем переменная V2 должна иметь значение и им должен быть список. Если этот список пуст, то функция ничего не делает и выдает значение (). Иначе функция "расщепляет" список на две части - на его первый элемент, который присваивается переменной V1, и на его "хвост" (без первого элемента), который становится новым значением переменной V2; в данном случае функция выдает результат T.

[return e]

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

[go e]

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

Функции для режима возвратов

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

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

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

[among e]

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

[fail]

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

[pset v e]

Это аналог функции set, т.е. переменной, имя которой является значением аргумента v, присваивается новое значение - значение аргумента e. Однако, если присваивание, осуществленное функцией set, отменяется при неуспехе, то действие функции pset при неуспехе не будет отменено. Функция pset (и ей подобные) применяется, когда надо сохранить информацию, полученную на неуспешном пути вычисления программы, для последующих путей.

[permex e f]

Функция осуществляет выход из ближайшей объемлющей функции с именем f и объявляет ее результатом значение аргумента e. При этом уничтожаются все развилки, появившиеся в программе с начала вычисления этой функции f, и "замораживаются" все изменения (в значениях переменных и т.п.), произведенные внутри этой функции. Это значит, что при последующем неуспехе функция уже не будет возобновлять свою работу и ее действия не будут отменены.