Математическая энциклопедия - лисп

алгоритмический язык, разработанный в. 1959-62 Дж. Маккар'ти [1]. Характеризуется весьма однородным синтаксисом, в к-ром как программа, так и ее объекты выглядят одинаково в виде т. н. с п и с о ч н о й структуры графа, в частности дерева, висячими вершинами к-рого являются атомы (см. ниже), а остальными вершинами списки, т. е. последовательности (возможно, пустые) элементов (списков или атомов), разделенных пробелами и взятых в скобки, напр.

Атомы это непустые слова в алфавите языка, не содержащие скобок, пробелов и обозначающие переменные, конетанты, функции или самих себя. Списки и атомы, для к-рых имеет смысл говорить об их значениях, наз. выражениями. Первым элементом списка выражения Е - является атом, обозначающий функцию, или список, изображающий функцию. Остальные элементы списка Еэто выражения, к-рые берутся в качестве аргументов функции, а значением Еявляется результат взятия функции от ее аргументов. Значения переменных и константы понимаются обычным образом. Изображение функции имеет вид списка (lambda (x1, . . ., хп).ехр), где lambda фиксированный атом, (x1, . . ., хп) - список связанных переменных, обозначающих аргументы функции, а ехр выражение, вычисляющее значение функции и содержащее в себе x1, . . ., хп как свободные переменные.

Среди фундаментальных функций Л. имеются: сат(l).и cdr (l), выдающие соответственно первый элемент списка lи его "хвост"; quote (l), выдающая lв качестве своего значения; cons (l т),"продолжающая" список lсписком т;cond ((p1 e1)(p2 e2)), выбирающая в качестве своего значения значение выражений e1 или е2 в зависимости от того, какое по порядку из предикатных выражений p1 и р2 оказывается истинным. Фундаментальными предикатами являются: atom (l), проверяющий, является ли lатомом; eq (l1 l2), истинный, если l1 и l2 -равные друг другу атомы; null (l), истинный, если lоказывается пустым списком. Фундаментальные функции и предикаты образуют набор средств, достаточный, чтобы реализовать в Л. и другие конструкции алгоритмич. языков, напр. конструкцию присваивания переменной значения выражения или связывания с атомом обозначаемого им изображения функции. Программой в Л. является произвольный список, образованный выражениями.

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

Лит.:[1] McCarthy J., Recursive functions of symbolic expressions and their computation by machine, Pt. 1, CACM, 3(Apr. 19(30), p. 184; [2] Лавров С. С., С и л а г а д з е Г. С., Автоматическая обработка данных. Язык лисп и его реализация, М., 1978; [3] X и г м а н Б., Сравнительное изучение языков программирования, пер. с англ., М., 1974. А. П. Ершов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985