Лисп (язык программирования) - Lisp (programming language)

Лисп

Парадигма	Мультипарадигма: функциональный, процедурный, отражающий, мета
Разработано	Джон Маккарти
Разработчик	Стив Рассел, Тимоти П. Харт и Майк Левин
Впервые появился	1958; 62 года назад (1958)
Печатная дисциплина	Динамический, сильный
Диалекты
Дуга AutoLISP Clojure Common Lisp Emacs Lisp EuLisp Ференц Лисп Hy Интерлисп ISLISP LeLisp LFE Маклисп Лей newLISP Ноль Пиколисп Портативный стандартный Лисп Ракетка РПЛ Схема НАВЫК Spice Lisp Т Zetalisp
Под влиянием
IPL
Под влиянием
КЛИПЫ CLU КОУСЕЛЬ Дилан Эликсир Четвертый Haskell Ио Иоке JavaScript Юля[1] Логотип Lua ML Ним Nu OPS5 Perl ПОП-2 /11 Python р Ребол Рубин Scala Быстрый Болтовня Tcl Язык Wolfram Language[2]

Лисп (исторически LISP) - это семья языки программирования с долгой историей и отличительной, полностью в скобках префиксная запись.^[3]Первоначально указанный в 1958 году, Лисп является вторым по возрасту язык программирования высокого уровня широко используется сегодня. Только Фортран старше, на год.^[4][5] Lisp изменился с самого начала, и многие диалекты существовали на протяжении всей своей истории. Сегодня наиболее известными диалектами Лиспа общего назначения являются Ракетка, Common Lisp, Схема и Clojure.

Lisp изначально создавался как практический математическая запись за компьютерные программы, находящийся под влиянием (хотя и не происходящий от ^[6]) обозначение Церковь Алонсо с лямбда-исчисление. Он быстро стал излюбленным языком программирования для искусственный интеллект (AI) исследования. Как один из самых ранних языков программирования, Lisp впервые применил множество идей в Информатика, включая древовидные структуры данных, автоматическое управление хранилищем, динамическая типизация, условные, функции высшего порядка, рекурсия, то компилятор на собственном хостинге,^[7] и цикл чтения – оценки – печати.^[8]

Название LISP происходит от "LISt Processor".^[9] Связанные списки являются одними из основных структуры данных, и Лисп исходный код состоит из списков. Таким образом, программы на Лиспе могут манипулировать исходным кодом как структурой данных, что приводит к макрос системы, которые позволяют программистам создавать новый синтаксис или новые предметно-ориентированные языки встроен в Лисп.

Взаимозаменяемость кода и данных дает Лиспу мгновенно узнаваемый синтаксис. Весь программный код написан как s-выражения, или списки в скобках. Вызов функции или синтаксическая форма записываются в виде списка с именем функции или оператора вначале и последующими аргументами; например, функция ж который принимает три аргумента, будет называться (ж arg1 arg2 arg3).

История

Джон Маккарти (вверху) и Стив Рассел

Джон Маккарти разработал Lisp в 1958 году, когда работал в Массачусетский Институт Технологий (Массачусетский технологический институт). Маккарти опубликовал свой дизайн в статье в Коммуникации ACM в 1960 году под названием «Рекурсивные функции символьных выражений и их вычисление машиной, часть I».^[10] Он показал, что с помощью нескольких простых операторов и обозначения анонимных функций, заимствованных у Черча, можно построить Полный по Тьюрингу язык для алгоритмов.

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

Исходные обозначения Маккарти заключены в квадратные скобки "М-выражения "это будет переведено на S-выражения. Например, M-выражение автомобиль [минусы [A, B]] эквивалентно S-выражению (машина (минусы А B)). После того, как Lisp был реализован, программисты быстро решили использовать S-выражения, и M-выражения были оставлены. Снова всплыли М-выражения с кратковременными попытками MLisp^[11] к Гораций Энеа и CGOL к Воан Пратт.

Lisp был впервые реализован Стив Рассел на IBM 704 компьютер с использованием перфокарты.^[12] Рассел прочитал статью Маккарти и понял (к удивлению Маккарти), что Лисп оценка функция может быть реализована в Машинный код.^[13] Результатом стал работающий интерпретатор Лиспа, который можно было использовать для запуска программ на Лиспе или, точнее, «оценки выражений Лиспа».

Два макросы на языке ассемблера для IBM 704 стали примитивными операциями декомпозиции списков: машина (Содержание адресной части реестра номер) и CDR (Содержание декрементной части реестра номер),^[14] где "регистр" используется для обозначения регистры компьютерных центральное процессорное устройство (ЦПУ). Диалекты Лиспа все еще используют машина и CDR (/kɑːr/ и /ˈkʊdər/) для операций, которые возвращают первый элемент в списке и остальную часть списка соответственно.

Первый полный компилятор Лиспа, написанный на Лиспе, был реализован в 1962 году Тимом Хартом и Майком Левиным из Массачусетского технологического института.^[15] Этот компилятор представил Lisp-модель инкрементальной компиляции, в которой скомпилированные и интерпретируемые функции могут свободно смешиваться. Язык, используемый в записке Харта и Левина, намного ближе к современному стилю Лиспа, чем к более раннему коду Маккарти.

Первый вывоз мусора процедуры были разработаны аспирантом MIT Дэниел Эдвардс.^[16]

