Язык функционального программирования лисп + видео обзор

Содержание
  1. Функциональные языки программирования: LISP (Scheme/Racket) + Haskell. Использование рекурсии для решения задач
  2. Сильная (строгая) и слабая типизация
  3. Краткость и простота
  4. Строгая типизация
  5. Чистота (нет побочных эффектов)
  6. Отложенные (ленивые) вычисления
  7. Скачивание и установка
  8. Вычисление длины списка
  9. Haskell
  10. LISP. Атом первый
  11. Краткая история
  12. Типы данных
  13. Крылья, ноги… Главное хвост
  14. Основные функции и предикаты
  15. Функция QUOTE
  16. Функция CAR
  17. Фунция CDR
  18. Функция CONS
  19. Функция ATOM
  20. Функция EQ
  21. Функция NULL
  22. Что дальше?
  23. Язык функционального программирования лисп
  24. Содержание
  25. Архитектура и синтаксис
  26. Основные элементы языка
  27. Базовые символы, операторы и функции
  28. Типизация
  29. Парадигмы программирования в Лиспе
  30. Функциональное программирование
  31. Императивное (операторное) программирование
  32. Макропрограммирование
  33. Объектно-ориентированное программирование
  34. История
  35. Предпосылки
  36. Первые реализации
  37. Диалекты 1960-х — 1980-х годов
  38. MacLisp
  39. Interlisp
  40. Franz Lisp
  41. Scheme
  42. Zetalisp
  43. NIL и T
  44. Создание Common Lisp
  45. Новые диалекты
  46. ISLISP
  47. OpenLisp
  48. PicoLisp
  49. EuLisp
  50. newLisp
  51. Racket
  52. Диалекты для других сред
  53. Стандарт Common Lisp
  54. Основные особенности
  55. Дальнейшие модификации
  56. Примеры
  57. Временная шкала диалектов Лиспа
  58. Применение
  59. Языки-потомки
  60. Лисп-машины
  61. Лисп в СССР и России
  62. Видео

Функциональные языки программирования: LISP (Scheme/Racket) + Haskell. Использование рекурсии для решения задач

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

Противопоставляется парадигме императивного программирования, которая описывает процесс вычислений как последовательное изменение состояний (как в теории автоматов).

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

Сильная (строгая) и слабая типизация

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

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

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

Вариант данного языка широко используется в системе автоматизированного проектирования AutoCAD и называется AutoLISP

Основные преимущества функциональных языков:

Краткость и простота

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

Строгая типизация

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

Модульность

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

Функции — объекты вычисления

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

Чистота (нет побочных эффектов)

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

Отложенные (ленивые) вычисления

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

Скачивание и установка

Программы и данные неотличимы друг от друга — всё есть списки.

Программа на языке LISP — список. Первый элемент списка — имя функции которую надо вызвать, остальные — аргументы.

Сначала вычисляются аргументы.

Функция list конструирует список:

Условный оператор (больше похож на тернарный)

Конструирование списка из головы и конца:

Разберем и построим снова список L :

null? — пуст ли список?

Вычисление длины списка

Получить элемент списка L с номером n

Факториал Применить одну операцию ко всем элементам списка

(close-output-port out) — закрытие файла (нужно при работе в среде разработки)

Тексты программ на функциональных языках программирования описывают «как решить задачу», но не предписывают последовательность действий для решения.

Первым спроектированным функциональным языком стал Лисп.

Лисп является вторым в истории (после Фортрана) используемым по сей день высокоуровневым языком программирования.

Haskell

Концепция языка отражает идею математика Хаскелла Карри, писавшего, что «доказательство — это программа, а доказываемая формула — это тип программы». Именно в честь Х. Карри язык и получил своё название.

Источник

LISP. Атом первый

Привет, Хабр!
LISP заинтересовал меня уже давно, но, к сожалению, активно использовать свои знания и стремления на практике шанса не было. Скоро новый учебный год, а значит у меня опять будет возможность изучать и, уже второй год, преподавать студентам LISP. Еще одной проблемой, кроме традиционного отсутствия интереса к сложным вещам, кажется отсутствие литературы. Да и вообще, тема LISP-а в интернете, а тем более в рунете освещена слабо. Вот и на Хабре публикаций довольно мало.

Надеюсь, эта статья понравится общественности и откроет серию, повествующую об одном из наиболее интересных и наименее понятных (хотя до brainfuck и далеко) языков программирования – LISP. Ведь, как это не банально, еще один язык — еще одна жизнь

Начнем с базовых понятий LISP-а – атомов и списков. Немного позже, если будет интересно, в приквеле «Атоме нулевом» можно будет более подробно поговорить о философии и причинах возникновения LISP, а так же о современных направлениях его использования.

Краткая история

