Lisp (исторически LISP , сокращение от «обработка списков») — это семейство языков программирования с долгой историей и отличительной, полностью заключенной в скобки префиксной нотацией . [3] Первоначально описанный в конце 1950-х годов, это второй старейший язык программирования высокого уровня, который до сих пор широко используется, после Fortran . [4] [5] Lisp изменился с момента своего появления, и за его историю существовало множество диалектов . Сегодня наиболее известными диалектами Lisp общего назначения являются Common Lisp , Scheme , Racket и Clojure . [6] [7] [8]
Lisp изначально был создан как практическая математическая нотация для компьютерных программ , под влиянием (хотя изначально не производной от) [9] нотации лямбда-исчисления Алонзо Чёрча . Он быстро стал излюбленным языком программирования для исследований искусственного интеллекта (ИИ). [10] Будучи одним из самых ранних языков программирования, Lisp стал пионером многих идей в компьютерной науке , включая древовидные структуры данных , автоматическое управление хранилищем , динамическую типизацию , условные операторы , функции высшего порядка , рекурсию , самостоятельный компилятор [11] и цикл чтение–вычисление–печать . [12]
Название LISP происходит от "LISt Processor". [13] Связанные списки являются одной из основных структур данных Lisp , а исходный код Lisp состоит из списков. Таким образом, программы Lisp могут манипулировать исходным кодом как структурой данных, что приводит к появлению макросистем , которые позволяют программистам создавать новый синтаксис или новые предметно-ориентированные языки, встроенные в Lisp.
Взаимозаменяемость кода и данных дает Lisp его мгновенно узнаваемый синтаксис. Весь программный код записывается как s-выражения или списки в скобках. Вызов функции или синтаксическая форма записывается как список с именем функции или оператора в начале и аргументами за ними; например, функция f, которая принимает три аргумента, будет вызываться как .(f arg1 arg2 arg3)
Джон Маккарти начал разрабатывать Lisp в 1958 году, когда он работал в Массачусетском технологическом институте (MIT). Маккарти опубликовал его проект в статье в Communications of the ACM в апреле 1960 года под названием «Рекурсивные функции символических выражений и их вычисление машиной, часть I». [14] Он показал, что с помощью нескольких простых операторов и нотации для анонимных функций, заимствованной у Чёрча, можно построить полный по Тьюрингу язык для алгоритмов.
Язык обработки информации был первым языком искусственного интеллекта , появившимся в 1955 или 1956 году, и уже включал в себя многие концепции, такие как обработка списков и рекурсия, которые впоследствии использовались в Lisp.
Первоначальная нотация Маккарти использовала заключенные в скобки « M-выражения », которые можно было бы перевести в S-выражения . Например, M-выражение car[cons[A,B]]эквивалентно S-выражению . После того, как был реализован Lisp, программисты быстро перешли на использование S-выражений, и M-выражения были заброшены. M-выражения снова появились в кратковременных попытках MLisp [15] Горация Энеа и CGOL Воана Пратта .(car (cons A B))
Lisp был впервые реализован Стивом Расселом на компьютере IBM 704 с использованием перфокарт . [16] Рассел прочитал статью Маккарти и понял (к удивлению Маккарти), что функция eval в Lisp может быть реализована в машинном коде .
По словам Маккарти [17]
Стив Рассел сказал, слушай, почему бы мне не запрограммировать этот eval ... и я сказал ему, хо-хо, ты путаешь теорию с практикой, этот eval предназначен для чтения, а не для вычислений. Но он пошел дальше и сделал это. То есть, он скомпилировал eval в моей статье в машинный код IBM 704 , исправив ошибки , а затем разрекламировал это как интерпретатор Lisp, которым он, безусловно, и был. Так что в тот момент Lisp имел по сути ту форму, которую он имеет сегодня...
Результатом стал работающий интерпретатор Lisp , который можно было использовать для запуска программ Lisp или, точнее, «оценки выражений Lisp».
Два макроса на языке ассемблера для IBM 704 стали примитивными операциями для разложения списков: car ( Содержимое адресной части номера регистра) и cdr ( Содержимое декрементной части номера регистра), [18] где «регистр» относится к регистрам центрального процессора компьютера (ЦП). Диалекты Лиспа по-прежнему используют carи cdr( / k ɑːr / и / ˈ k ʊ d ər / ) для операций, которые возвращают первый элемент в списке и остальную часть списка соответственно.
Первый полный компилятор Lisp, написанный на Lisp, был реализован в 1962 году Тимом Хартом и Майком Левиным в Массачусетском технологическом институте, и мог быть скомпилирован просто заставив существующий интерпретатор LISP интерпретировать код компилятора, производя вывод машинного кода, который мог быть выполнен с 40-кратным улучшением скорости по сравнению с интерпретатором. [19] Этот компилятор представил модель Lisp инкрементальной компиляции , в которой скомпилированные и интерпретируемые функции могут свободно смешиваться. Язык, используемый в записке Харта и Левина, гораздо ближе к современному стилю Lisp, чем более ранний код Маккарти.
Процедуры сбора мусора были разработаны аспирантом Массачусетского технологического института Дэниелом Эдвардсом до 1962 года. [20]
В 1980-х и 1990-х годах были предприняты большие усилия по объединению работы над новыми диалектами Lisp (в основном преемниками Maclisp, такими как ZetaLisp и NIL (New Implementation of Lisp)) в один язык. Новый язык, Common Lisp , был в некоторой степени совместим с диалектами, которые он заменил (в книге Common Lisp the Language отмечается совместимость различных конструкций). В 1994 году ANSI опубликовал стандарт Common Lisp, «ANSI X3.226-1994 Information Technology Programming Language Common Lisp».
С момента своего создания Lisp был тесно связан с сообществом исследователей искусственного интеллекта , особенно в системах PDP-10 [21] . Lisp использовался в качестве реализации языка Micro Planner , который использовался в знаменитой системе искусственного интеллекта SHRDLU . В 1970-х годах, когда исследования искусственного интеллекта породили коммерческие ответвления, производительность существующих систем Lisp стала растущей проблемой, поскольку программистам нужно было быть знакомыми с последствиями производительности различных методов и вариантов, задействованных в реализации Lisp. [22]
За свою шестидесятилетнюю историю Lisp породил множество вариаций на основную тему языка S-выражений. Более того, каждый данный диалект может иметь несколько реализаций — например, существует более дюжины реализаций Common Lisp .
Различия между диалектами могут быть весьма заметны — например, Common Lisp использует ключевое слово defunдля наименования функции, а Scheme использует define. [23] Однако в пределах стандартизированного диалекта соответствующие реализации поддерживают один и тот же базовый язык, но с разными расширениями и библиотеками.
После некоторого спада в 1990-х годах интерес к Lisp вновь возрос после 2000 года. Большая часть новой активности была сосредоточена вокруг реализаций Common Lisp , Scheme , Emacs Lisp , Clojure и Racket и включает разработку новых переносимых библиотек и приложений.
Многие новые программисты Lisp были вдохновлены такими писателями, как Пол Грэм и Эрик С. Рэймонд, чтобы заняться языком, который другие считали устаревшим. Новые программисты Lisp часто описывают язык как открывающий глаза опыт и утверждают, что он значительно более продуктивен, чем другие языки. [36] Этот рост осведомленности можно сравнить с « зимой ИИ » и кратковременным ростом Lisp в середине 1990-х годов. [37]
По состоянию на 2010 год [обновлять]существовало одиннадцать активно поддерживаемых реализаций Common Lisp. [38]
Сообщество разработчиков программного обеспечения с открытым исходным кодом создало новую инфраструктуру поддержки: CLiki — это вики, которая собирает информацию, связанную с Common Lisp, каталог Common Lisp содержит список ресурсов, #lisp — популярный канал IRC, позволяющий делиться и комментировать фрагменты кода (при поддержке lisppaste, IRC-бота, написанного на Lisp), Planet Lisp [39] собирает содержимое различных блогов, связанных с Lisp, на LispForum [40] пользователи обсуждают темы, связанные с Lisp, Lispjobs [41] — это сервис для объявления о вакансиях, а также есть еженедельная служба новостей Weekly Lisp News . Common-lisp.net — это сайт для хостинга проектов Common Lisp с открытым исходным кодом. Quicklisp [42] — это менеджер библиотек для Common Lisp.
Пятьдесят лет Lisp (1958–2008) отмечалось на LISP50@OOPSLA. [43] Регулярно проводятся встречи местных пользователей в Бостоне, Ванкувере и Гамбурге. Другие мероприятия включают European Common Lisp Meeting, European Lisp Symposium и International Lisp Conference.
Сообщество Scheme активно поддерживает более двадцати реализаций . Несколько значительных новых реализаций (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) были разработаны в 2000-х годах (десятилетие). Пересмотренный 5-й отчет по алгоритмическому языку Scheme [44] стандарт Scheme был широко принят в сообществе Scheme. Процесс Scheme Requests for Implementation создал множество квазистандартных библиотек и расширений для Scheme. Сообщества пользователей отдельных реализаций Scheme продолжают расти. Новый процесс стандартизации языка был начат в 2003 году и привел к стандарту R 6 RS Scheme в 2007 году. Академическое использование Scheme для преподавания компьютерных наук, похоже, несколько снизилось. Некоторые университеты больше не используют Scheme в своих вводных курсах по компьютерным наукам; [45] [46] MIT теперь использует Python вместо Scheme для своей программы бакалавриата по компьютерным наукам и массового открытого онлайн-курса MITx. [47] [48]
Есть несколько новых диалектов Lisp: Arc , Hy , Nu , Liskell и LFE (Lisp Flavored Erlang). Парсер для Julia реализован на Femtolisp, диалекте Scheme (Julia вдохновлена Scheme, который в свою очередь является диалектом Lisp).
В октябре 2019 года Пол Грэм выпустил спецификацию Bel, «нового диалекта Lisp».
Common Lisp и Scheme представляют собой два основных направления развития Lisp. Эти языки воплощают существенно разные варианты дизайна.
Common Lisp является преемником Maclisp . Основное влияние оказали Lisp Machine Lisp , Maclisp, NIL , S-1 Lisp , Spice Lisp и Scheme. [49] Он обладает многими особенностями Lisp Machine Lisp (большой диалект Lisp, используемый для программирования Lisp Machines ), но был разработан для эффективной реализации на любом персональном компьютере или рабочей станции. Common Lisp является языком программирования общего назначения и, таким образом, имеет большой языковой стандарт, включающий множество встроенных типов данных, функций, макросов и других языковых элементов, а также объектную систему ( Common Lisp Object System ). Common Lisp также заимствовал некоторые особенности из Scheme, такие как лексическая область видимости и лексические замыкания . Реализации Common Lisp доступны для различных платформ, таких как LLVM , [50] виртуальная машина Java , [51] x86-64, PowerPC, Alpha, ARM, Motorola 68000 и MIPS, [52] и операционных систем, таких как Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD и Heroku. [53]
Scheme — это статически ограниченный и правильно хвостово-рекурсивный диалект языка программирования Lisp, изобретенный Гаем Л. Стилом-младшим и Джеральдом Джеем Сассманом . Он был разработан с исключительно ясной и простой семантикой и несколькими различными способами формирования выражений. Разработанный примерно на десятилетие раньше Common Lisp, Scheme имеет более минималистский дизайн. Он имеет гораздо меньший набор стандартных функций, но с определенными функциями реализации (такими как оптимизация хвостового вызова и полные продолжения ), не указанными в Common Lisp. Широкий спектр парадигм программирования, включая императивный, функциональный и стили передачи сообщений, находит удобное выражение в Scheme. Scheme продолжает развиваться с серией стандартов (Revised n Report on the Algorithmic Language Scheme) и серией Scheme Requests for Implementation .
Clojure — это диалект Lisp, ориентированный в основном на виртуальную машину Java , а также на Common Language Runtime (CLR), Python VM, Ruby VM YARV и компиляцию в JavaScript . Он разработан как прагматичный язык общего назначения. Clojure черпает значительное влияние из Haskell и уделяет большое внимание неизменяемости. [54] Clojure предоставляет доступ к фреймворкам и библиотекам Java с дополнительными подсказками типов и выводом типов , так что вызовы Java могут избегать рефлексии и обеспечивать быстрые примитивные операции. Clojure не разработан для обратной совместимости с другими диалектами Lisp. [55]
Кроме того, диалекты Lisp используются в качестве языков сценариев во многих приложениях, наиболее известными из которых являются Emacs Lisp в редакторе Emacs , AutoLISP и позже Visual Lisp в AutoCAD , Nyquist в Audacity и Scheme в LilyPond . Потенциально небольшой размер полезного интерпретатора Scheme делает его особенно популярным для встроенных сценариев. Примерами являются SIOD и TinyScheme , оба из которых были успешно встроены в процессор изображений GIMP под общим названием «Script-fu». [56] LIBREP, интерпретатор Lisp Джона Харпера, изначально основанный на языке Emacs Lisp , был встроен в оконный менеджер Sawfish . [57]
Lisp имеет официально стандартизированные диалекты: R6RS Scheme , R7RS Scheme , IEEE Scheme, [58] ANSI Common Lisp и ISO ISLISP .
Пол Грэм выделяет девять важных аспектов Lisp, которые отличают его от существующих языков, таких как Fortran : [59]
Lisp был первым языком, в котором структура программного кода была представлена точно и напрямую в стандартной структуре данных — качество, которое гораздо позже было названо « гомиконичностью ». Таким образом, функции Lisp можно манипулировать, изменять или даже создавать в программе Lisp без низкоуровневых манипуляций. Это обычно считается одним из главных преимуществ языка в отношении его выразительной силы и делает язык подходящим для синтаксических макросов и метациклической оценки .
Условие с использованием синтаксиса if–then–else было изобретено Маккарти для шахматной программы, написанной на Фортране . Он предложил включить его в ALGOL , но оно не было сделано частью спецификации Algol 58. Для Lisp Маккарти использовал более общую cond -структуру. [60] Algol 60 взял if–then–else и популяризировал его.
Lisp глубоко повлиял на Алана Кея , руководителя исследовательской группы, которая разработала Smalltalk в Xerox PARC ; и в свою очередь Lisp находился под влиянием Smalltalk, с более поздними диалектами, перенявшими функции объектно-ориентированного программирования (классы наследования, инкапсуляция экземпляров, передача сообщений и т. д.) в 1970-х годах. Система объектов Flavors ввела концепцию множественного наследования и mixin . Система объектов Common Lisp обеспечивает множественное наследование, мультиметоды с множественной диспетчеризацией и первоклассные универсальные функции , давая гибкую и мощную форму динамической диспетчеризации . Она послужила шаблоном для многих последующих систем объектов Lisp (включая Scheme ), которые часто реализуются через протокол метаобъектов , рефлексивную метациклическую конструкцию , в которой система объектов определяется в терминах самой себя: Lisp был всего лишь вторым языком после Smalltalk (и до сих пор остается одним из очень немногих языков), обладающим такой системой метаобъектов. Много лет спустя Алан Кей предположил, что в результате слияния этих особенностей только Smalltalk и Lisp можно считать правильно задуманными объектно-ориентированными системами программирования. [61]
Lisp представил концепцию автоматической сборки мусора , в которой система просматривает кучу в поисках неиспользуемой памяти. Прогресс в современных сложных алгоритмах сборки мусора, таких как генерационная сборка мусора, был стимулирован ее использованием в Lisp. [62]
Эдсгер В. Дейкстра в своей лекции на вручении премии Тьюринга в 1972 году сказал:
Имея в своей основе несколько очень простых принципов, он [LISP] продемонстрировал замечательную стабильность. Кроме того, LISP был носителем для значительного числа в некотором смысле наших самых сложных компьютерных приложений. LISP в шутку описывали как «самый разумный способ неправильного использования компьютера». Я думаю, что это описание — большой комплимент, потому что оно передает весь аромат освобождения: он помог многим нашим самым одаренным собратьям-людям думать о ранее невозможных вещах. [63]
Во многом из-за своих ресурсных требований по отношению к раннему вычислительному оборудованию (включая ранние микропроцессоры), Lisp не стал таким популярным за пределами сообщества ИИ , как Fortran и язык C , произошедший от ALGOL . Из-за своей пригодности для сложных и динамических приложений Lisp пережил некоторое возрождение популярного интереса в 2010-х годах. [64]
Lisp — это язык, ориентированный на выражения . В отличие от большинства других языков, здесь не делается различий между «выражениями» и «операторами» ; [ сомнительно – обсудить ] весь код и данные записываются в виде выражений. Когда выражение вычисляется , оно выдает значение (возможно, несколько значений), которое затем может быть встроено в другие выражения. Каждое значение может быть любого типа данных.
В статье Маккарти 1958 года были представлены два типа синтаксиса: символические выражения ( S-выражения , sexps), которые отражают внутреннее представление кода и данных; и метавыражения ( M-выражения ), которые выражают функции S-выражений. M-выражения никогда не пользовались популярностью, и почти все Lisp сегодня используют S-выражения для манипулирования как кодом, так и данными.
Использование скобок — самое очевидное отличие Lisp от других семейств языков программирования. В результате студенты давно дали Lisp прозвища, такие как « Затерянные в глупых скобках » или «Множество раздражающих лишних скобок» . [65] Однако синтаксис S-выражений также отвечает за большую часть мощи Lisp: синтаксис прост и последователен, что облегчает манипуляции с помощью компьютера. Однако синтаксис Lisp не ограничивается традиционной нотацией скобок. Его можно расширить, включив альтернативные нотации. Например, XMLisp — это расширение Common Lisp, которое использует протокол метаобъектов для интеграции S-выражений с расширяемым языком разметки ( XML ).
Опора на выражения дает языку большую гибкость. Поскольку функции Lisp записываются в виде списков, их можно обрабатывать точно так же, как данные. Это позволяет легко писать программы, которые манипулируют другими программами ( метапрограммирование ). Многие диалекты Lisp используют эту возможность с помощью макросистем, что позволяет расширять язык практически без ограничений.
Список Lisp записывается с элементами, разделенными пробелами и заключенными в скобки. Например, это список, элементами которого являются три атома , и . Эти значения неявно типизированы: они представляют собой соответственно два целых числа и специфичный для Lisp тип данных, называемый «символ», и не должны быть объявлены как таковые.(1 2 foo) 12foo
Пустой список ()также представлен как специальный атом nil. Это единственная сущность в Lisp, которая является и атомом, и списком.
Выражения записываются в виде списков с использованием префиксной нотации . Первый элемент списка — это имя функции, имя макроса, лямбда-выражения или имя «специального оператора» (см. ниже). Оставшаяся часть списка — это аргументы. Например, функция listвозвращает свои аргументы в виде списка, поэтому выражение
( список 1 2 ( цитата foo )) вычисляется в список . «Кавычка» перед в предыдущем примере — это «специальный оператор», который возвращает свой аргумент без его вычисления. Любые выражения без кавычек рекурсивно вычисляются до того, как будет вычислено включающее выражение. Например,(1 2 foo)foo
( список 1 2 ( список 3 4 )) вычисляется как список . Третий аргумент — список; списки могут быть вложенными.(1 2 (3 4))
Арифметические операторы обрабатываются аналогично. Выражение
( + 1 2 3 4 ) оценивается как 10. Эквивалент в инфиксной нотации будет " ".1 + 2 + 3 + 4
В Lisp нет понятия операторов, как это реализовано в языках, производных от Algol. Арифметические операторы в Lisp являются вариативными функциями (или n-арными ), способными принимать любое количество аргументов. Оператор инкремента в стиле C '++' иногда реализуется под именем, incfдающим синтаксис
( вкл. x ) эквивалентно (setq x (+ x 1)), возвращая новое значение x.
«Специальные операторы» (иногда называемые «специальными формами») обеспечивают структуру управления Lisp. Например, специальный оператор ifпринимает три аргумента. Если первый аргумент не равен нулю, он вычисляется как второй аргумент; в противном случае он вычисляется как третий аргумент. Таким образом, выражение
( если ноль ( список 1 2 "foo" ) ( список 3 4 "bar" )) оценивается как . Конечно, это было бы полезнее, если бы вместо было подставлено нетривиальное выражение .(3 4 "bar")nil
Lisp также предоставляет логические операторы and , or и not . Операторы and и or выполняют сокращенную оценку и возвращают свой первый аргумент nil и non-nil соответственно.
( или ( и "ноль" ноль "никогда" ) "Джеймс" 'задача 'время ) будет оценен как «Джеймс».
Другой специальный оператор, lambda, используется для связывания переменных со значениями, которые затем оцениваются в выражении. Этот оператор также используется для создания функций: аргументы to lambda— это список аргументов и выражение или выражения, которые оценивает функция (возвращаемое значение — это значение последнего вычисляемого выражения). Выражение
( лямбда ( арг ) ( + арг 1 )) вычисляется как функция, которая при применении принимает один аргумент, связывает его argи возвращает число, на единицу большее, чем этот аргумент. Лямбда-выражения обрабатываются так же, как и именованные функции; они вызываются таким же образом. Следовательно, выражение
(( лямбда ( арг ) ( + арг 1 )) 5 ) оценивается как 6. Здесь мы выполняем применение функции: мы выполняем анонимную функцию , передавая ей значение 5.
Именованные функции создаются путем сохранения лямбда-выражения в символе с помощью макроса defun.
( defun foo ( a b c d ) ( + a b c d )) (defun f (a) b...)определяет новую функцию, названную fв глобальной среде. Концептуально она похожа на выражение:
( setf ( fdefinition 'f ) #' ( lambda ( a ) ( block f b... ))) где setf— макрос, используемый для установки значения первого аргумента в новый объект функции. — глобальное определение функции с именем . — сокращение от специального оператора, возвращающего объект функции.fdefinition 'ffdefinitionf#'function
В оригинальном LISP было два основных типа данных : атомы и списки. Список представлял собой конечную упорядоченную последовательность элементов, где каждый элемент был либо атомом, либо списком, а атом был числом или символом. Символ по сути был уникальным именованным элементом, записанным как буквенно-цифровая строка в исходном коде и использовавшимся либо как имя переменной, либо как элемент данных в символической обработке . Например, список содержит три элемента: символ , список и число 2.(FOO (BAR 1) 2)FOO(BAR 1)
Существенное различие между атомами и списками заключалось в том, что атомы были неизменяемыми и уникальными. Два атома, которые появлялись в разных местах исходного кода, но были написаны совершенно одинаково, представляли один и тот же объект, [ необходима цитата ] , тогда как каждый список был отдельным объектом, который можно было изменять независимо от других списков и можно было отличить от других списков с помощью операторов сравнения.
По мере того, как в более поздних диалектах Lisp появлялось все больше типов данных и развивались стили программирования , концепция атома утратила свое значение. [ требуется ссылка ] Во многих диалектах предикат atom по-прежнему сохранялся для совместимости с устаревшими версиями , [ требуется ссылка ] определяя его как истинный для любого объекта, который не является cons.
Список Lisp реализован как односвязный список . [66] Каждая ячейка этого списка называется cons (в Scheme — pair ) и состоит из двух указателей , называемых car и cdr . Они соответственно эквивалентны полям dataи , nextобсуждаемым в статье linked list .
Из множества структур данных, которые можно построить из cons-ячеек, одна из самых основных называется правильным списком . Правильный список — это либо специальный nilсимвол (пустой список), либо cons, в котором carуказывает на данные (которые могут быть другой структурой cons, например списком), а cdrуказывает на другой правильный список.
Если данный cons берется за голову связанного списка, то его car указывает на первый элемент списка, а его cdr указывает на остальную часть списка. По этой причине функции carи cdrтакже называются firstи restпри обращении к cons, которые являются частью связанного списка (а не, скажем, дерева).
Таким образом, список Lisp не является атомарным объектом, как экземпляр класса-контейнера в C++ или Java. Список — это не более чем совокупность связанных cons. Переменная, которая ссылается на данный список, — это просто указатель на первый cons в списке. Обход списка можно выполнить, проведя cdr вниз по списку; то есть, используя последовательные cdr для посещения каждого cons списка; или используя любую из нескольких функций высшего порядка для отображения функции на список.
Поскольку cons и списки настолько универсальны в системах Lisp, распространено заблуждение, что они являются единственными структурами данных Lisp. На самом деле, все, кроме самых простых Lisp, имеют другие структуры данных, такие как векторы ( массивы ), хэш-таблицы , структуры и т. д.
Скобочные S-выражения представляют собой связанные списочные структуры. Существует несколько способов представления того же списка в виде S-выражения. Cons может быть записан в точечно-парной нотации как , где — car, а cdr. Более длинный правильный список может быть записан в точечно-парной нотации. Это обычно сокращается как в нотации списка . Неправильный список [67] может быть записан в виде комбинации двух — как для списка из трех cons, последний cdr — (т. е. список в полностью указанной форме).(a . b)ab(a . (b . (c . (d . nil))))(a b c d)(a b c . d)d(a . (b . (c . d)))
Lisp предоставляет множество встроенных процедур для доступа к спискам и управления ими. Списки можно создавать напрямую с помощью listпроцедуры, которая принимает любое количество аргументов и возвращает список этих аргументов.
( список 1 2 'a 3 ) ;Выход: (1 2 a 3) ( список 1 ' ( 2 3 ) 4 ) ;Выход: (1 (2 3) 4) Из-за того, как списки строятся из cons-пар , consпроцедура может использоваться для добавления элемента в начало списка. consПроцедура асимметрична в том, как она обрабатывает аргументы списка, из-за того, как строятся списки.
( минус 1 ' ( 2 3 )) ;Выход: (1 2 3) ( минус ' ( 1 2 ) ' ( 3 4 )) ;Выход: ((1 2) 3 4) Процедура appendдобавляет два (или более) списка друг к другу. Поскольку списки Lisp являются связанными списками, добавление двух списков имеет асимптотическую временную сложность
( добавить ' ( 1 2 ) ' ( 3 4 )) ;Выход: (1 2 3 4) ( добавить ' ( 1 2 3 ) ' () ' ( a ) ' ( 5 6 )) ;Выход: (1 2 3 a 5 6) Списки Lisp, будучи простыми связанными списками, могут иметь общую структуру друг с другом. То есть, два списка могут иметь один и тот же tail , или конечную последовательность conses. Например, после выполнения следующего кода Common Lisp:
( setf foo ( list 'a 'b 'c )) ( setf bar ( cons 'x ( cdr foo ))) списки fooи barявляются и соответственно. Однако хвост имеет одинаковую структуру в обоих списках. Это не копия; ячейки cons, указывающие на и находятся в одних и тех же ячейках памяти для обоих списков.(a b c)(x b c)(b c)bc
Совместное использование структуры вместо копирования может дать значительное улучшение производительности. Однако эта техника может взаимодействовать нежелательным образом с функциями, которые изменяют списки, переданные им в качестве аргументов. Изменение одного списка, например, путем замены на c, gooseповлияет на другой:
( setf ( third foo ) 'goose ) Это изменяется fooна , но тем самым также изменяется на – возможно неожиданный результат. Это может быть источником ошибок, и функции, которые изменяют свои аргументы, документируются как деструктивные именно по этой причине.(a b goose)bar(x b goose)
Поклонники функционального программирования избегают деструктивных функций. В диалекте Scheme, который отдает предпочтение функциональному стилю, имена деструктивных функций помечаются предостерегающим восклицательным знаком или «bang» — например, set-car!(читай set car bang ), который заменяет car у cons. В диалекте Common Lisp деструктивные функции являются обычным явлением; эквивалент set-car!назван rplacaдля «replace car». Однако эта функция встречается редко, поскольку Common Lisp включает в себя специальное средство, setf, чтобы упростить определение и использование деструктивных функций. Распространенный стиль в Common Lisp — писать код функционально (без деструктивных вызовов) при прототипировании, а затем добавлять деструктивные вызовы в качестве оптимизации там, где это безопасно.
Lisp оценивает выражения, которые вводит пользователь. Символы и списки оцениваются в некоторые другие (обычно более простые) выражения – например, символ оценивается в значение переменной, которую он называет; оценивается в . Однако большинство других форм оцениваются в себя: при вводе в Lisp он возвращает .(+ 2 3)555
Любое выражение также может быть помечено, чтобы предотвратить его вычисление (как это необходимо для символов и списков). Это роль quoteспециального оператора или его сокращения '(одна кавычка). Например, обычно при вводе символа fooон возвращает значение соответствующей переменной (или ошибку, если такой переменной нет). Чтобы сослаться на литеральный символ, введите или, как правило, .(quote foo)'foo
И Common Lisp, и Scheme также поддерживают оператор обратной кавычки (называемый в Scheme квазицитатником ), вводимый с `символом ( гравитационный акцент ). Это почти то же самое, что и простая кавычка, за исключением того, что она позволяет вычислять выражения и интерполировать их значения в кавычки с помощью операторов запятая- , unquote и запятая-at ,@ splice . Если переменная snueимеет значение, то вычисляется как , в то время как вычисляется как . Обратная кавычка чаще всего используется при определении макрорасширений. [68] [69](bar baz)`(foo ,snue)(foo (bar baz))`(foo ,@snue)(foo bar baz)
Самооцениваемые формы и кавычки являются эквивалентом литералов в Lisp. Может быть возможным изменять значения (изменяемых) литералов в программном коде. Например, если функция возвращает кавычки, а код, вызывающий функцию, изменяет форму, это может изменить поведение функции при последующих вызовах.
( defun должен быть-константой () ' ( один два три )) ( let (( stuff ( should-be-constant ))) ( setf ( third stuff ) 'bizarre )) ; плохо! ( должно быть постоянным ) ; возвращает (один два странных) Подобное изменение формы в кавычках обычно считается плохим стилем и определяется ANSI Common Lisp как ошибочное (приводящее к «неопределенному» поведению в скомпилированных файлах, поскольку компилятор файлов может объединять похожие константы, помещать их в защищенную от записи память и т. д.).
Формализация цитирования в Lisp была отмечена Дугласом Хофштадтером (в работах Гёделя, Эшера, Баха ) и другими как пример философской идеи самореференции .
Семейство Lisp разделяется по использованию динамической или статической (т. е. лексической) области видимости . Clojure, Common Lisp и Scheme используют статическую область видимости по умолчанию, в то время как newLISP , Picolisp и встроенные языки в Emacs и AutoCAD используют динамическую область видимости. Начиная с версии 24.1, Emacs использует как динамическую, так и лексическую область видимости.
Фундаментальное различие между Lisp и другими языками заключается в том, что в Lisp текстовое представление программы — это просто понятное человеку описание тех же внутренних структур данных (связанных списков, символов, чисел, знаков и т. д.), которые использовались бы базовой системой Lisp.
Lisp использует это для реализации очень мощной макросистемы. Как и другие макроязыки, такие как определенный препроцессором C (препроцессор макросов для языков программирования C , Objective-C и C++ ), макрос возвращает код, который затем может быть скомпилирован. Однако, в отличие от макросов препроцессора C, макросы являются функциями Lisp и поэтому могут использовать всю мощь Lisp.
Кроме того, поскольку код Lisp имеет ту же структуру, что и списки, макросы могут быть построены с помощью любой из функций обработки списков в языке. Короче говоря, все, что Lisp может сделать со структурой данных, макросы Lisp могут сделать с кодом. Напротив, в большинстве других языков вывод парсера является чисто внутренним по отношению к реализации языка и не может быть изменен программистом.
Эта функция позволяет легко разрабатывать эффективные языки внутри языков. Например, Common Lisp Object System может быть реализована чисто как расширение языка с использованием макросов. Это означает, что если приложению требуется другой механизм наследования, оно может использовать другую объектную систему. Это резко контрастирует с большинством других языков; например, Java не поддерживает множественное наследование, и нет разумного способа добавить его.
В упрощенных реализациях Lisp эта структура списка напрямую интерпретируется для запуска программы; функция — это буквально часть структуры списка, которую интерпретатор обходит при ее выполнении. Однако большинство существенных систем Lisp также включают компилятор. Компилятор транслирует структуру списка в машинный код или байт-код для выполнения. Этот код может выполняться так же быстро, как и код, скомпилированный на обычных языках, таких как C.
Макросы расширяются до этапа компиляции и, таким образом, предлагают некоторые интересные возможности. Если программе нужна предварительно вычисленная таблица, то макрос может создать таблицу во время компиляции, поэтому компилятору нужно только вывести таблицу и не нужно вызывать код для создания таблицы во время выполнения. Некоторые реализации Lisp даже имеют механизм, eval-whenкоторый позволяет коду присутствовать во время компиляции (когда макрос нуждается в этом), но не присутствовать в выпущенном модуле. [70]
Языки Lisp часто используются с интерактивной командной строкой , которая может быть объединена с интегрированной средой разработки (IDE). Пользователь вводит выражения в командной строке или указывает IDE передать их в систему Lisp. Lisp считывает введенные выражения, оценивает их и выводит результат. По этой причине командная строка Lisp называется циклом чтения–вычисления–печати ( REPL ).
Основная операция REPL выглядит следующим образом. Это упрощенное описание, в котором опущены многие элементы настоящего Lisp, такие как цитирование и макросы.
Функция readпринимает текстовые S-выражения в качестве входных данных и анализирует их во внутреннюю структуру данных. Например, если вы вводите текст в приглашении, преобразует его в связанный список с тремя элементами: символом , числом 1 и числом 2. Так уж получилось, что этот список также является допустимым фрагментом кода Lisp; то есть его можно вычислить. Это происходит потому, что car списка именует функцию — операцию сложения.(+ 1 2)read+
А fooбудет прочитано как один символ. 123будет прочитано как число сто двадцать три. "123"будет прочитано как строка «123».
Функция evalоценивает данные, возвращая в качестве результата ноль или более других данных Lisp. Оценка не обязательно означает интерпретацию; некоторые системы Lisp компилируют каждое выражение в машинный код. Однако просто описать оценку как интерпретацию: чтобы оценить список, car которого называет функцию, evalсначала оценивает каждый из аргументов, указанных в его cdr, затем применяет функцию к аргументам. В этом случае функция — это сложение, и применение ее к списку аргументов дает ответ . Это результат оценки.(1 2)3
Символ fooоценивается как значение символа foo. Данные, такие как строка "123", оцениваются как та же строка. Список оценивается как список (1 2 3).(quote (1 2 3))
Задача функции print— представлять вывод пользователю. Для простого результата, такого как 3этот, это тривиально. Выражение, которое вычисляется как часть структуры списка, потребует printобхода списка и вывода его в виде S-выражения.
Для реализации REPL на Lisp необходимо реализовать только эти три функции и функцию бесконечного цикла. (Естественно, реализация evalбудет сложной, поскольку она должна также реализовать все специальные операторы, такие как ifили lambda.) После этого базовый REPL представляет собой одну строку кода: .(loop (print (eval (read))))
Lisp REPL обычно также обеспечивает редактирование ввода, историю ввода, обработку ошибок и интерфейс для отладчика.
Lisp обычно оценивается с нетерпением . В Common Lisp аргументы оцениваются в аппликативном порядке («самый левый внутренний»), тогда как в Scheme порядок аргументов не определен, что оставляет место для оптимизации компилятором.
Первоначально в Lisp было очень мало управляющих структур, но в ходе эволюции языка их было добавлено гораздо больше. (Первоначальный условный оператор Lisp, cond, является предшественником более поздних if-then-elseструктур.)
Программисты на диалекте Scheme часто выражают циклы с помощью хвостовой рекурсии . Распространенность Scheme в академической информатике привела некоторых студентов к мысли, что хвостовая рекурсия — единственный или наиболее распространенный способ записи итераций в Lisp, но это неверно. Все часто встречающиеся диалекты Lisp имеют конструкции итераций в императивном стиле, от doцикла Scheme до сложных выражений Common Lisploop . Более того, ключевой вопрос, который делает это объективным, а не субъективным вопросом, заключается в том, что Scheme предъявляет особые требования к обработке хвостовых вызовов , и, таким образом, причина, по которой использование хвостовой рекурсии обычно поощряется для Scheme, заключается в том, что эта практика явно поддерживается определением языка. Напротив, ANSI Common Lisp не требует [71] оптимизации, обычно называемой устранением хвостового вызова. Таким образом, тот факт, что хвостовой рекурсивный стиль как случайная замена использованию более традиционных итерационных конструкций (таких как do, dolistили loop) не приветствуется [72] в Common Lisp, является не просто вопросом стилистических предпочтений, но и потенциально вопросом эффективности (поскольку очевидный хвостовой вызов в Common Lisp может не скомпилироваться как простой переход ) и корректности программы (поскольку хвостовая рекурсия может увеличить использование стека в Common Lisp, что может привести к переполнению стека ).
Некоторые управляющие структуры Lisp являются специальными операторами , эквивалентными синтаксическим ключевым словам других языков. Выражения, использующие эти операторы, имеют тот же внешний вид, что и вызовы функций, но отличаются тем, что аргументы не обязательно оцениваются — или, в случае итерационного выражения, могут оцениваться более одного раза.
В отличие от большинства других основных языков программирования, Lisp позволяет реализовывать управляющие структуры с помощью языка. Несколько управляющих структур реализованы как макросы Lisp и даже могут быть расширены макросами программистом, который хочет знать, как они работают.
И в Common Lisp, и в Scheme есть операторы для нелокального потока управления. Различия в этих операторах являются одними из самых глубоких различий между двумя диалектами. Scheme поддерживает реентерабельные продолжения с использованием call/ccпроцедуры, которая позволяет программе сохранять (и позже восстанавливать) определенное место в выполнении. Common Lisp не поддерживает реентерабельные продолжения, но поддерживает несколько способов обработки escape-продолжений.
Часто один и тот же алгоритм может быть выражен в Lisp как в императивном, так и в функциональном стиле. Как отмечено выше, Scheme склоняется к функциональному стилю, используя хвостовую рекурсию и продолжения для выражения потока управления. Однако императивный стиль все еще вполне возможен. Стиль, предпочитаемый многими программистами Common Lisp, может показаться более знакомым программистам, привыкшим к структурированным языкам, таким как C, в то время как стиль, предпочитаемый Schemer, больше напоминает чисто функциональные языки, такие как Haskell .
Из-за раннего наследия Lisp в обработке списков, он имеет широкий спектр функций высшего порядка, связанных с итерацией по последовательностям. Во многих случаях, когда в других языках потребовался бы явный цикл (например, цикл forв C), в Lisp ту же задачу можно выполнить с помощью функции высшего порядка. (То же самое относится ко многим функциональным языкам программирования.)
Хорошим примером является функция, которая в Scheme называется map, а в Common Lisp называется mapcar. При наличии функции и одного или нескольких списков, mapcarприменяет функцию последовательно к элементам списков по порядку, собирая результаты в новом списке:
( mapcar #' + ' ( 1 2 3 4 5 ) ' ( 10 20 30 40 50 )) Это применяет +функцию к каждой соответствующей паре элементов списка, получая результат .(11 22 33 44 55)
Вот примеры кода Common Lisp.
Базовая программа « Привет, мир! »:
( напечатать "Привет, мир!" ) ( defun факториал ( n ) ( if ( Zerop n ) 1 ( * n ( факториал ( 1- n ))))) Альтернативная реализация занимает меньше места в стеке, чем предыдущая версия, если базовая система Lisp оптимизирует хвостовую рекурсию :
( defun factorial ( n &optional ( acc 1 )) ( if ( zerop n ) acc ( factorial ( 1- n ) ( * acc n )))) Сравните приведенные выше примеры с итеративной версией, которая использует макрос Common Lisp loop:
( defun factorial ( n ) ( loop for i from 1 to n for fac = 1 then ( * fac i ) finally ( return fac ))) Следующая функция переворачивает список. (Встроенная функция переворота Lisp делает то же самое.)
( defun -reverse ( list ) ( let (( return-value )) ( dolist ( e list ) ( push e return-value )) return-value )) Различные объектные системы и модели были построены поверх, рядом или в Lisp, включая
Несколько операционных систем , включая системы на основе языка , основаны на Lisp (используют возможности Lisp, соглашения, методы, структуры данных и т. д.) или написаны на Lisp, [75] включая:
Genera , переименованная в Open Genera, [76] компанией Symbolics ; Medley, написанная на Interlisp, изначально семействе графических операционных систем, которые работали на более поздних рабочих станциях Star компании Xerox ; [77] [78] Mezzano; [79] Interim; [80] [81] ChrysaLisp, [82] от разработчиков TAOS компании Tao Systems. [83] а также Guix
Lisp — выживший, используемый уже около четверти века. Среди активных языков программирования только Fortran прожил дольше.
Один из самых важных и увлекательных языков программирования — LISP (сокращение от «List Processing»), который был изобретен Джоном Маккарти примерно в то же время, когда был изобретен Algol. Впоследствии LISP пользовался большой популярностью у специалистов в области искусственного интеллекта.
Проект PDP-6 стартовал в начале 1963 года как 24-битная машина. Он вырос до 36 бит для LISP, что было целью проектирования.
(defun f (x) x)(define f (lambda (x) x))или(define (f x) x)— это Lisp, не ограниченный обратной совместимостью
Я изобрел условные выражения в связи с набором подпрограмм допустимых шахматных ходов, которые я написал на FORTRAN для IBM 704 в MIT в 1957–58 годах... Статья, определяющая условные выражения и предлагающая их использование в Algol, была отправлена в отдел коммуникаций ACM, но была произвольно понижена до письма редактору, поскольку была очень короткой.
Тогда я не понимал чудовищную идею LISP ощутимого метаязыка, но немного приблизился к идеям о расширяемых языках... Второй этап этого состоял в том, чтобы наконец понять LISP и затем использовать это понимание для создания гораздо более красивых, меньших, более мощных и более позднесвязанных подструктур... ООП для меня означает только обмен сообщениями, локальное сохранение и защиту и сокрытие состояния процесса, и крайне позднее связывание всех вещей. Это можно сделать в Smalltalk и в LISP. Возможно, есть и другие системы, в которых это возможно, но я о них не знаю.
Определения из Викисловаря
Медиа из Commons
Цитаты из Викицитатника
Тексты из Викиресурса
Учебники из Wikibooks
Ресурсы из Викиверситета