Лисп (LISP, от — «язык обработки списков»; современное написание: Lisp) — семейство языков программирования, программы и данные в которых представляются системами односвязных списков из элементов любой природы. Лисп, созданный Джоном Маккарти для исследований в области искусственного интеллекта, долгое время играл ключевую роль в этой сфере. Однако в современной практике ИИ его влияние значительно снизилось, уступив место Python и другим языкам. Тем не менее, Лисп продолжает использоваться в некоторых специализированных областях, а также в промышленном программировании — от встроенных скриптов до веб-приложений, хотя остаётся нишевым и сравнительно малораспространённым языком.
Это один из старейших (наряду с Фортраном и Коболом) используемых по сей день высокоуровневых языков программирования, а также первый из сохранившихся в использовании языков, использующих автоматическое управление памятью и сборку мусора.
Лисп был первым языком, в котором структура программного кода представляется непосредственно в виде стандартной структуры данных — качество, позже названное гомоикони́чностью.
Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но начиная уже с ранних версий обладает также чертами императивности, к тому же, имея полноценные средства символьной обработки, позволяет реализовать объектно-ориентированность; примером такой реализации является платформа 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)) …)