LISP был придуман Джоном Маккарти в 1958 году для решения задач нечислового характера и базировался на трех основных китах: алгебре списочных структур, лямбда исчислении, теории рекурсивных функций. Долгое время LISP использовался исключительно узким кругом специалистов по искусственному интеллекту. Но, начиная с 80-х годов прошлого века, LISP начал набирать обороты и сейчас активно используется, например, в AutoCad и Emacs.

Типы данных

Традиционно в LISP рассматривают два типа атомов: символы и числа. Символы могут обозначать числа, строки, сложные структуры, функции и другие объекты. Ограничения на имена символов зависят от используемого диалекта, но большинство из них не накладывает практически никаких ограничений на используемые в именах символы. Кроме того, опять же в большинстве диалектов, имена символов не зависят от регистра.
Некоторые символы имеют специальное назначение – это константы, встроенные функции, T (true, истина) и NIL (false, ложь).

Числа, в отличии от символов, не могут представлять другие объекты, таким образом число всегда является константным числом. Немного позже мы рассмотрим типы чисел в LISP.
Символы и числа представляют собой наиболее простые объекты LISP – атомы. Второй основной тип данных – точечные пары, которые синтаксически выражаются следующим образом:

Например, точечными парами являются выражения:

Атомы и точечные пары объединяют под общим названием S-выражения (S-expression, symbolic expression). Особым видом S-выражения является список, выражаемый следующим образом:

NIL в большинстве случаев определяется как пустой список, в таком случае определение списка можно переписать следующим образом:

Крылья, ноги… Главное хвост

И голова и хвост являются ключевыми понятиями в списочном контексте LISP. Первый элемент списка именуется головой списка, все остальные элементы – хвостом. Для работы с головой и хвостом существует набор базовых функций, рассмотренный немного ниже.
Пустой список эквивалентен паре пустых скобок:
NIL ().
Непустой список, состоящий из элементов a1, a2, a3… в соответствии с правилами записи S-выражений может быть записан следующим образом:

В LISP список можно записать и последовательностью элементов, заключенных в скобки и разделенных пробелами. По большему счету, список – это многоуровневая структура данных, для которой архиважна последовательность открывающих и закрывающих скобок.
Элементами списка могут быть атомы и списки, в том числе и пустой список. Например, () – пустой список, а (NIL) – список, состоящий из одного элемента NIL – что эквивалентно (()).
Следует понимать, что обычный синтаксис S-выражений может использоваться наравне со списочным синтаксисом, например, следующие выражение эквивалентны:

(a.(b.nil)), (a b.nil), (a b nil), (a b)

Если кому-нибудь интересно – можно будет рассказать и о внутреннем представлении списков в памяти. Это вполне самостоятельная и по интересу и по объему тема.

Основные функции и предикаты

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

Традиционном к базовым функциям относят QUOTE, CAR, CDR, CONS, ATOM, EQ.

Функция QUOTE

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

Функцию QUOTE можно записать и короче:

Функция CAR

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

Для удобство головой пустого списка считается NIL.

Фунция CDR

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

Хвостом списка является весь список без первого элемента. Если список состоит из одного элемента, хвостом будет NIL. Хвостом пустого списка для удобства так же считается nil.
Несколько примеров:

Функции CAR и CDR реализованы во всех диалектах LISP, но в некоторых для них созданы и синонимы: FIRST и REST, HEAD и TAIL).

Функция CONS

Фактически функция CONS является антиподом функций CAR и CDR:

Функция ATOM

ATOM и EQ являются предикатами – т.е. функциями, проверяющих соответствие аргумента некоторому свойству и возвращающими T или NIL в зависимости от успешности проверки.

Предикат ATOM проверяет, является ли объект, переданный в качестве аргумента, атомом:

atom (S-выражение)

Функция EQ

Предикат, проверяющий идентичность двух символов.

eq (атом, атом)

Следует помнить, что предикат EQ применим лишь к атомарным аргументам и не может быть использован для списков. Так же не следует использовать EQ при сравнении чисел.

Более общим по сравнению с EQ является предикат EQL, позволяющий сравнивать однотипный числа:

Еще более общим для чисел является предикат =, позволяющий сравнивать значения чисел различных типов:

Более общим для списков является предикат EQUAL, позволяющий сравнивать идентичность двух списков:

Наиболее общим предикатом является EQUALP, позволяющий сравнивать произвольные объекты.

Функция NULL

NULL проверяет, является ли объект, переданный в качестве аргумента, пустым списком:

Судя по двум последним примером, можно сделать вывод, что функцию NULL можно использовать и как логическое отрицание. Для этих же целей в LISP существует и предикат NOT.

Что дальше?

