История языка программирования Scheme
История языка программирования Scheme начинается с разработки ранних членов семейства языков Lisp во второй половине двадцатого века. В период проектирования и разработки Scheme дизайнеры языка Гай Л. Стил и Джеральд Джей Сассман выпустили влиятельную серию Массачусетского технологического института (MIT), заметок об искусственном интеллекте известную как Lambda Papers (1975–1980). Это привело к росту популярности языка и наступлению эпохи стандартизации с 1990 года. Большая часть истории Scheme задокументирована самими разработчиками. [1]
Предыстория [ править ]
![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( январь 2011 г. ) |
На разработку Scheme сильно повлияли два предшественника, которые сильно отличались друг от друга: Lisp предоставил общую семантику и синтаксис, а ALGOL обеспечил лексическую область видимости и блочную структуру. Scheme — это диалект Лиспа, но Лисп эволюционировал; Диалекты Лиспа, из которых возникла Scheme, хотя в то время они были в мейнстриме, сильно отличаются от любого современного Лиспа.
Лисп [ править ]
Лисп был изобретен Джоном Маккарти в 1958 году, когда он работал в Массачусетском технологическом институте (MIT). Маккарти опубликовал свой дизайн в статье в журнале Communications of ACM в 1960 году под названием «Рекурсивные функции символических выражений и их машинное вычисление, часть I». [2] (Часть II так и не была опубликована). Он показал, что с помощью нескольких простых операторов и обозначений функций можно построить полный по Тьюрингу язык алгоритмов.
Использование s-выражений , характеризующих синтаксис Лиспа, изначально задумывалось как временная мера до разработки языка, использующего то, что Маккарти называл « m-выражениями ». Например, m-выражение car[cons[A,B]] эквивалентно s-выражению (car (cons A B)). Однако S-выражения оказались популярными, и многочисленные попытки реализовать m-выражения не прижились.
Первая реализация Lisp была на IBM 704 Стивом Расселом , который прочитал статью Маккарти и закодировал описанную им функцию eval в машинном коде. Знакомые (но озадачивающие новичков) имена CAR и CDR , используемые в Lisp для описания главного элемента списка и его хвоста, произошли от двух команд языка ассемблера IBM 704 : Contents of Address Register и Contents of Decrement Register, каждая из которых возвращала содержимое 15-битного регистра, соответствующее сегментам 36-битного IBM 704 командного слова .
Первый полноценный компилятор Lisp, написанный на Lisp, был реализован в 1962 году Тимом Хартом и Майком Левином в Массачусетском технологическом институте. [3] Этот компилятор представил модель инкрементной компиляции Lisp, в которой скомпилированные и интерпретируемые функции могут свободно смешиваться.
Два варианта Lisp, наиболее значимые для развития Scheme, были разработаны в Массачусетском технологическом институте: LISP 1.5. [4] разработанный Маккарти и другими, а также Maclisp [5] MIT – разработан для проекта MAC , прямого потомка LISP 1.5. который работал на системах PDP-10 и Multics .
С момента своего создания Lisp был тесно связан с исследовательским сообществом искусственного интеллекта (ИИ), особенно в отношении PDP-10 . На 36-битный размер слова PDP-6 и PDP-10 повлияла полезность наличия двух 18-битных указателей Lisp в одном слове. [6]
ALGOL[editАЛГОЛ
АЛГОЛ 58 , первоначально называвшийся IAL (что означает «Международный алгоритмический язык»), был разработан совместно комитетом европейских и американских ученых-компьютерщиков на встрече в 1958 году в ETH Zurich . АЛГОЛ 60 , более поздняя версия, разработанная на встрече АЛГОЛ 60 в Париже и теперь обычно называемая АЛГОЛ , стала стандартом для публикации алгоритмов и оказала глубокое влияние на будущее развитие языка, несмотря на отсутствие коммерческого успеха языка и его ограничения. Тони Хоар заметил: «Это язык, настолько опередивший свое время, что он стал улучшением не только своих предшественников, но и почти всех своих преемников». [7]
АЛГОЛ представил использование блочной структуры и лексической области видимости. Он также был известен своим сложным вызовом по имени механизма передачи параметров по умолчанию, который был определен так, чтобы требовать текстовой замены выражения, представляющего рабочий параметр, вместо формального параметра во время выполнения процедуры или функции, что приводило к его повторному использованию. -оценивается каждый раз, когда на него ссылаются во время выполнения. Разработчики АЛГОЛА разработали механизм, который они назвали thunk , который фиксирует контекст рабочего параметра, позволяя его оценивать во время выполнения процедуры или функции.
рождение Scheme , модель Актера и Карл Хьюитт
В 1971 году Сассман, Дрю Макдермотт и Юджин Чарняк разработали систему под названием Micro-Planner , которая представляла собой частичную и несколько неудовлетворительную реализацию проекта Карла Хьюитта амбициозного Planner . Сассман и Хьюитт вместе с другими работали над Muddle, позже переименованным в MDL , расширенным языком Lisp, который стал компонентом проекта Хьюитта. Дрю МакДермотт и Сассман в 1972 году разработали основанный на Lisp язык Conniver , который изменил использование автоматического возврата в Planner, которое, по их мнению, было непродуктивным. Хьюитт сомневался, что «волосатая структура управления» в Conniver может решить проблемы Planner. Пэт Хейс заметил: «Их решение [Сассмана и Макдермотта] предоставить пользователю доступ к примитивам реализации Planner, однако, является своего рода ретроградным шагом (какова семантика Коннивера?)» [8]
В ноябре 1972 года Хьюитт и его ученики изобрели модель вычислений «Актер» как решение проблем Planner. [9] Частичная реализация Актеров была разработана под названием Planner-73 (позже названная PLASMA). Стил, тогда еще аспирант Массачусетского технологического института, следил за этими разработками, и они с Сассманом решили реализовать версию модели Актера в своем собственном «крошечном Лиспе», разработанном на Maclisp , чтобы лучше понять модель. Используя эту основу, они затем начали разрабатывать механизмы создания акторов и отправки сообщений. [10]
Использование лексической области видимости в PLASMA было похоже на лямбда-исчисление . Сассман и Стил решили попытаться смоделировать Актеров с помощью лямбда-исчисления. Они назвали свою систему моделирования Schemer, в конечном итоге изменив ее на Scheme, чтобы соответствовать шестисимвольному пределу файловой системы ITS на своем DEC PDP-10 . Вскоре они пришли к выводу, что Актеры — это, по сути, замыкания, которые никогда не возвращаются, а вместо этого вызывают продолжение , и поэтому они решили, что замыкание и Актер для целей их исследования были, по сути, идентичными понятиями. Они устранили то, что считали избыточным кодом, и в этот момент обнаружили, что написали очень небольшой и функциональный диалект Лиспа. Хьюитт по-прежнему критически относился к «волосатой структуре управления» в «Схеме». [11] [12] и считались примитивами (например, START!PROCESS, STOP!PROCESS, и EVALUATE!UNINTERRUPTIBLY), используемый в реализации Scheme как шаг назад.
25 лет спустя, в 1998 году, Сассман и Стил отметили, что минимализм Scheme не был сознательной целью дизайна, а скорее непреднамеренным результатом процесса проектирования. «На самом деле мы пытались построить что-то сложное и по счастливой случайности обнаружили, что случайно спроектировали что-то, что отвечало всем нашим целям, но оказалось намного проще, чем мы предполагали... мы поняли, что лямбда-исчисление — небольшой простой формализм — может служить ядром мощного и выразительного языка программирования». [10]
С другой стороны, Хьюитт по-прежнему критиковал лямбда-исчисление как основу для написания вычислений: «Фактическая ситуация такова, что λ-исчисление способно выражать некоторые виды последовательных и параллельных структур управления, но, в целом, не параллелизм, выраженный в модель Актера, с другой стороны, модель Актера способна выразить все в λ-исчислении и даже больше». Он также критиковал аспекты Scheme, вытекающие из лямбда-исчисления, такие как использование функций продолжения и отсутствие исключений. [13]
Лямбда-документы [ править ]
Между 1975 и 1980 годами Сассман и Стил работали над развитием своих идей об использовании лямбда-исчисления, продолжений и других передовых концепций программирования, таких как оптимизация хвостовой рекурсии , и опубликовали их в серии AI Memos , которые стали коллективно называться Lambda Papers . [14]
Список статей [ править ]
- 1975: Схема: интерпретатор расширенного лямбда-исчисления
- 1976: Лямбда: высший императив
- 1976: Лямбда: величайший декларатив
- 1977: Развенчание мифа о «дорогом вызове процедур», или «Реализации вызова процедур считаются вредными», или «Лямбда: окончательный вариант GOTO»
- 1978: Искусство интерпретатора или комплекс модульности (нулевая, первая и вторая части)
- 1978: КРОЛИК: Компилятор СХЕМЫ
- 1979: Проектирование процессоров на основе LISP, или СХЕМА: диалект LISP, или Конечная память считается вредной, или LAMBDA: окончательный код операции
- 1980: Оптимизация компилятора на основе просмотра LAMBDA как RENAME + GOTO
- 1980: Разработка процессора на основе Lisp.
Влияние [ править ]
Scheme был первым диалектом Лиспа, в котором была выбрана лексическая область видимости . Это также был один из первых языков программирования после языка определений Рейнольдса. [15] для поддержки первоклассных продолжений . Он оказал большое влияние на усилия, которые привели к разработке его родственного языка, Common Lisp , в котором участвовал Гай Стил. [16]
Стандартизация [ править ]
Язык Scheme стандартизирован в официальном стандарте Института инженеров по электротехнике и электронике (IEEE). [17] и стандарт де-факто под названием « Пересмотренный». н Отчет об алгоритмической языковой схеме (R n RS). Наиболее широко внедренный стандарт — R5RS (1998 г.). [18] и новый стандарт R6RS , [19] был ратифицирован в 2007 году. [20] Помимо стандартов RnRS, существуют также документы «Запросы на реализацию схемы» , которые содержат дополнительные библиотеки, которые могут быть добавлены реализациями схемы.
Хронология [ править ]
| 1958 | 1960 | 1965 | 1970 | 1975 | 1980 | 1985 | 1990 | 1995 | 2000 | 2005 | 2010 | 2015 | 2020 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ЛИСП 1, 1.5, ЛИСП 2 (заброшенный) | |||||||||||||||
| Маклисп | |||||||||||||||
| Интерлисп | |||||||||||||||
| леев | |||||||||||||||
| Лисп-машина Лисп | |||||||||||||||
| Схема | Р5РС | Р6РС | R7RS маленький | ||||||||||||
| НОЛЬ | |||||||||||||||
| ЗИЛ (язык реализации Zork) | |||||||||||||||
| Франц Лисп | |||||||||||||||
| Общий Лисп | стандарт ANSI | ||||||||||||||
| Лисп | |||||||||||||||
| Схема СО | |||||||||||||||
| XLISP | |||||||||||||||
| Т | |||||||||||||||
| На схеме | |||||||||||||||
| Эмакс Лисп | |||||||||||||||
| АвтоЛИСП | |||||||||||||||
| ПикоЛисп | |||||||||||||||
| Гамбит | |||||||||||||||
| EuLisp | |||||||||||||||
| ИСЛИСП | |||||||||||||||
| ОпенЛисп | |||||||||||||||
| Схема PLT | Ракетка | ||||||||||||||
| новыйЛИСП | |||||||||||||||
| GNU Коварство | |||||||||||||||
| Визуальный ЛИСП | |||||||||||||||
| Кложур | |||||||||||||||
| Дуга | |||||||||||||||
| ЛФЭ | |||||||||||||||
| Он | |||||||||||||||
| Хиалисп | |||||||||||||||
Ссылки [ править ]
- ^ Стил, Гай (2006). «История схемы» (слайд-шоу в формате PDF) . Лаборатории Сан Микросистемс .
- ^ Маккарти, Джон . «Рекурсивные функции символьных выражений и их машинное вычисление, часть I» . Архивировано из оригинала 4 октября 2013 г. Проверено 13 октября 2006 г.
- ^ Харт, Тим; Левин, Майк. «Памятка AI 39, Новый компилятор» (PDF) . Архивировано из оригинала (PDF) 13 декабря 2020 г. Проверено 13 октября 2006 г.
- ^ Маккарти, Джон ; Абрахамс, Пол В.; Эдвардс, Дэниел Дж.; Харт, Тимоти П.; Левин, Майкл И. (1985). Руководство программиста LISP 1.5 . МТИ Пресс . ISBN 978-0-262-13011-0 .
- ^ «Справочное руководство по Maclisp» . 3 марта 1979 г. Архивировано из оригинала 14 декабря 2007 г.
- ^ Херли, Питер Дж. (18 октября 1990 г.). «История ТОПС или жизнь в быстрых АС» . Группа новостей : alt.folklore.computers . Usenet: [электронная почта защищена] .
Проект PDP-6 стартовал в начале 1963 года как 24-битная машина. Для LISP он вырос до 36 бит, что было целью разработки.
- ^ Хоар, Тони (декабрь 1973 г.). Советы по проектированию языков программирования (PDF) . п. 27. (Это утверждение иногда ошибочно приписывают Эдсгеру В. Дейкстре , также участвовавшему в реализации первого компилятора ALGOL 60. )
- ^ Хейс, Пэт (1974). «Некоторые проблемы и непроблемы теории представлений». Общество изучения искусственного интеллекта и моделирования поведения (AISB) .
- ^ Хьюитт, Карл ; Епископ Питер; Штайгер, Ричард (1973). «Универсальный модульный формализм актеров для искусственного интеллекта». IJCAI.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ↑ Перейти обратно: Перейти обратно: а б Сассман, Джеральд Джей ; Стил-младший, Гай Л. (декабрь 1998 г.). «Первый отчет о пересмотре схемы» (PDF) . Вычисления высшего порядка и символьные вычисления . 11 (4): 399–404. дои : 10.1023/А:1010079421970 . ISSN 1388-3690 . S2CID 7704398 . Архивировано из оригинала (PDF) 15 июня 2006 г. Проверено 19 июня 2006 г.
- ^ Хьюитт, Карл (декабрь 1976 г.). «Просмотр структур управления как шаблонов передачи сообщений». AI Памятка 410 .
- ^ Хьюитт, Карл (июнь 1977 г.). «Просмотр структур управления как шаблонов передачи сообщений». Журнал искусственного интеллекта . 8 (3): 323–364. дои : 10.1016/0004-3702(77)90033-9 . hdl : 1721.1/6272 .
- ^ Хьюитт, Карл (2009). «ActorScript: Промышленная интеграция локального и нелокального параллелизма для клиентских облачных вычислений». arXiv : 0907.3330 [ cs.PL ].
- ^ «Онлайн-версия лямбда-документов» . Архивировано из оригинала (PDF) 25 июня 2018 г.
- ^ Рейнольдс, Джон (1972). «Определенные интерпретаторы языков программирования высшего порядка». Материалы конференции ACM . Ассоциация вычислительной техники.
- ^ «Common Lisp Hyperspec – История 1.1.2» . Лиспворкс . 2005 . Проверено 2 декабря 2018 г.
- ^ 1178-1990 (R1995) Стандарт IEEE для языка программирования Scheme
- ^ Келси, Ричард; Клингер, Уильям; Рис, Джонатан; и др. (август 1998 г.). «Пересмотренный 5 Отчет об алгоритмической языковой схеме» . Высшие порядки и символические вычисления . 11 (1): 7–105. doi : 10.1023/A:1010051815785 .
- ^ Спербер, Майкл; Дибвиг, Р. Кент; Флэтт, Мэтью; Ван Страатен, Антон; Финдлер, Робби; Мэтьюз, Джейкоб (август 2009 г.). «Пересмотренный 6 Отчет о схеме алгоритмического языка» . Журнал функционального программирования . 19 (S1): 1–301. CiteSeerX 10.1.1.154.5197 . doi : 10.1017/S0956796809990074 . S2CID 62724224 .
- ^ «Результаты голосования по ратификации R6RS» .