В течение 1980-х и 1990-х годов были предприняты большие усилия по унификации работы над новыми диалектами Лиспа (в основном преемниками диалектов Лиспа). Маклисп Такие как ZetaLisp и NIL (новая реализация Lisp) на одном языке. Новый язык, Common Lisp, был несколько совместим с диалектами, которые он заменил (книга Common Lisp язык отмечает совместимость различных конструкций). В 1994 г. ANSI опубликовал стандарт Common Lisp, "ANSI X3.226-1994, язык программирования информационных технологий Common Lisp".

График

Подключение к искусственному интеллекту

С самого начала Lisp был тесно связан с искусственный интеллект исследовательское сообщество, особенно PDP-10^[17] системы. Лисп использовался как реализация языка программирования Микро планировщик, который использовался в известной системе ИИ ШРДЛУ. В 1970-х годах, когда исследования AI породили коммерческие ответвления, производительность существующих систем Lisp стала растущей проблемой.^{[нужна цитата ]}

Генеалогия и варианты

За свою шестидесятилетнюю историю Lisp породил множество вариаций основной темы языка S-выражений. Более того, каждый данный диалект может иметь несколько реализаций - например, существует более десятка реализаций Common Lisp.

Различия между диалектами могут быть весьма заметными - например, Common Lisp использует ключевое слово defun чтобы назвать функцию, но Scheme использует определять.^[18] Однако внутри стандартизованного диалекта соответствующие реализации поддерживают один и тот же базовый язык, но с разными расширениями и библиотеками.

Исторически значимые диалекты

А Лисп-машина в Музей Массачусетского технологического института

4.3 BSD от Университет Висконсина, отображая страница руководства за Ференц Лисп

• LISP 1^[19] - Первая реализация.
• LISP 1.5^[16] - Первая широко распространенная версия, разработанная Маккарти и другими в Массачусетском технологическом институте. Назван так потому, что он содержал несколько улучшений исходного интерпретатора "LISP 1", но не представлял собой серьезную реструктуризацию, как планировалось. LISP 2 было бы.
• Стэнфордский LISP 1.6^[20] - Это был преемник LISP 1.5, разработанный в Стэнфордская лаборатория искусственного интеллекта, и широко распространены в PDP-10 системы, управляющие ТОП-10 Операционная система. Maclisp и InterLisp сделали его устаревшим.
• МАКЛИСП^[21] - разработан для MIT Проект MAC MACLISP является прямым потомком LISP 1.5. Он работал на PDP-10 и Мультики системы. MACLISP позже стал называться Maclisp и часто упоминается как MacLisp. «MAC» в MACLISP не имеет отношения к Apple Macintosh ни к Маккарти.
• Интерлисп^[22] - разработан в BBN Technologies для систем PDP-10 под управлением Операционная система Техас, позже принятый в качестве Lisp "Западного побережья" для машин Xerox Lisp как ИнтерЛисп-Д. Небольшая версия под названием «InterLISP 65» была опубликована для 6502 -основан Семейство 8-битных Atari компьютерная линия. Некоторое время Maclisp и InterLisp были сильными конкурентами.
• Ференц Лисп - изначально Калифорнийский университет в Беркли проект; позже разработано Franz Inc. Название представляет собой юмористическую деформацию имени "Ференц Лист ", и не относится к Аллегро Common Lisp, диалект Common Lisp, продаваемый Franz Inc. в последние годы.
• XLISP, который AutoLISP был основан на.
• Стандартный Лисп и Портативный стандартный Лисп широко использовались и переносились, особенно с системой компьютерной алгебры REDUCE.
• ZetaLisp, также называемый Lisp Machine Lisp - используется на Лисп-машины, прямой потомок Маклиспа. ZetaLisp оказал большое влияние на Common Lisp.
• LeLisp это французский диалект Лиспа. Один из первых Разработчики интерфейсов (так называемый интерфейс SOS^[23]) был написан на LeLisp.
• Схема (1975).^[24]
• Common Lisp (1984), как описано Common Lisp язык - объединение нескольких расходящихся попыток (ZetaLisp, Spice Lisp, Ноль, и S-1 Лисп ) для создания диалектов-преемников^[25] до Маклиспа, с существенным влиянием диалекта Схемы. Эта версия Common Lisp была доступна для самых разных платформ и была принята многими как стандарт де-факто^[26] до публикации ANSI Common Lisp (ANSI X3.226-1994). Среди наиболее распространенных поддиалектов Common Lisp: Стальной банк Common Lisp (SBCL), CMU Common Lisp (CMU-CL), Clozure OpenMCL (не путать с Clojure!), GNU CLisp и более поздние версии Franz Lisp; все они соответствуют более позднему стандарту ANSI CL (см. ниже).
• Дилан В своей первой версии представлял собой смесь Scheme с объектной системой Common Lisp.
• EuLisp - попытка разработать новый эффективный и очищенный Лисп.
• ISLISP - попытка разработать новый эффективный и очищенный Лисп. Стандартизован как ISO / IEC 13816: 1997^[27] и позже пересмотрен как ISO / IEC 13816: 2007:^[28] Информационные технологии. Языки программирования, их среды и интерфейсы системного программного обеспечения. Язык программирования ISLISP..
• IEEE Схема - Стандарт IEEE, 1178–1990 (R1995)
• ANSI Common Lisp - ан Американский национальный институт стандартов (ANSI) стандарт для Common Lisp, созданный подкомитетом X3J13, зафрахтованный^[29] начать с Common Lisp: язык как базовый документ и работать через общедоступный консенсус процесс поиска решений общих проблем переносимость программ и совместимость реализаций Common Lisp. Хотя формально это стандарт ANSI, реализация, продажа, использование и влияние ANSI Common Lisp были и продолжают наблюдаться во всем мире.
• ACL2 или «Вычислительная логика для аппликативного Common Lisp», аппликативный (свободный от побочных эффектов) вариант Common LISP. ACL2 - это и язык программирования, который может моделировать компьютерные системы, и инструмент, помогающий доказывать свойства этих моделей.
• Clojure, недавний диалект Лиспа, который компилируется в Виртуальная машина Java и уделяет особое внимание параллелизм.
• Игровой ассемблер Lisp (или GOAL) - язык программирования видеоигр, разработанный Энди Гэвином и Джек и Дакстер команда в Игривый щенок. Он был написан с использованием Allegro Common Lisp и использовался при разработке всего Серия игр Jak and Daxter.

