Войти
 | |
| Парадигма | Мультипарадигма : функциональный, процедурный, отражающий, мета |
|---|---|
| Разработан | Джон Маккарти |
| Разработчик | Стив Рассел, Тимоти П., Харт и Майк Левин |
| Впервые появилось | 1958; 62 года назад (1958) |
| Дисциплина набора текста | Динамический, сильный |
| Диалекты | |
| Под влиянием | |
| IPL | |
| Под влиянием | |
Lisp (исторически LISP ) - это семейство языков программирования с долгой историей и отличительной, полностью скобкой нотацией префикса. Первоначально указанный в 1958 году, Lisp является вторым по возрасту языком программирования высокого уровня, широко используемым сегодня. Только Fortran старше, на год. Лисп изменился с самого начала, и за его историю существовало множество диалектов. Сегодня наиболее известными диалектами Лиспа общего назначения являются Racket, Common Lisp, Scheme и Clojure.
Lisp изначально создавался как практическая математическая нотация для компьютерных программ, на которую повлияла (хотя и не была изначально) нотация Алонзо Чёрча лямбда-исчисления. Он быстро стал излюбленным языком программирования для исследований искусственного интеллекта (AI). Как один из самых ранних языков программирования, Lisp был пионером многих идей в информатике, включая древовидные структуры данных, автоматическое управление памятью, динамическую типизацию, условные выражения, функции высшего порядка, рекурсия, self-hosting компилятор и цикл чтения – оценки – печати.
Название LISP происходит от «LISt Processor». Связанные списки являются одной из основных структур данных Лиспа, а исходный код Лиспа состоит из списков. Таким образом, программы на Лиспе могут манипулировать исходным кодом как структурой данных, что дает начало системам макросов , которые позволяют программистам создавать новый синтаксис или новые предметно-ориентированные языки, встроенные в Лисп.
Взаимозаменяемость кода и данных придает Lisp мгновенно узнаваемый синтаксис. Весь программный код записывается в виде s-выражений или списков в скобках. Вызов функции или синтаксическая форма записываются в виде списка с именем функции или оператора вначале и последующими аргументами; например, функция f, которая принимает три аргумента, будет вызываться как (f arg1 arg2 arg3).
Джон Маккарти (вверху) и Стив Рассел Джон Маккарти разработал Lisp в 1958 году, когда он работал в Массачусетсе Технологический институт (MIT). Маккарти опубликовал свой проект в статье Communications of the ACM в 1960 году, озаглавленной «Рекурсивные функции символьных выражений и их машинное вычисление, часть I». Он показал, что с помощью нескольких простых операторов и обозначения анонимных функций, заимствованных у Черча, можно построить полный по Тьюрингу язык для алгоритмов.
Язык обработки информации был первым языком искусственного интеллекта с 1955 или 1956 года и уже включал многие концепции, такие как обработка списков и рекурсия, которые стали использоваться в Лиспе.
В исходной нотации Маккарти использовались заключенные в квадратные скобки «M-выражения », которые могли быть переведены в S-выражения. Например, M-выражение car [cons [A, B]]эквивалентно S-выражению (car (cons A B)). После того, как Lisp был реализован, программисты быстро решили использовать S-выражения, и M-выражения были оставлены. M-выражения снова появились с недолгими попытками MLisp by и CGOL by Vaughan Pratt.
Лисп был впервые реализован Стивом Расселом на компьютер IBM 704, использующий перфокарты. Рассел прочитал статью Маккарти и понял (к удивлению Маккарти), что функция eval Лиспа может быть реализована в машинном коде. Результатом стал работающий интерпретатор Лиспа, который можно было использовать для запуска программ Лиспа, или, точнее, «оценки выражений Лиспа».
Два макроса языка ассемблера для IBM 704 стали примитивными операциями для декомпозиции списков: car (Содержимое адресная часть номера регистра) и cdr (содержание части уменьшения номера регистра), где «регистр» используется для ссылки на регистры компьютерный центральный процессор (CPU). Диалекты Лиспа по-прежнему используют carи cdr(и ) для операций, возвращающих первый элемент в list и остальной список соответственно.
Первый полный компилятор Лиспа, написанный на Лиспе, был реализован в 1962 году Тимом Хартом и Майком Левиным из Массачусетского технологического института. Этот компилятор представил Lisp-модель инкрементальной компиляции, в которой скомпилированные и интерпретируемые функции могут свободно смешиваться. Язык, использованный в записке Харта и Левина, намного ближе к современному стилю Лиспа, чем к более раннему коду Маккарти.
Первые процедуры сборки мусора были разработаны аспирантом Массачусетского технологического института.
В течение 1980-х и 1990-х годов были предприняты большие усилия по унификации работы над новыми диалектами Лиспа ( в основном преемники Maclisp, такие как ZetaLisp и NIL (новая реализация Лиспа) на одном языке. Новый язык, Common Lisp, был в некоторой степени совместим с диалекты, которые он заменил (книга Common Lisp the Language отмечает совместимость различных конструкций). В 1994 году ANSI опубликовал стандарт Common Lisp "ANSI X3.226-1994. Программирование информационных технологий Язык Common Lisp ".
С самого начала Lisp был тесно связан с сообществом исследователей искусственного интеллекта, особенно в Системы PDP-10. Lisp использовался как реализация языка программирования Micro Planner, который использовался в известной системе AI ШРДЛУ. В 1970-х годах, когда исследования ИИ породили коммерческие ответвления, производительность существующих систем Lisp стала растущей проблемой.
За свою шестидесятилетнюю историю Lisp породил множество вариаций на тему основная тема языка S-выражения. Более того, каждый данный диалект может иметь несколько реализаций - например, существует более дюжины реализаций Common Lisp.
. Различия между диалектами могут быть весьма заметными - например, Common Lisp использует ключевое слово defun, чтобы назвать функцию, но в схеме используется define. Однако внутри стандартизованного диалекта соответствующие реализации поддерживают один и тот же базовый язык, но с разными расширениями и библиотеками.
A Лисп-машина в MIT Museum 
4.3 BSD из Университета Висконсина, с изображением человека страница для Franz Lisp После некоторого упадка в 1990-х годах Lisp пережил возрождение интерес после 2000 года. Большая часть новой деятельности была сосредоточена вокруг реализации Common Lisp, Scheme, Emacs Lisp, Clojure и Racket и включает разработку новых переносимых библиотек и приложений.
Многие начинающие программисты на Лиспе были вдохновлены такими писателями, как Пол Грэм и Эрик С. Реймонд, на изучение языка, который другие считали устаревшим. Программисты-новички в Lisp часто описывают язык как открывающий глаза опыт и заявляют, что он значительно более продуктивен, чем на других языках. Это повышение осведомленности можно сравнить с «AI winter » и кратковременным успехом Lisp в середине 1990-х.
Дэн Вайнреб перечисляет в своем обзоре реализаций Common Lisp одиннадцать активно поддерживаемых Common Lisp реализации. Scieneer Common Lisp - это новая коммерческая реализация, созданная на основе CMUCL с первым выпуском в 2002 году.
Сообщество с открытым исходным кодом создало новую вспомогательную инфраструктуру: CLiki - это вики который собирает информацию, относящуюся к Common Lisp, списки ресурсов, #lisp - популярный канал IRC, позволяющий обмениваться фрагментами кода и комментировать их (при поддержке IRC-ботом, написанным на Lisp), собирает содержимое различные блоги, связанные с Lisp, на которых пользователи обсуждают темы Lisp, это служба для объявления предложений о работе и еженедельная служба новостей. Common-lisp.net - это хостинг для проектов Common Lisp с открытым исходным кодом. Quicklisp - менеджер библиотек для Common Lisp.
50 лет Lisp (1958–2008) отмечалось на LISP50 @ OOPSLA. Регулярно проводятся встречи местных пользователей в Бостоне, Ванкувере и Гамбурге. Другие мероприятия включают Европейскую встречу по Лиспу, Европейский симпозиум по Лиспу и Международную конференцию по Лисп.
Сообщество Scheme активно поддерживает более двадцати реализаций. Несколько важных новых реализаций (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) были разработаны в 2000-х годах (десятилетие). Пересмотренный отчет о стандарте схемы алгоритмического языка Scheme получил широкое признание в сообществе Scheme. Процесс Scheme Requests for Implementation создал множество квазистандартных библиотек и расширений для Scheme. Сообщества пользователей отдельных реализаций схем продолжают расти. Новый процесс стандартизации языка был начат в 2003 году и привел к стандарту RRS Scheme в 2007 году. Академическое использование Scheme для обучения информатике, похоже, несколько снизилось. Некоторые университеты больше не используют Scheme в своих вводных курсах по информатике; MIT теперь использует Python вместо Scheme для своей программы бакалавриата информатики и массового открытого онлайн-курса MITx.
Есть несколько новых диалектов Лиспа: Arc, Hy, Nu и LFE (Erlang со вкусом Lisp). Синтаксический анализатор для Julia реализован на Femtolisp, диалекте Scheme (Julia вдохновлен Scheme, который, в свою очередь, является диалектом Lisp).
В октябре 2019 года Пол Грэм выпустил спецификацию для Bel, «нового диалекта Лиспа».
Common Lisp и Scheme представляют два основных потока разработки Lisp. Эти языки воплощают в себе существенно разные варианты дизайна.
Common Lisp является преемником Maclisp. Основное влияние оказали Lisp Machine Lisp, Maclisp, NIL, S-1 Lisp, Spice Lisp и Scheme. Он имеет многие особенности Lisp Machine Lisp (большой диалект Lisp, используемый для программирования Lisp Machines ), но был разработан для эффективной реализации на любом персональном компьютере или рабочей станции. Common Lisp - это язык программирования общего назначения и, следовательно, имеет большой стандарт языка, включающий множество встроенных типов данных, функций, макросов и других языковых элементов, а также объектную систему (Common Lisp Object System ). Common Lisp также заимствовал некоторые функции из Scheme, такие как лексическая область видимости и лексические замыкания. Доступны реализации Common Lisp для различных платформ, таких как LLVM, виртуальная машина Java, x86-64, PowerPC, Alpha, ARM, Motorola 68000 и MIPS, а также операционные системы. таких как Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD и Heroku.
Схема - это статически ограниченный и правильно рекурсивный диалект языка программирования Lisp, изобретенный Гаем Л. Стил-младший и Джеральд Джей Сассман. Он был разработан, чтобы иметь исключительно ясную и простую семантику и несколько различных способов формирования выражений. Разработанная примерно на десять лет раньше, чем Common Lisp, Scheme представляет собой более минималистичный дизайн. Он имеет гораздо меньший набор стандартных функций, но с некоторыми функциями реализации (такими как оптимизация хвостового вызова и полные продолжения ), не указанные в Common Lisp. Широкий спектр парадигм программирования, включая императивный, функциональный и стиль передачи сообщений, находит удобное выражение в Scheme. Scheme продолжает развиваться с рядом стандартов (Revised 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 и делает очень сильный упор на неизменяемость. Clojure обеспечивает доступ к инфраструктурам и библиотекам Java, с дополнительными подсказками типов и выводом типа, так что вызовы Java могут избежать отражения и обеспечить быстрые примитивные операции. Clojure не предназначен для обратной совместимости с другими диалектами Лиспа.
Кроме того, диалекты Лиспа используются в качестве языков сценариев во многих приложениях, наиболее известным из которых является Emacs Lisp в редакторе Emacs, AutoLISP и более поздних версиях Visual Lisp в AutoCAD, Найквист в, Схема в LilyPond. Потенциально небольшой размер полезного интерпретатора схемы делает его особенно популярным для встраиваемых сценариев. Примеры включают SIOD и TinyScheme, оба из которых были успешно встроены в процессор изображений GIMP под общим названием "Script-fu". LIBREP, интерпретатор Лиспа Джона Харпера, изначально основанный на языке Emacs Lisp, был встроен в оконный менеджер Sawfish .
Lisp имеет официально стандартизованные диалекты: Схема R6RS, Схема R7RS, Схема IEEE, ANSI Common Lisp и ISO ISLISP.
Лисп был первым языком, в котором структура программного кода точно и прямо представлена в стандартной структуре данных - качество, которое намного позже было названо «гомоиконностью ». Таким образом, функциями Lisp можно управлять, изменять или даже создавать в программе на Лиспе без манипуляций нижнего уровня. Это обычно считается одним из основных преимуществ языка в отношении его выразительной силы и делает язык пригодным для синтаксических макросов и метакруглого вычисления.
условного выражения с использованием if – then – else Синтаксис был изобретен Маккарти в контексте Фортрана. Он предложил включить его в АЛГОЛ, но он не стал частью спецификации Алгол 58. Для Лиспа Маккарти использовал более общую структуру cond. Algol 60 взял if – then – else и популяризировал его.
Лисп оказал глубокое влияние на Алана Кея, руководителя исследовательской группы, которая разработала Smalltalk в Xerox PARC ; и, в свою очередь, Lisp находился под влиянием Smalltalk, а в более поздних диалектах в 1970-х годах были приняты функции объектно-ориентированного программирования (классы наследования, инкапсуляция экземпляров, передача сообщений и т.д.). В объектной системе Flavors введена концепция множественного наследования и примеси . Common Lisp Object System обеспечивает множественное наследование, мультиметоды с множественной диспетчеризацией и первоклассные универсальные функции, обеспечивая гибкую и мощную форму динамической отправка. Он служил шаблоном для многих последующих объектных систем Lisp (включая Scheme ), которые часто реализуются через протокол метаобъектов, отражающий метациркулярный протокол. дизайн, в котором объектная система определяется в терминах самого себя: Lisp был лишь вторым языком после Smalltalk (и все еще одним из очень немногих языков), обладающим такой системой метаобъектов. Много лет спустя Алан Кей предположил, что в результате слияния этих возможностей только Smalltalk и Lisp можно рассматривать как правильно задуманные системы объектно-ориентированного программирования.
Lisp ввел концепцию автоматического мусора. коллекция, в которой система просматривает кучу в поисках неиспользуемой памяти. Прогресс в современных сложных алгоритмах сборки мусора, таких как сборка мусора поколений, был стимулирован их использованием в Лиспе.
Эдсгер В. Дейкстра в своей лекции Премии Тьюринга 1972 года сказал:
В основном из-за требований к ресурсам. Что касается раннего компьютерного оборудования (включая ранние микропроцессоры), Lisp не стал таким популярным за пределами сообщества AI, как Fortran и ALGOL -desceded C язык. Благодаря своей пригодности для сложных и динамических приложений, Lisp вновь стал популярным в 2010-х.
Lisp - это язык, ориентированный на выражения. В отличие от большинства других языков, никаких различий находится между «выражениями» и «операторами» ; весь код и данные записываются как выражения. Когда выражение вычисляется, оно производит значение (в Common Lisp, возможно, несколько значений), которое затем может быть встроены в другие выражения. Каждое значение может быть любым типом данных.
В статье Маккарти 1958 года были представлены два типа синтаксиса: символические выражения (S-выражения, sexps), которые отражают внутреннее представление код и данные; и мета-выражения (M-выражения ), которые выражают функции S-выражений. M-выражения никогда не Унд пользу, и почти все Lisp сегодня используют S-выражения для управления как кодом, так и данными.
Использование круглых скобок - наиболее очевидное отличие Лиспа от других семейств языков программирования. В результате студенты давно дали Lisp прозвища, такие как «Затерянный в глупых скобках» или «Множество раздражающих лишних скобок». Однако синтаксис S-выражения также отвечает за большую часть возможностей Лиспа: синтаксис чрезвычайно регулярный, что облегчает манипуляции с компьютером. Однако синтаксис Лиспа не ограничивается традиционными скобками. Его можно расширить, включив альтернативные обозначения. Например, XMLisp - это расширение Common Lisp, которое использует протокол метаобъектов для интеграции S-выражений с Extensible Markup Language (XML ).
Использование выражений придает языку большую гибкость. Поскольку Lisp функции записаны в виде списков, их можно обрабатывать точно так же, как данные. Это позволяет легко писать программы, которые манипулируют другими программами (метапрограммирование ). Многие диалекты Лиспа используют эту возможность с помощью макросистем, которые позволяют расширять язык почти без ограничений.
Список Лиспа записывается с элементами, разделенными пробелом и окруженными круглыми скобками. Например, (1 2 foo)- это список, элементами которого являются три атома 1, 2и foo. Эти значения неявно типизированы: они представляют собой соответственно два целых числа и специфичный для Лиспа тип данных, называемый «символом», и их не нужно объявлять как таковые.
Пустой список ()также представлен как специальный атом nil. Это единственная сущность в Лиспе, которая одновременно является атомом и списком.
Выражения записываются в виде списков с использованием префиксной записи . Первый элемент в списке - это имя функции, имя макроса, лямбда-выражение или имя «специального оператора» (см. Ниже). Остальная часть списка - аргументы. Например, функция listвозвращает свои аргументы в виде списка, поэтому выражение
(list 1 2 (quote 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, что дает синтаксис
(incf x)
, эквивалентный (setq x (+ x 1)), возвращая новое значение x.
«Специальные операторы» (иногда называемые «специальными формами») предоставляют структуру управления Лиспа. Например, специальный оператор ifпринимает три аргумента. Если первый аргумент не равен нулю, он оценивает второй аргумент; в противном случае вычисляется третий аргумент. Таким образом, выражение
(если nil (list 1 2 "foo") (list 3 4 "bar"))
оценивается как (3 4 "bar"). Конечно, это было бы более полезно, если бы вместо nil.
было подставлено нетривиальное выражение. Lisp также предоставляет логические операторы и, orи not . Операторы и и или выполняют оценку короткого замыкания и возвращают свой первый аргумент nil и non-nil соответственно.
(или (и «ноль» ноль «никогда») «время задачи Джеймса»)
будет оцениваться как «Джеймс».
Другой специальный оператор, лямбда, используется для привязки переменных к значениям, которые затем оцениваются в выражении. Этот оператор также используется для создания функций: аргументы для лямбда- это список аргументов, а выражение или выражения, которые оценивает функция (возвращаемое значение - это значение последнего вычисляемого выражения). Выражение
(lambda (arg) (+ arg 1))
оценивает функцию, которая при применении принимает один аргумент, связывает его с argи возвращает число на единицу больше, чем это аргумент. Лямбда-выражения обрабатываются так же, как именованные функции; они вызываются таким же образом. Следовательно, выражение
((lambda (arg) (+ 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 'fна новый объект функции. fdefinition- определение глобальной функции для функции с именем f. #'- это сокращение для functionспециального оператора, возвращающего объект функции.
В исходном LISP было два основных типа данных : атомы и списки. Список представляет собой конечную упорядоченную последовательность элементов, где каждый элемент является либо атомом, либо списком, а атом представляет собой число или символ. По сути, символ был уникальным именованным элементом, записанным в виде буквенно-цифровой строки в исходном коде и использовавшимся либо как имя переменной, либо как элемент данных в символьной обработке. Например, список (FOO (BAR 1) 2)содержит три элемента: символ FOO, список (BAR 1)и цифру 2..
Существенная разница между атомами и списками заключалась в том, что атомы неизменны и уникальны. Два атома, которые появлялись в разных местах исходного кода, но были написаны точно так же, представляли один и тот же объект, тогда как каждый список был отдельным объектом, который можно было изменять независимо от других списков и отличать от других списков с помощью операторов сравнения.
По мере того, как в более поздних диалектах Лиспа было введено больше типов данных и развились стили программирования, концепция атома потеряла значение. Многие диалекты по-прежнему сохранили атом предиката для совместимости с наследием, определяя его истинным для любого объекта, который не является недостатком.
Блок-и- указатель диаграмма для списка (42 69 613) Список Лиспа реализован как односвязный список. Каждая ячейка этого списка называется cons (на схеме пара) и состоит из двух указателей , называемых car и cdr. Они соответственно эквивалентны полям dataи next, обсуждаемым в статье связанный список.
. Из многих структур данных, которые могут быть построены из cons-ячеек, одна из самый простой называется правильным списком. Правильный список - это либо специальный символ nil(пустой список), либо минус, в котором carуказывает на элемент данных (который может быть другой структурой cons, например списком), а cdrуказывает на другой правильный список.
Если данный cons считается заголовком связанного списка, то его car указывает на первый элемент списка, а его cdr указывает на остальную часть списка. По этой причине функции carи cdrтакже называются firstи restпри обращении к conses, которые являются частью связанного списка. (а не, скажем, дерево).
Таким образом, список Лиспа не является атомарным объектом, в отличие от экземпляра контейнерного класса в C ++ или Java. Список - это не что иное, как совокупность связанных запросов. Переменная, которая ссылается на данный список, является просто указателем на первые минусы в списке. Обход списка можно выполнить, пролистывая список вниз; то есть брать последовательные компакт-диски для посещения каждого минуса списка; или с помощью любой из нескольких функций высшего порядка для отображения функции на список.
Поскольку conses и списки настолько универсальны в системах Lisp, распространено заблуждение, что они являются единственными структурами данных Lisp. Фактически, все лиспы, кроме самых упрощенных, имеют другие структуры данных, такие как векторы (массивы ), хеш-таблицы, структуры и так далее.
Заключенные в скобки S-выражения представляют структуры связанных списков. Есть несколько способов представить один и тот же список в виде S-выражения. Cons можно записать в виде пар с точками как (a. B), где a- автомобиль, а b- cdr. Более длинный правильный список может быть записан как (a. (B. (C. (D. Nil))))в нотации, состоящей из пар точек. В нотации списка это условно сокращается как (a b c d). Неправильный список может быть записан в комбинации двух - как (abc. D)для списка из трех conses, последний cdr которых равен 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 являются связанными списками, добавление двух списков имеет асимптотическую временную сложность
(append '(1 2)' (3 4)); Вывод: (1 2 3 4)
(append '(1 2 3)' () '(a)' (5 6)); Вывод: (1 2 3 a 5 6)
Списки Лиспа, будучи простыми связными списками, могут иметь общую структуру друг с другом. Другими словами, два списка могут иметь один и тот же хвост или последнюю последовательность ответов. Например, после выполнения следующего кода Common Lisp:
(setf foo (list 'a 'b' c)) (setf bar (cons 'x (cdr foo)))
списки fooи bar: (abc)и (xbc)соответственно. Однако хвост (b c)имеет одинаковую структуру в обоих списках. Это не копия; cons-ячейки, указывающие на bи c, находятся в одинаковых ячейках памяти для обоих списков.
Совместное использование структуры вместо копирования может значительно улучшить производительность. Однако этот метод может нежелательным образом взаимодействовать с функциями, которые изменяют списки, переданные им в качестве аргументов. Изменение одного списка, например, замена cна goose, повлияет на другой:
(setf (third foo) 'goose)
Это изменит fooна (ab goose), но при этом также изменяет barна (xb goose)- возможно, неожиданный результат. Это может быть источником ошибок, и функции, которые изменяют свои аргументы, документируются как деструктивные именно по этой причине.
Поклонники функционального программирования избегают деструктивных функций. В диалекте Scheme, который отдает предпочтение функциональному стилю, имена деструктивных функций помечаются предупреждающим восклицательным знаком или "бахом" - например, set-car!(читай: set car bang), который заменяет машина из минусов. В диалекте Common Lisp деструктивные функции являются обычным явлением; эквивалент set-car!называется rplacaдля «заменить автомобиль». Однако эта функция встречается редко, поскольку Common Lisp включает специальную возможность, setf, чтобы упростить определение и использование деструктивных функций. Часто в Common Lisp используется стиль написания кода функционально (без деструктивных вызовов) при прототипировании, а затем добавление деструктивных вызовов в качестве оптимизации там, где это безопасно.
Lisp оценивает выражения, которые вводит пользователь. Символы и списки оцениваются как другое (обычно более простое) выражение - например, символ оценивается как значение переменной, которую он называет; (+ 2 3)оценивается как 5. Однако большинство других форм оценивают сами себя: если вводить 5в Lisp, он возвращает 5.
. Любое выражение также может быть помечено, чтобы предотвратить его оценку (как это необходимо для символов и списков). Это роль специального оператора quoteили его аббревиатуры '(одна кавычка). Например, обычно при вводе символа fooон возвращает значение соответствующей переменной (или ошибку, если такой переменной нет). Чтобы сослаться на буквальный символ, введите (quote foo)или, как правило, 'foo.
И Common Lisp, и Scheme также поддерживают оператор обратных кавычек (называемый квазицитат в Схема), вводится с помощью символа `(ударение ). Это почти то же самое, что и обычная кавычка, за исключением того, что она позволяет вычислять выражения и интерполировать их значения в список в кавычках с помощью запятой ,unquote и запятой-at , @операторов соединения.. Если переменная snueимеет значение (bar baz), тогда `(foo, snue)оценивается как (foo (bar baz)), а `(foo, @ snue)оценивается как (foo bar baz). Обратные кавычки чаще всего используются при определении расширений макросов.
Формы с самооценкой и формы в кавычках являются эквивалентами литералов в Лиспе. В программном коде можно изменить значения (изменяемых) литералов. Например, если функция возвращает форму в кавычках, а код, вызывающий функцию, изменяет форму, это может изменить поведение функции при последующих вызовах.
(defun should-be-constant () '(раз, два, три)) (let ((штука (должна быть-константой))) (setf (третья штука)' странно)); плохой! (должно быть постоянным); возвращает (one two bizarre)
Изменение формы в кавычках, как эта, обычно считается плохим стилем и определяется ANSI Common Lisp как ошибочное (приводящее к «неопределенному» поведению в скомпилированных файлах, потому что файловый компилятор может объединять похожие константы, поместите их в защищенную от записи память и т. д.).
Формализация цитат в Лиспе была отмечена Дугласом Хофштадтером (в Гёдель, Эшер, Бах ) и другими как пример философского идея ссылки на себя.
Семейство Lisp разделяется на использование динамического или статического (также известного как лексический) область действия. Clojure, Common Lisp и Scheme по умолчанию используют статическую область видимости, в то время как newLISP, Picolisp и встроенные языки в Emacs и AutoCAD использовать динамическую область видимости. Начиная с версии 24.1 Emacs использует как динамическую, так и лексическую область видимости.
Фундаментальное отличие Лиспа от других языков заключается в том, что в Лиспе текстовое представление программы - это просто удобочитаемое описание одних и тех же внутренних структур данных (связанные списки, символы, числа, символы и т. д.), которые будут использоваться базовой системой Lisp.
Lisp использует это для реализации очень мощной макросистемы. Как и другие языки макросов, такие как C, макрос возвращает код, который затем можно скомпилировать. Однако, в отличие от макросов C, макросы являются функциями Лиспа и поэтому могут использовать всю мощь Лиспа.
Кроме того, поскольку код на Лиспе имеет ту же структуру, что и списки, макросы могут быть построены с любой из функций обработки списков на языке. Короче говоря, все, что Lisp может делать со структурой данных, макросы Lisp могут делать с кодом. Напротив, в большинстве других языков вывод синтаксического анализатора является чисто внутренним по отношению к реализации языка и не может быть изменен программистом.
Эта функция упрощает разработку эффективных языков внутри языков. Например, объектная система Common Lisp может быть реализована чисто как расширение языка с использованием макросов. Это означает, что если приложению нужен другой механизм наследования, оно может использовать другую объектную систему. Это резко контрастирует с большинством других языков; например, Java не поддерживает множественное наследование, и нет разумного способа его добавить.
В упрощенных реализациях Лиспа эта структура списка напрямую интерпретируется для запуска программы; функция - это буквально часть структуры списка, через которую проходит интерпретатор при ее выполнении. Однако наиболее существенные системы Lisp также включают компилятор. Компилятор переводит структуру списка в машинный код или байт-код для выполнения. Этот код может выполняться так же быстро, как код, скомпилированный на традиционных языках, таких как C.
Макросы раскрываются перед этапом компиляции и, таким образом, предлагают некоторые интересные варианты. Если программе требуется предварительно вычисленная таблица, то макрос может создать таблицу во время компиляции, поэтому компилятору нужно только вывести таблицу и не нужно вызывать код для создания таблицы во время выполнения. В некоторых реализациях Лиспа даже есть механизм eval-when, который позволяет коду присутствовать во время компиляции (когда он понадобится макросу), но не присутствует в переданном модуле.
Языки Lisp часто используются с интерактивной командной строкой, которую можно комбинировать с интегрированной средой разработки (IDE). Пользователь вводит выражения в командной строке или предписывает IDE передать их системе Lisp. Lisp читает введенные выражения, оценивает их и печатает результат. По этой причине командная строка Lisp называется циклом чтение – оценка – печать (REPL ).
Основная операция REPL заключается в следующем. Это упрощенное описание, в котором отсутствуют многие элементы настоящего Лиспа, такие как цитирование и макросы.
Функция readпринимает текстовые S-выражения в качестве входных данных и анализирует их во внутреннюю структуру данных. Например, если вы наберете в приглашении текст (+ 1 2), readпреобразует его в связанный список с тремя элементами: символ +, число 1 и число 2. Так получилось, что этот список также является действительным фрагментом кода Lisp; то есть его можно оценить. Это потому, что машина списка называет функцию - операцию сложения.
Обратите внимание, что fooбудет читаться как один символ. 123будет читаться как число сто двадцать три. «123»будет читаться как строка «123».
Функция evalоценивает данные, возвращая в результате ноль или более других данных Лиспа. Оценка не обязательно означает интерпретацию; некоторые системы Lisp компилируют каждое выражение в машинный код. Однако описать оценку как интерпретацию просто: для оценки списка, машина которого называет функцию, evalсначала оценивает каждый из аргументов, указанных в его cdr, затем применяет функцию к аргументам. В этом случае функция является сложением, и ее применение к списку аргументов (1 2)дает ответ 3. Это результат оценки.
Символ fooоценивается как значение символа foo. Такие данные, как строка «123», оцениваются как одна и та же строка. Список (цитата (1 2 3))оценивается как список (1 2 3).
Это задание функции printдля представления вывода пользователю. Для простого результата, такого как 3, это тривиально. Выражение, оцениваемое как часть структуры списка, потребует, чтобы printпрошел по списку и распечатал его как S-выражение.
Чтобы реализовать Lisp REPL, необходимо реализовать только эти три функции и функцию бесконечного цикла. (Естественно, реализация evalбудет сложной, поскольку она также должна реализовывать все специальные операторы, такие как ifили лямбда.) Это сделано, базовый REPL - это одна строка кода: (loop (print (eval (read)))).
Lisp REPL обычно также обеспечивает редактирование ввода, историю ввода, обработку ошибок и интерфейс для отладчика.
Lisp обычно оценивается с нетерпением. В Common Lisp аргументы оцениваются в аппликативном порядке ('крайний левый внутренний'), в то время как в схеме порядок аргументов не определен, оставляя место для оптимизации с помощью компилятор.
Изначально в Лиспе было очень мало управляющих структур, но в процессе развития языка было добавлено гораздо больше. (Исходный условный оператор Лиспа, cond, является предшественником более поздних структур if-then-else.)
Программисты на диалекте Scheme часто выражают циклы, используя хвостовая рекурсия. Общность схемы в академической информатике привела к тому, что некоторые студенты поверили, что хвостовая рекурсия является единственным или наиболее распространенным способом написания итераций на Лиспе, но это неверно. Все часто встречающиеся диалекты Лиспа имеют конструкции итераций императивного стиля, от цикла doв Scheme до сложных выражений циклав Common Lisp. Более того, ключевой вопрос, который делает это скорее объективным, чем субъективным вопросом, заключается в том, что Scheme предъявляет особые требования к обработке хвостовых вызовов, и, таким образом, причина, по которой использование хвостовой рекурсии обычно поощряется для Scheme, заключается в том, что практика прямо поддерживается определением языка. Напротив, ANSI Common Lisp не требует оптимизации, обычно называемой устранением хвостового вызова. Таким образом, тот факт, что хвостовой рекурсивный стиль в качестве случайной замены использования более традиционных конструкций итераций (таких как do, dolistили loop) не приветствуется в Common Lisp. это не просто вопрос стилистических предпочтений, но потенциально один из вопросов эффективности (поскольку очевидный хвостовой вызов в Common Lisp может не компилироваться как простой jump ) и правильность программы (поскольку хвостовая рекурсия может увеличить использование стека в Common Lisp Лисп, рискуя переполнением стека ).
Некоторые управляющие структуры Лиспа представляют собой специальные операторы, эквивалентные синтаксическим ключевым словам других языков. Выражения, использующие эти операторы, имеют тот же внешний вид, что и вызовы функций, но отличаются тем, что аргументы не обязательно вычисляются или, в случае выражения итерации, могут оцениваться более одного раза.
В отличие от большинства других основных языков программирования, Lisp позволяет реализовать управляющие структуры с использованием языка. Некоторые управляющие структуры реализованы как макросы Лиспа, и программист может даже расширить их макрос, желающий узнать, как они работают.
И Common Lisp, и Scheme имеют операторы для нелокального потока управления. Различия в этих операторах - одни из самых глубоких различий между двумя диалектами. Схема поддерживает реентерабельные продолжения с использованием процедуры call / cc, которая позволяет программе сохранять (и позже восстанавливать) конкретное место в процессе выполнения. Common Lisp не поддерживает повторные продолжения, но поддерживает несколько способов обработки escape-продолжений.
Часто один и тот же алгоритм может быть выражен в Лиспе либо в императивном, либо в функциональном стиле. Как отмечалось выше, Scheme предпочитает функциональный стиль, используя хвостовую рекурсию и продолжения для выражения потока управления. Однако императивный стиль все же вполне возможен. Стиль, предпочитаемый многими программистами Common Lisp, может показаться более знакомым программистам, привыкшим к структурированным языкам, таким как C, в то время как тот, который предпочитают программисты, больше напоминает чисто функциональные языки, такие как Haskell.
Из-за раннего наследия Lisp в списке обработки, он имеет широкий спектр функций высшего порядка, связанных с итерацией по последовательностям. Во многих случаях, когда явный цикл может быть необходим на других языках (например, цикл дляв C) в Лиспе, та же задача может быть выполнена с помощью функции высшего порядка. (То же самое верно для многих языков функционального программирования.)
Хорошим примером является функция, которая в Scheme называется map, а в Common Lisp - mapcar. Учитывая функцию и один или несколько списков, mapcarпоследовательно применяет функцию к элементам списков по порядку, собирая результаты в новый список:
(mapcar # '+' (1 2 3 4 5) '(10 20 30 40 50))
Применяет функцию +к каждой соответствующей паре элементов списка, получая результат (11 22 33 44 55).
Вот примеры кода Common Lisp.
Базовая программа «Hello world »:
(вывод «Hello world»)
Синтаксис Лиспа естественно поддается рекурсии. Математические задачи, такие как перечисление рекурсивно определенных множеств, легко выразить в этой нотации.
Вычислить значение факториала :
числа (defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1))))
Альтернативная реализация занимает меньше места в стеке, чем предыдущая версия, если базовая система Lisp оптимизирует хвостовую рекурсию :
(defun factorial (n optional (acc 1)) (if (= n 0) acc (factorial (- n 1) (* acc n))))
В отличие от итеративной версии, в которой используется макрос loopCommon Lisp :
(defun factorial (n) (loop for i from 1 на n для fac = 1, затем (* fac i) finally (return fac)))
Следующая функция переворачивает список. (Встроенная функция обратного просмотра Lisp делает то же самое.)
(defun -reverse (list) (let ((return-value '())) (dolist (e list) (push e return-value)) return -value))
Различные объектные системы и модели были построены поверх, параллельно или в Lisp, включая:
