PART2 (Печатные лекции)

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

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

К числу основных особенностей языка Лисп относится то, что программой является несколько определенных пользователем функций. С точки зрения синтаксиса лисп-функция, как и обрабатываемые ею данные, представляет собой так называемое 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)