2000, чтобы представить

После некоторого упадка в 1990-х годах, Lisp снова начал интересоваться после 2000 года. Большая часть новой деятельности была сосредоточена вокруг реализации Common Lisp, Схема, Emacs Lisp, Clojure, и Ракетка, и включает разработку новых переносимых библиотек и приложений.

Многие начинающие программисты на Лиспе были вдохновлены такими писателями, как Пол Грэм и Эрик С. Раймонд изучать язык, который другие считали устаревшим. Программисты-новички в Lisp часто описывают язык как открывающий им глаза опыт и утверждают, что он значительно более продуктивен, чем на других языках.^[30] Этот рост осведомленности можно противопоставить "AI зима "и кратковременный успех Lisp в середине 1990-х годов.^[31]

Дэн Вайнреб в своем обзоре реализаций Common Lisp перечисляет^[32] одиннадцать активно поддерживали реализации Common Lisp. Scieneer Common Lisp - это новая коммерческая реализация, созданная на основе CMUCL с первым выпуском в 2002 году.

В Открытый исходный код Сообщество создало новую вспомогательную инфраструктуру: CLiki это вики, которая собирает информацию, относящуюся к Common Lisp, Каталог Common Lisp перечисляет ресурсы, #lisp - популярный канал IRC, позволяющий публиковать и комментировать фрагменты кода (при поддержке лиспаста, IRC бот написано на Лиспе), Планета Лисп собирает содержимое различных блогов, связанных с Lisp, на LispForum пользователи обсуждают темы Lisp, Lispjobs это сервис для объявления предложений о работе и есть еженедельная служба новостей, Еженедельные новости Lisp. Common-lisp.net - это хостинг для проектов Common Lisp с открытым исходным кодом. Quicklisp это менеджер библиотеки Common Lisp.

50 лет Lisp (1958–2008) отмечалось на LISP50 @ OOPSLA.^[33] Регулярно проводятся встречи местных пользователей в Бостоне, Ванкувере и Гамбурге. Другие мероприятия включают Европейскую встречу по Лиспу, Европейский симпозиум по Лиспу и Международную конференцию по Лисп.

Сообщество Scheme активно поддерживает более двадцати внедрений. Несколько важных новых реализаций (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) были разработаны в 2000-х годах (десятилетие). Пересмотренный⁵ Отчет по алгоритмической языковой схеме^[34] Стандарт Scheme был широко принят в сообществе Scheme. В Схема запросов на реализацию Процесс создал множество квазистандартных библиотек и расширений для Scheme. Сообщества пользователей отдельных реализаций схем продолжают расти. Новый процесс стандартизации языка был начат в 2003 году и привел к тому, что R⁶Стандарт RS Scheme в 2007 году. Академическое использование Scheme для обучения информатике, похоже, несколько уменьшилось. Некоторые университеты больше не используют Scheme в своих вводных курсах по информатике;^[35][36] MIT теперь использует Python вместо схемы для студентов Информатика программа и массовый открытый онлайн-курс MITx.^[37][38]

Есть несколько новых диалектов Лиспа: Дуга, Hy, Nu, Лискелл, и LFE (Erlang со вкусом Lisp). Парсер для Юля реализован на фемтолиспе, диалекте Схема (Джулия вдохновлена ​​Scheme, которая, в свою очередь, является диалектом Лиспа).

В октябре 2019 года Пол Грэм выпустил спецификация для Bel, «новый диалект Лиспа».

Основные диалекты

Common Lisp и Схема представляют два основных потока разработки Lisp. Эти языки воплощают в себе существенно разные варианты дизайна.

Common Lisp является преемником Маклисп. Основное влияние было Лисп-машина Лисп, Маклисп, Ноль, S-1 Лисп, Spice Lisp, и Схема.^[39] Он имеет многие особенности Lisp Machine Lisp (большой диалект Lisp, используемый для программирования Машины Лисп ), но был разработан для эффективной реализации на любом персональном компьютере или рабочей станции. Common Lisp - это язык программирования общего назначения и, следовательно, имеет большой стандарт языка, включающий множество встроенных типов данных, функций, макросов и других языковых элементов, а также объектную систему (Общая объектная система Lisp ). Common Lisp также позаимствовал некоторые функции из Scheme, такие как лексическая область видимости и лексические замыкания. Доступны реализации Common Lisp для различных платформ, таких как LLVM,^[40] то Виртуальная машина Java,^[41]x86-64, PowerPC, Alpha, ARM, Motorola 68000 и MIPS,^[42] и операционные системы, такие как Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD и Heroku.^[43]

