История языка программирования Scheme - History of the Scheme programming language

История языка программирования Схема начинается с развития более ранних членов Лисп языковая семья во второй половине двадцатого века. В период проектирования и разработки Scheme дизайнеры языков Гай Л. Стил и Джеральд Джей Сассман выпустила влиятельную серию Массачусетский Институт Технологий (Массачусетский технологический институт) Заметки AI известный как Лямбда-документы (1975–1980). Это привело к росту популярности языка и наступлению эры стандартизации с 1990 года. Большая часть истории Scheme задокументирована самими разработчиками.[1]

Предыстория

На разработку Scheme сильно повлияли два предшественника, которые сильно отличались друг от друга: Лисп предоставил его общую семантику и синтаксис, и АЛГОЛ предоставил свой лексическая область и блочная структура. Схема - это диалект Лиспа, но Лисп эволюционировал; диалекты Lisp, из которых произошла Scheme, - хотя в то время они были мейнстримом - сильно отличаются от любого современного Lisp.

Лисп

Дальнейшая информация: Лисп (язык программирования)

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

Использование s-выражения которые характеризуют синтаксис Lisp, изначально задумывались как временная мера в ожидании разработки языка, использующего то, что Маккарти назвал "м-выражения ". Например, m-выражение автомобиль [минусы [A, B]] эквивалентно s-выражению (автомобиль (минусы A B)). Однако S-выражения оказались популярными, и многие попытки реализовать m-выражения не увенчались успехом.

Первая реализация Lisp была на IBM 704 к Стив Рассел, который прочитал статью Маккарти и закодировал описанную им функцию eval в машинном коде. Знакомые (но непонятные для новичков) имена CAR и CDR используется в Лиспе для описания головного элемента списка и его хвоста. IBM 704 Команды на языке ассемблера: содержимое регистра адреса и содержимое регистра декремента, каждая из которых вернула содержимое 15-битного регистра, соответствующего сегментам 36-битный Инструкция IBM 704 слово.

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

Два варианта Lisp, наиболее значимые для разработки Scheme, были разработаны в MIT: LISP 1.5.[4] разработан Маккарти и другими, и Маклисп[5] - разработан для MIT Проект MAC, прямой потомок LISP 1.5. который работал на PDP-10 и Мультики системы.

С момента своего создания Lisp был тесно связан с искусственный интеллект (AI) исследовательское сообщество, особенно PDP-10. 36-битный размер слова PDP-6 и PDP-10 на него повлияла полезность наличия двух Lisp 18-битный указатели одним словом.[6]

АЛГОЛ

Дальнейшая информация: АЛГОЛ

АЛГОЛ 58, первоначально называвшийся IAL для «международного алгоритмического языка», был разработан совместно комитетом европейских и американских компьютерных ученых на встрече в 1958 г. ETH Цюрих. АЛГОЛ 60, более поздняя версия, разработанная на встрече ALGOL 60 в Париже и теперь обычно называемая АЛГОЛ, стал стандартом для публикации алгоритмов и оказал глубокое влияние на развитие языков в будущем, несмотря на отсутствие коммерческого успеха языка и его ограничения. Тони Хоар заметил: «Этот язык настолько опередил свое время, что стал не только улучшением своих предшественников, но и почти всех его преемников».[7]

Алгол ввел использование блочной структуры и лексической области видимости. Он также был известен своей сложной позвонить по имени механизм передачи параметров по умолчанию, который был определен таким образом, чтобы требовать текстовой замены выражения, представляющего рабочий параметр, вместо формального параметра во время выполнения процедуры или функции, заставляя его повторно оценивать каждый раз, когда на него ссылаются во время выполнения. Разработчики ALGOL разработали механизм, который они назвали thunk, который захватил контекст рабочего параметра, позволяя оценить его во время выполнения процедуры или функции.

Карл Хьюитт, модель-актер и рождение Схема

Смотрите также: Актерская модель, Планировщик (язык программирования), и MDL (язык программирования)

В 1971 году Сассман, Дрю Макдермотт, и Евгений Чарняк разработал систему под названием Микро-планировщик что было частичной и несколько неудовлетворительной реализацией Карл Хьюитт амбициозный Планировщик проект. Сассман и Хьюитт вместе с другими работали над Muddle, позже переименованным в Лей, расширенный Lisp, который составлял компонент проекта Хьюитта. Дрю Макдермотт и Сассман в 1972 году разработали язык на основе Лисп. Conniver, который пересмотрел использование автоматического поиска с возвратом в Planner, которое, по их мнению, было непродуктивным. Хьюитт сомневался, что "волосатая структура управления" в Conniver была решением проблем с Planner. Пэт Хейс заметил: «Их решение [Sussman and McDermott], чтобы предоставить пользователю доступ к примитивам реализации Planner, тем не менее, является чем-то вроде ретроградного шага (какова семантика Conniver?)»[8]

