Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Предыстория [ править ]

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

Лисп [ править ]

Дополнительная информация: Lisp (язык программирования)

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

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

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

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

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

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

АЛГОЛ [ править ]

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

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

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

Карл Хьюитт, модель актера и рождение Схема [ править ]

См. Также: Модель актера , Planner (язык программирования) и MDL (язык программирования).

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

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

Использование лексической области в PLASMA было похоже на лямбда-исчисление . Суссман и Стил решили попытаться смоделировать актеров с помощью лямбда-исчисления. Они назвали свою систему моделирования Schemer, в конечном итоге изменив ее на Scheme, чтобы соответствовать шестизначному ограничению файловой системы ITS на их DEC PDP-10 . Вскоре они пришли к выводу, что Актеры - это, по сути, замыкания, которые никогда не возвращаются, а вместо этого вызывают продолжение., и, таким образом, они решили, что закрытие и Актер были, для целей их расследования, по существу идентичными концепциями. Они устранили то, что считали избыточным кодом, и в этот момент обнаружили, что они написали очень маленький и способный диалект Лиспа. Хьюитт оставался критически «волосатая структура управления» в схеме [11] [12] и рассмотренных примитивы (например, START!PROCESS, STOP!PROCESS, и EVALUATE!UNINTERRUPTIBLY) , используемая при осуществлении схемы , чтобы быть шагом назад.

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

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

Лямбда-документы [ править ]

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

Список статей [ править ]

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

Влияние [ править ]

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

Стандартизация [ править ]

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

Хронология [ править ]

Хронология диалектов Лиспа ( править )
1955 г.1960 г.1965 г.1970 г.1975 г.1980 г.1985 г.1990 г.1995 г.2000 г.2005 г.2010 г.2015 г.2020 г.
 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 . Проверено 13 октября 2006 .
  3. ^ Харт, Тим; Левин, Майк. «AI Memo 39, Новый компилятор» (PDF) . Проверено 13 октября 2006 . [ постоянная мертвая ссылка ]
  4. ^ Маккарти, Джон ; Abrahams, Paul W .; Эдвардс, Дэниел Дж .; Харт, Тимоти П .; Левин, Михаил I. (1985). Руководство программиста LISP 1.5 . MIT Press . ISBN 978-0-262-13011-0.
  5. ^ "Справочное руководство Maclisp" . 3 марта, 1979. Архивировано из оригинала на 2007-12-14.
  6. ↑ Херли, Питер Дж. (18 октября 1990 г.). «История ТОПов или Жизнь в быстрых АС» . Группа новостей :  alt.folklore.computers . Usenet: [email protected] . Проект PDP-6 стартовал в начале 1963 года как 24-битная машина. Он вырос до 36 бит для LISP, что было целью разработки. 
  7. ^ Хоар, Тони (декабрь 1973). Советы по дизайну языков программирования (PDF) . п. 27. (Это утверждение иногда ошибочно приписывают Эдсгеру В. Дейкстре , который также участвовал в реализации первого компилятора ALGOL 60. )
  8. Перейти ↑ Hayes, Pat (1974). «Некоторые проблемы и непроблемы теории представлений». Общество изучения искусственного интеллекта и моделирования поведения (AISB) .
  9. ^ Хьюитт, Карл ; Епископ Петр; Стейгер, Ричард (1973). «Универсальный модульный актерский формализм для искусственного интеллекта». IJCAI. Цитировать журнал требует |journal=( помощь )
  10. ^ а б Сассман, Джеральд Джей ; Стил-младший, Гай Л. (декабрь 1998 г.). «Первый отчет о пересмотренной схеме» (PDF) . Вычисление высшего порядка и символическое вычисление . 11 (4): 399–404. DOI : 10,1023 / A: 1010079421970 . ISSN 1388-3690 . Архивировано из оригинального (PDF) 15 июня 2006 года . Проверено 19 июня 2006 .  
  11. ^ Хьюитт, Карл (декабрь 1976). «Просмотр управляющих структур как шаблонов передачи сообщений». Памятка AI 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 . Проверено 2 декабря 2018 .
  17. ^ 1178-1990 (R1995) Стандарт IEEE для языка программирования схем
  18. ^ Келси, Ричард; Клингер, Уильям; Рис, Джонатан; и другие. (Август 1998 г.). «Пересмотренный отчет 5 по алгоритмической языковой схеме» . Вычисление высшего порядка и символическое вычисление . 11 (1): 7–105. DOI : 10,1023 / A: 1010051815785 .
  19. ^ Спербер, Майкл; Дибвиг, Р. Кент; Флатт, Мэтью; Ван Страатен, Антон; Финдлер, Робби; Мэтьюз, Джейкоб (август 2009 г.). «Пересмотренный отчет 6 по алгоритмической языковой схеме» . Журнал функционального программирования . 19 (S1): 1–301. CiteSeerX 10.1.1.154.5197 . DOI : 10.1017 / S0956796809990074 . 
  20. ^ "Результаты голосования-ратификации R6RS" .