Схема - это статически ограниченный и правильно рекурсивный диалект языка программирования Lisp, изобретенный Гай Л. Стил-младший. и Джеральд Джей Сассман. Он был разработан, чтобы иметь исключительно ясную и простую семантику и несколько различных способов формирования выражений. Разработанный примерно на десять лет раньше Common Lisp, Схема более минималистичный дизайн. Он имеет гораздо меньший набор стандартных функций, но с некоторыми функциями реализации (такими как оптимизация хвостового вызова и полный продолжения ) не указан в Common Lisp. Широкий спектр парадигм программирования, включая императивный, функциональный и стиль передачи сообщений, находит удобное выражение в Scheme. Scheme продолжает развиваться с рядом стандартов (пересмотренный^п Report on the Algorithmic Language Scheme) и серию Схема запросов на реализацию.

Clojure - недавний диалект Лиспа, ориентированный в основном на Виртуальная машина Java, а общеязыковая среда выполнения (CLR), Python ВМ, Ruby VM YARV, и компилируем в JavaScript. Он разработан как прагматичный язык общего назначения. Clojure сильно зависит от Haskell и уделяет очень большое внимание неизменности.^[44] Clojure предоставляет доступ к фреймворкам и библиотекам Java, с дополнительными подсказками типов и вывод типа, так что вызовы Java могут избежать отражения и включить быстрые примитивные операции. Clojure не предназначен для обратной совместимости с другими диалектами Лиспа.^[45]

Далее диалекты Лиспа используются как языки сценариев во многих приложениях, наиболее известным из которых является Emacs Lisp в Emacs редактор, AutoLISP и позже Визуальный Лисп в AutoCAD, Найквист в Мужество, Схема в Лилипруд. Потенциально небольшой размер полезного интерпретатора схемы делает его особенно популярным для встраиваемых сценариев. Примеры включают SIOD и TinyScheme, оба из которых были успешно встроены в GIMP обработчик изображений под общим названием «Скрипт-фу».^[46] LIBREP, интерпретатор Лиспа Джона Харпера, первоначально основанный на Emacs Lisp язык, был встроен в Рыба-пила оконный менеджер.^[47]

Стандартизированные диалекты

Лисп имеет официально стандартизованные диалекты: Схема R6RS, Схема R7RS, Схема IEEE,^[48] ANSI Common Lisp и ISO ISLISP.

Языковые инновации

Лисп был первым языком, в котором структура программного кода точно и прямо представлена ​​в стандартной структуре данных - качество, которое позже было названо "гомоиконность ". Таким образом, функциями Lisp можно манипулировать, изменять или даже создавать в программе Lisp без манипуляций нижнего уровня. Это обычно считается одним из основных преимуществ языка в отношении его выразительной силы и делает язык пригодным для синтаксических макросы и метациркулярная оценка.

Условное использование если – то – еще синтаксис был изобретен Маккарти в контексте Фортрана. Он предложил включить его в АЛГОЛ, но это не было частью Алгол 58 Технические характеристики. Для Лиспа Маккарти использовал более общий cond-структура.^[49] Алгол 60 взял если – то – еще и популяризировал это.

Lisp сильно повлиял Алан Кей, руководитель исследовательской группы, которая разработала Болтовня в Xerox PARC; и, в свою очередь, на Лисп повлиял Smalltalk, а в более поздних диалектах в 1970-х годах были приняты функции объектно-ориентированного программирования (классы наследования, инкапсуляция экземпляров, передача сообщений и т. д.). В Ароматизаторы объектная система ввела понятие множественное наследование и миксин. В Общая объектная система Lisp обеспечивает множественное наследование, мультиметоды с множественная отправка, и первоклассный общие функции, давая гибкую и мощную форму динамическая отправка. Он служил шаблоном для многих последующих Лиспов (включая Схема ) объектные системы, которые часто реализуются через протокол метаобъектов, а отражающий метакруглый дизайн в котором объектная система определяется в терминах самого себя: Lisp был лишь вторым языком после Smalltalk (и все еще одним из очень немногих языков), обладающим такой системой метаобъектов. Много лет спустя Алан Кей предположил, что в результате слияния этих функций только Smalltalk и Lisp можно рассматривать как правильно задуманные системы объектно-ориентированного программирования.^[50]

Lisp представил концепцию автоматический сбор мусора, в котором система проходит куча ищу неиспользуемую память. Прогресс в современных сложных алгоритмах сборки мусора, таких как сборка мусора поколений, был стимулирован ее использованием в Лиспе.^[51]

Эдсгер В. Дейкстра в его 1972 Премия Тьюринга лекция сказала,

«Имея в основе несколько очень простых принципов, он [LISP] продемонстрировал замечательную стабильность. Кроме того, LISP был носителем значительного числа в некотором смысле наших самых сложных компьютерных приложений. LISP в шутку был описан как« самый разумный способ злоупотребления компьютером ». Я считаю это описание отличным комплиментом, потому что оно передает весь аромат освобождения: оно помогло ряду наших наиболее одаренных собратьев-людей в размышлениях о ранее невозможных мыслях».^[52]

