Лисп ( LISP , от англ. Lis t P rocessing language — «язык обработки списков»; современное написание: Lisp ) — семейство языков программирования , программы и данные в которых представляются системами линейных списков символов . Лисп был создан Джоном Маккарти для работ по искусственному интеллекту и до сих пор остаётся одним из основных инструментальных средств в данной области. Применяется он и как средство обычного промышленного программирования, от встроенных скриптов до веб-приложений массового использования, хотя популярным его назвать нельзя.

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

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

Традиционный Лисп имеет динамическую систему типов . Язык является функциональным , но начиная уже с ранних версий обладает также чертами императивности , к тому же, имея полноценные средства символьной обработки , позволяет реализовать объектно-ориентированность ; примером такой реализации является платформа CLOS .

Является языком системного программирования для так называемых лисп-машин , производившихся в 1980-е годы , например, фирмой .

Наряду с языком Ада Лисп прошёл процесс фундаментальной стандартизации для использования в промышленности, в результате чего появился диалект Common Lisp , впоследствии стандартизованный ANSI . Его реализации существуют для большинства платформ.

Архитектура и синтаксис

Основные элементы языка

Лисп — регистронезависимый язык. Исходно алфавит языка ограничивался символьной таблицей ASCII , некоторые современные реализации поддерживают Unicode .

Базовыми элементами языка являются символы, атомы и построенные из них динамические списочные структуры — S-выражения .

Символ в Лиспе — это объект в машинной памяти, представляющий собой совокупность «слотов» — ячеек, хранящих ссылки. Часть слотов имеет изначально определённое языком назначение:

• Имя — строка знаков, по которой программа может ссылаться на данный символ (основополагающее аристотелево А=А, из которого вырастает лямбда-исчисление ).
• Функциональный слот — лямбда-выражение , связанное с символом. Когда обращение к символу в программе синтаксически соответствует вызову функции, в результате вычисляется лямбда-выражение, связанное с символом.
• Значение — объект в машинной памяти, который можно трактовать как данные. Когда программа обращается к символу как переменной, она получает значение данного слота.
• Прочие системные слоты, определяемые реализацией.

Набор слотов является динамически расширяемым и может, вследствие этого, использоваться как список произвольных свойств символа (можно свободно расширить слотовую систему удобным для решения задачи способом). Такое представление позволяет рассматривать символы как узлы многокоординатной сети, где каждая координата записана в своём слоте.

Атомы — это символы и числа. Числа не являются лисповскими символами, поскольку могут иметь только собственное числовое значение и никакого другого. В то же время числа наравне с символами могут входить в списки. Этим и обусловлено объединение этих двух понятий в одну общую категорию.

Основная структура данных Лиспа — динамический список атомов, определяемый рекурсивно как головной объект и присоединённый к нему список-хвост. Поскольку голова списка тоже может быть списком, список является формой представления произвольного дерева (сам список верхнего уровня — корень, входящие в него подсписки второго и следующих уровней — узлы, атомы — листья). Для атомов и списков язык использует крайне примитивный скобочный синтаксис: символ представляется своим именем, число — записью его значения, а список — в виде заключённой в круглые скобки последовательности списков и атомов, в которой идущие подряд атомы при необходимости разделены пробелами.

Список является последовательностью элементов любого рода, в том числе других списков. Например, (1 3/7 'foo #'+) состоит из целого числа, рациональной дроби, символа foo и указателя на функцию сложения. Выражения представляются списками в префиксной записи : первый элемент должен быть формой , то есть функцией , оператором , макросом или специальным оператором ; прочие элементы — аргументы этой формы , передаваемые форме для обработки. Арифметические операторы записываются по тому же принципу, например (+ 4 (* 2 3)) выдаёт 10 (в инфиксной записи это 2 * 3 + 4 ).

Синтаксис в форме Бэкуса — Наура :

s_expression ::= atomic_symbol | "(" s_expression "." s_expression ")" | list 
list ::= "(" s_expression { s_expression } ")" 
atomic_symbol ::= letter atom_part 
atom_part ::= empty | letter atom_part | number atom_part 
letter ::= "a" | "b" | " ..." | "z" 
number ::= "1" | "2" | " ..." | "9" 
empty ::= " "

Характерная особенность программы на Лиспе состоит в том, что абсолютно всё: и данные, и код любой сложности — описывается в этом примитивном синтаксисе. Результатов такого подхода два:

• Внешне программа на Лиспе выглядит как гигантское нагромождение скобок. Имеющиеся в любой современной системе средства форматированного вывода, позволяющие отобразить список так, чтобы была видна его структура, несколько исправляют ситуацию, но в целом для восприятия программ на лиспе «на глаз» требуется определённый навык. Впрочем, редактирование программ значительно упрощается использованием текстового редактора , поддерживающего автоматическое выравнивание кода, подсветку соответствующих пар скобок и такие специальные команды, как «закрыть все открытые скобки», «перейти через список вправо» и так далее .
• Первичный синтаксический разбор программы и обрабатываемых ею данных может выполняться одним и тем же простейшим кодом, данные могут без каких-либо трудностей обрабатываться в качестве программы, а программа — в качестве данных. Вследствие этого Лисп позволяет легко создавать мощные программы, динамически порождающие код. Лисп-машина способна воспринимать каждый поступающий на неё список на самом абстрактном уровне, например как мета-лисп-машину, модифицирующую воспринимающую машину. В такой динамичной, высокоабстрактной среде можно реализовать как строго научные системы, так и неисчислимое множество программистских трюков и генераторов всевозможных машин.

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

Базовые символы, операторы и функции

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

T и NIL

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

Помимо этого у символа NIL есть ещё одно значение — он может обозначать пустой список.

CAR и CDR

Функции возвращают, соответственно, голову и хвост списка:

(CAR '(A B C D)) ==>> A (здесь и далее в примерах ==>> означает, что в результате вычисления левой части интерпретатор Лиспа выдаёт то, что находится справа)

(CAR '((A B)(C D))) ==>> (A B)

(CDR '(A B C D)) ==>> (B C D)

(CDR '((A B)(C D))) ==>> ((C D))

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

Формально в чистом функциональном программировании значение головы пустого списка является неопределённым, но в Лиспе (по крайней мере, в большинстве диалектов) принято соглашение, по которому и голова, и хвост пустого списка равны NIL .

(CAR NIL) ==>> NIL

(CDR NIL) ==>> NIL

Системные функции CAR и CDR получили такие необычные имена по историческим причинам. Машина IBM 704 , на которой Маккарти создавал самую первую реализацию Лиспа, содержала инструкции, позволяющие модифицировать части машинного слова. Машинное слово рассматривалось как структура с полями префикса, декремента, тега и адреса. Функции CAR (сокращение от Contents of the Address part of Register — «содержимое адресной части регистра») и CDR ( Contents of the Decrement part of Register — «содержимое декрементной части регистра») получили свои названия в соответствии с этими полями . В этой реализации поля адреса и декремента использовались для хранения, соответственно, указателей на голову и хвост списка. В некоторых новых реализациях Лиспа традиционные имена заменены на FIRST и REST (англ. «первый» и «остаток», соответственно) или дополнены этими синонимами.

C*R

Здесь на месте звёздочки «*» в имени функции может стоять от 2 до 4 букв «A» и «D» в любых комбинациях. То есть возможны функции CDDDDR , CADAR , CADDR и так далее. Вызов такой функции эквивалентен вложенному вызову соответствующего набора функций CAR и CDR , например, (CADAR '((A B C) D E F)) соответствует (CAR (CDR (CAR '((A B C) D E F)))) и вернёт значение «B». Необходимость в подобных странных функциях связана с часто повторяющейся задачей: извлечь из списка определённый элемент, положение которого известно.

CONS

Принимает в качестве аргумента голову и хвост и создаёт из них список или точечную пару, если аргументы являются атомами:

(CONS 'A '(B C D)) ==>> (A B C D) — присоединение атома к списку;

(CONS '(A B) '((C D))) ==>> ((A B) (C D)) — добавление списка к голове другого списка;

(CONS 'A 'B) ==>> (A . B) — создание точечной пары из двух атомов.

LIST

Эта функция возвращает список своих аргументов:

(list 1 3/7 'foo) ==>> (1 3/7 'foo)

Если аргументов нет, возвращается пустой список:

(list) ==>> NIL

Если некоторые элементы являются выражениями, то сначала вычисляется их значение:

(list 1 2 (list 1 2)) ==>> (1 2 (1 2)) .

QUOTE

Системный оператор QUOTE подавляет вычисление своего аргумента. Если он не используется, то интерпретатор Лиспа, получив на входе список или символ, пытается его вычислить: для символа возвращается его значение, для списка — результат вызова функции, имя которой находится в голове списка, с параметрами — хвостом списка. Если же нужно, чтобы интерпретатор не вычислял значения, а взял символ или список «как есть», к нему применяют QUOTE .

(LIST 1 2 (QUOTE(LIST 1 2))) ==>> (1 2 (LIST 1 2))

(QUOTE (list 1 2 (list 1 2))) ==>> (LIST 1 2 (LIST 1 2))

Поскольку подавление вычислений — очень частая операция, имеется сокращающий её запись синтаксический сахар — вместо полной формы вызова QUOTE можно просто поставить перед выражением апостроф:

(LIST 1 2 '(LIST 1 2)) ==>> (1 2 (LIST 1 2)) .

EVAL

Эта функция, по сути, и есть интерпретатор Лиспа. Являясь противоположностью QUOTE, она вычисляет значение своего аргумента.

(EVAL '(LIST 1 2 '(LIST 1 2))) ==>> (1 2 (LIST 1 2))

(EVAL '(LIST 1 2 (EVAL'(LIST 1 2)))) ==>> (1 2 (1 2))

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