В ноябре 1972 года Хьюитт и его ученики изобрели Актерская модель вычислений как решение проблем с Planner.[9] Была разработана частичная реализация Актеров под названием Planner-73 (позже названная PLASMA). Стил, тогда аспирант Массачусетского технологического института, следил за этими разработками, и он и Сассман решили реализовать версию модели Actor в своем собственном «маленьком Лиспе», разработанном на Маклисп, чтобы лучше понять модель. Используя эту основу, они затем начали разрабатывать механизмы для создания акторов и отправки сообщений.[10]

Использование лексической области в PLASMA было похоже на лямбда-исчисление. Суссман и Стил решили попытаться смоделировать актеров с помощью лямбда-исчисления. Они назвали свою систему моделирования Schemer, в конечном итоге изменив ее на Scheme, чтобы соответствовать шестизначному ограничению на ЭТО файловая система на их DEC PDP-10. Вскоре они пришли к выводу, что Актеры - это, по сути, замыкания, которые никогда не возвращаются, а вместо этого вызывают продолжение, и, таким образом, они решили, что закрытие и Актер были для целей их расследования по существу идентичными концепциями. Они устранили то, что они считали избыточным кодом, и в этот момент обнаружили, что они написали очень маленький и способный диалект Лиспа. Хьюитт по-прежнему критически относился к «сложной структуре управления» в схеме.[11][12] и считались примитивами (например, НАЧАТЬ! ПРОЦЕСС, СТОП! ПРОЦЕСС, и ОЦЕНИТЬ! НЕПРЕРЫВНО), который используется в реализации схемы, как шаг назад.

25 лет спустя, в 1998 году, Сассман и Стил пришли к выводу, что минимализм Scheme был не сознательной целью дизайна, а скорее непреднамеренным результатом процесса проектирования. «Мы на самом деле пытались построить что-то сложное и случайно обнаружили, что случайно разработали что-то, что соответствовало всем нашим целям, но было намного проще, чем мы планировали ... мы поняли, что лямбда-исчисление - небольшой простой формализм - может служат ядром мощного и выразительного языка программирования ».[10]

С другой стороны, Хьюитт по-прежнему критиковал лямбда-исчисление как основу для написания вычислений «Фактическая ситуация такова, что λ-исчисление способно выражать некоторые виды последовательных и параллельных управляющих структур, но, в целом, не параллелизм, выраженный в Модель Актера. С другой стороны, модель Актера способна выразить все в λ-исчислении и многом другом ». Он также критически относился к аспектам схемы, которые вытекают из лямбда-исчисления, таким как зависимость от функций продолжения и отсутствие исключений.[13]

Лямбда-документы

Между 1975 и 1980 годами Суссман и Стил работали над развитием своих идей об использовании лямбда-исчисления, продолжений и других сложных концепций программирования, таких как оптимизация хвостовая рекурсия, и опубликовал их в серии Заметки AI которые в совокупности стали называть Лямбда-документы.[14]

Список статей

  • 1975: Схема: интерпретатор для расширенного лямбда-исчисления
  • 1976: Лямбда: высший императив
  • 1976: Лямбда: окончательная декларативная
  • 1977: Развенчание мифа о «дорогостоящем вызове процедур» или реализации вызова процедур, признанных вредными, или лямбда: окончательный GOTO
  • 1978: Искусство интерпретатора или комплекс модульности (части ноль, один и два)
  • 1978: RABBIT: компилятор для SCHEME
  • 1979: Разработка процессоров на основе LISP, или СХЕМА: диалект LISP, или конечные воспоминания, считающиеся вредными, или LAMBDA: окончательный код операции
  • 1980: Оптимизация компилятора на основе просмотра LAMBDA как RENAME + GOTO
  • 1980: Разработка процессора на основе Lisp

Влияние

Scheme был первым диалектом Lisp, который выбрал лексическая область. Это также был один из первых языков программирования после определения языка Рейнольда.[15] поддерживать первый класс продолжения. Это оказало большое влияние на усилия, которые привели к развитию родственного языка, Common Lisp, участником которого был Гай Стил.[16]

Стандартизация

Язык схемы стандартизированный в официальном Институт инженеров по электротехнике и электронике (IEEE) стандарт,[17] и стандарт де-факто, называемый Пересмотреноп Отчет по алгоритмической языковой схеме (РпRS). Наиболее широко применяемым стандартом является R5RS (1998),[18] и новый стандарт, R6RS,[19] был ратифицирован в 2007 году.[20]

График

