Лисп (исторически LISP , аббревиатура от «обработка списков») — это семейство языков программирования с долгой историей и характерной, полностью заключенной в круглые скобки префиксной нотацией . [3] Первоначально созданный в 1960 году, Лисп является третьим старейшим языком программирования высокого уровня, до сих пор широко используемым, после Фортрана и КОБОЛа . [4] [5] Лисп изменился с первых дней своего существования, и на протяжении его истории существовало множество диалектов . Сегодня наиболее известными диалектами Lisp общего назначения являются Common Lisp , Scheme , Racket и Clojure . [6] [7] [8]
Первоначально Lisp был создан как практическая математическая система обозначений для компьютерных программ под влиянием (хотя изначально не является производным от) [9] обозначения лямбда-исчисления Алонзо Чёрча . Он быстро стал излюбленным языком программирования для исследований искусственного интеллекта (ИИ). [10] Как один из самых ранних языков программирования, Лисп стал пионером многих идей в информатике , включая древовидные структуры данных , автоматическое управление хранилищем , динамическую типизацию , условные выражения , функции высшего порядка , рекурсию , автономный компилятор , [11] и цикл чтения -оценки-печати . [12]
Название LISP происходит от «LISt Processor». [13] Связанные списки — одна из основных структур данных Lisp , а исходный код Lisp состоит из списков. Таким образом, программы на Лиспе могут манипулировать исходным кодом как структурой данных, создавая макросистемы , которые позволяют программистам создавать новый синтаксис или новые предметно-ориентированные языки, встроенные в Лисп.
Взаимозаменяемость кода и данных придает Lisp мгновенно узнаваемый синтаксис. Весь программный код записывается в виде s-выражений или списков в круглых скобках. Вызов функции или синтаксическая форма записывается в виде списка, в котором сначала имя функции или оператора, а затем аргументы; например, функция f, принимающая три аргумента, будет называться как .(f arg1 arg2 arg3)
Джон Маккарти начал разработку Lisp в 1958 году, когда работал в Массачусетском технологическом институте (MIT). Маккарти опубликовал свой дизайн в статье в журнале Communications of ACM в апреле 1960 года под названием «Рекурсивные функции символических выражений и их машинное вычисление, часть I». [14] Он показал, что с помощью нескольких простых операторов и обозначений анонимных функций, заимствованных у Чёрча, можно построить полный по Тьюрингу язык алгоритмов.
Язык обработки информации был первым языком искусственного интеллекта , появившимся в 1955 или 1956 году, и уже включал в себя многие концепции, такие как обработка списков и рекурсия, которые стали использоваться в Лиспе.
В исходной записи Маккарти использовались « М-выражения », заключенные в квадратные скобки, которые можно было перевести в S-выражения . Например, M-выражение car[cons[A,B]]эквивалентно S-выражению . Как только Lisp был реализован, программисты быстро решили использовать S-выражения, и от M-выражений отказались. М-выражения снова всплыли на поверхность благодаря недолгим попыткам MLisp [15] Горация Энеа и CGOL Воана Пратта .(car (cons A B))
Lisp был впервые реализован Стивом Расселом на компьютере IBM 704 с использованием перфокарт . [16] Рассел прочитал статью Маккарти и понял (к удивлению Маккарти), что функция eval в Лиспе может быть реализована в машинном коде .
По мнению Маккарти [17]
Стив Рассел сказал, смотри, почему бы мне не запрограммировать этот eval ... и я ему сказал: хо-хо, ты путаешь теорию с практикой, этот eval предназначен для чтения, а не для вычислений. Но он пошел дальше и сделал это. То есть он скомпилировал eval из моей статьи в машинный код IBM 704 , исправив ошибки , а затем рекламировал это как интерпретатор Лиспа, что, безусловно, и было. Итак, на тот момент Лисп по сути имел ту форму, которую он имеет сегодня...
Результатом стал работающий интерпретатор Лиспа , который можно было использовать для запуска программ на Лиспе или, точнее, «оценки выражений Лиспа».
Два макроса языка ассемблера для IBM 704 стали примитивными операциями для разложения списков: car ( Содержимое адресной части номера регистра ) и cdr ( Содержимое декрементной части номера регистра), [18] где «регистр» относится к регистрам. центрального процессора компьютера (ЦП). Диалекты Лиспа по-прежнему используют carи cdr( / k ɑːr / и / ˈ k ʊ d ər / ) для операций, которые возвращают первый элемент в списке и остальную часть списка соответственно.
Первый полноценный компилятор Lisp, написанный на Lisp, был реализован в 1962 году Тимом Хартом и Майком Левином в Массачусетском технологическом институте. Его можно было скомпилировать, просто заставив существующий интерпретатор LISP интерпретировать код компилятора, создавая выходные данные машинного кода , которые можно было выполнить со скоростью 40 секунд. -кратное увеличение скорости по сравнению со скоростью переводчика. [19] Этот компилятор представил модель инкрементной компиляции Lisp , в которой скомпилированные и интерпретируемые функции могут свободно смешиваться. Язык, использованный в записке Харта и Левина, гораздо ближе к современному стилю Лиспа, чем более ранний код Маккарти.
Правила сбора мусора были разработаны аспирантом Массачусетского технологического института Дэниелом Эдвардсом еще до 1962 года. [20]
В течение 1980-х и 1990-х годов были предприняты большие усилия по объединению работы над новыми диалектами Lisp (в основном преемниками Maclisp, такими как ZetaLisp и NIL (новая реализация Lisp) в один язык. Новый язык, Common Lisp , был в некоторой степени совместим. с диалектами, которые он заменил (книга Common Lisp the Language отмечает совместимость различных конструкций).В 1994 году ANSI опубликовал стандарт Common Lisp, «ANSI X3.226-1994 Язык программирования информационных технологий Common Lisp».
С момента своего создания Lisp был тесно связан с исследовательским сообществом искусственного интеллекта , особенно в системах PDP-10 [21] . Lisp использовался как реализация языка Micro Planner , который использовался в знаменитой системе искусственного интеллекта SHRDLU . В 1970-х годах, когда исследования искусственного интеллекта породили коммерческие ответвления, производительность существующих систем Lisp стала растущей проблемой, поскольку программистам необходимо было знать влияние на производительность различных методов и вариантов реализации Lisp. [22]
За свою шестидесятилетнюю историю Лисп породил множество вариаций основной темы языка S-выражений. Более того, каждый данный диалект может иметь несколько реализаций — например, существует более десятка реализаций Common Lisp .
Различия между диалектами могут быть весьма заметными — например, Common Lisp использует ключевое слово defunдля имени функции, а Scheme использует define. [23] Однако в рамках стандартизированного диалекта соответствующие реализации поддерживают один и тот же базовый язык, но с разными расширениями и библиотеками.
После некоторого снижения в 1990-х годах интерес к Лиспу возобновился после 2000 года. Большая часть новой деятельности была сосредоточена вокруг реализаций Common Lisp , Scheme , Emacs Lisp , Clojure и Racket , а также включала разработку новых переносимых библиотек и приложений.
Многие новые программисты на Лиспе были вдохновлены такими авторами, как Пол Грэм и Эрик С. Рэймонд, на разработку языка, который другие считали устаревшим. Программисты New Lisp часто описывают этот язык как поучительный опыт и утверждают, что он значительно более продуктивен, чем другие языки. [36] Этот рост осведомленности можно противопоставить « зиме искусственного интеллекта » и кратковременному успеху Лиспа в середине 1990-х годов. [37]
По состоянию на 2010 год [обновлять]существовало одиннадцать активно поддерживаемых реализаций Common Lisp. [38]
Сообщество открытого исходного кода создало новую вспомогательную инфраструктуру: CLiki — это вики, которая собирает информацию, связанную с Common Lisp, в каталоге Common Lisp перечислены ресурсы, #lisp — популярный IRC-канал, позволяющий делиться и комментировать фрагменты кода (при поддержке lispaste, IRC -бот , написанный на Lisp), Planet Lisp [39] собирает содержимое различных блогов, посвященных Lisp, на LispForum [40] пользователи обсуждают темы Lisp, Lispjobs [41] — сервис для объявления предложений о работе, есть еженедельные новости сервис, Еженедельные новости Лиспа . Common-lisp.net — это хостинг для проектов Common Lisp с открытым исходным кодом. Quicklisp [42] — менеджер библиотек Common Lisp.
Пятьдесят лет Лиспа (1958–2008) отмечали на LISP50@OOPSLA. [43] Регулярно проводятся встречи местных пользователей в Бостоне, Ванкувере и Гамбурге. Другие мероприятия включают Европейское собрание Common Lisp, Европейский симпозиум Lisp и Международную конференцию Lisp.
Сообщество Scheme активно поддерживает более двадцати реализаций . Несколько значительных новых реализаций (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) были разработаны в 2000-х (десятилетии). Стандарт Scheme Revised 5 Report on the Algorithmic Language Scheme [44] получил широкое признание в сообществе 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). Парсер 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, такие как лексическая область видимости и лексические замыкания . Доступны общие реализации 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]
Схема — это статически ограниченный и правильно рекурсивный диалект языка программирования Lisp, изобретенный Гаем Л. Стилом-младшим и Джеральдом Джеем Сассманом . Он был разработан, чтобы иметь исключительно ясную и простую семантику и несколько различных способов формирования выражений. Разработанный примерно на десять лет раньше, чем Common Lisp, Scheme имеет более минималистичный дизайн. Он имеет гораздо меньший набор стандартных функций, но с некоторыми функциями реализации (такими как оптимизация хвостовых вызовов и полные продолжения ), не указанными в Common Lisp. Широкий спектр парадигм программирования, включая императивные, функциональные стили и стили передачи сообщений, находят удобное выражение в Scheme. Схема продолжает развиваться благодаря серии стандартов (пересмотренный отчет об алгоритмической языковой схеме) и серии запросов на реализацию схемы .
Clojure — это диалект Lisp, ориентированный в основном на виртуальную машину Java , среду Common Language Runtime (CLR), виртуальную машину Python , виртуальную машину Ruby 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, интерпретатор Лиспа Джона Харпера, первоначально основанный на языке Emacs Lisp , был встроен в оконный менеджер Sawfish . [57]
Лисп имеет официально стандартизированные диалекты: R6RS Scheme , R7RS Scheme , IEEE Scheme, [58] ANSI Common Lisp и ISO ISLISP .
Пол Грэм выделяет девять важных аспектов Лиспа, которые отличают его от существующих языков, таких как Фортран : [59]
Лисп был первым языком, в котором структура программного кода точно и непосредственно представлена в стандартной структуре данных — качество, гораздо позже получившее название « гомоиконичность ». Таким образом, функциями Lisp можно манипулировать, изменять или даже создавать внутри программы Lisp без манипуляций на более низком уровне. Обычно это считается одним из основных преимуществ языка с точки зрения его выразительной силы и делает язык подходящим для синтаксических макросов и метациклических вычислений .
Условное выражение, использующее синтаксис if-then-else, было изобретено Маккарти для шахматной программы, написанной на Фортране . Он предложил включить его в АЛГОЛ , но он не стал частью спецификации Алгола 58 . Для Лиспа Маккарти использовал более общую структуру cond . [60] Алгол 60 взял на вооружение принцип «если-то-иначе» и популяризировал его.
Лисп оказал глубокое влияние на Алана Кея , руководителя исследовательской группы, разработавшей Smalltalk в Xerox PARC ; и, в свою очередь, на Лисп повлиял Smalltalk, а более поздние диалекты в 1970-х годах переняли функции объектно-ориентированного программирования (классы наследования, инкапсуляция экземпляров, передача сообщений и т. д.). Объектная система Flavors представила концепцию множественного наследования и примеси . Объектная система Common Lisp обеспечивает множественное наследование, мультиметоды с множественной диспетчеризацией и первоклассные универсальные функции , создавая гибкую и мощную форму динамической диспетчеризации . Он послужил шаблоном для многих последующих объектных систем Lisp (включая Scheme ), которые часто реализовывались через метаобъектный протокол — рефлексивный метациклический дизайн , в котором объектная система определяется с точки зрения самой себя: Lisp был лишь вторым языком. после Smalltalk (и до сих пор это один из немногих языков), обладающих такой метаобъектной системой. Много лет спустя Алан Кей предположил, что в результате слияния этих функций только Smalltalk и Lisp можно рассматривать как правильно продуманные системы объектно-ориентированного программирования. [61]
Лисп представил концепцию автоматической сборки мусора , при которой система ходит по куче в поисках неиспользуемой памяти. Прогресс в разработке современных сложных алгоритмов сборки мусора, таких как сборка мусора по поколениям, был стимулирован их использованием в Lisp. [62]
Эдсгер В. Дейкстра в своей лекции на Премии Тьюринга 1972 года сказал:
Имея в своей основе несколько базовых принципов, он [LISP] продемонстрировал замечательную стабильность. Кроме того, LISP стал основой для значительного числа наших самых сложных компьютерных приложений. LISP в шутку называют «самым разумным способом неправильного использования компьютера». Я думаю, что это описание — великий комплимент, поскольку оно передает всю суть освобождения: оно помогло ряду наших самых одаренных собратьев задуматься о ранее невозможных мыслях. [63]
Во многом из-за своих требований к ресурсам раннего вычислительного оборудования (включая ранние микропроцессоры), Лисп не стал таким популярным за пределами сообщества искусственного интеллекта , как Фортран и язык C , потомок АЛГОЛА . Из-за своей пригодности для сложных и динамичных приложений в 2010-х годах к Лиспу вновь возродился общественный интерес. [64]
Лисп — язык, ориентированный на выражения . В отличие от большинства других языков, между «выражениями» и «утверждениями» не делается различий ; [ сомнительно ] весь код и данные написаны в виде выражений. Когда выражение оценивается , оно создает значение (возможно, несколько значений), которое затем можно внедрить в другие выражения. Каждое значение может быть любым типом данных.
В статье Маккарти 1958 года были представлены два типа синтаксиса: символические выражения ( S-выражения , sexps), которые отражают внутреннее представление кода и данных; и метавыражения ( М-выражения ), которые выражают функции S-выражений. М-выражения никогда не пользовались популярностью, и сегодня почти все Lisps используют S-выражения для манипулирования как кодом, так и данными.
Использование круглых скобок — самое очевидное отличие Лиспа от других семейств языков программирования. В результате студенты уже давно дали Лиспу прозвища, такие как « Потерянные в глупых скобках » или «Множество раздражающих лишних скобок» . [65] Однако синтаксис S-выражений также отвечает за большую часть возможностей Лиспа: синтаксис прост и последователен, что облегчает манипулирование компьютером. Однако синтаксис Лиспа не ограничивается традиционной записью в круглых скобках. Его можно расширить, включив в него альтернативные обозначения. Например, XMLisp — это расширение Common Lisp, которое использует протокол метаобъектов для интеграции S-выражений с расширяемым языком разметки ( XML ).
Использование выражений придает языку большую гибкость. Поскольку функции Лиспа написаны в виде списков, их можно обрабатывать точно так же, как и данные. Это позволяет легко писать программы, которые манипулируют другими программами ( метапрограммирование ). Многие диалекты Лиспа используют эту возможность с помощью макросистем, что позволяет расширять язык практически без ограничений.
Список Lisp записывается так, что его элементы разделяются пробелами и заключаются в круглые скобки. Например, это список, элементами которого являются три атома , и . Эти значения типизированы неявно: они представляют собой соответственно два целых числа и тип данных, специфичный для Lisp, называемый «символ», и их не обязательно объявлять как таковые.(1 2 foo) 12foo
Пустой список ()также представлен как специальный атом nil. Это единственная сущность в Лиспе, которая одновременно является атомом и списком.
Выражения записываются в виде списков с использованием префиксной записи . Первый элемент в списке — это имя функции, имя макроса, лямбда-выражение или имя «специального оператора» (см. ниже). Остальная часть списка — это аргументы. Например, функция 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
В Лиспе нет понятия операторов, реализованного в языках, производных от Алгола. Арифметические операторы в Лиспе — это вариативные функции (или n-арные ), способные принимать любое количество аргументов. Оператор приращения '++' в стиле C иногда реализуется в синтаксисе, incfдающем имя.
( вкл. х ) эквивалентно (setq x (+ x 1)), возвращая новое значение x.
«Специальные операторы» (иногда называемые «специальными формами») обеспечивают структуру управления Лиспом. Например, специальный оператор ifпринимает три аргумента. Если первый аргумент не равен нулю, он оценивается как второй аргумент; в противном случае он оценивается как третий аргумент. Таким образом, выражение
( если ноль ( список 1 2 «foo» ) ( список 3 4 «бар» )) оценивается как . Конечно, это было бы полезнее, если бы вместо .(3 4 "bar")nil
В Lisp также предусмотрены логические операторы and , or и not . Операторы and и or выполняют сокращенную оценку и возвращают свой первый нулевой и ненулевой аргумент соответственно.
( или ( и «ноль» ноль «никогда» ) «Джеймс» « время задачи » ) будет оцениваться как «Джеймс».
Другой специальный оператор lambdaиспользуется для привязки переменных к значениям, которые затем вычисляются в выражении. Этот оператор также используется для создания функций: аргументы представляют собой 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 ) #' ( лямбда ( a ) ( блок f b... ))) где setf— макрос, используемый для установки значения первого аргумента нового функционального объекта. — это глобальное определение функции для функции с именем . — это сокращение от специального оператора, возвращающего объект функции.fdefinition 'ffdefinitionf#'function
В исходном LISP было два фундаментальных типа данных : атомы и списки. Список представлял собой конечную упорядоченную последовательность элементов, где каждый элемент был либо атомом, либо списком, а атом — числом или символом. Символ по существу представлял собой уникальный именованный элемент, записанный в виде буквенно-цифровой строки в исходном коде и используемый либо как имя переменной, либо как элемент данных при символьной обработке . Например, список содержит три элемента: символ , список и цифру 2.(FOO (BAR 1) 2)FOO(BAR 1)
Существенная разница между атомами и списками заключалась в том, что атомы были неизменяемыми и уникальными. Два атома, которые появлялись в разных местах исходного кода, но были написаны совершенно одинаково, представляли один и тот же объект, тогда как каждый список представлял собой отдельный объект, который мог быть изменен независимо от других списков и отличался от других списков по операторы сравнения.
По мере того как в более поздних диалектах Лиспа было введено больше типов данных и развивались стили программирования , концепция атома теряла значение. [ нужна цитация ] Многие диалекты по-прежнему сохраняли предикат атом для совместимости с устаревшими версиями , [ нужна цитация ] определяя его истинным для любого объекта, который не является минусом.
Список Lisp реализован как односвязный список . [66] Каждая ячейка этого списка называется cons (в Scheme — пара ) и состоит из двух указателей , называемых car и cdr . Они соответственно эквивалентны полям dataи , обсуждаемым в связанном спискеnext статьи .
Из множества структур данных, которые можно построить из ячеек cons, одна из самых простых называется правильным списком . Правильный список — это либо специальный nilсимвол (пустой список), либо cons, в котором carуказывает на элемент данных (который может быть другой структурой cons, такой как список), а указывает cdrна другой правильный список.
Если данный cons считается главой связанного списка, то его car указывает на первый элемент списка, а его cdr указывает на остальную часть списка. По этой причине функции carи также cdrвызываются при обращении к конусам, которые являются частью связанного списка (а не, скажем, дерева).firstrest
Таким образом, список Lisp не является атомарным объектом, каким был бы экземпляр класса-контейнера в C++ или Java. Список — это не что иное, как совокупность связанных конусов. Переменная, которая ссылается на данный список, является просто указателем на первый минус в списке. Обход списка можно выполнить, пропустив список вниз ; то есть использование последовательных CDR для посещения каждого минуса в списке; или используя любую из нескольких функций более высокого порядка для сопоставления функции со списком.
Поскольку константы и списки настолько универсальны в системах Lisp, распространено заблуждение, что они являются единственными структурами данных Lisp. Фактически, все Лиспы, кроме самых упрощенных, имеют другие структуры данных, такие как векторы ( массивы ), хеш-таблицы , структуры и т. д.
S-выражения в скобках представляют структуры связанного списка. Существует несколько способов представить один и тот же список в виде S-выражения. Минусы можно записать в виде пар точек , где находится автомобиль и CDR. Более длинный правильный список можно записать в виде пар точек. Это условно сокращается, как в нотации списка . Неправильный список [67] может быть записан в виде комбинации этих двух – как и список из трех конусов, последним 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процедура асимметрична в обработке аргументов списка из-за особенностей построения списков.
( cons 1 ' ( 2 3 ) ) ; Выход: (1 2 3) ( cons ' ( 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, будучи простыми связанными списками, могут иметь общую структуру. То есть два списка могут иметь один и тот же хвост или конечную последовательность выводов. Например, после выполнения следующего кода Common Lisp:
( setf foo ( list 'a 'b 'c )) ( setf bar ( cons 'x ( cdr foo ))) списки fooи barявляются и соответственно. Однако хвост имеет одинаковую структуру в обоих списках. Это не копия; ячейки минусов указывают на одни и те же ячейки памяти для обоих списков и находятся в них.(a b c)(x b c)(b c)bc
Совместное использование структуры вместо копирования может привести к значительному повышению производительности. Однако этот метод может нежелательным образом взаимодействовать с функциями, которые изменяют списки, передаваемые им в качестве аргументов. Изменение одного списка, например замена на ca goose, повлияет на другой:
( setf ( третий foo ) 'гусь ) Это изменится fooна , но при этом также изменится на – возможно, неожиданный результат. Это может быть источником ошибок, и именно по этой причине функции, изменяющие свои аргументы, документируются как деструктивные .(a b goose)bar(x b goose)
Поклонники функционального программирования избегают деструктивных функций. В диалекте Scheme, который предпочитает функциональный стиль, имена деструктивных функций отмечаются предостерегающим восклицательным знаком или «bang» — например set-car!(читай set car bang ), который заменяет car в минусах. В диалекте Common Lisp деструктивные функции являются обычным явлением; эквивалент set-car!назван rplacaв честь «заменить машину». Однако эту функцию можно увидеть редко, поскольку Common Lisp включает специальную возможность, setfупрощающую определение и использование деструктивных функций. В Common Lisp часто используется функциональный стиль написания кода (без деструктивных вызовов) при создании прототипа, а затем добавление деструктивных вызовов в качестве оптимизации там, где это безопасно.
Лисп оценивает выражения, которые вводит пользователь. Символы и списки оцениваются как некоторые другие (обычно более простые) выражения — например, символ вычисляется как значение переменной, которую он называет; оценивается как . Однако большинство других форм оценивают сами себя: при входе в Лисп они возвращают .(+ 2 3)555
Любое выражение также можно пометить, чтобы предотвратить его оценку (что необходимо для символов и списков). Это роль quoteспециального оператора или его сокращения '(одна кавычка). Например, обычно при вводе символа fooвозвращается значение соответствующей переменной (или ошибка, если такой переменной нет). Чтобы обратиться к буквальному символу, введите или, обычно, .(quote foo)'foo
И Common Lisp, и Scheme также поддерживают оператор обратной кавычки (называемый в Scheme квазицитой ), вводимый с `символом ( гравитационный акцент ). Это почти то же самое, что и простая кавычка, за исключением того, что она позволяет оценивать выражения и интерполировать их значения в список кавычек с помощью операторов , снятия кавычек и операторов склейки с ,@ запятой . Если переменная snueимеет значение, то ее значение равно , а значение — . Обратная кавычка чаще всего используется при определении расширений макросов. [68] [69](bar baz)`(foo ,snue)(foo (bar baz))`(foo ,@snue)(foo bar baz)
Самовычисляемые формы и формы в кавычках являются эквивалентом лисперов в Лиспе. Возможно изменение значений (изменяемых) литералов в программном коде. Например, если функция возвращает форму в кавычках, а код, вызывающий функцию, изменяет форму, это может изменить поведение функции при последующих вызовах.
( defun должна быть постоянной () ' ( один два три )) ( let (( вещи ( должны быть постоянными ))) ( setf ( третьи вещи ) 'странно ) ) ; плохой! ( должно быть постоянным ) ; возвращается (один два странных) Изменение формы в кавычках, как это, обычно считается плохим стилем и определяется ANSI Common Lisp как ошибочное (приводящее к «неопределённому» поведению в скомпилированных файлах, поскольку компилятор файла может объединить похожие константы, поместить их в память, защищенную от записи, и и т. д.).
Формализация цитаты в Лиспе была отмечена Дугласом Хофштадтером (в Гёделе, Эшере, Бахе ) и другими как пример философской идеи самореференции .
Семейство Lisp разделяется по использованию динамической или статической (лексической) области видимости . Clojure, Common Lisp и Scheme по умолчанию используют статическую область видимости, тогда как newLISP , Picolisp и встроенные языки в Emacs и AutoCAD используют динамическую область видимости. Начиная с версии 24.1, Emacs использует как динамическую, так и лексическую область видимости.
Фундаментальное различие между Лиспом и другими языками заключается в том, что в Лиспе текстовое представление программы представляет собой просто удобочитаемое описание тех же внутренних структур данных (связных списков, символов, чисел, символов и т. д.), которые используются базовая система Lisp.
Лисп использует это для реализации очень мощной системы макросов. Как и другие макроязыки, например тот, который определяется препроцессором C (препроцессор макросов для языков программирования C , Objective-C и C++ ), макрос возвращает код, который затем можно скомпилировать. Однако, в отличие от макросов препроцессора C, макросы являются функциями Lisp и поэтому могут использовать всю мощь Lisp.
Кроме того, поскольку код Lisp имеет ту же структуру, что и списки, макросы можно создавать с помощью любой функции обработки списков в языке. Короче говоря, все, что Lisp может сделать со структурой данных, макросы Lisp могут сделать с кодом. Напротив, в большинстве других языков выходные данные синтаксического анализатора являются чисто внутренними по отношению к реализации языка и не могут манипулироваться программистом.
Эта функция позволяет легко разрабатывать эффективные языки внутри языков. Например, объектная система Common Lisp может быть реализована как расширение языка с использованием макросов. Это означает, что если приложению нужен другой механизм наследования, оно может использовать другую объектную систему. Это резко контрастирует с большинством других языков; например, Java не поддерживает множественное наследование, и нет разумного способа его добавить.
В упрощенных реализациях Lisp эта структура списка напрямую интерпретируется для запуска программы; функция — это буквально часть структуры списка, по которой интерпретатор проходит при ее выполнении. Однако большинство существенных систем Lisp также включают в себя компилятор. Компилятор преобразует структуру списка в машинный код или байт-код для выполнения. Этот код может работать так же быстро, как код, скомпилированный на обычных языках, таких как C.
Макросы расширяются перед этапом компиляции и, таким образом, предлагают некоторые интересные возможности. Если программе нужна предварительно вычисленная таблица, то макрос может создать таблицу во время компиляции, поэтому компилятору нужно только вывести таблицу и не вызывать код для создания таблицы во время выполнения. Некоторые реализации Lisp даже имеют механизм, eval-whenкоторый позволяет коду присутствовать во время компиляции (когда он понадобится макросу), но не присутствовать в создаваемом модуле. [70]
Языки Lisp часто используются с интерактивной командной строкой , которую можно объединить с интегрированной средой разработки (IDE). Пользователь вводит выражения в командной строке или дает команду IDE передать их в систему Lisp. Лисп читает введенные выражения, оценивает их и печатает результат. По этой причине командная строка Lisp называется циклом чтения-оценки-печати ( REPL ).
Основная работа REPL заключается в следующем. Это упрощенное описание, в котором опущены многие элементы настоящего Лиспа, такие как кавычки и макросы.
Функция readпринимает на вход текстовые S-выражения и анализирует их во внутреннюю структуру данных. Например, если вы вводите текст в приглашении, преобразует его в связанный список с тремя элементами: символом , числом 1 и числом 2. Так получается, что этот список также является допустимой частью кода Lisp; то есть его можно оценить. Это связано с тем, что машина списка называет функцию — операцию сложения.(+ 1 2)read+
Обратите внимание, что a fooбудет читаться как один символ. 123будет читаться как число сто двадцать три. "123"будет читаться как строка «123».
Функция evalоценивает данные, возвращая в результате ноль или более других данных Lisp. Оценка не обязательно должна означать интерпретацию; некоторые системы Lisp компилируют каждое выражение в собственный машинный код. Однако описать оценку как интерпретацию просто: чтобы оценить список, машина которого называет функцию, evalсначала оценивается каждый из аргументов, заданных в его cdr, а затем применяется функция к аргументам. В данном случае функция является сложением, и ее применение к списку аргументов дает ответ . Это результат оценки.(1 2)3
Символ fooоценивается как значение символа foo. Такие данные, как строка «123», оцениваются как одна и та же строка. Результатом списка является список (1 2 3).(quote (1 2 3))
Задача функции print— представлять вывод пользователю. Ведь такой простой результат 3тривиален. Выражение, которое оценивается как часть структуры списка, потребует printпройти по списку и распечатать его как S-выражение.
Чтобы реализовать Lisp REPL, необходимо реализовать только эти три функции и функцию бесконечного цикла. (Естественно, реализация evalбудет сложной, поскольку она также должна реализовывать все специальные операторы, такие как ifили lambda.) После этого базовый REPL представляет собой одну строку кода: .(loop (print (eval (read))))
Lisp REPL обычно также обеспечивает редактирование ввода, историю ввода, обработку ошибок и интерфейс для отладчика.
Lisp обычно оценивается с нетерпением . В Common Lisp аргументы оцениваются в аппликативном порядке («самый левый внутренний»), тогда как в Scheme порядок аргументов не определен, что оставляет место для оптимизации компилятором.
Первоначально в Lisp было очень мало управляющих структур, но в ходе эволюции языка было добавлено гораздо больше. (Первоначальный условный оператор Лиспа , condявляется предшественником более поздних if-then-elseструктур.)
Программисты, использующие диалект Scheme, часто выражают циклы, используя хвостовую рекурсию . Общность Scheme в академической информатике привела некоторых студентов к мысли, что хвостовая рекурсия — единственный или наиболее распространенный способ написания итераций в Lisp, но это неверно. Все часто встречающиеся диалекты Лиспа имеют конструкции итерации в императивном стиле, от doцикла Scheme до сложных выражений Common Lisploop . Более того, ключевой вопрос, который делает это объективным, а не субъективным вопросом, заключается в том, что Scheme предъявляет особые требования к обработке хвостовых вызовов , и, таким образом, причина, по которой использование хвостовой рекурсии обычно поощряется для Scheme, заключается в том, что эта практика явно поддерживается определение языка. Напротив, ANSI Common Lisp не требует [71] оптимизации, обычно называемой устранением хвостового вызова. Таким образом, тот факт, что стиль хвостовой рекурсии в качестве случайной замены использования более традиционных итерационных конструкций (таких как do, dolistили loop) не приветствуется [72] в Common Lisp, является не просто вопросом стилистических предпочтений, но потенциально вопросом эффективности (поскольку очевидный хвостовой вызов в Common Lisp может не скомпилироваться как простой переход ) и корректность программы (поскольку хвостовая рекурсия может увеличить использование стека в Common Lisp, рискуя переполнением стека ).
Некоторые управляющие структуры Лиспа представляют собой специальные операторы , эквивалентные синтаксическим ключевым словам других языков. Выражения, использующие эти операторы, имеют тот же внешний вид, что и вызовы функций, но отличаются тем, что аргументы не обязательно оцениваются или, в случае выражения итерации, могут оцениваться более одного раза.
В отличие от большинства других основных языков программирования, Лисп позволяет реализовывать структуры управления с помощью языка. Некоторые структуры управления реализованы в виде макросов Lisp и могут даже быть расширены макросами программистом, который хочет знать, как они работают.
И Common Lisp, и Scheme имеют операторы для нелокального потока управления. Различия в этих операторах являются одними из самых глубоких различий между двумя диалектами. Схема поддерживает реентерабельные продолжения с использованием call/ccпроцедуры, которая позволяет программе сохранять (а затем восстанавливать) определенное место выполнения. Common Lisp не поддерживает повторные продолжения, но поддерживает несколько способов обработки escape-продолжений.
Часто один и тот же алгоритм может быть выражен в Лиспе либо в императивном, либо в функциональном стиле. Как отмечалось выше, Scheme имеет тенденцию отдавать предпочтение функциональному стилю, используя хвостовую рекурсию и продолжения для выражения потока управления. Однако императивный стиль все же вполне возможен. Стиль, предпочитаемый многими программистами Common Lisp, может показаться более знакомым программистам, привыкшим к структурированным языкам, таким как C, тогда как стиль, предпочитаемый Schemers, больше напоминает чисто функциональные языки, такие как Haskell .
Благодаря раннему наследию Лиспа в области обработки списков, он имеет широкий набор функций высшего порядка, связанных с итерацией по последовательностям. Во многих случаях, когда в других языках необходим явный цикл (например, 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 Lisploop :
( defun факториал ( n ) ( цикл для i от 1 до n для fac = 1 , затем ( * fac i ) наконец ( return fac ))) Следующая функция переворачивает список. (Встроенная обратная функция Лиспа делает то же самое.)
( defun -reverse ( список ) ( let (( возвращаемое значение )) ( dolist ( e list ) ( push e возвращаемое значение )) возвращаемое значение )) Различные объектные системы и модели были построены поверх Lisp, вместе с ним или в него, в том числе
Некоторые операционные системы , включая системы на основе языка , основаны на Lisp (используют функции Lisp, соглашения, методы, структуры данных и т. д.) или написаны на Lisp, [75] в том числе
Genera , переименованная в Open Genera, [76] компанией Symbolics ; Medley, написанная на Interlisp, первоначально семействе графических операционных систем, работавших на более поздних рабочих станциях Xerox Star ; [77] [78] Медзано; [79] Временный; [80] [81] ChrysaLisp, [82] от разработчиков TAOS компании Tao Systems. [83]
Lisp выжил, его используют уже около четверти века. Среди активных языков программирования только Фортран просуществовал дольше.
Проект PDP-6 стартовал в начале 1963 года как 24-битная машина. Для LISP он вырос до 36 бит, что было целью разработки.
(defun f (x) x)(define f (lambda (x) x))или(define (f x) x)Clojure — это Lisp, не ограниченный обратной совместимостью.
Я изобрел условные выражения в связи с набором правильных ходов в шахматах, которые я написал на ФОРТРАНЕ для IBM 704 в Массачусетском технологическом институте в 1957–58 годах ... Документ, определяющий условные выражения и предлагающий их использование в Алголе, был отправлен в отдел сообщений ACM. но был произвольно понижен в должности до письма в редакцию, потому что оно было очень коротким.
Тогда я не понимал чудовищной идеи LISP о материальном метаязыке, но был в некотором роде близок к идеям о расширяемых языках... Второй этап этого заключался в том, чтобы наконец понять LISP, а затем использовать это понимание, чтобы сделать намного лучше, меньше и больше. мощные и более поздние связываемые подструктуры... ООП для меня означает только обмен сообщениями, локальное сохранение и защиту, а также сокрытие состояний-процессов и крайне позднее связывание всех вещей. Это можно сделать в Smalltalk и LISP. Возможно, есть и другие системы, в которых это возможно, но я о них не знаю.
Определения из Викисловаря
СМИ из Commons
Цитаты из Wikiquote
Тексты из Wikisource
Учебники из Wikibooks
Ресурсы из Викиверситета