Надеюсь, что смог заинтересовать. В следующий раз я планирую рассказать о существующих диалектах LISP (хотя на первых порах достаточно будет университетского XLisp), менее часто используемых базовых функциях, сворачивании CAR и CDR в что-то вроде CAAAADDAAR и определении собственных функций. Позже — рекурсия, управляющие структуры, область действия, ввод-вывод. Еще позже — если не надоем — о функционалах, макросах, свойствах символов и замыканиях. Ну и конечно, о том, о чем попросит общественность.
До встречи!

Источник

Язык функционального программирования лисп

Язык функционального программирования лисп

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

Типизация

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

Язык функционального программирования лисп

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Среди промышленных известных объектно-ориентированных расширений Лиспа прежде всего следует назвать объектную подсистему 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 был языком обработки списков и предназначался для реализации проекта «Логик-теоретик» — системы искусственного интеллекта, предназначенной для автоматического вывода теорем математической логики. 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» был изобретённый Маккарти механизм, позволявший запускать интерпретатор Лиспа одновременно с выполнением обычных вычислительных работ в пакетном режиме (то, что сейчас известно как «система разделения времени»).

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

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

MacLisp

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

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

Система MAC Lisp эксплуатировалась и развивалась вплоть до 1980-х годов, оказав существенное влияние на появлявшиеся в 1960—1980 годах реализации Лиспа, в том числе став одним из источников проектирования стандарта Common Lisp. Эксплуатация системы практически прекратилась в 1980-х годах вместе с прекращением использования компьютеров PDP-10/20, на которых она изначально базировалась. Намного пережили систему разработанные на Маклиспе и уже упоминавшиеся 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 превратился в Interlisp (Интерлисп).

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

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

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

Лисп попал в Калифорнию вместе с Маккарти, перешедшим в Стенфорд в 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 — единственный «старый» диалект Лиспа, который продолжает использоваться после повсеместного перехода лисп-сообщества на стандартизованный Common Lisp. В настоящее время существует несколько поддерживаемых реализаций Scheme, в том числе свободных, есть примеры использования этого языка и в качестве встроенного (например, используемый в качестве средства создания скриптов GIMP Tiny-Scheme). В нескольких американских университетах Scheme используется как язык для базового обучения программированию.

Zetalisp

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

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

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

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

NIL и T

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

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

Создание 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

OpenLisp

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

PicoLisp

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

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

EuLisp

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

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

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). Поддерживается централизованный репозиторий для пакетов и расширений, созданных сообществом.

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

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

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

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

Стандарт 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 году:

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

Примеры

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

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

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

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

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

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

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

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

Диалекты языка программирования Лисп (править)

19551960196519701975198019851990199520002005201020152018
Lisp 1.5Lisp 1.5
MaclispMaclisp
InterlispInterlisp
ZetaLispLisp Machine Lisp
SchemeScheme
NILNIL
Common LispCommon Lisp
LeLispLe_Lisp
TT
Emacs LispEmacs Lisp
AutoLISPAutoLISP
OpenLispOpenLisp
PicoLispPicoLisp
EuLispEuLisp
ISLISPISLISP
newLISPnewLISP
RacketRacket
GuileGNU Guile
Visual LISPVisual LISP
ClojureClojure
ArcArc
LFELFE
HyHy

Применение

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

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

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

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

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

Лисп-машины

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

В США исследования по созданию Лисп-компьютера велись в 1970-х годах в двух местах — исследовательском центре Palo Alto, принадлежащем корпорации Xerox, и в MIT (последнее спонсировалось DARPA). Результатом стало появление в начале-середине 1980-х годов трёх основных производителей: Xerox, Lisp Mashine Inc. (LMI) и Symbolics Inc. 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). После распада СССР российское IT-сообщество достаточно быстро перешло на использование практически исключительно западной вычислительной техники и системного ПО. На сегодняшний день невозможно назвать ни одной Лисп-системы российского происхождения, которая находилась бы в эксплуатации.

Источник

Видео

Язык программирования Lisp №1: Введение

Язык программирования Lisp №1: Введение

Язык LISP для студентов и инженеров. Первая программа

Язык LISP для студентов и инженеров. Первая программа

А нахуя lisp нужен?

А нахуя lisp нужен?

Лекция №3. Язык функционального программирования Common Lisp

Лекция №3. Язык функционального программирования Common Lisp

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

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

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

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

История программирования. LISP, Пол Грэм и причем здесь BEL

История программирования.  LISP,  Пол Грэм и причем здесь  BEL

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

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

Никита Соболев: Функциональное программирование для новичков [Хекслет]

Никита Соболев: Функциональное программирование для новичков [Хекслет]

СИЛА Функционального Программирования / Всё о Scala / Интервью со Scala Developer Олегом Нижниковым

СИЛА Функционального Программирования / Всё о Scala / Интервью со Scala Developer Олегом Нижниковым
Поделиться или сохранить к себе:
Добавить комментарий

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