COND

Обобщённая условная конструкция. Имеет вид:

(COND ((Условие1)(Выражение1)) ((Условие2)(Выражение2)) …)

Последовательно вычисляются Условие1, Условие2 и так далее до тех пор, пока очередное УсловиеN не окажется истинным (станет иметь значение T ). Тогда будет выполнено соответствующее ВыражениеN и его значение будет возвращено в качестве значения вызова COND . Если истинного условия не будет найдено, COND вернёт значение NIL . Обычной практикой является ставить в качестве последнего условия в COND значение T , гарантируя тем самым, что при невыполнении всех остальных условий будет вычислено последнее из выражений; так создаётся аналог ветви ELSE условных операторов императивных языков программирования.

DEFUN

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

(DEFUN Имя (Параметр1 Параметр2 …) Выражение1 Выражение2 …)

Здесь Имя — имя функции. Соответствующий символ, если его ещё нет, будет создан в системе и в его функциональный слот запишется определение функции. В дальнейшем интерпретатор Лиспа, встретив Имя в голове вычисляемого списка, интерпретирует его как вызов данной функции с перечисленными в хвосте параметрами. Параметр1 и так далее — имена формальных параметров функции.

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

Специальные операторы позволяют управлять последовательностью вычислений. С их помощью реализуются ветвления и циклы . Оператор if позволяет вычислить одно из двух выражений в зависимости от выполнения условия, которое тоже является выражением. Если его результат не ЛОЖЬ (не nil ), то вычисляется первый аргумент, иначе — второй. Например, (if nil (list 1 2 "foo") (list 3 4 "bar")) всегда возвращает (3 4 "bar") .

Типизация

