stringtranslate.com

История языка программирования Scheme

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

Предыстория

На разработку 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] — разработанный для проекта MAC MIT , прямой потомок LISP 1.5. который работал на системах PDP-10 и Multics .

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

АЛГОЛ

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

АЛГОЛ представил использование блочной структуры и лексической области видимости. Он также был известен своим сложным вызовом по имени механизма передачи параметров по умолчанию, который был определен так, чтобы требовать текстовой замены выражения, представляющего рабочий параметр, вместо формального параметра во время выполнения процедуры или функции, что приводило к его повторному использованию. -оценивается каждый раз, когда на него ссылаются во время выполнения. Разработчики ALGOL разработали механизм, названный 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 . Вскоре они пришли к выводу, что Актеры — это, по сути, замыкания, которые никогда не возвращаются, а вместо этого вызывают продолжение , и поэтому они решили, что замыкание и Актер для целей их исследования являются, по сути, идентичными понятиями. Они устранили то, что считали избыточным кодом, и в этот момент обнаружили, что написали очень небольшой и работоспособный диалект Лиспа. Хьюитт оставался критически настроенным по отношению к «волосатой структуре управления» в Scheme [11] [12] и считал примитивы (например, START!PROCESS, STOP!PROCESSи EVALUATE!UNINTERRUPTIBLY), используемые в реализации Scheme, шагом назад.

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

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

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

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

Список документов

Влияние

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

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

Язык схемы стандартизирован в официальном стандарте Института инженеров по электротехнике и электронике (IEEE) [17] и фактическом стандарте, называемом Revised n Report on the Algorithmic Language Scheme (R n RS). Наиболее широко внедряемым стандартом является R5RS (1998), [18] , а новый стандарт, R6RS , [19] был ратифицирован в 2007 году. [20] Помимо стандартов RnRS существуют также документы «Запросы на схему внедрения» , которые содержат дополнительные библиотеки, которые могут быть добавлены реализациями Scheme.

График

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

  1. ^ Стил, Гай (2006). «История схемы» (слайд-шоу в формате PDF) . Лаборатории Сан Микросистемс .
  2. ^ Маккарти, Джон . «Рекурсивные функции символьных выражений и их машинное вычисление, часть I». Архивировано из оригинала 4 октября 2013 г. Проверено 13 октября 2006 г.
  3. ^ Харт, Тим; Левин, Майк. «Памятка AI 39, Новый компилятор» (PDF) . Архивировано из оригинала (PDF) 13 декабря 2020 г. Проверено 13 октября 2006 г.
  4. ^ Маккарти, Джон ; Абрахамс, Пол В.; Эдвардс, Дэниел Дж.; Харт, Тимоти П.; Левин, Майкл И. (1985). Руководство программиста LISP 1.5 . МТИ Пресс . ISBN 978-0-262-13011-0.
  5. ^ «Справочное руководство Maclisp» . 3 марта 1979 г. Архивировано из оригинала 14 декабря 2007 г.
  6. ↑ Херли, Питер Дж. (18 октября 1990 г.). «История ТОПС или жизнь в быстрых АС». Группа новостей : alt.folklore.computers. Usenet:  [email protected]. Проект PDP-6 стартовал в начале 1963 года как 24-битная машина. Для LISP он вырос до 36 бит, что было целью разработки.
  7. ^ Хоар, Тони (декабрь 1973 г.). Советы по проектированию языков программирования (PDF) . п. 27. (Это утверждение иногда ошибочно приписывают Эдсгеру В. Дейкстре , также участвовавшему в реализации первого компилятора ALGOL 60. )
  8. ^ Хейс, Пэт (1974). «Некоторые проблемы и непроблемы теории представлений». Общество изучения искусственного интеллекта и моделирования поведения (AISB) .
  9. ^ Хьюитт, Карл ; Епископ Питер; Штайгер, Ричард (1973). «Универсальный модульный формализм актеров для искусственного интеллекта». IJCAI. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  10. ^ аб Суссман, Джеральд Джей ; Стил-младший, Гай Л. (декабрь 1998 г.). «Первый отчет о пересмотре схемы» (PDF) . Вычисления высшего порядка и символьные вычисления . 11 (4): 399–404. дои : 10.1023/А: 1010079421970. ISSN  1388-3690. S2CID  7704398. Архивировано из оригинала (PDF) 15 июня 2006 г. Проверено 19 июня 2006 г.
  11. ^ Хьюитт, Карл (декабрь 1976 г.). «Просмотр структур управления как шаблонов передачи сообщений». AI Памятка 410 .
  12. ^ Хьюитт, Карл (июнь 1977 г.). «Просмотр структур управления как шаблонов передачи сообщений». Журнал искусственного интеллекта . 8 (3): 323–364. дои : 10.1016/0004-3702(77)90033-9. hdl : 1721.1/6272 .
  13. ^ Хьюитт, Карл (2009). «ActorScript: Промышленная интеграция локального и нелокального параллелизма для клиентских облачных вычислений». arXiv : 0907.3330 [cs.PL].
  14. ^ "Онлайн-версия лямбда-документов" . Архивировано из оригинала (PDF) 25 июня 2018 г.
  15. ^ Рейнольдс, Джон (1972). «Определенные интерпретаторы языков программирования высшего порядка». Материалы конференции ACM . Ассоциация вычислительной техники.
  16. ^ «Гиперспец Common Lisp – История 1.1.2» . Лиспворкс . 2005 . Проверено 2 декабря 2018 г.
  17. ^ 1178-1990 (R1995) Стандарт IEEE для языка программирования Scheme
  18. ^ Келси, Ричард; Клингер, Уильям; Рис, Джонатан; и другие. (август 1998 г.). «Пересмотренный отчет 5 об алгоритмической языковой схеме». Вычисления высшего порядка и символьные вычисления . 11 (1): 7–105. дои : 10.1023/А: 1010051815785.
  19. ^ Спербер, Майкл; Дибвиг, Р. Кент; Флэтт, Мэтью; Ван Страатен, Антон; Финдлер, Робби; Мэтьюз, Джейкоб (август 2009 г.). «Пересмотренный отчет 6 по алгоритмической языковой схеме». Журнал функционального программирования . 19 (С1): 1–301. CiteSeerX 10.1.1.154.5197 . дои : 10.1017/S0956796809990074. S2CID  62724224. 
  20. ^ «Результаты голосования по ратификации R6RS» .