Хронология диалектов Лиспа(редактировать )
19551960196519701975198019851990199520002005201020152020
LISP 1, 1.5, LISP 2(заброшенный)
 Маклисп
 Интерлисп
 Лисп-машина Лисп
 Схема R5RS R6RS R7RS маленький
 Ноль
 Ференц Лисп
 Common Lisp
 Le Lisp
 Т
 Chez Scheme
 Emacs Lisp
 AutoLISP
 ПикоЛисп
 EuLisp
 ISLISP
 OpenLisp
 Схема PLT Ракетка
 GNU Guile
 Визуальный LISP
 Clojure
 Дуга
 LFE
 Hy

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

  1. ^ Стил, Гай (2006). «История схемы» (Слайд-шоу в формате PDF). Лаборатории Sun Microsystems.
  2. ^ Маккарти, Джон. "Рекурсивные функции символьных выражений и их машинное вычисление, часть I". Архивировано из оригинал на 2013-10-04. Получено 2006-10-13.
  3. ^ Харт, Тим; Левин, Майк. «AI Memo 39, новый компилятор» (PDF). Получено 2006-10-13.[постоянная мертвая ссылка ]
  4. ^ Маккарти, Джон; Abrahams, Paul W .; Эдвардс, Дэниел Дж .; Харт, Тимоти П .; Левин, Михаил И. (1985). Руководство программиста LISP 1.5. MIT Press. ISBN  978-0-262-13011-0.
  5. ^ «Справочное руководство Maclisp». 3 марта 1979 г. Архивировано с оригинал на 2007-12-14.
  6. ^ Херли, Питер Дж. (18 октября 1990 г.). «История TOPS или жизнь в быстрых АС». Группа новостей: alt.folklore.comкомпьютеры. Usenet:  [email protected]. Проект PDP-6 стартовал в начале 1963 года как 24 бит машина. Он вырос до 36 бит для LISP, что было целью разработки.
  7. ^ Хоар, Тони (Декабрь 1973 г.). Подсказки по дизайну языков программирования (PDF). п. 27. (Это утверждение иногда ошибочно приписывают Эдсгер В. Дейкстра, также участвовал в реализации первого АЛГОЛА 60 компилятор.)
  8. ^ Хейс, Пэт (1974). «Некоторые проблемы и непроблемы в теории представлений». Общество изучения искусственного интеллекта и моделирования поведения (AISB).
  9. ^ Хьюитт, Карл; Епископ Петр; Стейгер, Ричард (1973). «Универсальный модульный актерский формализм для искусственного интеллекта». IJCAI. Цитировать журнал требует | журнал = (помощь)
  10. ^ а б Сассман, Джеральд Джей; Стил-младший, Гай Л. (Декабрь 1998 г.). "Первый отчет о схеме пересмотрен" (PDF). Вычисление высшего порядка и символическое вычисление. 11 (4): 399–404. Дои:10.1023 / А: 1010079421970. ISSN  1388-3690. Архивировано из оригинал (PDF) на 2006-06-15. Получено 2006-06-19.
  11. ^ Хьюитт, Карл (Декабрь 1976 г.). «Просмотр управляющих структур как шаблонов передачи сообщений». AI Memo 410.
  12. ^ Хьюитт, Карл (Июнь 1977 г.). «Просмотр управляющих структур как шаблонов передачи сообщений». Журнал искусственного интеллекта.
  13. ^ Хьюитт, Карл (2009). «ActorScript: промышленная интеграция локального и нелокального параллелизма для клиентских облачных вычислений». arXiv:0907.3330 [cs.PL ].
  14. ^ «Онлайн-версия лямбда-документов». Архивировано из оригинал (PDF) на 2018-06-25.
  15. ^ Рейнольдс, Джон (1972). «Определительные интерпретаторы для языков программирования высшего порядка». Материалы конференции ACM. Ассоциация вычислительной техники.
  16. ^ "Common Lisp Hyperspec - 1.1.2 История". LispWorks. 2005. Получено 2018-12-02.
  17. ^ 1178-1990 (R1995) Стандарт IEEE для языка программирования схем
  18. ^ Келси, Ричард; Клингер, Уильям; Рис, Джонатан; и другие. (Август 1998 г.). "Пересмотренный5 Отчет об алгоритмической языковой схеме ». Вычисление высшего порядка и символическое вычисление. 11 (1): 7–105. Дои:10.1023 / А: 1010051815785.
  19. ^ Спербер, Майкл; Дибвиг, Р. Кент; Флэтт, Мэтью; Ван Страатен, Антон; Финдлер, Робби; Мэтьюз, Джейкоб (август 2009 г.). "Пересмотренный6 Отчет об алгоритмической языковой схеме ». Журнал функционального программирования. 19 (S1): 1–301. CiteSeerX  10.1.1.154.5197. Дои:10.1017 / S0956796809990074.
  20. ^ «Результаты голосования-ратификации R6RS».