Лисп не требует, вообще говоря, явно указывать типы переменных, параметров и функций. Но это не означает, что типов в Лиспе нет. В Лиспе используется динамическая типизация , когда тип данных относится не к переменной (параметру, функции), а к значению . Это означает, что переменная может, в отсутствие специальных уточнений, содержать значение любого типа данных, причём в разные моменты времени иметь значения различных типов. Типы значений определяются тем, как эти значения создаются. Например, в выражении (CONS 10 (CONS 2.01 (CONS 'A (CONS "abc" NIL)))) в одном и том же (первом) параметре одна и та же функция ( CONS ) получает последовательно целое число , число с плавающей точкой , атом и строку.

Развитые современные лисп-системы, в том числе стандартный Common Lisp, имеют большой набор встроенных типов данных, организованный в иерархическую систему, в которой у типа может быть несколько надтипов и несколько подтипов. Корнем иерархии является встроенный тип T , надтип всех типов, конечным типом иерархии — тип NIL , подтип всех типов.

На иллюстрации справа показан фрагмент этой иерархии: надтипом для значений числовых типов является NUMBER , его подтипы — RATIONAL , FLOAT и COMPLEX , — представляют, соответственно, рациональное число , число с плавающей запятой и комплексное число , первый из которых, в свою очередь, имеет подтипы INTEGER ( целое число ) и RATIO ( рациональная дробь ), второй — несколько подтипов, представляющих числа с плавающей запятой с разной степенью точности, и так далее.

Типы, создаваемые программистом, также встраиваются в данную систему.

Поскольку не все типы значений являются допустимыми для всех операций, применение операций к некоторым значениям приводит к ошибкам времени выполнения. Программист может либо игнорировать данную возможность (что приведёт к внезапной остановке программы в случае появления данных непредусмотренного типа), либо воспользоваться обработкой исключений, либо проверить, относится ли значение, с которым он собирается работать (например, переданное в функцию в качестве параметра), к нужному типу, и в случае несовпадения выбрать другой способ решения задачи или преобразовывать данные в нужный тип, когда это возможно. Для работы с типами имеются: предикат проверки типа TYPEP , функция определения типа TYPE-OF , а для преобразования типов, если оно может быть выполнено — целый набор узкоспециализированных функций и общая функция COERCE . Проверка типов облегчается тем, что система типов в Лиспе, как говорилось выше, является иерархической. Любой из подтипов совместим с любым из своих надтипов. Например, арифметические операции определены для любых комбинаций любых типов чисел, поэтому для допустимости применения, например, сложения, достаточно проверить с помощью предиката TYPEP , что операнды относятся к типу NUMBER .

(defun SmartPlus (a b) 
    (cond 
       ((and (typep a 'number) (typep b 'number)) 
           (+ a b))
       (t 
           nil)))

Так, в примере выше функция SmartPlus возвращает сумму своих аргументов, если они будут числами любых типов, либо nil, если хотя бы один из них окажется не-числом. При этом конкретный тип возвращаемого значения будет зависеть от фактических типов параметров:

(SmartPlus 1 2)
==> 3
(type-of (SmartPlus 1 2 ))
==> (INTEGER 0 4611686018427387903)
(SmartPlus 1 1.2)
==> 2.2
(type-of (SmartPlus 1 1.2))
==> SINGLE-FLOAT
(SmartPlus 2 2/3)
==> 8/3
(type-of (SmartPlus 2 2/3))
==> RATIO
(SmartPlus "abc" 20)
==> NIL
(type-of (SmartPlus "abc" 20))
==> NULL

Использование динамической типизации не всегда удобно, особенно при применении компилятора. Во-первых, отсутствие ограничений на типы, к которым могут относиться значения переменной или параметра, снижает эффективность компиляции. Во-вторых, оно не позволяет статически (во время компиляции, а не исполнения программы) выявлять ошибки, связанные с нарушением согласованности типов. В ситуациях, когда эти неудобства существенны, Лисп позволяет с помощью специального оператора DECLARE уточнять типы параметров и переменных, задавая их с любой необходимой точностью (можно указывать как конкретные типы, например, RATIO или SHORT-FLOAT , так и надтипы любой степени общности, например, NUMBER ).

Парадигмы программирования в Лиспе

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

Функциональное программирование

Функциональная парадигма является для Лиспа «родной», поскольку основой его архитектуры является лямбда-исчисление Чёрча . Собственно, именно с Лиспа началось функциональное программирование как практическая методология разработки программного обеспечения. Лямбда-выражения являются в Лиспе полноправными языковыми объектами, допускающими не только непосредственный вызов, но и присваивание, сохранение в качестве значения символа, передачу в качестве параметра вызова и возврат в качестве результата. Таким образом, Лисп поддерживает функционалы, то есть функции, принимающие в качестве параметров и возвращающие в результате другие функции.

В разных диалектах Лиспа подход к характеру функций как языковых объектов несколько различается. В Common Lisp функция и лямбда-выражение представляют собой отдельную категорию программных объектов, для которых существуют специфические правила и ограничения; в частности, это выражается в том, что у символа имеются раздельные слоты для значения и для функции, связанной с этим символом, и в этом смысле функция — это не вполне то же самое, что элемент данных. В других диалектах, таких как T-Lisp или Scheme, функции являются так называемыми « полноправными гражданами » — могут без ограничений присваиваться переменным, передаваться в качестве параметров вызова и возвращаться как результаты вызова.

Современный стандарт Лиспа — Common Lisp, — вызывает нарекания сторонников «чистого» функционального программирования тем, что не все его функциональные средства являются теоретически «чистыми». Это действительно так, поскольку Common Lisp разрабатывался как универсальный промышленный язык, и в ряде случаев соображениям практической целесообразности сознательно отдавалось предпочтение перед соображениями теоретической чистоты. Тем не менее, Лисп был и остаётся функциональным языком программирования.

Императивное (операторное) программирование

Исходно в синтаксис Лиспа заложена возможность описания алгоритмов путём перечисления последовательности требуемых действий. Она заключается в так называемом «неявном PROGN», поддерживаемом в структуре лямбда-вызовов Лиспа: в том месте, где должна размещаться команда, составляющая основу лямбда-выражения, может быть записано не одна, а несколько команд, и результатом лямбда-вызова станет результат последней из них. Таким образом, Лисп поддерживает неявное последовательное исполнение операций. Помимо неявного PROGN, поддерживаются явные императивные механизмы императивного программирования:

• Конструкции PROG1 и PROGN — обеспечивают выполнение команд последовательно.
• LET — позволяет задать локальные переменные блока и выполнить с ними последовательные операции.
• Все виды циклов.
• Конструкции присваивания SET, SETF, SETQ, выполняющие присваивания.
• Ряд системных структуроразрушающих функций (выполняющих операции с данными «на том же месте»).

В Common Lisp особое место занимает системный макрос LOOP. Он позволяет создать в лисп-программе фрагмент, написанный на языке программирования с привычной императивной структурой и инфиксной записью операторов.

Макропрограммирование

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

(defun назвать (name lv) (eval (cons 'defun (cons name (cdr lv)))))
(назвать 'сложить '(lambda (x y) (+ x y)))

(сложить 5 7)
==>12

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

Однако эта возможность используется редко из-за своей громоздкости. Гораздо чаще используется система макросов . Современные варианты Лиспа, в том числе стандарт Common Lisp, обладают развитыми возможностями создания и использования макросов . Описание макроса в Лиспе синтаксически подобно описанию функции (разница состоит только в использовании ключевого слова defmacro вместо defun в описании), но поведение макроса существенно отличается: каждый вызов макроса «раскрывается» в момент трансляции программы, порождая код, который на этапе исполнения выполняется так, как будто был непосредственно написан в месте вызова. Ещё одним отличием макросов от обычных функций является то, что их аргументы по умолчанию не вычисляются. Реализация вышеприведённого примера в виде макроса могла бы выглядеть так:

(defmacro назвать (name lv) (cons 'defun (cons name (cdr lv))))
(назвать сложить (lambda (x y) (+ x y)))

(сложить 12 8)
==>20

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

Кроме того, ряд реализаций Лиспа поддерживает создание так называемых «макросов чтения» — макросов, непосредственно преобразующих текст программы. Макросы позволяют прозрачно определять новые языковые конструкции и даже дополнять синтаксис языка. Последняя возможность активно используется при реализации на Лиспе исходно не поддерживаемых в нём методов и средств программирования.

Объектно-ориентированное программирование

Лисп создавался не как объектно-ориентированный язык. Сама парадигма объектно-ориентированного программирования была разработана на полтора десятка лет позже Лиспа, тем не менее, когда она появилась и стала популярной, объектные возможности были добавлены и в этот язык.

Набор базовых возможностей Лиспа делает добавление в него объектно-ориентированной подсистемы не только возможным, но и простым. Благодаря наличию свойств (слотов) у символов, Лисп изначально поддерживает инкапсуляцию . Функциональные свойства Лиспа (поддержка функционалов, присваивание функций переменным и сохранение их в свойствах символов) дают возможность связывать код (методы) с данными (объектами). Наконец, динамический характер языка в сочетании с вышеперечисленными особенностями обеспечивает полиморфное поведение кода и данных в программе. Единственный компонент ООП-системы, которого нет в базовом Лиспе — наследование, но оно может быть реализовано без затруднений. Таким образом, Лисп содержит в себе все элементы, на которых базируется технология ООП, и реализация её поддержки в языке сводится к созданию соответствующих синтаксических элементов. Благодаря развитому механизму макросов, они могут быть добавлены средствами самого языка, без необходимости расширения базового синтаксиса и модификации трансляторов. Простой и элегантный пример создания собственной подсистемы ООП в Лиспе можно найти в книге Пола Грэма «ANSI Common Lisp» .

Среди промышленных известных объектно-ориентированных расширений Лиспа прежде всего следует назвать объектную подсистему Flavors, которая была включена в состав системы Зеталисп. Эта подсистема обеспечивала объявление классов (flavors — «ароматов»), единичное и множественное наследование, полиморфные методы классов, Smaltalk-подобную систему взаимодействия объектов путём передачи сообщений (реализованную как вызов методов объекта). Другим примером может служить LOOPS (Lisp Object-Oriented Programming System) — объектная подсистема, реализованная в 1983 году в диалекте Интерлисп.

Объектная система CLOS (Common Lisp Object System), первоначально созданная в дополнение к Common Lisp, а позже вошедшая в стандарт языка, подобна Flavors и поддерживает принципиально тот же набор возможностей, стандартный для почти любого современного объектно-ориентированного языка. Применение объектно-ориентированного программирования в Лиспе, в основном, связано с решением задач моделирования и/или управления, которые по своему характеру удачно совмещаются с объектно-ориентированной технологией. Например, одним из первых приложений системы Flavors было взаимодействие с многооконным интерфейсом пользователя, который как раз удобно моделировать в виде набора объектов, обменивающихся сообщениями.

История

Предпосылки

Автором Лиспа является Джон Маккарти , на период создания языка работавший в Массачусетском технологическом институте (MIT) в должности профессора по связи. Вместе с Марвином Мински он занимался работами по искусственному интеллекту, в связи с чем и возникла потребность в создании языка программирования, адекватного задачам, решаемым в этой области. Работа по созданию языка была проделана Маккарти в MIT в период с 1958 по 1963 год , после чего он перешёл в Стенфордский университет в Калифорнии, где получил должность «профессор по искусственному интеллекту».

Основой для Лиспа послужил ранний язык , разработанный Ньюэллом, Шоу и Саймоном. IPL был языком обработки списков и предназначался для реализации проекта «Логик-теоретик» — системы искусственного интеллекта, предназначенной для автоматического вывода теорем математической логики. IPL был довольно низкоуровневым языком, но в нём уже были реализованы такие базовые идеи, как единый механизм хранения программ и данных в виде списков — иерархических структур элементов, связанных ссылками (сама идея списочного представления знаний была позаимствована из исследований по психологии и ассоциативной памяти), а также идея динамического распределения памяти. После ознакомления в 1956 году с IPL у Маккарти появилась идея реализовать обработку IPL-списков в Фортране , который как раз в это время проектировался в IBM (причём под ту же систему IBM 704 , с которой Маккарти работал в MIT), но эта идея так и не была реализована. Позже Маккарти принял участие в работе «комитета по языку высокого уровня», разрабатывавшего Алгол , но и там его предложения были встречены холодно. В результате Маккарти пришёл к мысли о необходимости создания нового языка программирования.

Первоначально Маккарти сформулировал списочный формализм для описания данных ( S-выражения ) и основанный на нём же механизм описания лямбда-выражений , что позволило записывать программы в виде наборов функций, представленных в списочной форме. Как писал позже Маккарти, изначально он планировал применять для записи программ отдельный формализм, отличающийся от S-выражений, но это оказалось излишним. Когда с помощью своей списочной записи Маккарти описал алгоритм функционирования интерпретатора нового языка (формализм, который впоследствии стал известен как «Лисп на Лиспе»), Стив Рассел заметил, что теперь для создания реального работающего интерпретатора достаточно просто перевести эту запись в машинный код. Маккарти отнёсся к этой идее скептически, но Рассел действительно проделал данную работу и получил первый интерпретатор Лиспа для компьютера IBM 704. В дальнейшем идея написания транслятора языка на нём самом многократно использовалась, и не только в функциональных и логических языках, но и в императивных.

Первые реализации

Исторически первой реализацией Лиспа, включающей все современные базовые элементы языка, был интерпретатор, работавший на IBM 704, появившийся в октябре 1958 года. Это, кстати, позволяет говорить о Лиспе как об одном из двух старейших языков высокого уровня, которые находятся в употреблении с момента создания до настоящего времени (первый — Фортран). Помимо этого, Лисп сохранил первенство ещё в одном отношении. Дело в том, что активная работа с динамическими списками сделала невозможным ручное управление памятью, которое в императивных языках отчасти сохраняется по сей день. Создание новых списочных ячеек и списков и выход из использования имеющихся при работе лисп-программы происходят настолько активно, что практически невозможно обойтись без системы автоматического управления памятью, которая контролировала бы использование ранее созданных в памяти объектов и периодически удаляла те из них, использование которых прекратилось, то есть системы сборки мусора . Маккарти пришлось реализовать эту систему, благодаря чему Лисп, помимо прочего, является ещё и самым старым из применяемых сегодня языков программирования с автоматическим управлением памятью и сборкой мусора.

Позднее были созданы реализации для IBM 7090, в дальнейшем — для серий IBM 360 и 370. Компьютеры IBM оказались неудобны для работы в интерактивном режиме, вследствие чего в конце 1950-х годов небольшая группа разработчиков, в том числе работавших ранее в IBM, выделилась в самостоятельную компанию Digital Equipment Corporation (DEC). Первым её изделием стал компьютер PDP-1 , изначально ориентированный на интерактивный режим работы. На этой машине в 1960 году была реализована интерактивная система «Lisp 1», включающая в себя интегрированные интерпретатор, редактор исходного кода и отладчик, позволявшая выполнять весь цикл работ над программой непосредственно в системе. По сути, это была первая «среда программирования» в том смысле, который вкладывается в это понятие сейчас. Тогда же в журнале «Communications of ACM» вышла статья Маккарти «Recursive Functions of Symbolic Expressions and their Computation by Machine.», в которой Лисп был описан в виде алгебраического формализма на самом Лиспе. Статья стала классической, а формализм типа «Лисп на Лиспе» с тех пор стал одним из наиболее употребимых в литературе по теории программирования. Ещё одним технологическим новшеством, появившимся в связи с реализацией системы «Lisp 1» был изобретённый Маккарти механизм, позволявший запускать интерпретатор Лиспа одновременно с выполнением обычных вычислительных работ в пакетном режиме (то, что сейчас известно как «система разделения времени»).

К 1962 году была готова следующая версия оригинальной лисп-системы «Lisp 1.5», в которой были устранены обнаруженные за время эксплуатации недостатки первой версии. Её описание было выпущено в издательстве «MIT Press» в виде отдельной книги . Поскольку руководство включало описание реализации системы, оно стало основой для создания лисп-систем для множества других компьютеров как в США, так и за её пределами.

Диалекты 1960-х — 1980-х годов

Несмотря на использование, подчас весьма активное, Лиспа в европейских и азиатских странах и создание там собственных лисп-систем, большинство распространённых диалектов Лиспа происходят из США.

MacLisp

С начала 1960-х годов в MIT был запущен проект MAC, в рамках которого на основе Lisp 1.5 был разработан MacLisp, ориентированная в основном на компьютеры PDP. MacLisp был чрезвычайно мощной для своего времени системой, отличался высокой вычислительной эффективностью и широким набором математических типов данных, в том числе векторов, матриц и битовых полей. В части вклада в развитие самого языка можно отметить появившиеся в MacLisp макросы чтения и таблицы чтения, позволившие «достраивать» язык, расширяя его в нужном направлении новыми структурами. Также в язык были включены средства обработки исключений и средства параллельной обработки. Также MacLisp стал первой лисп-системой, для которой был реализован высокоэффективный компилятор .

На MacLisp была целиком написана система компьютерной алгебры Macsyma , разработка которой была начата в рамках проекта MAC в 1968 году. Macsyma в течение многих лет оставалась наиболее развитой системой такого типа, несколько диалектов Лиспа были созданы специально для того, чтобы выполнить перенос Macsyma на другие платформы. Другим очень известным и находящимся в употреблении до сих пор программным продуктом, изначально разработанным на MacLisp, является полноэкранный текстовый редактор Emacs .

Система MacLisp эксплуатировалась и развивалась вплоть до 1980-х годов, оказав существенное влияние на появлявшиеся в 1960—1980 годах реализации Лиспа, в том числе став одним из источников проектирования стандарта Common Lisp. Эксплуатация системы практически прекратилась в 1980-х годах вместе с прекращением использования компьютеров PDP-10/20, на которых она изначально базировалась. Намного пережили систему разработанные на MacLisp и уже упоминавшиеся Macsyma и Emacs .

Interlisp

Разработкой лисп-систем в середине 1960-х годов занимались многие компании и исследовательские центры в США. Interlisp стал результатом объединения усилий BBN (Bolt, Beranek and Newman Inc.), SDS (Scientific Data Systems) и Xerox. Исследовательский центр BBN в 1966 году приступил к созданию своей реализации Лиспа, ориентированной на компьютеры PDP-10 и SDS-930. Версия BBN-Lisp для PDP использовала аппаратный механизм страничной организации памяти и переключения контекста, созданный специально для обеспечения высокоэффективного разделения времени. BBN-Lisp стал популярен среди исследователей в области искусственного интеллекта и во многом способствовал тому, что именно машины PDP-10/20 вплоть до 1980-х годов оставались основными инструментами в работах по ИИ. В начале 1970-х корпорация Xerox купила обанкротившуюся SDS и начала сотрудничать с BBN. Несмотря на то, что машины SDS не имели большого коммерческого успеха, реализация Лиспа от BBN была достаточно перспективной, чтобы Xerox поддержала её дальнейшую разработку, в результате чего BBN-Lisp превратился в .

А в 1974 году в Xerox началась разработка персональной рабочей станции Alto, исходно ориентированной на Лисп. В этой системе впервые была произведена разработка аппаратуры и системы машинных команд под конкретный язык программирования. На основе Interlisp была создана упрощённая версия системы Interlisp-D, предназначенная для лисп-машин серии 1100 («потомков» станции Alto). В этих машинах был впервые реализован многооконный графический интерфейс пользователя, использована графика с высокой разрешающей способностью и применён манипулятор «мышь».

Система была тщательно документирована, и включала хорошо продуманную интегрированную среду разработки с редактором исходных кодов, отладчиком, интерпретатором и множеством вспомогательных инструментов разработчика, став одним из образцов программной среды для систем разделения времени. В системных библиотеках было реализовано свыше 500 функций, система имела большое количество настроек, позволявших «подогнать» её под пользователя. Реализации Interlisp со временем были выполнены на большинстве широко распространённых больших компьютеров, работавших в режиме разделения времени.

Что же касается собственно языка, то можно заметить, что диалект со всеми его характерными особенностями был зафиксирован уже в середине-конце 1970-х годов, после чего кардинальных изменений в язык не вносилось. Это привело к некоторому отставанию системы от более новых разработок в части функциональности и к фиксации некоторых устаревших проектных решений. Вследствие этого уже к началу 1980-х годов Interlisp испытывал трудности как с совместимостью с новыми системами, так и с дальнейшим расширением. Наиболее существенные недостатки — отсутствие иерархии типов данных, объектов и замыканий (тем не менее, в 1983 году была реализована объектная система LOOPS, дающая возможности объектно-ориентированного программирования). Более существенно то, что Interlisp базируется на динамическом связывании, тогда как все новые версии Лиспа — статические.

PSL

Лисп попал в Калифорнию вместе с Маккарти, перешедшим в Стенфорд в 1963 году. За следующие несколько лет были разработаны системы Lisp 1.6 (прямой потомок «классического» Lisp 1.5), UCI Lisp (University of California, Irvine) и Stanford Lisp/360. Оттуда вместе с Энтони Хёрном Лисп попал в Университет штата Юта , где занималась исследованиями в области символьной математики в приложениях теоретической физики. Хёрн предложил решать эти задачи с помощью Лиспа, в результате чего в 1968 году была создана система компьютерной алгебры Reduce .

Хёрн в 1966 году опубликовал спецификацию Standard Lisp, которую предлагал в качестве основы для стандартизации языка. Предложение его не встретило поддержки, так как не было одобрено исследователями искусственного интеллекта, указавшими на ряд нежелательных для них особенностей предлагаемого стандарта, в частности, излишнюю привязку к типам. Тем не менее, на основе данной спецификации в Юте был реализован Portable Standard Lisp — PSL. Эта реализация была использована для развития Reduce и переноса её на различные аппаратные платформы. Специально для улучшения переносимости в PSL был включён сокращённый набор системных функций и структур. Реализация была основана на промежуточном низкоуровневом лисп-подобном языке SYSLisp; ядро PSL было написано на SYSLisp, а вся остальная часть системы — на самом PSL. Для PDP-10 был реализован транслятор SYSLisp и написанный на том же SYSLisp кросс-компилятор, с помощью которого ядро PSL можно было перенести на любую другую аппаратуру. С помощью этой технологии PSL и Reduce были реализованы на целом ряде платформ, в том числе на DEC-10/20, VAX/UNIX, HP9000, Apollo, Wicat, IBM, Cray.

Таким образом, PSL стал одним из первых примеров реализации техники «раскрутки» при переносе программных систем на новую архитектуру, когда для переноса системы ядро изначально пишется на машинно-независимом промежуточном языке, для которого, в свою очередь, создаются реализации на всех целевых платформах. Дальнейшее сопровождение PSL осуществлялось исследовательским центром фирмы Hewlett-Packard в Калифорнии.

Franz Lisp

Мотивом для создания в конце 1970-х годов системы Franz Lisp послужило желание получить лисп-систему для новых компьютеров VAX, чтобы обеспечить выполнение на них системы Macsyma и другого написанного на Лиспе программного обеспечения. Поскольку основной целью был перенос Macsyma, за основу был взят MACLisp, однако из языка были исключены некоторые устаревшие особенности и добавлены новые механизмы, заимствованные из разрабатываемого в то время в том же MIT Zetalisp. Наиболее значительный вклад в создание данного диалекта внесли Университет Беркли , Университет Пенсильвания , Bell Labs , Ливерморская национальная лаборатория и Университет Карнеги — Меллона . Одним из основных вдохновителей проекта был профессор Университета Беркли Ричард Фэйтман, ранее работавший в MIT и участвовавший в разработке оригинальной системы Macsyma. В числе создателей Franz Lisp было несколько его учеников. Название системы было выбрано в честь известного венгерского композитора Ференца Листа (английское написание: Franz Liszt).

Система была реализована в 1981 году на C для VAX 780/11 под управлением ОС UNIX . Входящий в состав системы компилятор носил имя «Liszt» — фамилии композитора, давшего имя диалекту. В 1982 году система была портирована на процессор Motorola 68000 , затем ещё на ряд 32-разрядных персональных платформ, в результате она стала наиболее широко используемой версией Лиспа как для 32-разрядных систем с разделением времени, так и для 32-битовых мини-ЭВМ и персональных рабочих станций.

Система Franz Lisp распространялась бесплатно под лицензией BSD, но аспирант Университета Беркли Фридрих Кунце подал идею создания коммерческой компании, которая бы обеспечивала качественную платную поддержку пользователей и выполняла заказы по портированию Franz Lisp на новые аппаратные и программные платформы. Это было время активного роста компьютерного рынка и перспективы выглядели неплохо. Компания была зарегистрирована в 1984 году и получила название «Franz Inc». Начало деятельности фирмы было достаточно удачным, ей удалось получить контракт на портирование Franz Lisp на платформу Sun, а позже — ещё несколько аналогичных предложений. Однако в 1985 году под давлением Министерства обороны США американское лисп-сообщество начало активную переориентацию на новый диалект — Common Lisp, создание которого в это время завершалось. В этих условиях Franz Inc. не могла найти новых контрактов, оказалась на грани закрытия и была вынуждена перейти к разработке собственной реализации Common Lisp — Allegro Common Lisp (название было выбрано, чтобы сохранить преемственность «музыкальной» темы). История Franz Lisp на этом, фактически, завершилась. В настоящее время оригинальная система полностью вышла из употребления.

Scheme

Язык Scheme был разработан в 1976 году в MIT в рамках проекта по созданию лисп-машины — персональной рабочей станции, разработанной полностью, начиная с аппаратуры, в расчёте на максимально эффективное использование языка Лисп. Исходно Scheme был всего лишь «исследовательским языком», в ходе разработки которого опробовались различные идеи и методы. Ставилась цель реализовать минимальный набор базовых возможностей, который обеспечивал бы построение полноценной лисп-системы путём надстраивания этого набора.

В результате получилось небольшое по объёму и элегантно определённое ядро, при этом весьма эффективно реализованное. В частности, Scheme стал первым диалектом Лиспа, в котором гарантировалась оптимизация хвостовой рекурсии. В языке реализован мощный механизм макросов, помимо списков в качестве базовых конструкций поддерживаются массивы. Характерное синтаксическое отличие Scheme от большинства диалектов Лиспа — немного другая форма определения функции. Если в большинстве диалектов используется вариант: (DEFUN ИмяФункции (Аргументы) Выражения) , то в Scheme сокращённая форма определения выглядит как (DEFINE (ИмяФункции Аргументы) Выражения) . (Различается ключевое слово и взаимное расположение имени функции и аргументов). Scheme использует динамическое связывание и реализует единое пространство имён для функций и переменных, что отличает его от Common Lisp’а.

Scheme — единственный «старый» диалект Лиспа, который продолжает использоваться после повсеместного перехода лисп-сообщества на стандартизованный Common Lisp. В настоящее время существует несколько поддерживаемых реализаций Scheme, в том числе свободных, есть примеры использования этого языка и в качестве встроенного (например, используемый в качестве средства создания скриптов GIMP Tiny-Scheme). В нескольких американских университетах Scheme используется как язык для базового обучения программированию.

Zetalisp

или «Lisp Machine Lisp» был создан в MIT во второй половине 1970-х годов в рамках проекта лисп-машины, профинансированного американским оборонным агентством DARPA.

Система основывалась на MacLisp и редакторе Emacs, но язык был существенно обновлён и дополнен, в частности, в нём появились новые типы данных, объектно-ориентированная подсистема Flavors, на которой основано взаимодействие программ с многооконным интерфейсом пользователя, новые директивные управляющие конструкции, частично заимствованные из Интерлиспа, многозначные функции (способные штатным образом возвращать более одного значения без предварительной «сборки» их в контейнер), потоковый ввод-вывод, пространства имён, мощная библиотека функций, в том числе математических, обеспечивающих векторные и матричные вычисления и работу с линейными системами.

Гораздо больше новшеств было внесено в саму систему программирования. Система изначально рассчитывалась на работу с графическим пользовательским терминалом и мышью. В ней был реализован графический многооконный интерфейс пользователя. В состав системы входил многооконный интерпретатор Лиспа, частичный транслятор, текстовый редактор Zmacs, инспектор структур данных, отладчик, программа исследования состояния системы, редактор системных файлов, редактор шрифтов и клиент электронной почты Zmail. В состав системы входили трансляторы других языков высокого уровня, преобразователь, обеспечивающий поддержку программ на Интерлиспе, и набор инструментов более высокого уровня. Для Фортрана, Паскаля, Ады и Пролога, поставлявшихся в составе системы, имелись развитые средства взаимодействия с программами на Лиспе, что позволяло в случае необходимости разрабатывать и применять программные системы на нескольких языках.

Изначально проект имел целью создание коммерческого продукта. В 1979 году было создано два предприятия — производителя лисп-машин: Symbolics и Lisp Machine Inc. (LMI). После этого работа по развитию Зеталиспа велась этими фирмами независимо. Тем не менее, при наличии некоторых различий в самих лисп-машинах, в части языка они были почти полностью совместимы.

NIL и T

Реализация MACLisp на машине VAX в самом MIT была начата в 1979 году. Проект получил название (одновременно аббревиатура «New Implementation of Lisp» — «Новая реализация Лиспа» — и стандартный лисповский атом «NIL», обозначающий, в зависимости от использования, логическую не-истинность или пустой список). NIL имел довольно большое ядро, написанное на ассемблере VAX, на котором всё тем же методом раскрутки строилась лисп-система. В какой-то мере можно считать NIL «ответом на Franz Lisp», поскольку в качестве одной из целей проекта был назван всё тот же перенос на VAX системы Macsyma. NIL много позаимствовал у Зеталиспа, в том числе систему Flavors, превращающую Лисп-систему в объектно-ориентированную. В 1981 году группа, занимавшаяся проектом NIL, распалась из-за непримиримых разногласий в отношении идеологии создаваемой системы. Несмотря на распад, начиная с 1982 года выходили регулярные обновления системы и она получила достаточно заметное распространение. В 1980-е годы NIL нередко использовался в организациях, имевших как VAX, так и лисп-машины, поскольку принципиальных идеологических отличий между NIL и Zetalisp нет, хотя Zetalisp намного богаче возможностями.

Отделившаяся от проекта NIL группа разработчиков приступила к созданию собственной версии лисп-системы, которая получила ироничное имя « » (одновременно — от «True Lisp» — «Настоящий (истинный) Лисп» и ещё один стандартный лисповский атом «T», обозначающий логическую истинность, то есть — противоположность «NIL»). Разработка этого диалекта велась в Йельском университете в 1982—1984 годы. В отличие от «старых» систем, диалект T использовал по умолчанию статическое связывание переменных, кроме того, его создатели ввели реализацию функций как «полноправных граждан», что означает, что функции могут без специальных синтаксических средств и без ограничений присваиваться переменным и возвращаться в качестве значений других функций. T-Lisp, в отличие от NIL, имел довольно небольшое ядро, написанное на машинном языке. Разработчики использовали технику «раскрутки», перенося ядро вручную на новые платформы и реализуя остальную часть системы непосредственно на Лиспе, рассчитывая, что высокоэффективный транслятор обеспечит лучшую производительность конечной системы, чем ручная реализация крупного ядра на машинном языке.

Спорным моментом в T-Lisp стало решение авторов обновить и систематизировать имена системных функций. Так, например, имена всех без исключения предикатов оканчивались на вопросительный знак, «исторически сложившиеся» стандартные имена элементарных функций были заменены на мнемонические, соответствующие тому, что функция делает. Например, функции CAR и CDR , возвращающие, соответственно, голову и хвост списка, получили имена FIRST и REST (англ. «первый» и «остаток»). Безусловным плюсом такого решения было облегчение изучения, очевидным минусом стала несовместимость со всеми остальными диалектами языка. В результате создателям всё равно пришлось впоследствии дополнить систему набором макросов, приводящих систему имён в соответствие со стандартом Common Lisp. Безусловно значительное влияние, которое на T оказал диалект Scheme. В целом же T-Lisp получился достаточно простой, элегантной и мобильной системой, которая была реализована для VAX и перенесена на многие 32-битовые рабочие станции.

Создание Common Lisp

К первой половине 1980-х годов в лисп-сообществе сложилась ситуация, которую некоторые авторы сравнивали с Вавилонской башней : параллельно существовали и развивались более десятка крупных диалектов Лиспа, общее же число несовместимых между собой реализаций было существенно больше. Похожая ситуация наблюдалась в это время в большинстве распространённых языков программирования, в случае же с Лиспом ситуация усугублялась тем, что язык изначально был разработан как произвольно расширяемый, что спровоцировало развитие его возможностей в разных диалектах в существенно разных направлениях. Если на начальном этапе, когда Лисп использовался почти исключительно в лабораториях и институтах, многообразие диалектов не особенно мешало и даже было отчасти полезным, поскольку способствовало быстрому развитию языка, то к 1980-м годам, когда появилась потребность в промышленных разработках на Лиспе, обилие реализаций стало тормозом, поскольку приводило к массовому дублированию разработок и рассредоточению сил на поддержку множества лисп-систем.

Попытки стандартизации Лиспа предпринимались почти с момента его появления (первое предложение по стандартизации датируется 1960 годом), но из-за разобщённости и значительных различий в потребностях заинтересованных групп разработчиков ни одно из предложений не было принято. Во второй половине 1970-х годов Министерство обороны США провело огромную работу по анализу ситуации в программных разработках военного назначения, после чего организовало конкурс на разработку нового языка высокого уровня для встроенных систем, которым стал язык Ада . Однако Ада изначально не предназначалась для искусственного интеллекта и символьной обработки, вследствие чего для таких разработок военное ведомство США оказалось вынуждено допустить к использованию более подходящий язык. Поэтому Министерство обороны США оказало организационную и финансовую поддержку формированию промышленного стандарта языка Лисп, который и приняло в качестве дополнительного средства разработки ПО для военных применений.

Первоначальный вариант стандарта начали готовить в Университете Карнеги — Меллона на основе внутреннего проекта Spice Lisp, также первоначально нацеленного на разработку лисп-системы для рабочей станции. Проектируемый стандарт с самого начала получил наименование «Common Lisp» («Общий Лисп»), подчёркивающее цель разработки — получить единый базовый язык, на основании которого можно было бы создавать программно-совместимые системы. В разработке и редактировании стандарта приняли участие около 80 специалистов из университетов, лабораторий и фирм США. Процесс разработки впервые происходил дистанционно, через компьютерную сеть ARPANET , через которую было передано свыше 3000 сообщений. Процесс разработки стандарта завершился в 1984 году. Его результат был зафиксирован в первом издании руководства «Common Lisp: the Language» Гая Стила.

Новые диалекты

Появление Common Lisp затормозило создание новых диалектов языка. «Старые» диалекты продолжали существовать, но по мере выхода из употребления платформ, на которых они работали, переставали использоваться и соответствующие Лисп-системы. Большинство из них прекратило своё существование в 1985—1995 годах. Новые разработки производились уже на Common Lisp. Тем не менее, в последующие годы появилось несколько новых диалектов Лиспа, большинство из которых шло по пути упрощения и ориентировалось на микрокомпьютеры.

ISLISP

ISLISP — спецификация Лиспа, разработанная в 1990-х годах и опубликованная ISO в 1997 году . Спецификация была обновлена в 2007 году . ISLISP представляет собой попытку стандартизовать ядро Лиспа путём консолидации существовавших и разрабатывавшихся на момент его создания промышленных диалектов Лиспа. Диалект во многом похож на Common Lisp (лексическая область видимости, раздельные пространства имён для функций и переменных, достаточно мощная система типов данных, поддержка сложных типов, макросистема, объектная система), но меньше по объёму. На 2018 год существует около десятка основных реализаций ISLISP’а, выпускаемых преимущественно под проприетарными лицензиями.

OpenLisp

Диалект, созданный Кристианом Джулиеном в 1988 году. Первоначально назывался MLisp, в 1993 году был переименован в OpenLisp. Название символизирует использование открытых стандартов, но не имеет отношения ни к Open Source Initiative , ни к свободному программному обеспечению : система распространяется по проприетарной лицензии.

Полностью соответствует спецификации ISLISP , дополнительно реализует ряд отсутствующих в данном стандарте средств. Возможна интерактивная разработка ( REPL ) в среде Emacs . Кроме интерпретатора, система содержит компилятор, преобразующий исходный код в LAP (Lisp Asssembly Program, ассемблеро-подобный низкоуровневый код в формате лисповских списков), и генератор кода, компилирующий LAP-программу в исходный текст на языке Си . Много внимания уделено взаимодействию с кодом на языках C/C++ и Java, поддержке встраивания в программные системы в качестве интерпретатора встроенного языка. Система продолжает развиваться и поддерживаться, существуют версии для большинства доступных ОС и аппаратных платформ.

PicoLisp

PicoLisp — свободная реализация Лиспа, рассчитанная на использование в Linux и других POSIX -системах. Проект появился в конце 1980-х годов, его целью было создание минималистичной и при этом практичной Лисп-системы для персональных компьютеров.

Со стороны языка PicoLisp отличается регистро-зависимостью, поддержкой UTF-8 и предельной простотой. Ядро поддерживает лишь три типа данных: числа, строки и списки. Введены синтаксические средства, позволяющие управлять вычислимостью параметров, форма quote расширена на неопределённое число параметров. Такое решение исключило необходимость в специальном синтаксисе для макросов и выражении lambda. Не поддерживаются структуры и массивы, имеется экономно выполненная, но мощная объектная подсистема. В отличие от Common Lisp, язык применяет динамическое связывание параметров.

Среда PicoLisp не имеет компилятора (это принципиальное решение, за счёт которого произведены многие упрощения в языке), но включает встроенные сервер приложений и подсистему хранения . Реализован прямой вызов внешних функций, написанных на Си, а также взаимодействие с кодом на Java. Диалект продолжает развиваться, регулярно выходят новые версии среды программирования для нескольких платформ.

EuLisp

Диалект, разрабатываемый с 1985 года сообществом европейских разработчиков и пользователей Лиспа из академической и промышленной среды. Может рассматриваться как своеобразный «ответ Европы на Common Lisp» — альтернативная попытка создать пригодный для широкого круга задач единый диалект Лиспа. Целью проекта было создание эффективного, компактного и не обременённого «лисповским прошлым» языка. Одной из приоритетных задач в разработке этого проекта было добавление в Лисп объектно-ориентированных средств.

Диалект поддерживает определение модулей с лексической областью видимости, замыкания с динамическим связыванием, единое пространство имён для переменных и функций, как в Scheme, встроенную поддержку параллелизма, объектную систему с единичным и множественным наследованием. Особенностью проекта является разделение языка на два уровня, Level-0 и Level-1, некоторые возможности доступны только на уровне 1, например, множественное наследование и метаобъекты.

Последняя официальная спецификация (версия .99) вышла в 1993 году, её неофициальная переработка (версия .991) — в 2010 году. Первый интерпретатор вышел в 1990 году, в 1990—2000-х годах было создано несколько реализаций, развитие которых прекратилось к 2011 году.

newLisp

Разработанный в 1991 году Лутцем Мюллером диалект, предназначенный для использования в качестве скриптового языка на рабочих станциях Sun под SunOS и FreeBSD. В настоящее время доступен на 32- и 64-разрядных платформах Intel под FreeBSD, Linux, Windows, Mac. Отличается простотой, малым объёмом, динамической областью видимости переменных, имеет ряд особенностей в синтаксисе. Поддерживает объектную систему FOOP, средства межпроцессного взаимодействия и многое другое. Среда включает интерпретатор, мини-IDE с редактором кода и эмулятором терминала для интерактивной разработки, библиотеки для веб-разработки и работы по сети через протоколы TCP и UDP.

Racket

Разрабатываемый с 1994 года компанией PLT Inc. диалект, первоначально носивший имя PLT Scheme. Является потомком диалекта Scheme, но существенно расширяет его. Одной из целей создания Racket было получение платформы для разработки и реализации предметно-ориентированных языков. Характерной его особенностью является очень мощная макросистема, которая позволяет создавать новые синтаксические конструкции и даже языки. При этом система модулей обеспечивает использование в единой программе элементов, написанных на различных диалектах с различной семантикой.

Реализация включает компилятор, систему времени выполнения, JIT-компилятор, интегрированную среду разработки с набором инструментов, библиотеки. IDE DrRacket, написанная на самом Racket, содержит профайлер, отладчик и систему юнит-тестирования. Доступны библиотеки, поддерживающие системное и сетевое программирование, веб-разработку, единый интерфейс к операционной системе, интерфейс для вызова внешних функций, несколько вариантов регулярных выражений, генераторы программ лексического и грамматического разбора, средства логического программирования и развитый графический интерфейс пользователя. Платформа реализована для Windows, MacOS, Linux и других вариантов UNIX. Она распространяется как бесплатное ПО с открытым кодом под лицензией GNU Lesser General Public License (LGPL). Поддерживается централизованный репозиторий для пакетов и расширений, созданных сообществом.

Используется в качестве исследовательского (в основном — как платформа для разработки языков и инструментов программирования), учебного, скриптового , промышленного языка (в частности — для разработки видеоигр). В учебном курсе применяется в концепции «обучение путём кодирования игр».

Arc

Arc — диалект, созданный Полом Грэмом . Заявленная автором цель проекта — создание простой, построенной на минимальном наборе экономно определённых сущностей, Лисп-системы с набором практически полезных библиотек, ориентированной на профессиональное применение и допускающей эффективные «Лисп-хаки» (различные вычислительные трюки, основанные на особенностях Лиспа). Автор принципиально отказался от поддержки в Arc некоторых технологий, в частности, ООП , так как счёл, что они нужны только при ведении разработки в рамках крупных организаций, а сами по себе не дают реального полезного эффекта. Разработка была анонсирована в 2001 году, первая публичная версия появилась в 2008. Первая реализация языка была написана в среде Racket. С 2009 года оригинальная система практически перестала разрабатываться, и сейчас развитие Arc продолжается в нескольких форках .

Диалекты для других сред

В последние десятилетия широко распространились языки, использующие автоматическое управление памятью, компиляцию в промежуточный код и исполнение его в виртуальной машине, такие как Java, Python, C#, и другие. Было создано и несколько диалектов Лиспа, ориентированных на исполнение в динамических средах других языков. Эти диалекты получают возможность напрямую работать с библиотеками соответствующей языковой среды и взаимодействовать с программами на других языках, исполняемыми в той же среде. Среди них:

• Clojure — Scheme-подобный язык, предназначенный для исполнения под JVM.
• Kawa — ещё один вариант реализации Scheme для JVM.
• (или Hylang) — диалект, работающий под управлением среды исполнения языка Python.
• (Lisp Flavored Erlang) — диалект Лиспа, написанный на Erlang и исполняемый под его виртуальной машиной BEAM.
• Pixi (Проект не развивается) — минималистичный Лисп, написанный на альтернативной реализации Python — PyPy

Стандарт Common Lisp

Основные особенности

В основном на идеологические основы стандарта повлияли MACLisp и его диалекты, большое количество возможностей было заимствовано из InterLISP и новых систем, таких как Zetalisp и NIL.

Common Lisp — язык со статическим связыванием переменных, традиционным представлением функций (функции не являются «полноправными гражданами»), поддерживает макросы, функционалы, лексические замыкания. То есть с точки зрения функциональной части языка он содержит весь тот набор синтаксических средств, который за предыдущие четверть века сложился в Лиспе и достаточен для любых приложений функционального программирования и расширения языка в любом желаемом направлении. Системные функции в Common Lisp сохранили традиционные имена, но многие из них имеют синонимы с более наглядными именами, например, функции CAR (получение головы списка) и CDR (получение хвоста списка) имеют синонимы, соответственно, FIRST («первый») и REST («остаток»).

Поскольку ставилась цель разработки системы, пригодной для максимально широкого спектра применений, спецификация существенно расширена функциями, синтаксическими средствами и механизмами, нехарактерными для исходного Лиспа. Так, например, в язык добавлены практически все существующие в императивных языках синтаксические конструкции, включая несколько видов циклов. Объектная система CLOS (Common Lisp Object System) первоначально не была включена в стандарт, но вошла в него позже. Common Lisp пригоден для написания программ как в функциональном, так и в директивном стиле, на нём возможно обобщённое программирование (посредством стандартных макросов), продукционное программирование, имеются средства для организации логического, объектного программирования и программирования, управляемого данными. Спецификация не включает в себя подробного описания среды программирования, определяя лишь в самых общих чертах её состав и принципы взаимодействия элементов.

Критики нового стандарта указывали на его раздутость и чрезмерное внимание, уделённое практическим требованиям, что привело к нарушению «функциональной чистоты» Лиспа и увеличению объёма лисп-системы. Тем не менее, под нажимом Министерства обороны США и частично с его финансовой поддержкой во второй половине 1980-х годов были созданы Common Lisp-реализации практически для всех распространённых платформ.

Дальнейшие модификации

Серьёзный пересмотр вышедшего в 1984 году стандарта, состоялся в 1990 году :

• Объектная система CLOS , исходно не входившая в спецификацию Common Lisp, а считавшаяся неким «дополнением» к ней, стала частью официального стандарта
• Был стандартизован макрос loop, реализующий встроенный императивный язык с инфиксным синтаксисом.
• Внесены изменения в типы данных.
• Стандартизован механизм pretty-print — форматированного вывода кода и данных.
• Введены макросы компиляции.
• Добавлены новые операторы и внесены изменения в существующие.
• Обновлена система поддержки пакетов.
• Сделан ряд более мелких изменений.

В 1995 году Common Lisp был стандартизован ANSI . Стандарт практически повторил спецификацию 1990 года, изменения незначительны и состоят, в основном, в добавлении, удалении и переименовании операторов и системных переменных и изменениях в системных вызовах. Можно отметить появление в Common Lisp типа boolean (логического), значениями которого могут быть только NIL и T.

Примеры

Пример программы, выводящей сообщение « Hello, world! »:

(format t "Hello, world!~%")

Рекурсивная версия функции N-го числа Фибоначчи:

(defun fibonacci (n)
  (if (> n 1)
      (+ (fibonacci (- n 1))
         (fibonacci (- n 2)))
      n))

Итеративная версия функции определения N-го числа Фибоначчи с использованием макроса Loop:

(defun fibonacci (n)
  (loop repeat n
        for a = 0 then b
        and b = 1 then (+ a b)
        finally (return b)))

Рекурсивная функция вычисления произвольной целой степени (алгоритм с логарифмическими временем выполнения и глубиной рекурсии):

(defun power (x n)
  (cond
    ((minusp n) (/ 1 (power x (- n))))
    ((zerop  n) 1)
    ((evenp n)(power (* x x) (/ n 2)))
    (t (* x (power (* x x) (/ (- n 1) 2))))))

Здесь использованы системные предикаты ZEROP — проверка на равенство нулю, MINUSP — проверка на отрицательность, EVENP — проверка на чётность.

Варианты Куайн (программы, выводящей свой исходный код) на Лиспе:

((lambda (x) (list x (list 'quote x))) (quote (lambda (x) (list x (list 'quote x)))))

((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))

Оба будут работать на большинстве диалектов Лиспа, в том числе и на Scheme . Какой из них окажется точнее, зависит от реализации лисп-системы: в одних при выводе списочного значения для отображения блокировки вычисления специальный оператор quote выводится в виде полного имени (для них подойдёт первый вариант), в других — в виде апострофа (второй вариант). Вариант Куайн на Common Lisp c использованием backquote :

((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))

Временная шкала диалектов Лиспа

Применение

Сферы применения языка Лисп многообразны: наука и промышленность, образование и медицина, от декодирования генома человека до системы проектирования авиалайнеров. Первые области применения языка Лисп были связаны с символьной обработкой данных и процессами принятия решений. Наиболее популярный сегодня диалект Common Lisp является универсальным языком программирования. Он широко используется в самых разных проектах: Интернет-серверы и службы, серверы приложений и клиенты, взаимодействующие с реляционными и объектными базами данных, научные расчёты и игровые программы.

Существуют специализированные диалекты Лиспа, предназначенные для конкретных применений, например, (GOAL) создан для написания высокодинамичных трёхмерных игр, на нём целиком написана серия игр Jak and Daxter .

Одно из направлений применения Лиспа — его использование в качестве скриптового языка , автоматизирующего работу в ряде прикладных программ, в том числе:

• AutoLISP — скриптовый язык САПР AutoCAD ;
• Emacs Lisp — встроенный язык текстового редактора Emacs , использованный как в реализации самого редактора, так и в разработке дополнений к нему, что даёт неограниченные возможности расширения функциональности;
• — скриптовый язык в издательском программном обеспечении Interleaf/Quicksilver;
• Nyquist — скриптовый язык в аудиоредакторе Audacity .
• (близок к Emacs Lisp) — язык настроек и расширений в оконном менеджере Sawfish ;
• — скриптовый язык САПР компании Cadence Design Systems ;
• — один из скриптовых языков в свободном графическом процессоре Gimp версии 2.4 или более. В предыдущих версиях использовался ещё один диалект Лиспа — .
• ICAD — система «знаний на основе знаний» которая позволяет пользователям кодировать знания дизайна и опыт инженерного проектирования.

Языки-потомки

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

• Scheme — разработанный в 1976 вариант Лиспа, по сей день используемый в обучении программированию и в исследовательских целях, а также применяемый в качестве встраиваемого языка.
• Racket — потомок Scheme, разрабатываемый с 1994 года и находящийся в использовании по сей день. Мощная расширяемая лисп-система, включающая в себя все современные средства поддержки программирования и большой массив библиотек.
• Clojure — созданный в 2007 году на основе Лиспа язык функционального программирования, интегрированный с платформой Java (программы транслируются в байт-код и работают под управлением JVM ). Унаследовав основные черты Лиспа, язык имеет целый ряд синтаксических отличий и нововведений. Интеграция с Java-платформой даёт возможность непосредственно применять весь массив накопленных библиотек для данной платформы. Также Clojure имеет встроенную поддержку параллельного программирования, причём является одним из немногих языков, поддерживающих механизм транзакционной памяти .
• Лого — язык и интерактивная среда, разработанные в 1967 году Сеймуром Пейпертом и Идит Харель для обучения детей дошкольного и младшего школьного возраста основным концепциям программирования. Язык имеет лисп-подобный списочный синтаксис, в котором устранена необходимость использования большинства скобок. Поддерживается также и императивная форма программы, напоминающая Бейсик . Повторение, кроме рекурсии, может быть реализовано с помощью конструкции цикла с фиксированным числом итераций. Характерная особенность среды интерпретатора Лого — поддержка визуального агента («черепашки»), изображаемой в виде пиктограммы на графическом поле (в окне). Черепашка может двигаться и поворачиваться, она имеет «перо», которое может быть поднято или опущено. При движении с опущенным пером черепашка оставляет след (линию на экране). Управляя черепашкой сначала с помощью отдельных команд («вперёд», «повернуть», «поднять перо», «опустить перо», «выбрать цвет» и т. д.), а затем — наборов команд и целых программ, содержащих сложные конструкции, обучаемый получает возможность осваивать программирование в игровой форме, непосредственно наблюдая результаты своих усилий в виде изображений на экране. Существуют реализации с поддержкой ООП и параллельного исполнения.

Лисп-машины

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

В США разработки лисп-компьютера велись в 1970-х годах в исследовательском центре Palo Alto, принадлежащем корпорации Xerox , и в MIT (последнее спонсировалось DARPA ). Их результатом стало появление в начале-середине 1980-х годов трёх основных производителей: Xerox, (LMI) и Xerox производил лисп-машины, поддерживающие Интерлисп, две последние компании происходили из MIT и ориентировались на Зеталисп. Несколько позже производством лисп-машин занялась Texas Instruments . В Японии в 1984 году был показан первый прототип коммерческой лисп-машины Alpha фирмы Фудзицу .

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

Для своего времени лисп-машины были одними из мощнейших ЭВМ в классе персональных рабочих станций. Им пророчили большое будущее, но в 1990-х годах все они вышли из употребления, а производители либо прекратили свою деятельность, либо переориентировались на выпуск компьютеров общего назначения. Причиной стало то, что в условиях длительного экспоненциального роста скорости и объёмов памяти компьютеров разработка оборудования «под язык» оказалась бесперспективной — быстро развивающиеся компьютеры общего назначения, снабжённые трансляторами Лиспа, по своим возможностям обогнали лисп-машины, которые из-за своей специализации были дороже и проигрывали в универсальности.

Лисп в СССР и России

В СССР работы, связанные с использованием Лиспа и созданием собственных лисп-систем, активизировались после 1968 года, когда группа американских учёных, среди которых были Маккарти и Б. Беркли ^{[ уточнить ]} , посетила Советский Союз. В Новосибирске, в ВЦ Сибирского отделения Академии наук, где Маккарти провёл больше всего времени, он заложил основу реализации Лиспа на БЭСМ-6 . В Москве, в ВЦ АН СССР советские математики Лавров и при содействии Беркли начали работу над собственной версией лисп-интерпретартора для БЭСМ-6. Впоследствии Лавров перешёл на работу в ЛГУ , а Силагадзе — в ВЦ Грузинской академии наук в Тбилиси, где они продолжили работу с Лиспом и участвовали в создании нескольких лисп-систем для ЕС ЭВМ .

В Ленинграде была создана лисп-система для польского компьютера Odra 1204, в Москве — реализация для БЭСМ-6, совместимая с английской версией Лиспа для компьютера ICL 4, в МЭИ и в Дальневосточном научном центре во Владивостоке появились реализации для ЕС ЭВМ. В Институте проблем передачи информации (Москва) в конце 1970-х была создана лисп-система ЭКЛИСП для мини-компьютера ECLIPS. На компьютерах западного производства в СССР использовались Stanford Lisp и UT-Lisp (Дубна, IBM 370 и CDC 6600). Также популярна была шведская система Нордстрёма (Лисп на Фортране).

В 1975 году в Тбилиси состоялась четвёртая международная конференция по проблемам искусственного интеллекта IJCAI-75, которая способствовала повышению интереса к Лиспу и распространению его в университетах и НИИ. В 1978 году вышел первый учебник Лиспа на русском языке авторства Святослава Лаврова и Гиви Силагадзе («Автоматическая обработка данных. Язык ЛИСП и его реализация»).

В 1980-е годы интерес к Лиспу в СССР сохранялся, тем не менее, литературы по языку издавалось очень мало (за десятилетие вышло две книги, обе переводные: «Функциональное программирование. Применение и реализация» Хендерсона, переведённая в 1983 году, и двухтомник «Мир Лиспа» Хювёнена и Сеппянена, перевод которой был издан в 1990).

В постсоветской России использование Лиспа в основном ограничивается академическими исследованиями и работами отдельных энтузиастов. Кроме того, Лисп продолжает использоваться в учебных целях в некоторых российских университетах, но и здесь в последние годы он оказался заметно потеснён: как язык общего назначения он не преподаётся и не используется, а в качестве учебных языков для преподавания функционального программирования часто предпочитают использовать более молодые функциональные языки, появившиеся в последние два десятилетия. Тем не менее, интерес к языку сохраняется, свидетельством чего является появление переводных и оригинальных печатных работ по Лиспу, возобновившееся в 2010-2020-е годы .

Лисп в фольклоре программистов

• Существует альтернативная расшифровка названия LISP: Lots of Irritating Superfluous Parentheses ( «Много раздражающих лишних скобок» ) — намёк на особенности синтаксиса языка.
• Шутливое « Десятое правило Гринспена » гласит: «Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp». Правило, несмотря на свою юмористичность, фиксирует достаточно широко распространённое среди сторонников функциональных языков программирования мнение о том, что при программировании на традиционных императивных языках разработчики тратят очень много времени на реализацию, причём в неполном объёме и с худшим качеством, тех возможностей, которые функциональным языкам, в частности, Лиспу, присущи изначально.

Примечания

Литература

• Х. Абельсон, Д. Сассман. Структура и интерпретация компьютерных программ . — Книга и курс лекций MIT. В качестве основного языка используется Scheme .
• Paul Graham . ANSI Common Lisp. — Prentice Hall, 1995. — ISBN 0-13-370875-6 (англ.).

  Перевод: Пол Грэм. ANSI Common Lisp. — СПб. : Символ-Плюс, 2012. — 448 с. — ISBN 978-5-93286-206-3 .

• Paul Graham . . — Prentice Hall, 1993. — ISBN 0-13-030552-9 (англ.).
• Peter Seibel. .
• Хювёнен Э., Сеппянен Й. Мир Лиспа. В 2-х т. / Пер. с финск.. — М. : Мир, 1990. — ISBN 5-03-001935-9 (русск.). — ISBN 5-03-001336-9 . — ISBN 951-26-2787-6 (финск.).
• Горлянский С. П. . — Казань: Бук, 2023. — 3052 с. — ISBN 978-5-907665-30-9 .

Ссылки

• — русский перевод книги (англ.)
• — русский перевод (незаконченный) сборника рецептов (англ.)
• — ресурсы по языку Лисп (учебники, статьи).
• — Лисп у «Истоков» (литература, ссылки, проекты с исходным кодом)

Ссылки на английском

• — статья Джона Маккарти Recursive Functions of Symbolic Expressions and Their Computation by Machine, содержащей первоначальное описание языка Лисп.
• — сайт книги Practical Common Lisp, откуда может быть скачана электронная версия (pdf) и архив с исходными кодами для книги
• — вики-ресурс о библиотеках и проектах Common Lisp. Сам ресурс написан полностью на Common Lisp.
• — основной хостинг Common Lisp проектов.
• — ассоциация пользователей Лисп
• на Gmane .