Во многом из-за требований к ресурсам относительно раннего вычислительного оборудования (включая ранние микропроцессоры) Lisp не стал таким популярным за пределами AI сообщество как Фортран и АЛГОЛ - спустился C язык. Благодаря своей пригодности для сложных и динамических приложений, Lisp в 2010-х годах снова стал популярным.^[53]

Синтаксис и семантика

Примечание: Примеры в этой статье написаны на Common Lisp (хотя большинство из них также действительны в Схема ).

Символьные выражения (S-выражения)

Лисп - это экспрессионно-ориентированный язык. В отличие от большинства других языков, не делается различия между «выражениями» и "заявления";^{[сомнительный – обсуждать]} весь код и данные записываются в виде выражений. Когда выражение оценен, он производит значение (в Common Lisp, возможно, несколько значений), которое затем может быть встроено в другие выражения. Каждое значение может быть любым типом данных.

В статье Маккарти 1958 года были представлены два типа синтаксиса: Символические выражения (S-выражения, sexps), которые отражают внутреннее представление кода и данных; и Мета-выражения (М-выражения ), которые выражают функции S-выражений. M-выражения никогда не пользовались популярностью, и почти все Lisp сегодня используют S-выражения для управления как кодом, так и данными.

Использование круглых скобок - это наиболее очевидное отличие Лиспа от других семейств языков программирования. В результате студенты давно дали Lisp псевдонимы, такие как Потеряны в дурацких скобках, или же Множество раздражающих лишних скобок.^[54] Однако синтаксис S-выражения также отвечает за большую часть возможностей Лиспа: синтаксис чрезвычайно регулярный, что облегчает манипуляции с компьютером. Однако синтаксис Лиспа не ограничивается традиционными скобками. Его можно расширить, включив альтернативные обозначения. Например, XMLisp - это расширение Common Lisp, которое использует протокол метаобъектов для интеграции S-выражений с Extensible Markup Language (XML ).

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

Списки

Список Лиспа записывается с элементами, разделенными пробел, и заключен в круглые скобки. Например, (1 2 фу) это список, элементами которого являются три атомы 1, 2, и фу. Эти значения неявно типизированы: они представляют собой соответственно два целых числа и специфичный для Лиспа тип данных, называемый «символом», и их не нужно объявлять как таковые.

Пустой список () также представлен как специальный атом ноль. Это единственная сущность в Лиспе, которая одновременно является атомом и списком.

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

 (список 1 2 (Цитировать фу))

оценивает список (1 2 фу). "Цитата" перед фу в предыдущем примере - это «специальный оператор», который возвращает свой аргумент, не оценивая его. Любые выражения, не заключенные в кавычки, рекурсивно вычисляются перед вычислением включающего выражения. Например,

 (список 1 2 (список 3 4))

оценивает список (1 2 (3 4)). Обратите внимание, что третий аргумент - это список; списки могут быть вложенными.

Операторы

Аналогично рассматриваются арифметические операторы. Выражение

 (+ 1 2 3 4)

оценивается в 10. Эквивалент под инфиксная запись было бы "1 + 2 + 3 + 4".

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

 (incf Икс)

эквивалентно (установить q x (+ x 1)), возвращая новое значение Икс.

«Специальные операторы» (иногда называемые «специальными формами») обеспечивают структуру управления Лиспа. Например, специальный оператор если принимает три аргумента. Если первый аргумент не равен нулю, он оценивает второй аргумент; в противном случае вычисляется третий аргумент. Таким образом, выражение

 (если ноль     (список 1 2 "фу")     (список 3 4 "бар"))

оценивает (3 4 "бар"). Конечно, это было бы более полезно, если бы вместо выражения было подставлено нетривиальное выражение. ноль.

Lisp также предоставляет логические операторы и, или же и нет. В и и или же операторы делают оценка короткого замыкания и вернет свой первый аргумент nil и ненулевой аргумент соответственно.

 (или же (и "нуль" ноль "никогда") "Джеймс" 'задача 'время)

оценит "Джеймсу".

Лямбда-выражения и определение функции

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

 (лямбда (аргумент) (+ аргумент 1))

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

 ((лямбда (аргумент) (+ аргумент 1)) 5)

оценивает 6. Здесь мы выполняем приложение-функцию: мы выполняем анонимная функция передав ему значение 5.

Именованные функции создаются путем сохранения лямбда-выражения в символе с использованием defun макрос.

 (defun фу (а б c d) (+ а б c d))

