Схема — это диалект семейства языков программирования Lisp . Схема была создана в 1970-х годах в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (MIT AI Lab) и выпущена ее разработчиками Гаем Л. Стилом и Джеральдом Джеем Сассманом в виде серии записок, теперь известных как Lambda Papers . Это был первый диалект Лиспа, в котором была выбрана лексическая область видимости , и первый, который требовал реализации для выполнения хвостовой оптимизации , обеспечивая более надежную поддержку функционального программирования и связанных с ним методов, таких как рекурсивные алгоритмы. Это был также один из первых языков программирования, поддерживавший первоклассные продолжения . Он оказал значительное влияние на усилия, которые привели к разработке Common Lisp . [2]
Язык схемы стандартизирован в официальном стандарте Института инженеров по электротехнике и электронике (IEEE) [3] и фактическом стандарте, называемом Revised n Report on the Algorithmic Language Scheme (R n RS). Широко внедренным стандартом является R5RS (1998 г.). [4] Последний ратифицированный стандарт Схемы — «R7RS-small» (2013 г.). [5] Более обширный и модульный R6RS был ратифицирован в 2007 году. [6] Оба ведут свое происхождение от R5RS; график ниже отражает хронологический порядок ратификации.
Scheme зародился в 1970-х годах как попытка понять модель актера Карла Хьюитта , для чего Стил и Сассман написали «крошечный интерпретатор Лиспа», используя Maclisp , а затем «добавили механизмы для создания актеров и отправки сообщений». [7] Первоначально Scheme назывался «Schemer», в традициях других языков, производных от Lisp , таких как Planner или Conniver . Текущее название возникло в результате использования авторами операционной системы ITS , которая ограничивала имена файлов двумя компонентами длиной не более шести символов каждый. В настоящее время «Комбинатор» обычно используется для обозначения программиста Scheme.
Новый процесс стандартизации языка начался на семинаре Scheme в 2003 году с целью создания стандарта R6RS в 2006 году. Этот процесс порвал с более ранним подходом единогласия R n RS.
R6RS имеет стандартную систему модулей, позволяющую разделить основной язык и библиотеки . Было выпущено несколько проектов спецификации R6RS, окончательной версией стала R5.97RS. Успешное голосование привело к ратификации нового стандарта, объявленного 28 августа 2007 г. [6]
В настоящее время новейшие версии различных реализаций Scheme [8] поддерживают стандарт R6RS. Существует портативная эталонная реализация предлагаемых неявно поэтапных библиотек для R6RS, называемая psyntax, которая правильно загружает и загружает себя в различных старых реализациях Scheme. [9]
Особенностью R6RS является дескриптор типа записи (RTD). Когда RTD создается и используется, представление типа записи может отображать структуру памяти. Он также рассчитывал битовую маску поля объекта и битовые маски изменяемого объекта Scheme и помогал сборщику мусора знать, что делать с полями, не просматривая весь список полей, сохраненный в RTD. RTD позволяет пользователям расширять базовый RTD для создания новой системы записей. [10]
R6RS вносит в язык множество существенных изменений. [11] Исходный код теперь указан в Unicode , и большое подмножество символов Unicode теперь может появляться в символах и идентификаторах Scheme , а также есть другие незначительные изменения в лексических правилах. Символьные данные теперь также указываются в Юникоде. Многие стандартные процедуры были перенесены в новые стандартные библиотеки, которые сами по себе представляют собой значительное расширение стандарта и содержат процедуры и синтаксические формы, которые ранее не были частью стандарта. Была введена новая модульная система, а системы обработки исключений теперь стандартизированы. Синтаксические правила были заменены более выразительным средством синтаксической абстракции (syntax-case), которое позволяет использовать всю схему во время расширения макроса. Для поддержки полной числовой башни Scheme теперь требуются совместимые реализации , а семантика чисел была расширена, главным образом, в направлении поддержки стандарта IEEE 754 для числового представления с плавающей запятой.
Стандарт R6RS вызвал споры, поскольку некоторые считают его отходом от минималистской философии. [12] [13] В августе 2009 года Руководящий комитет схемы, который наблюдает за процессом стандартизации, объявил о своем намерении рекомендовать разделить схему на два языка: большой современный язык программирования для программистов; и маленькая версия, подмножество большой версии, сохраняющая минимализм, хвалимый преподавателями и случайными разработчиками. [14] Для работы над этими двумя новыми версиями Scheme были созданы две рабочие группы. На сайте Scheme Reports Process есть ссылки на уставы рабочих групп, общественные обсуждения и систему отслеживания проблем.
Девятый проект R7RS (малый язык) был доступен 15 апреля 2013 г. [15] Голосование по ратификации этого проекта завершилось 20 мая 2013 г., [16] а окончательный отчет доступен с 6 августа 2013 г., в котором описывается «маленький» язык этой работы: поэтому его нельзя рассматривать изолированно как преемника R6RS». [5]
Scheme — это прежде всего функциональный язык программирования . Он имеет много общих характеристик с другими членами семейства языков программирования Lisp. Очень простой синтаксис Scheme основан на s-выражениях — списках в круглых скобках, в которых за префиксным оператором следуют его аргументы. Таким образом, программы-схемы состоят из последовательностей вложенных списков. Списки также являются основной структурой данных в Scheme, что приводит к тесной эквивалентности между исходным кодом и форматами данных ( гомоиконичность ). Программы Scheme могут легко создавать и динамически оценивать фрагменты кода Scheme.
Использование списков как структур данных характерно для всех диалектов Лиспа. Scheme унаследовал богатый набор примитивов обработки списков, таких как cons, carиcdr от своих предшественников на Lisp. Scheme использует строго, но динамически типизированные переменные и поддерживает первоклассные процедуры . Таким образом, процедуры могут присваиваться как значения переменным или передаваться в качестве аргументов процедурам.
В этом разделе основное внимание уделяется инновационным особенностям языка, включая те особенности, которые отличают Scheme от других Lisp. Если не указано иное, описания функций относятся к стандарту R5RS. В примерах, приведенных в этом разделе, обозначение «===> результат» используется для обозначения результата вычисления выражения в предыдущей строке. Это то же соглашение, которое используется в R5RS.
Scheme — очень простой язык, его гораздо проще реализовать, чем многие другие языки с сопоставимой выразительной силой . [17] Эта легкость объясняется использованием лямбда-исчисления для получения большей части синтаксиса языка из более примитивных форм. Например, из 23 синтаксических конструкций на основе s-выражений, определенных в стандарте схемы R5RS, 14 классифицируются как производные или библиотечные формы, которые могут быть написаны как макросы, включающие более фундаментальные формы, главным образом лямбда. Как говорит R5RS (§3.1): «Наиболее фундаментальной из конструкций привязки переменных является лямбда-выражение, поскольку все остальные конструкции привязки переменных можно объяснить с помощью лямбда-выражений». [4]
Пример: макрос, который нужно реализовать letв виде выражения, используемого lambdaдля выполнения привязки переменных.
( define-syntax let ( синтаксические правила () (( let (( var expr ) ... ) body ... ) (( лямбда ( var ... ) body ... ) expr ... )))) Таким образом, использование letописанной выше реализации схемы приведет к переписыванию " (let ((a 1)(b 2)) (+ b a))" как " ((lambda (a b) (+ b a)) 1 2)", что сводит задачу реализации к задаче кодирования экземпляров процедур.
В 1998 году Сассман и Стил заметили, что минимализм Scheme не был сознательной целью дизайна, а скорее непреднамеренным результатом процесса проектирования. «На самом деле мы пытались построить что-то сложное и по счастливой случайности обнаружили, что случайно спроектировали что-то, что отвечало всем нашим целям, но оказалось намного проще, чем мы предполагали… мы поняли, что лямбда-исчисление — небольшой простой формализм — может послужить основой мощного и выразительного языка программирования». [7]
Как и большинство современных языков программирования и в отличие от более ранних Lisps, таких как Maclisp , Scheme имеет лексическую область видимости: все возможные привязки переменных в программном модуле могут быть проанализированы путем чтения текста программного модуля без учета контекстов, в которых он может быть вызван. Это контрастирует с динамической областью видимости, которая была характерна для ранних диалектов Лиспа из-за затрат на обработку, связанных с примитивными методами текстовой замены, используемыми для реализации алгоритмов лексической области видимости в компиляторах и интерпретаторах того времени. В этих Лиспах ссылка на свободную переменную внутри процедуры вполне могла ссылаться на совершенно разные привязки, внешние по отношению к процедуре, в зависимости от контекста вызова.
Стимулом к включению лексической области видимости, которая была необычной моделью области видимости в начале 1970-х годов, в их новую версию Lisp, послужили исследования Суссмана АЛГОЛА . Он предположил, что механизмы лексического обзора, подобные ALGOL , помогут реализовать первоначальную цель реализации модели актера Хьюитта в Lisp. [7]
Ключевые идеи о том, как ввести лексическую область видимости в диалект Лиспа, были популяризированы в лямбда-документе Сассмана и Стила 1975 года «Схема: интерпретатор расширенного лямбда-исчисления» [18] , где они приняли концепцию лексического замыкания (на странице 21). ), который был описан в AI Memo в 1970 году Джоэлом Мозесом , который приписал идею Питеру Дж. Ландину . [19]
Математическая нотация Алонзо Чёрча , лямбда-исчисление, вдохновила Лисп использовать слово «лямбда» в качестве ключевого слова для введения процедуры, а также повлияла на развитие методов функционального программирования , включающих использование функций высшего порядка в Лиспе. Но ранние версии Лиспов не были подходящим выражением лямбда-исчисления из-за того, что они обрабатывали свободные переменные . [7]
Формальная лямбда-система имеет аксиомы и полное правило расчета. Это полезно для анализа с использованием математической логики и инструментов. В этой системе расчет можно рассматривать как направленный вычет. Синтаксис лямбда-исчисления следует рекурсивным выражениям из x, y, z,..., круглых скобок, пробелов, периода и символа λ. [20] Функция расчета лямбды включает в себя: Во-первых, служить отправной точкой мощной математической логики. Во-вторых, это может снизить потребность программистов в рассмотрении деталей реализации, поскольку его можно использовать для имитации машинной оценки. Наконец, вычисление лямбды создало существенную метатеорию. [21]
Введение лексической области видимости решило проблему, установив эквивалентность между некоторыми формами лямбда-нотации и их практическим выражением в рабочем языке программирования. Сассман и Стил показали, что новый язык можно использовать для элегантного вывода всей императивной и декларативной семантики других языков программирования, включая АЛГОЛ и Фортран , а также динамической области действия других Лиспов, используя лямбда-выражения не как простые экземпляры процедур, а как «управляющие». структуры и модификаторы среды». [22] Они представили стиль передачи продолжения вместе со своим первым описанием Scheme в первой из статей о лямбда-исчислении, а в последующих статьях они приступили к демонстрации необузданной силы этого практического использования лямбда-исчисления.
Scheme наследует свою блочную структуру от более ранних языков с блочной структурой, в частности от ALGOL . В Scheme блоки реализуются тремя конструкциями привязки : let, let*и letrec. Например, следующая конструкция создает блок , в котором вызываемый символ varпривязан к числу 10:
( определить var "гусь" ) ;; Любая ссылка на var здесь будет привязана к "goose" ( let (( var 10 )) ;; сюда идут операторы. Любая ссылка на var здесь будет привязана к 10. ) ;; Любая ссылка на var здесь будет привязана к слову «гусь». Блоки могут быть вложены друг в друга для создания произвольно сложных блочных структур в соответствии с потребностями программиста. Использование блочной структуризации для создания локальных привязок снижает риск конфликта пространств имен , который может возникнуть в противном случае.
Один вариант let, let*, позволяет привязкам ссылаться на переменные, определенные ранее в той же конструкции, таким образом:
( let* (( var1 10 ) ( var2 ( + var1 12 ))) ;; Но определение var1 не может относиться к var2 ) Другой вариант, letrec, предназначен для привязки взаимно рекурсивных процедур друг к другу.
;; Расчет мужских и женских последовательностей Хофштадтера как списка пар( define ( hofstadter-мужчина-женщина n ) ( letrec (( женщина ( лямбда ( n ) ( if ( = n 0 ) 1 ( - n ( мужчина ( женщина ( - n 1 ))))))) ( мужчина ( лямбда ( n ) ( if ( = n 0 ) 0 ( - n ( женщина ( мужчина ( - n 1 )))))))) ( пусть цикл (( i 0 )) ( if ( > i n ) ' () ( минусы ( минусы ( женщина я ) ( мужчина я )) ( петля ( + я 1 ))))))) ( hofstadter-мужской-женский 8 ) ===> (( 1 . 0 ) ( 1 . 0 ) ( 2 . 1 ) ( 2 . 2 ) ( 3 . 2 ) ( 3 . 3 ) ( 4 . 4 ) ( 5 . 4 ) ( 5 . 5 ) ) ( Определения, используемые в этом примере, см. в мужских и женских последовательностях Хофштадтера .)
Все процедуры, связанные в один файл, letrecмогут ссылаться друг на друга по имени, а также на значения переменных, определенных ранее в том же файле letrec, но они не могут ссылаться на значения , определенные позже в том же файле letrec.
Вариант letформы «named let» имеет идентификатор после letключевого слова. Это связывает переменные let с аргументом процедуры, именем которой является заданный идентификатор, а телом является тело формы let. Тело можно повторить по желанию, вызвав процедуру. Именованный let широко используется для реализации итерации.
Пример: простой счетчик
( пусть цикл (( n 1 )) ( if ( > n 10 ) ' () ( cons n ( цикл ( + n 1 ))))) ===> ( 1 2 3 4 5 6 7 8 9 10 ) Как и любая процедура в Scheme, процедура, созданная в именованном элементе let, является объектом первого класса.
В Scheme есть конструкция итерации, doно в Scheme более идиоматично использовать хвостовую рекурсию для выражения итерации . Реализации Scheme, соответствующие стандарту, необходимы для оптимизации хвостовых вызовов, чтобы поддерживать неограниченное количество активных хвостовых вызовов (R5RS, раздел 3.5) [4] (свойство, которое в отчете Scheme описывает как правильная хвостовая рекурсия ), что делает его безопасным для программистов Scheme. писать итерационные алгоритмы, используя рекурсивные структуры, которые иногда более интуитивны. Процедуры хвостовой рекурсии и именованнаяlet форма обеспечивают поддержку итерации с использованием хвостовой рекурсии.
;; Построение списка квадратов от 0 до 9: ;; Примечание. Цикл — это просто произвольный символ, используемый в качестве метки. Любой символ подойдет.( define ( список квадратов n ) ( пусть цикл (( i n ) ( res ' ())) ( if ( < i 0 ) res ( цикл ( - i 1 ) ( cons ( * i i ) res )) ))) ( список квадратов 9 ) ===> ( 0 1 4 9 16 25 36 49 64 81 ) Продолжения в Scheme являются объектами первого класса . Scheme предоставляет процедуру call-with-current-continuation(также известную как call/cc) для захвата текущего продолжения, упаковывая ее как escape-процедуру, привязанную к формальному аргументу в процедуре, предоставленной программистом. (R5RS, раздел 6.4) [4] Продолжения первого класса позволяют программисту создавать нелокальные конструкции управления , такие как итераторы , сопрограммы и возвраты .
Продолжения можно использовать для эмуляции поведения операторов возврата в императивных языках программирования. Следующая функция find-first, учитывая function funcи list lst, возвращает первый элемент, возвращающий xtrue .lst(func x)
( define ( find-first func lst ) ( вызов с текущим продолжением ( лямбда ( return-immediately ) ( for-each ( лямбда ( x ) ( if ( func x ) ( return-immediate x ))) lst ) # х ))) ( найти первое целое число? ' ( 1/2 3/4 5.6 7 8/9 10 11 )) ===> 7 ( найти первый ноль? ' ( 1 2 3 4 )) ===> #f Следующий пример, традиционная загадка программиста, показывает, что Scheme может обрабатывать продолжения как первоклассные объекты, привязывая их к переменным и передавая их в качестве аргументов процедурам.
( let* (( инь (( лямбда ( cc ) ( display "@" ) cc ) ( вызов с текущим продолжением ( лямбда ( c ) c )))) ( yang (( лямбда ( cc ) ( display "* " ) cc ) ( вызов с текущим продолжением ( лямбда ( c ) c ))))) ( инь янь )) При выполнении этот код отображает последовательность подсчета:@*@**@***@****@*****@******@*******@********...
В отличие от Common Lisp, все данные и процедуры в Scheme имеют общее пространство имен, тогда как в Common Lisp функции и данные имеют отдельные пространства имен , что позволяет функции и переменной иметь одно и то же имя и требует специальных обозначений для обращения к функционировать как ценность. Иногда это называют различием « Lisp-1 против Lisp-2 », имея в виду единое пространство имен Scheme и отдельные пространства имен Common Lisp. [23]
В Scheme для привязки процедур можно использовать те же примитивы, которые используются для манипулирования и привязки данных. Не существует эквивалента Common Lisp defunи #'примитивов.
;; Переменная, привязанная к числу: ( define f 10 ) f ===> 10 ;; Мутация (изменение связанного значения) ( set! f ( + f f 6 )) f ===> 26 ;; Присвоение процедуры одной и той же переменной: ( set! f ( лямбда ( n ) ( + n 12 ))) ( f 6 ) ===> 18 ;; Присвоение результата выражения той же переменной: ( set! f ( f 1 )) f ===> 13 ;; функциональное программирование: ( применить + ' ( 1 2 3 4 5 6 )) ===> 21 ( set! f ( лямбда ( n ) ( + n 100 ))) ( карта f ' ( 1 2 3 )) === > ( 101 102 103 ) В этом подразделе документируются проектные решения, принятые на протяжении многих лет, которые придали Схеме особый характер, но не являются прямым результатом первоначального проекта.
Схема определяет сравнительно полный набор числовых типов данных, включая комплексные и рациональные типы, которые известны в Scheme как числовая башня (R5RS, раздел 6.2 [4] ). Стандарт рассматривает их как абстракции и не обязывает разработчика использовать какие-либо конкретные внутренние представления.
Числа могут иметь качество точности. Точное число можно получить только с помощью последовательности точных операций, включающих другие точные числа, поэтому неточность заразительна. Стандарт определяет, что любые две реализации должны давать эквивалентные результаты для всех операций, приводящих к точным числам.
Стандарт R5RS определяет процедуры exact->inexact, inexact->exactкоторые можно использовать для изменения точности числа. inexact->exactвыдает «точное число, наиболее близкое к аргументу». exact->inexactвыдает «неточное число, которое численно наиболее близко к аргументу». Стандарт R6RS исключает эти процедуры из основного отчета, но определяет их как процедуры совместимости R5RS в стандартной библиотеке (rnrs r5rs (6)).
В стандарте R5RS реализации Scheme не обязаны реализовывать всю числовую башню, но они должны реализовывать «связное подмножество, соответствующее как целям реализации, так и духу языка Scheme» (R5RS, раздел 6.2.3). [4] Новый стандарт R6RS требует реализации всей башни, а также «точных целочисленных объектов и точных объектов рационального числа практически неограниченного размера и точности, а также реализации определенных процедур... чтобы они всегда возвращали точные результаты при задании точных аргументов». (Р6РС п. 3.4, п. 11.7.1). [6]
Пример 1: точная арифметика в реализации, поддерживающей точные рациональные комплексные числа.
;; Сумма трех рациональных действительных чисел и двух рациональных комплексных чисел ( определите x ( + 1/3 1/4 -1/5 -1/3i 405/50+2/3i )) x ===> 509/60+1/ 3и ;; Проверьте точность. ( точно? x ) ===> #t Пример 2: Та же арифметика в реализации, которая не поддерживает ни точные рациональные числа, ни комплексные числа, но принимает действительные числа в рациональной записи.
;; Сумма четырех рациональных действительных чисел ( define xr ( + 1/3 1/4 -1/5 405/50 )) ;; Сумма двух рациональных действительных чисел ( определить xi ( + -1/3 2/3 )) xr ===> 8.48333333333333 xi ===> 0.333333333333333 ;; Проверьте точность. ( точно? xr ) ===> #f ( точно? xi ) ===> #f Обе реализации соответствуют стандарту R5RS, но вторая не соответствует R6RS, поскольку не реализует полную числовую башню.
Схема поддерживает отложенную оценку посредством delayформы и процедуры force.
( определить 10 ) ( определить eval-aplus2 ( задержка ( + a 2 ))) ( установить! a 20 ) ( принудительно eval-aplus2 ) ===> 22 ( определить eval-aplus50 ( задержка ( + a 50 ) )) ( let (( a 8 )) ( force eval-aplus50 )) ===> 70 ( set! a 100 ) ( force eval-aplus2 ) ===> 22 Лексический контекст исходного определения обещания сохраняется, и его значение также сохраняется после первого использования force. Обещание оценивается только один раз.
Эти примитивы, которые создают или обрабатывают значения, известные как обещания , могут использоваться для реализации расширенных конструкций отложенного вычисления , таких как потоки . [24]
В стандарте R6RS они больше не являются примитивами, а предоставляются как часть библиотеки совместимости R5RS (rnrs r5rs (6)).
В R5RS дается предлагаемая реализация delayи force, реализующая обещание как процедуру без аргументов ( thunk ) и использующая мемоизацию , чтобы гарантировать, что оно вычисляется только один раз, независимо от количества вызовов force(R5RS, раздел 6.4). ). [4]
SRFI 41 позволяет выражать как конечные, так и бесконечные последовательности с исключительной экономией. Например, это определение последовательности Фибоначчи с использованием функций, определенных в SRFI 41: [24]
;; Определим последовательность Фибоначчи: ( define fibs ( stream-cons 0 ( stream-cons 1 ( stream-map + fibs ( stream-cdr fibs ))))) ;; Вычислите сотое число в последовательности: ( stream-ref fibs 99 ) ===> 218922995834555169026 Большинство Лиспов определяют порядок вычисления аргументов процедуры. Схемы нет. Порядок вычисления, включая порядок, в котором оценивается выражение в позиции оператора, может выбираться реализацией для каждого вызова, и единственным ограничением является то, что «эффект любого одновременного вычисления оператора и Выражения операндов должны соответствовать некоторому последовательному порядку вычислений». (Р5РС п. 4.1.3) [4]
( let (( ev ( лямбда ( n ) ( отображение «Оценка » ) ( отображение ( if ( процедура? n ) «процедура» n )) ( новая строка ) n ))) (( ev + ) ( ev 1 ) ( ev 2 ))) ===> 3 Оценка 1 Оценка 2 Процедура оценкиev — это процедура, которая описывает переданный ей аргумент, а затем возвращает значение аргумента. В отличие от других Лиспов, появление выражения в позиции оператора (первый элемент) выражения Scheme вполне законно, если результатом выражения в позиции оператора является процедура.
При вызове процедуры « + » для сложения 1 и 2 выражения (ev +), (ev 1) и (ev 2) могут вычисляться в любом порядке, при условии, что эффект не будет таким, как если бы они вычислялись параллельно. . Таким образом, следующие три строки могут отображаться в любом порядке стандартной схемой при выполнении приведенного выше примера кода, хотя текст одной строки не может чередоваться с другой, поскольку это нарушит ограничение последовательного вычисления.
В стандарте R5RS, а также в более поздних отчетах синтаксис Scheme можно легко расширить с помощью системы макросов. Стандарт R5RS представил мощную гигиеническую систему макросов, которая позволяет программисту добавлять в язык новые синтаксические конструкции, используя простой подъязык сопоставления с образцом (R5RS, раздел 4.3). [4] До этого гигиеническая макросистема была отнесена к приложению к стандарту R4RS как система «высокого уровня» наряду с макросистемой «низкого уровня», причем обе из них рассматривались как расширение Схемы, а не как система. важнейшая часть языка. [25]
Реализации гигиенической макросистемы, также называемой syntax-rules, должны учитывать лексическую область видимости остальной части языка. Это обеспечивается специальными правилами именования и области действия для расширения макросов и позволяет избежать распространенных ошибок программирования, которые могут возникнуть в макросистемах других языков программирования. R6RS определяет более сложную систему преобразования, syntax-caseкоторая уже некоторое время доступна как языковое расширение схемы R5RS.
;; Определите макрос для реализации варианта «if» с мультивыражением ;; истинная ветвь и отсутствие ложной ветви. ( define-syntax When ( синтаксические правила () (( When pred exp exps ... ) ( if pred ( Begin exp exps ... ))))) Вызовы макросов и процедур очень похожи — оба являются s-выражениями, — но обрабатываются по-разному. Когда компилятор встречает в программе s-выражение, он сначала проверяет, определен ли этот символ как синтаксическое ключевое слово в текущей лексической области видимости. Если да, то он пытается расширить макрос, рассматривая элементы в хвосте s-выражения как аргументы без компиляции кода для их оценки, и этот процесс повторяется рекурсивно до тех пор, пока не останется вызовов макроса. Если это не синтаксическое ключевое слово, компилятор компилирует код для оценки аргументов в хвосте s-выражения, а затем для вычисления переменной, представленной символом в начале s-выражения, и вызова ее как процедуры с оцененные хвостовые выражения, переданные ему в качестве аргументов.
Большинство реализаций Scheme также предоставляют дополнительные макросистемы. Среди популярных — синтаксические замыкания , макросы явного переименования и define-macroнегигиеничная система макросов, аналогичная defmacroсистеме, представленной в Common Lisp .
Невозможность указать, является ли макрос гигиеничным, является одним из недостатков макросистемы. Альтернативные модели расширения, такие как наборы объемов, представляют собой потенциальное решение. [26]
До R5RS в Scheme не было стандартного эквивалента процедуры eval, которая повсеместно использовалась в других Lisp-ах, хотя в первой статье о лямбде она описывалась evaluateкак «похожая на функцию EVAL LISP» [18] , а в первом пересмотренном отчете 1978 года она была заменена на enclose, что взял два аргумента. Во втором, третьем и четвертом пересмотренных отчетах не было каких-либо эквивалентов eval.
Причина этой путаницы в том, что в Scheme с ее лексической областью видимости результат вычисления выражения зависит от того, где оно вычисляется. Например, неясно, должен ли результат вычисления следующего выражения быть 5 или 6: [27]
( let (( name '+ )) ( let (( + * )) ( оценить ( имя списка 2 3 )))) Если он оценивается во внешней среде, где nameон определен, результатом является сумма операндов. Если он вычисляется во внутренней среде, где символ «+» привязан к значению процедуры «*», результатом является произведение двух операндов.
R5RS разрешает эту путаницу, определяя три процедуры, возвращающие среды, и предоставляя процедуру eval, которая принимает s-выражение и среду и оценивает выражение в предоставленной среде. (R5RS, раздел 6.5) [4] R6RS расширяет это, предоставляя вызываемую процедуру, environmentс помощью которой программист может точно указать, какие объекты импортировать в среду оценки.
В современной схеме (обычно совместимой с R5RS) для вычисления этого выражения необходимо определить функцию, evaluateкоторая может выглядеть следующим образом:
( определить ( оценить выражение ) ( eval выражение ( среда взаимодействия ))) interaction-environmentэто глобальная среда интерпретатора.
В большинстве диалектов Lisp, включая Common Lisp, по соглашению значение NILвычисляется как значение false в логическом выражении. В Scheme, начиная со стандарта IEEE в 1991 году, [3] все значения, кроме #f, включая NILэквивалент в Scheme, который записывается как '(), оцениваются как значение true в логическом выражении. (Р5РС п. 6.3.1) [4]
Если в большинстве Lisp константа, представляющая логическое значение true T, то в Scheme она равна #t.
В Scheme примитивные типы данных не пересекаются. Для любого объекта Scheme может быть истинным только один из следующих предикатов: boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?. (R5RS раздел 3.2) [4]
Внутри числового типа данных, напротив, числовые значения перекрываются. Например, целочисленное значение одновременно удовлетворяет всем предикатам , integer?, rational?и real?. (R5RS раздел 6.2) [4]complex?number?
Схема имеет три различных типа эквивалентности между произвольными объектами , обозначаемыми тремя различными предикатами эквивалентности , реляционными операторами для проверки равенства, и eq?:eqv?equal?
eq?оценивается как, #fесли только его параметры не представляют один и тот же объект данных в памяти;eqv?обычно то же самое, что eq?и примитивные объекты (например, символы и числа), но обрабатывает их таким образом, чтобы числа, представляющие одно и то же значение, были одинаковыми, eqv?даже если они не относятся к одному и тому же объекту;equal?сравнивает структуры данных, такие как списки, векторы и строки, чтобы определить, имеют ли они конгруэнтную структуру и eqv?содержимое. (R5RS, раздел 6.1) [4]В Scheme также существуют операции эквивалентности, зависящие от типа: string=?и string-ci=?сравнение двух строк (последняя выполняет сравнение независимо от регистра); char=?и char-ci=?сравнивать персонажей; =сравнивает числа. [4]
До стандарта R5RS стандартным комментарием в Scheme была точка с запятой, что делало остальную часть строки невидимой для Scheme. Многочисленные реализации поддерживают альтернативные соглашения, позволяющие расширять комментарии более чем на одну строку, а стандарт R6RS допускает два из них: все s-выражение может быть превращено в комментарий (или «закомментировано»), предваряясь им #;(введено в SRFI 62 [28] ), а многострочный комментарий или «блочный комментарий» могут быть созданы путем окружения текста значками #|и |#.
Ввод и вывод схемы основаны на типе данных порта . (R5RS, раздел 6.6) [4] R5RS определяет два порта по умолчанию, доступные с помощью процедур current-input-portи current-output-port, которые соответствуют понятиям Unix стандартного ввода и стандартного вывода . Большинство реализаций также предоставляют current-error-port. Перенаправление ввода и стандартного вывода поддерживается в стандарте с помощью стандартных процедур, таких как with-input-from-fileи with-output-to-file. Большинство реализаций предоставляют строковые порты с аналогичными возможностями перенаправления, позволяя выполнять многие обычные операции ввода-вывода над строковыми буферами вместо файлов, используя процедуры, описанные в SRFI 6. [29] Стандарт R6RS определяет гораздо более сложные и функциональные процедуры порта и многие новые типы портов.
Следующие примеры написаны по строгой схеме R5RS.
Пример 1: с выходом по умолчанию (текущий-выходной порт):
( let (( hello0 ( лямбда () ( отобразить «Hello world» ) ( новая строка )))) ( hello0 )) Пример 2: Как 1, но с использованием дополнительного аргумента порта для процедур вывода.
( let (( hello1 ( лямбда ( p ) ( отобразить «Hello world» p ) ( новая строка p )))) ( hello1 ( текущий-выходной порт ))) Пример 3: Как 1, но вывод перенаправляется во вновь созданный файл.
;; Примечание: with-output-to-file — это необязательная процедура в R5RS ( let (( hello0 ( lambda () ( display "Hello world" ) ( newline )))) ( with-output-to-file "helloworldoutputfile" hello0 ) ) Пример 4: Как 2, но с явным открытием файла и закрытием порта для отправки вывода в файл.
( let (( hello1 ( лямбда ( p ) ( отобразить «Hello world» p ) ( новая строка p ))) ( выходной порт ( открытый выходной файл «helloworldoutputfile» ))) ( выходной порт hello1 ) ( close-output -порт -порт вывода )) Пример 5: Как 2, но с использованием вызова с выходным файлом для отправки вывода в файл.
( let (( hello1 ( лямбда ( p ) ( отображение «Hello world» p ) ( новая строка p )))) ( вызов с выходным файлом «helloworldoutputfile» hello1 )) Аналогичные процедуры предусмотрены для ввода. Схема R5RS предоставляет предикаты input-port?и output-port?. Для ввода и вывода символов предусмотрены , write-char, и . Для написания и чтения выражений Scheme Scheme предоставляет и . При операции чтения возвращаемым результатом является объект конца файла, если входной порт достиг конца файла, и это можно проверить с помощью предиката .read-charpeek-charchar-ready?readwriteeof-object?
В стандарте SRFI 28 также определяется базовая процедура форматирования, напоминающая функцию Common Lisp format, в честь которой она и названа. [30]
В Scheme процедуры привязаны к переменным. В R5RS стандарт языка формально требовал, чтобы программы могли изменять привязки переменных встроенных процедур, фактически переопределяя их. (R5RS «Изменения языка») [4] Например, +его можно расширить, чтобы принимать строки, а также числа, переопределив его:
( set! + ( let (( original+ + )) ( лямбда- аргументы ( применить ( if ( или ( null? args ) ( string? ( car args ))) string-append original+ ) args )))) ( + 1 2 3 ) ===> 6 ( + "1" "2" "3" ) ===> "123" В R6RS каждая привязка, включая стандартные, принадлежит какой-либо библиотеке, и все экспортированные привязки являются неизменяемыми. (R6RS раздел 7.1) [6] По этой причине переопределение стандартных процедур путем мутации запрещено. Вместо этого можно импортировать другую процедуру под именем стандартной, что по сути аналогично переопределению.
В стандартной схеме процедуры, преобразующие один тип данных в другой, содержат в своем имени строку символов «->», предикаты заканчиваются знаком «?», а процедуры, изменяющие значение уже выделенных данных, заканчиваются знаком «!». Программисты Scheme часто следуют этим соглашениям.
В формальных контекстах, таких как стандарты Scheme, слово «процедура» используется вместо слова «функция» для обозначения лямбда-выражения или примитивной процедуры. В обычном использовании слова «процедура» и «функция» используются как взаимозаменяемые. Применение процедуры иногда формально называют комбинацией .
Как и в других Лиспах, термин « thunk » используется в Scheme для обозначения процедуры без аргументов. Термин «правильная хвостовая рекурсия» относится к свойству всех реализаций Scheme, заключающемуся в том, что они выполняют оптимизацию хвостовых вызовов, чтобы поддерживать неопределенное количество активных хвостовых вызовов .
Форма заголовков документов стандартов, начиная с R3RS, «Пересмотренный отчет по схеме алгоритмического языка», является ссылкой на заголовок стандартного документа ALGOL 60 , «Пересмотренный отчет по алгоритмическому языку Algol 60», страница «Сводка». R3RS точно смоделирован на странице «Сводка» отчета ALGOL 60. [31] [32]
Формально язык определен в стандартах R5RS (1998) [4] и R6RS (2007). [6] Они описывают стандартные «формы»: ключевые слова и сопровождающий их синтаксис, которые обеспечивают структуру управления языком, а также стандартные процедуры, выполняющие общие задачи.
В этой таблице описаны стандартные формы в Scheme. Некоторые формы появляются более чем в одной строке, поскольку их нелегко классифицировать как одну функцию в языке.
Формы, отмеченные буквой «L» в этой таблице, классифицируются в стандарте как производные «библиотечные» формы и часто реализуются как макросы с использованием более фундаментальных форм на практике, что значительно упрощает задачу реализации, чем в других языках.
Хотя beginв R5RS он определен как библиотечный синтаксис, расширитель должен знать об этом, чтобы реализовать функцию сращивания. В R6RS это больше не библиотечный синтаксис.
В следующих двух таблицах описаны стандартные процедуры схемы R5RS. R6RS гораздо более обширен, и краткое изложение такого типа нецелесообразно.
Некоторые процедуры появляются более чем в одной строке, поскольку их нелегко классифицировать в одной функции языка.
Строковые и символьные процедуры, содержащие «-ci» в своих именах, выполняют сравнение своих аргументов независимо от регистра: версии одного и того же символа в верхнем и нижнем регистре считаются равными.
Реализации - и /, которые принимают более двух аргументов, определены, но оставлены необязательными в R5RS.
Из-за минимализма Scheme многие общие процедуры и синтаксические формы не определены стандартом. Чтобы сохранить небольшой размер основного языка, но облегчить стандартизацию расширений, сообщество Scheme имеет процесс «Запроса на реализацию схемы» (SRFI), с помощью которого библиотеки расширений определяются путем тщательного обсуждения предложений по расширениям. Это способствует переносимости кода. Многие из SRFI поддерживаются всеми или большинством реализаций Scheme.
SRFI с довольно широкой поддержкой в различных реализациях включают: [33]
Элегантный минималистичный дизайн сделал Scheme популярной целью для языковых дизайнеров, любителей и преподавателей, а из-за своего небольшого размера, как у типичного интерпретатора , он также является популярным выбором для встроенных систем и сценариев . В результате появилось множество реализаций, [34] большинство из которых настолько отличаются друг от друга, что перенос программ из одной реализации в другую довольно затруднителен, а небольшой размер стандартного языка означает, что написание полезной программы любой большой сложности в стандартной портативной схеме практически невозможно. [14] Стандарт R6RS определяет гораздо более широкий язык в попытке расширить его привлекательность для программистов.
Почти все реализации предоставляют традиционный цикл чтения-оценки-печати в стиле Лиспа для разработки и отладки. Многие также компилируют программы Scheme в исполняемый двоичный файл. Поддержка встраивания кода Scheme в программы, написанные на других языках, также распространена, поскольку относительная простота реализаций Scheme делает его популярным выбором для добавления возможностей сценариев в более крупные системы, разработанные на таких языках, как C. Интерпретаторы Gambit , Chicken и Bigloo Scheme компилируют Scheme в C, что значительно упрощает встраивание . Кроме того, компилятор Bigloo можно настроить для генерации байт-кода для виртуальной машины Java (JVM) и имеет экспериментальный генератор байт-кода для .NET .
Некоторые реализации поддерживают дополнительные функции. Например, Kawa и JScheme обеспечивают интеграцию с классами Java , а компиляторы Scheme to C часто упрощают использование внешних библиотек, написанных на C, вплоть до встраивания кода C в исходный код Scheme. Другим примером является Pvts, который предлагает набор визуальных инструментов, поддерживающих обучение Scheme.
Схема широко используется несколькими [35] школами; в частности, в нескольких вводных курсах информатики используется Scheme в сочетании с учебником « Структура и интерпретация компьютерных программ» (SICP). [36] За последние 12 лет PLT реализовала проект ProgramByDesign (ранее TeachScheme!), в рамках которого около 600 учителей средних школ и тысячи старшеклассников познакомились с элементарным программированием Scheme. Старый вводный курс по программированию MIT 6.001 преподавался на Scheme, [37] Хотя 6.001 был заменен более современными курсами, SICP продолжает преподаваться в MIT. [38] Аналогичным образом, вводный класс в Калифорнийском университете в Беркли , CS 61A, до 2011 года полностью преподавался на схеме, за исключением небольших отклонений на логотип для демонстрации динамического объема. Сегодня, как и MIT, Беркли заменил учебную программу на более современную версию, которая в основном преподается на Python 3 , но текущая программа по-прежнему основана на старой учебной программе, и некоторые части занятий по-прежнему преподаются на Scheme. [39]
Учебник «Как разрабатывать программы» Маттиаса Феллейзена, который в настоящее время учится в Северо-Восточном университете, используется некоторыми высшими учебными заведениями для вводных курсов по информатике. И Северо-Восточный университет, и Вустерский политехнический институт используют Scheme исключительно для своих вводных курсов «Основы информатики» (CS2500) и «Введение в разработку программ» (CS1101) соответственно. [40] [41] Роуз-Халман использует Scheme в своем более продвинутом курсе «Концепции языка программирования». [42] Основной курс Университета Брандейса «Структура и интерпретация компьютерных программ» (COSI121b) также преподается исключительно на Scheme ученым-теоретиком Гарри Мейрсоном . [43] Вводный курс C211 Университета Индианы полностью преподается по схеме. Версия курса для самостоятельного обучения CS 61AS продолжает использовать Scheme. [44] Вводные курсы информатики в Йельском и Гриннелл-колледже также преподаются на Scheme. [45] «Парадигмы проектирования программирования», [46] обязательный курс для аспирантов в области компьютерных наук в Северо-Восточном университете , также широко использует Scheme. Бывший вводный курс информатики в Университете Миннесоты - Города-побратимы, CSCI 1901, также использовал Scheme в качестве основного языка, за которым следовал курс, знакомивший студентов с языком Java; [47] однако, следуя примеру Массачусетского технологического института, кафедра заменила 1901 на основанный на Python CSCI 1133, [48] в то время как функциональное программирование подробно рассматривается в третьем семестре курса CSCI 2041. [49]
Схема также использовалась/использовалась для следующего:
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )Полезная метафора разницы между FUNCTION и QUOTE в LISP: думать о QUOTE как о пористом или открытом покрытии функции, поскольку свободные переменные уходят в текущую среду.
ФУНКЦИЯ действует как закрытое или непористое покрытие (отсюда и термин «закрытие», используемый Ландином).
Таким образом, мы говорим об «открытых» лямбда-выражениях (функции в LISP обычно являются лямбда-выражениями) и «закрытых» лямбда-выражениях.
[...] Мой интерес к проблеме окружающей среды начался, когда Ландин, глубоко разбиравшийся в этой проблеме, посетил Массачусетский технологический институт в 1966-67 годах.
Затем я понял соответствие между списками FUNARG, которые являются результатами оценки «закрытых» лямбда-выражений в
LISP
и
Lambda Closures
ISWIM .
Схемное программирование в WikibooksНапишите себе схему за 48 часов в Wikibooks
СМИ, связанные со схемой (языком программирования) на Викискладе?