(defun ж (а) б ...) определяет новую функцию с именем ж в глобальной среде. Концептуально оно похоже на выражение:

 (setf (f определение 'е) #'(лямбда (а) (блокировать ж б ...)))

куда setf макрос, используемый для установки значения первого аргумента f определение 'е к новому объекту функции. f определение - определение глобальной функции для функции с именем ж. #' это сокращение от функция специальный оператор, возвращающий объект функции.

Атомы

В оригинале LISP было два основных типы данных: атомы и списки. Список представлял собой конечную упорядоченную последовательность элементов, где каждый элемент был либо атомом, либо списком, а атом был номер или символ. По сути, символ представлял собой предмет с уникальным названием, записанный как буквенно-цифровой строка в исходный код, и используется либо как имя переменной, либо как элемент данных в символическая обработка. Например, список (FOO (БАР 1) 2) содержит три элемента: символ FOO, список (БАР 1), и число 2.

Существенная разница между атомами и списками заключалась в том, что атомы неизменны и уникальны. Два атома, которые появлялись в разных местах исходного кода, но были написаны одинаково, представляли один и тот же объект,^{[нужна цитата ]} тогда как каждый список был отдельным объектом, который можно было изменять независимо от других списков и отличать от других списков с помощью операторов сравнения.

Поскольку в более поздних диалектах Лиспа было введено больше типов данных, стили программирования В ходе эволюции концепция атома потеряла значение.^{[нужна цитата ]} Многие диалекты по-прежнему сохранили сказуемое атом за совместимость с наследием,^{[нужна цитата ]} определение его истинным для любого объекта, который не является минусом.

Консультации и списки

Коробка и-указатель диаграмма для списка (42 69 613)

Список Лиспа реализован как односвязный список.^[55] Каждая ячейка этого списка называется минусы (на схеме a пара) и состоит из двух указатели, называется машина и CDR. Они соответственно эквивалентны данные и следующий поля, обсуждаемые в статье связанный список.

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

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

Таким образом, список Лиспа не является атомарным объектом, как экземпляр класса контейнера в C ++ или Java. Список - это не что иное, как совокупность связанных запросов. Переменная, которая ссылается на данный список, является просто указателем на первые минусы в списке. Обход списка может быть выполнен с помощью спуститься список; то есть брать последовательные компакт-диски для посещения каждого минуса списка; или используя любой из нескольких функции высшего порядка для отображения функции в списке.

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

S-выражения представляют собой списки

Заключенные в скобки S-выражения представляют структуры связанных списков. Есть несколько способов представить один и тот же список в виде S-выражения. Минусы можно написать на обозначение пары точек в качестве (а . б), куда а это машина и б CDR. Можно написать более длинный правильный список (а . (б . (c . (d . ноль)))) в обозначении пары точек. Это условно обозначается как (а б c d) в обозначение списка. Неправильный список^[56] может быть записано в сочетании двух - как (а б c . d) для списка из трех conses, последний cdr которых d (т.е. список (а . (б . (c . d))) в полностью указанной форме).

Процедуры обработки списков

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

 (список 1 2 'а 3) ; Выход: (1 2 a 3)

 (список 1 '(2 3) 4) ; Выход: (1 (2 3) 4)

Поскольку списки строятся из минусы пары, то минусы Процедура может использоваться для добавления элемента в начало списка. Обратите внимание, что минусы Процедура асимметрична в том, как она обрабатывает аргументы списка, из-за того, как списки построены.

 (минусы 1 '(2 3)) ; Выход: (1 2 3)

 (минусы '(1 2) '(3 4)) ; Выход: ((1 2) 3 4)

В добавить процедура добавляет два (или более) списка друг к другу. Поскольку списки Лиспа являются связными списками, добавление двух списков имеет асимптотическая временная сложность ${ Displaystyle О (п)}$

 (добавить '(1 2) '(3 4)) ; Выход: (1 2 3 4)

 (добавить '(1 2 3) '() '(а) '(5 6)) ; Выход: (1 2 3 a 5 6)

Общая структура

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

(setf фу (список 'а 'б 'c))(setf бар (минусы 'Икс (CDR фу)))

списки фу и бар находятся (а б c) и (Икс б c) соответственно. Однако хвост (б c) одинаковая структура в обоих списках. Это не копия; cons-ячейки, указывающие на б и c находятся в одинаковых ячейках памяти для обоих списков.

Совместное использование структуры вместо копирования может значительно улучшить производительность. Однако этот метод может нежелательным образом взаимодействовать с функциями, которые изменяют списки, переданные им в качестве аргументов. Изменение одного списка, например, замена c с Гусь, повлияет на другое:

 (setf (в третьих фу) 'Гусь)

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

Поклонники функциональное программирование избегать деструктивных функций. В диалекте Scheme, который отдает предпочтение функциональному стилю, имена деструктивных функций помечаются предупреждающим восклицательным знаком или «взрывом» - например, поставил машину! (читать установить машину), который заменяет автомобиль из минусов. В диалекте Common Lisp деструктивные функции являются обычным явлением; эквивалент поставил машину! назван rplaca для «заменить автомобиль». Однако эта функция встречается редко, поскольку Common Lisp включает в себя специальное средство, setf, чтобы упростить определение и использование деструктивных функций. Часто в Common Lisp используется стиль написания кода функционально (без деструктивных вызовов) при создании прототипа, а затем добавление деструктивных вызовов в качестве оптимизации, где это безопасно.

Формы самооценки и цитирование

Lisp оценивает выражения, которые вводит пользователь. Символы и списки оцениваются как другое (обычно более простое) выражение - например, символ оценивается как значение переменной, которую он называет; (+ 2 3) оценивает 5. Однако большинство других форм оценивают сами себя: если вводятся 5 в Лисп он возвращает 5.

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

И Common Lisp, и Scheme также поддерживают обратная цитата оператор (называемый квазицитат на схеме), введенный с ` персонаж (серьезный акцент ). Это почти то же самое, что и обычная кавычка, за исключением того, что она позволяет вычислять выражения и их значения вставлять в список в кавычках с запятой. , не цитировать и запятая-в ,@ сращивание операторы. Если переменная snue имеет ценность (бар баз) тогда `(фу ,snue) оценивает (фу (бар баз)), пока `(фу ,@snue) оценивает (фу бар баз). Обратные кавычки чаще всего используются при определении расширений макросов.^[57][58]

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

(defun должен быть постоянным ()  '(один два три))(позволять ((вещи (должен быть постоянным)))  (setf (в третьих вещи) 'причудливый))   ; Плохо!(должен быть постоянным)   ; возвращается (один, два странных)

Изменение такой формы в кавычках обычно считается плохим стилем и определяется ANSI Common Lisp как ошибочное (приводящее к «неопределенному» поведению в скомпилированных файлах, потому что компилятор файла может объединять похожие константы, помещать их в защищенную от записи память, так далее.).

Формализация цитаты в Lisp была отмечена Дуглас Хофштадтер (в Гедель, Эшер, Бах ) и другие как пример философский Идея ссылка на себя.

Объем и закрытие

Семейство Lisp раскололось из-за использования динамичный или же статический (он же лексический) объем. Clojure, Common Lisp и Scheme по умолчанию используют статическую область видимости, а newLISP, Пиколисп и встроенные языки в Emacs и AutoCAD использовать динамическую область видимости. Начиная с версии 24.1 Emacs использует как динамическую, так и лексическую область видимости.

Списочная структура программного кода; использование макросами и компиляторами

Фундаментальное отличие Лиспа от других языков заключается в том, что в Лиспе текстовое представление программы - это просто удобочитаемое описание тех же внутренних структур данных (связанных списков, символов, чисел, символов и т. Д.), Которые будут использоваться базовая система Lisp.

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

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

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

В упрощенных реализациях Лиспа эта структура списка напрямую интерпретированный запустить программу; функция - это буквально часть структуры списка, через которую интерпретатор проходит при ее выполнении. Однако наиболее существенные системы Lisp также включают компилятор. Компилятор переводит структуру списка в машинный код или байт-код для исполнения. This code can run as fast as code compiled in conventional languages such as C.

Macros expand before the compilation step, and thus offer some interesting options. If a program needs a precomputed table, then a macro might create the table at compile time, so the compiler need only output the table and need not call code to create the table at run time. Some Lisp implementations even have a mechanism, eval-when, that allows code to be present during compile time (when a macro would need it), but not present in the emitted module.^[59]

Evaluation and the read–eval–print loop

Lisp languages are often used with an interactive командная строка, which may be combined with an интегрированная среда развития (IDE). The user types in expressions at the command line, or directs the IDE to transmit them to the Lisp system. Лисп reads the entered expressions, оценивает them, and отпечатки the result. For this reason, the Lisp command line is called a цикл чтения – оценки – печати (REPL ).

The basic operation of the REPL is as follows. This is a simplistic description which omits many elements of a real Lisp, such as quoting and macros.

В читать function accepts textual S-expressions as input, and parses them into an internal data structure. For instance, if you type the text (+ 1 2) at the prompt, читать translates this into a linked list with three elements: the symbol +, the number 1, and the number 2. It so happens that this list is also a valid piece of Lisp code; that is, it can be evaluated. This is because the car of the list names a function—the addition operation.

Обратите внимание, что фу will be read as a single symbol. 123 will be read as the number one hundred and twenty-three. "123" will be read as the string "123".

В оценка function evaluates the data, returning zero or more other Lisp data as a result. Evaluation does not have to mean interpretation; some Lisp systems compile every expression to native machine code. It is simple, however, to describe evaluation as interpretation: To evaluate a list whose car names a function, оценка first evaluates each of the arguments given in its cdr, then applies the function to the arguments. In this case, the function is addition, and applying it to the argument list (1 2) yields the answer 3. This is the result of the evaluation.

Символ фу evaluates to the value of the symbol foo. Data like the string "123" evaluates to the same string. Список (Цитировать (1 2 3)) evaluates to the list (1 2 3).

Это работа Распечатать function to represent output to the user. For a simple result such as 3 this is trivial. An expression which evaluated to a piece of list structure would require that Распечатать traverse the list and print it out as an S-expression.

To implement a Lisp REPL, it is necessary only to implement these three functions and an infinite-loop function. (Naturally, the implementation of оценка will be complex, since it must also implement all special operators like если или же лямбда.) This done, a basic REPL is one line of code: (петля (Распечатать (оценка (читать)))).

The Lisp REPL typically also provides input editing, an input history, error handling and an interface to the debugger.

Lisp is usually evaluated с нетерпением. В Common Lisp, arguments are evaluated in аппликативный порядок ('leftmost innermost'), while in Схема order of arguments is undefined, leaving room for optimization by a compiler.

Структуры управления

Lisp originally had very few control structures, but many more were added during the language's evolution. (Lisp's original conditional operator, cond, is the precursor to later если-то-еще structures.)

Programmers in the Scheme dialect often express loops using tail recursion. Scheme's commonality in academic computer science has led some students to believe that tail recursion is the only, or the most common, way to write iterations in Lisp, but this is incorrect. All oft-seen Lisp dialects have imperative-style iteration constructs, from Scheme's делать loop to Common Lisp 's complex петля выражения. Moreover, the key issue that makes this an objective rather than subjective matter is that Scheme makes specific requirements for the handling of tail calls, and thus the reason that the use of tail recursion is generally encouraged for Scheme is that the practice is expressly supported by the language definition. By contrast, ANSI Common Lisp does not require^[60] the optimization commonly termed a tail call elimination. Thus, the fact that tail recursive style as a casual replacement for the use of more traditional итерация constructs (such as делать, dolist или же петля) is discouraged^[61] in Common Lisp is not just a matter of stylistic preference, but potentially one of efficiency (since an apparent tail call in Common Lisp may not compile as a simple Прыгать ) and program correctness (since tail recursion may increase stack use in Common Lisp, risking переполнение стека ).

Some Lisp control structures are специальные операторы, equivalent to other languages' syntactic keywords. Expressions using these operators have the same surface appearance as function calls, but differ in that the arguments are not necessarily evaluated—or, in the case of an iteration expression, may be evaluated more than once.

In contrast to most other major programming languages, Lisp allows implementing control structures using the language. Several control structures are implemented as Lisp macros, and can even be macro-expanded by the programmer who wants to know how they work.

Both Common Lisp and Scheme have operators for non-local control flow. The differences in these operators are some of the deepest differences between the two dialects. Scheme supports повторно въезжающий продолжения с использованием вызов / cc procedure, which allows a program to save (and later restore) a particular place in execution. Common Lisp does not support re-entrant continuations, but does support several ways of handling escape continuations.

Often, the same algorithm can be expressed in Lisp in either an imperative or a functional style. As noted above, Scheme tends to favor the functional style, using tail recursion and continuations to express control flow. However, imperative style is still quite possible. The style preferred by many Common Lisp programmers may seem more familiar to programmers used to structured languages such as C, while that preferred by Schemers more closely resembles pure-functional languages such as Haskell.

Because of Lisp's early heritage in list processing, it has a wide array of higher-order functions relating to iteration over sequences. In many cases where an explicit loop would be needed in other languages (like a за loop in C) in Lisp the same task can be accomplished with a higher-order function. (The same is true of many functional programming languages.)

A good example is a function which in Scheme is called карта and in Common Lisp is called mapcar. Given a function and one or more lists, mapcar applies the function successively to the lists' elements in order, collecting the results in a new list:

 (mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))

This applies the + function to each corresponding pair of list elements, yielding the result (11 22 33 44 55).

Примеры

Here are examples of Common Lisp code.

The basic "Hello, World! " program:

(Распечатать "Привет, мир!")

Lisp syntax lends itself naturally to recursion. Mathematical problems such as the enumeration of recursively defined sets are simple to express in this notation. For example, to evaluate a number's факториал:

(defun факториал (п)    (если (= п 0) 1        (* п (факториал (- п 1)))))

An alternative implementation takes less stack space than the previous version if the underlying Lisp system optimizes tail recursion:

(defun факториал (п &optional (acc 1))    (если (= п 0) acc        (факториал (- п 1) (* acc п))))

Contrast the examples above with an iterative version which uses Common Lisp с петля macro:

(defun факториал (п)    (петля за я из 1 к п        за фак = 1 тогда (* фак я)        наконец-то (возвращаться фак)))

The following function reverses a list. (Lisp's built-in обеспечить регресс function does the same thing.)

(defun -reverse (список)    (позволять ((return-value '()))      (dolist (е список) (толкать е return-value))      return-value))

Object systems

Various object systems and models have been built on top of, alongside, or into Lisp, including:

• В Общая объектная система Lisp, CLOS, is an integral part of ANSI Common Lisp. CLOS descended from New Flavors and CommonLOOPS. ANSI Common Lisp was the first standardized object-oriented programming language (1994, ANSI X3J13).
• ObjectLisp^[62] или же Объект Лисп, использован Lisp Machines Incorporated and early versions of Macintosh Common Lisp
• LOOPS (Lisp Object-Oriented Programming System) and the later CommonLOOPS
• Ароматизаторы, построенный в Массачусетский технологический институт, and its descendant New Flavors (developed by Символика ).
• KR (short for Knowledge Representation), a ограничения -based object system developed to aid the writing of Garnet, a GUI library for Common Lisp.
• Инженерная среда знаний (KEE) used an object system called UNITS and integrated it with an Механизм логического вывода^[63] и truth maintenance system (ATMS).

Смотрите также

• Самомодифицирующийся код

Рекомендации

дальнейшее чтение

внешняя ссылка

История

• History of Lisp – Джон Маккарти 's history of 12 February 1979
• Lisp History – Herbert Stoyan's history compiled from the documents (acknowledged by McCarthy as more complete than his own, see: McCarthy's history links )
• History of LISP at the Computer History Museum

Associations and meetings

• Association of Lisp Users
• European Common Lisp Meeting
• European Lisp Symposium
• International Lisp Conference

Books and tutorials

• Casting SPELs in Lisp, a comic-book style introductory tutorial
• На Лиспе, a free book by Пол Грэм
• Практический Common Lisp, freeware edition by Peter Seibel
• Lisp for the web
• Land of Lisp
• Let over Lambda

Интервью

• Oral history interview with John McCarthy в Институт Чарльза Бэббиджа, Университет Миннесоты, Миннеаполис. McCarthy discusses his role in the development of time-sharing at the Massachusetts Institute of Technology. He also describes his work in artificial intelligence (AI) funded by the Advanced Research Projects Agency, including logic-based AI (LISP) and robotics.
• Опрос с Ричард П. Габриэль (Подкаст)

Ресурсы

• CLiki: the Common Lisp wiki
• The Common Lisp Directory (через Wayback Machine; заархивировано из оригинал )
• Lisp FAQ Index
• lisppaste
• Planet Lisp
• Weekly Lisp News
• newLISP - A modern, general-purpose scripting language
• Лисп в Керли