Схема (язык программирования)

Схема

Парадигмы	Мультипарадигмальность : функциональная , императивная , мета.
Семья	Лисп
Разработано	Гай Л. Стил Джеральд Джей Сассман
Впервые появился	1975 год ( 1975 )
Стабильная версия	Р7РС / 2013 ( 2013 )
Дисциплина набора текста	Динамичный , скрытый , сильный
Объем	Лексический
Расширения имен файлов	.скм, .сс
Веб-сайт	www .схема .org
Основные реализации
Много (см. Реализации схемы )
Под влиянием
АЛГОЛ , Лисп , MDL
Под влиянием
Clojure , Common Lisp , Dylan , EuLisp , Haskell , Hop , JavaScript , Julia , Lua , MultiLisp , Python , R , Racket , Ruby , Rust , С , Скала , Т
Схема в Wikibooks

Схема — это диалект семейства Lisp языков программирования . Схема была создана в 1970-х годах в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (MIT AI Lab) и выпущена ее разработчиками Гаем Л. Стилом и Джеральдом Джеем Сассманом в виде серии записок, теперь известных как Lambda Papers . Это был первый диалект Лиспа, в котором была выбрана лексическая область видимости , и первый, требующий реализации для выполнения хвостовой оптимизации , обеспечивая более надежную поддержку функционального программирования и связанных с ним методов, таких как рекурсивные алгоритмы. Это был также один из первых языков программирования, поддерживавший первоклассные продолжения . Он оказал значительное влияние на усилия, которые привели к разработке Common Lisp .

Язык схемы стандартизирован в официальном стандарте Института инженеров по электротехнике и электронике (IEEE). и стандарт де-факто под названием « Пересмотренный». ^н Отчет об алгоритмической языковой схеме (R n RS). Широко внедренным стандартом является R5RS (1998 г.). Последний ратифицированный стандарт Схемы — «R7RS-small» (2013 г.). Более обширный и модульный вариант R6RS был ратифицирован в 2007 году. Оба ведут свое происхождение от R5RS; график ниже отражает хронологический порядок ратификации.

История

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

Происхождение

Scheme зародился в 1970-х годах как попытка понять Хьюитта Карла модель актера , для чего Стил и Сассман написали «крошечный интерпретатор Лиспа», используя Maclisp , а затем «добавили механизмы для создания актеров и отправки сообщений». Первоначально Scheme назывался «Schemer», в традициях других языков, производных от Lisp, таких как Planner или Conniver . Текущее название возникло в результате использования авторами операционной системы ITS , которая ограничивала имена файлов двумя компонентами длиной не более шести символов каждый. В настоящее время «Комбинатор» обычно используется для обозначения программиста Scheme.

Р6РС

Новый процесс стандартизации языка начался на семинаре Scheme в 2003 году с целью создания стандарта R6RS в 2006 году. Этот процесс порвал с более ранним R n подходом единогласия RS.

R6RS имеет стандартную систему модулей, позволяющую разделить основной язык и библиотеки . Было выпущено несколько проектов спецификации R6RS, окончательной версией стала R5.97RS. Успешное голосование привело к ратификации нового стандарта, объявленного 28 августа 2007 года.

На данный момент новейшие версии различных реализаций Scheme. поддержка стандарта R6RS. Существует портативная эталонная реализация предлагаемых неявно поэтапных библиотек для R6RS, называемая psyntax, которая правильно загружает и загружает себя в различных старых реализациях Scheme.

Особенностью R6RS является дескриптор типа записи (RTD). Когда RTD создается и используется, представление типа записи может отображать структуру памяти. Он также рассчитывал битовую маску поля объекта и битовые маски полей изменяемого объекта Scheme и помогал сборщику мусора знать, что делать с полями, не просматривая весь список полей, сохраненный в RTD. RTD позволяет пользователям расширять базовый RTD для создания новой системы записей.

R6RS вносит в язык множество существенных изменений. Исходный код теперь указан в Unicode , и большое подмножество символов Unicode теперь может появляться в символах и идентификаторах Scheme , а также есть другие незначительные изменения в лексических правилах. Символьные данные теперь также указываются в Юникоде. Многие стандартные процедуры были перенесены в новые стандартные библиотеки, которые сами по себе представляют собой значительное расширение стандарта и содержат процедуры и синтаксические формы, которые ранее не были частью стандарта. Была введена новая система модулей, а системы обработки исключений теперь стандартизированы. Синтаксические правила были заменены более выразительным средством синтаксической абстракции (syntax-case), которое позволяет использовать всю схему во время расширения макроса. совместимые реализации теперь требуются Scheme Для поддержки полной числовой башни , а семантика чисел была расширена, главным образом, в направлении поддержки стандарта IEEE 754 для числового представления с плавающей запятой.

Р7РС

Стандарт R6RS вызвал споры, поскольку некоторые считают его отходом от минималистской философии. В августе 2009 года Руководящий комитет Scheme, который курирует процесс стандартизации, объявил о своем намерении рекомендовать разделить Scheme на два языка: большой современный язык программирования для программистов; и маленькая версия, подмножество большой версии, сохраняющая минимализм, хвалимый преподавателями и случайными разработчиками. Для работы над этими двумя новыми версиями Scheme были созданы две рабочие группы. На сайте Scheme Reports Process есть ссылки на уставы рабочих групп, общественные обсуждения и систему отслеживания проблем.

Девятый проект R7RS (малый язык) был доступен 15 апреля 2013 г. Голосование по ратификации этого проекта завершилось 20 мая 2013 г. а окончательный отчет доступен с 6 августа 2013 г., в котором описывается «маленький» язык этой работы: поэтому его нельзя рассматривать изолированно как преемника R6RS.

Отличительные особенности

См. также: Лисп (язык программирования).

Scheme — это прежде всего функциональный язык программирования . Он имеет много общих характеристик с другими членами семейства языков программирования Lisp. Очень простой синтаксис Scheme основан на s-выражениях — списках в круглых скобках, в которых за префиксным оператором следуют его аргументы. Таким образом, программы-схемы состоят из последовательностей вложенных списков. Списки также являются основной структурой данных в Scheme, что приводит к тесной эквивалентности между исходным кодом и форматами данных ( гомоиконичность ). Программы Scheme могут легко создавать и динамически оценивать фрагменты кода Scheme.

Использование списков как структур данных характерно для всех диалектов Лиспа. Схема наследует богатый набор примитивов обработки списков, таких как cons, car и cdr от своих прародителей Lisp. Scheme использует строго, но динамически типизированные переменные и поддерживает первоклассные процедуры . Таким образом, процедуры могут присваиваться как значения переменным или передаваться в качестве аргументов процедурам.

В этом разделе основное внимание уделяется инновационным особенностям языка, включая те особенности, которые отличают Scheme от других Lisp. Если не указано иное, описания функций относятся к стандарту R5RS. В примерах, приведенных в этом разделе, обозначение «===> результат» используется для обозначения результата вычисления выражения в предыдущей строке. Это то же соглашение, которое используется в R5RS.

Минимализм

Основная статья: Минимализм (вычисления)

Scheme — очень простой язык, его гораздо проще реализовать, чем многие другие языки с сопоставимой выразительной силой . Эта простота объясняется использованием лямбда-исчисления для получения большей части синтаксиса языка из более примитивных форм. Например, из 23 синтаксических конструкций на основе s-выражений, определенных в стандарте схемы R5RS, 14 классифицируются как производные или библиотечные формы, которые могут быть написаны как макросы, включающие более фундаментальные формы, главным образом лямбда. Как говорит R5RS (§3.1): «Самой фундаментальной из конструкций привязки переменных является лямбда-выражение, поскольку все остальные конструкции привязки переменных можно объяснить с помощью лямбда-выражений».

Основные формы : определение, лямбда, цитата, if, определение-синтаксис, let-синтаксис, letrec-синтаксис, правила синтаксиса, набор!

Производные формы : do, let, let*, letrec, cond, Case и, или, Begin, Named, Delay, Unquote, Unquote-Splicing, Quasiquote.

Пример: макрос для реализации let в качестве выражения, используя lambda для выполнения привязки переменных.

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))

Таким образом, используя let как определено выше, реализация схемы перепишет " (let ((a 1)(b 2)) (+ b a))" как " ((lambda (a b) (+ b a)) 1 2)", что сводит задачу реализации к созданию экземпляров процедур.

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

Лексическая область видимости

См. также: Область применения (программирование)

Как и большинство современных языков программирования и в отличие от более ранних Lisps, таких как Maclisp , Scheme имеет лексическую область видимости: все возможные привязки переменных в программном модуле могут быть проанализированы путем чтения текста программного модуля без учета контекстов, в которых он может быть вызван. Это контрастирует с динамической областью видимости, которая была характерна для ранних диалектов Лиспа из-за затрат на обработку, связанных с примитивными методами текстовой замены, используемыми для реализации алгоритмов лексической области видимости в компиляторах и интерпретаторах того времени. В этих Лиспах ссылка на свободную переменную внутри процедуры вполне могла ссылаться на совершенно разные привязки, внешние по отношению к процедуре, в зависимости от контекста вызова.

Стимулом к ​​включению лексической области видимости, которая была необычной моделью области видимости в начале 1970-х годов, в их новую версию Lisp, послужили исследования Суссмана АЛГОЛА . Он предположил, что механизмы лексического обзора, подобные ALGOL, помогут реализовать первоначальную цель реализации модели актера Хьюитта в Lisp.

Ключевые идеи о том, как ввести лексическую область видимости в диалект Лиспа, были популяризированы в лямбда-документе Сассмана и Стила 1975 года «Схема: интерпретатор расширенного лямбда-исчисления». где они приняли концепцию лексического замыкания (на странице 21), которая была описана в AI Memo в 1970 году Джоэлом Мозесом , который приписал эту идею Питеру Дж. Ландину .

Лямбда-исчисление

См. Также: Лямбда-исчисление

Математическая нотация Алонзо Чёрча , лямбда-исчисление, вдохновила Лисп на использование слова «лямбда» в качестве ключевого слова для введения процедуры, а также повлияла на развитие методов функционального программирования, включающих использование функций высшего порядка в Лиспе. Но ранние Лиспы не были подходящим выражением лямбда-исчисления из-за того, что в них обрабатывались свободные переменные .

Формальная лямбда-система имеет аксиомы и полное правило расчета. Это полезно для анализа с использованием математической логики и инструментов. В этой системе расчет можно рассматривать как направленный вычет. Синтаксис лямбда-исчисления следует рекурсивным выражениям из x, y, z,..., круглых скобок, пробелов, периода и символа λ. Функция расчета лямбды включает в себя: Во-первых, служить отправной точкой мощной математической логики. Во-вторых, это может снизить потребность программистов в рассмотрении деталей реализации, поскольку его можно использовать для имитации машинной оценки. Наконец, вычисление лямбда создало существенную метатеорию.

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

Блочная структура

Scheme наследует свою блочную структуру от более ранних языков с блочной структурой, в частности от ALGOL . В Scheme блоки реализуются тремя конструкциями привязки : let, let* и letrec. Например, следующая конструкция создает блок , в котором используется символ с именем var привязан к числу 10:

(define var "goose")
;; Any reference to var here will be bound to "goose"
(let ((var 10))
  ;; statements go here. Any reference to var here will be bound to 10.
  )
;; Any reference to var here will be bound to "goose"

Блоки могут быть вложены друг в друга для создания произвольно сложных блочных структур в соответствии с потребностями программиста. Использование блочной структуризации для создания локальных привязок снижает риск конфликта пространств имен , который может возникнуть в противном случае.

Один из вариантов let, let*, позволяет привязкам ссылаться на переменные, определенные ранее в той же конструкции, таким образом:

(let* ((var1 10)
       (var2 (+ var1 12)))
  ;; But the definition of var1 could not refer to var2
  )

Другой вариант, letrec, предназначен для обеспечения взаимно рекурсивных привязки процедур друг к другу.

;; Calculation of Hofstadter's male and female sequences as a list of pairs

(define (hofstadter-male-female n)
  (letrec ((female (lambda (n)
		     (if (= n 0)
			 1
			 (- n (male (female (- n 1)))))))
	   (male (lambda (n)
		   (if (= n 0)
		       0
		       (- n (female (male (- n 1))))))))
    (let loop ((i 0))
      (if (> i n)
	  '()
	  (cons (cons (female i)
		      (male i))
		(loop (+ i 1)))))))

(hofstadter-male-female 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 широко используется для реализации итерации.

Пример: простой счетчик

(let loop ((n 1))
  (if (> n 10)
      '()
      (cons n
	    (loop (+ n 1)))))

===> (1 2 3 4 5 6 7 8 9 10)

Как и любая процедура в Scheme, процедура, созданная в именованном элементе let, является объектом первого класса.

Правильная хвостовая рекурсия

Дополнительная информация: Хвостовая рекурсия.

Схема имеет конструкцию итерации, do, но в Scheme более идиоматично использовать хвостовую рекурсию для выражения итерации . Реализации схемы, соответствующие стандарту, необходимы для оптимизации хвостовых вызовов, чтобы поддерживать неограниченное количество активных хвостовых вызовов (R5RS, раздел 3.5). — свойство, которое в отчете Scheme описывается как правильная хвостовая рекурсия , — позволяющее программистам Scheme безопасно писать итеративные алгоритмы с использованием рекурсивных структур, которые иногда более интуитивны. Хвостовые рекурсивные процедуры и именованные let form обеспечивает поддержку итерации с использованием хвостовой рекурсии.

;; Building a list of squares from 0 to 9:
;; Note: loop is simply an arbitrary symbol used as a label. Any symbol will do.

(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
        res
        (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
===> (0 1 4 9 16 25 36 49 64 81)

Первоклассные продолжения

Основная статья: Продолжение

Продолжения в Scheme являются объектами первого класса . Схема обеспечивает порядок действий call-with-current-continuation (также известный как call/cc) для захвата текущего продолжения, упаковав его как escape-процедуру, привязанную к формальному аргументу в процедуре, предоставленной программистом. (Р5РС разд. 6.4) Первоклассные продолжения позволяют программисту создавать нелокальные конструкции управления, такие как итераторы , сопрограммы и возвраты .

Продолжения можно использовать для эмуляции поведения операторов возврата в императивных языках программирования. Следующая функция find-first, данная функция func и список lst, возвращает первый элемент x в lst такой, что (func x) возвращает истину.

(define (find-first func lst)
  (call-with-current-continuation
   (lambda (return-immediately)
     (for-each (lambda (x)
		 (if (func x)
		     (return-immediately x)))
	  lst)
     #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
===> 7
(find-first zero? '(1 2 3 4))
===> #f

Следующий пример, традиционная загадка программиста, показывает, что Scheme может обрабатывать продолжения как первоклассные объекты, привязывая их к переменным и передавая их в качестве аргументов процедурам.

(let* ((yin
         ((lambda (cc) (display "@") cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display "*") cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

При выполнении этот код отображает последовательность подсчета: @*@**@***@****@*****@******@*******@********...

Общее пространство имен для процедур и переменных

В отличие от Common Lisp, все данные и процедуры в Scheme имеют общее пространство имен, тогда как в Common Lisp функции и данные имеют отдельные пространства имен, что позволяет функции и переменной иметь одно и то же имя и требует специальных обозначений для обращения к функционировать как ценность. Иногда это называют различием « Lisp-1 против Lisp-2 », имея в виду единое пространство имен Scheme и отдельные пространства имен Common Lisp.

В Scheme для привязки процедур можно использовать те же примитивы, которые используются для манипулирования и привязки данных. Не существует эквивалента Common Lisp. defun и #' примитивы.

;; Variable bound to a number:
(define f 10)
f
===> 10
;; Mutation (altering the bound value)
(set! f (+ f f 6))
f
===> 26
;; Assigning a procedure to the same variable:
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; Assigning the result of an expression to the same variable:
(set! f (f 1))
f
===> 13
;; functional programming:
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

Стандарты реализации

В этом подразделе документируются проектные решения, принятые на протяжении многих лет, которые придали Схеме особый характер, но не являются прямым результатом первоначального проекта.

Числовая башня

Основная статья: Цифровая башня

Схема определяет сравнительно полный набор числовых типов данных, включая комплексные и рациональные типы, которые известны в Scheme как числовая башня (R5RS, раздел 6.2). ). Стандарт рассматривает их как абстракции и не обязывает разработчика использовать какие-либо конкретные внутренние представления.

Числа могут обладать качеством точности. Точное число может быть получено только с помощью последовательности точных операций, включающих другие точные числа, поэтому неточность заразительна. Стандарт определяет, что любые две реализации должны давать эквивалентные результаты для всех операций, приводящих к точным числам.

Стандарт R5RS определяет процедуры exact->inexact и inexact->exact который можно использовать для изменения точности числа. inexact->exact выдает «точное число, наиболее близкое к аргументу». exact->inexact выдает «неточное число, наиболее близкое к аргументу». Стандарт R6RS исключает эти процедуры из основного отчета, но определяет их как процедуры совместимости R5RS в стандартной библиотеке (rnrs r5rs (6)).

В стандарте R5RS реализации Scheme не обязаны реализовывать всю числовую башню, но они должны реализовывать «связное подмножество, соответствующее как целям реализации, так и духу языка Scheme» (R5RS, раздел 6.2.3). Новый стандарт R6RS действительно требует реализации всей башни, а также «точных целочисленных объектов и точных объектов рационального числа практически неограниченного размера и точности, а также реализации определенных процедур... чтобы они всегда возвращали точные результаты при задании точных аргументов» (R6RS разд. 3.4, разд. 11.7.1).

Пример 1: точная арифметика в реализации, поддерживающей точные рациональные комплексные числа.

;; Sum of three rational real numbers and two rational complex numbers
(define x (+ 1/3 1/4 -1/5 -1/3i 405/50+2/3i))
x
===> 509/60+1/3i
;; Check for exactness.
(exact? x)
===> #t

Пример 2. Та же арифметика в реализации, которая не поддерживает ни одно точное значение. рациональные числа и комплексные числа, но принимает действительные числа в рациональной записи.

;; Sum of four rational real numbers
(define xr (+ 1/3 1/4 -1/5 405/50))
;; Sum of two rational real numbers
(define xi (+ -1/3 2/3))
xr
===> 8.48333333333333
xi
===> 0.333333333333333
;; Check for exactness.
(exact? xr)
===> #f
(exact? xi)
===> #f

Обе реализации соответствуют стандарту R5RS, но вторая не соответствует R6RS, поскольку не реализует полную числовую башню.

Отложенная оценка

См. также: Ленивая оценка

Схема поддерживает отложенную оценку посредством delay форма и порядок действий force.

(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(set! a 20)
(force eval-aplus2)
===> 22
(define eval-aplus50 (delay (+ a 50)))
(let ((a 8))
  (force eval-aplus50))
===> 70
(set! a 100)
(force eval-aplus2)
===> 22

Лексический контекст исходного определения обещания сохраняется, а его значение также сохраняется после первого использования force. Обещание оценивается только один раз.

Эти примитивы, которые создают или обрабатывают значения, известные как обещания , могут использоваться для реализации расширенных конструкций отложенного вычисления, таких как потоки .

В стандарте R6RS они больше не являются примитивами, а предоставляются как часть библиотеки совместимости R5RS (rnrs r5rs (6)).

В R5RS предлагается реализация delay и force дается, реализуя обещание как процедуру без аргументов (thunk ) и используя мемоизацию , чтобы гарантировать, что оно вычисляется только один раз, независимо от количества раз. force называется (Р5РС разд. 6.4).

SRFI 41 позволяет выражать как конечные, так и бесконечные последовательности с исключительной экономией. Например, это определение последовательности Фибоначчи с использованием функций, определенных в SRFI 41:

;; Define the Fibonacci sequence:
(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))
;; Compute the hundredth number in the sequence:
(stream-ref fibs 99)
===>  218922995834555169026

Порядок оценки аргументов процедуры

Большинство Лиспов определяют порядок вычисления аргументов процедуры. Схемы нет. Порядок вычисления, включая порядок, в котором оценивается выражение в позиции оператора, может выбираться реализацией для каждого вызова, и единственным ограничением является то, что «эффект любого одновременного вычисления оператора и Выражения операндов должны соответствовать некоторому последовательному порядку вычислений». (Р5РС п. 4.1.3)

(let ((ev (lambda(n) (display "Evaluating ")
                     (display (if (procedure? n) "procedure" n))
                     (newline) n)))
  ((ev +) (ev 1) (ev 2)))
===> 3

Evaluating 1
Evaluating 2
Evaluating procedure

ev — это процедура, которая описывает переданный ей аргумент, а затем возвращает значение аргумента. В отличие от других Лиспов, появление выражения в позиции оператора (первый элемент) выражения Scheme вполне законно, если результатом выражения в позиции оператора является процедура.

При вызове процедуры " + ", чтобы сложить 1 и 2, выражения (ев+), (ев 1) и (ev 2) можно оценивать в любом порядке, пока эффект не будет таким, как если бы они оценивались параллельно. Таким образом, следующие три строки могут отображаться в любом порядке стандартной схемой при выполнении приведенного выше примера кода, хотя текст одной строки не может чередоваться с другой, поскольку это нарушит ограничение последовательного вычисления.

Гигиенические макросы

Основная статья: Гигиенический макрос

В стандарте R5RS, а также в более поздних отчетах синтаксис Scheme можно легко расширить с помощью системы макросов. Стандарт R5RS представил мощную гигиеническую систему макросов, которая позволяет программисту добавлять в язык новые синтаксические конструкции, используя простой подъязык сопоставления с образцом (R5RS, раздел 4.3). До этого гигиеническая макросистема была отнесена к приложению к стандарту R4RS как система «высокого уровня» наряду с макросистемой «низкого уровня», причем обе из них рассматривались как расширение Схемы, а не как существенная часть Схемы. язык.

Реализации гигиенической макросистемы, также называемой syntax-rules, обязаны соблюдать лексическую область действия остальной части языка. Это обеспечивается специальными правилами именования и области действия для расширения макросов и позволяет избежать распространенных ошибок программирования, которые могут возникнуть в макросистемах других языков программирования. R6RS определяет более сложную систему преобразования, syntax-case, который уже некоторое время доступен как языковое расширение схемы R5RS.

;; Define a macro to implement a variant of "if" with a multi-expression
;; true branch and no false branch.
(define-syntax when
  (syntax-rules ()
    ((when pred exp exps ...)
      (if pred (begin exp exps ...)))))

Вызовы макросов и процедур очень похожи — оба являются s-выражениями, — но обрабатываются по-разному. Когда компилятор встречает в программе s-выражение, он сначала проверяет, определен ли этот символ как синтаксическое ключевое слово в текущей лексической области видимости. Если да, то он пытается расширить макрос, рассматривая элементы в хвосте s-выражения как аргументы без компиляции кода для их вычисления, и этот процесс повторяется рекурсивно до тех пор, пока не останется вызовов макроса. Если это не синтаксическое ключевое слово, компилятор компилирует код для оценки аргументов в хвосте s-выражения, а затем для вычисления переменной, представленной символом в начале s-выражения, и вызова ее как процедуры с оцененные хвостовые выражения, переданные ему в качестве аргументов.

Большинство реализаций Scheme также предоставляют дополнительные макросистемы. Среди популярных — синтаксические замыкания , макросы явного переименования и define-macro, негигиеничная макросистема, подобная defmacro система, представленная в Common Lisp .

Невозможность указать, является ли макрос гигиеничным, является одним из недостатков макросистемы. Альтернативные модели расширения, такие как наборы объемов, представляют собой потенциальное решение.

Среды и оценка

До R5RS у Scheme не было стандартного эквивалента eval процедура, которая широко распространена в других Лиспах, хотя в первой Lambda Paper описывалась evaluate как «похоже на функцию LISP EVAL» и первый пересмотренный отчет 1978 года заменил это на enclose, который принял два аргумента. Во втором, третьем и четвертом пересмотренных отчетах не было каких-либо эквивалентов eval.

Причина этой путаницы в том, что в Scheme с ее лексической областью видимости результат вычисления выражения зависит от того, где оно вычисляется. Например, неясно, должен ли результат вычисления следующего выражения быть 5 или 6:

(let ((name '+))
  (let ((+ *))
    (evaluate (list name 2 3))))

Если оно оценивается во внешней среде, где name определено, результатом является сумма операндов. Если он вычисляется во внутренней среде, где символ «+» привязан к значению процедуры «*», результатом является произведение двух операндов.

R5RS разрешает эту путаницу, определяя три процедуры, возвращающие среды, и предоставляя процедуру eval который принимает s-выражение и среду и оценивает выражение в предоставленной среде. (Р5РС разд. 6.5) R6RS расширяет это, предоставляя процедуру, называемую environment с помощью которого программист может точно указать, какие объекты импортировать в среду оценки.

В современной схеме (обычно совместимой с R5RS) для вычисления этого выражения необходимо определить функцию evaluate который может выглядеть так:

(define (evaluate expr)
   (eval expr (interaction-environment)))

interaction-environment это глобальная среда интерпретатора.

Обработка небулевых значений в логических выражениях

В большинстве диалектов Лиспа, включая Common Lisp, по соглашению значение NIL принимает значение false в логическом выражении. В Scheme, начиная со стандарта IEEE в 1991 г., все значения, кроме #f, включая NILэквивалент в Scheme, который записывается как '(), оцените значение true в логическом выражении. (Р5РС п. 6.3.1)

Где константа, представляющая логическое значение true, равна T в большинстве Лиспов, в Схеме это так #t.

Непересекаемость примитивных типов данных

В Scheme примитивные типы данных не пересекаются. Для любого объекта Scheme может быть истинным только один из следующих предикатов: boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?. (R5RS раздел 3.2)

Внутри числового типа данных, напротив, числовые значения перекрываются. Например, целочисленное значение удовлетворяет всем integer?, rational?, real?, complex? и number? предикаты одновременно. (R5RS раздел 6.2)

Предикаты эквивалентности

См. также: оператор отношения

Схема имеет три различных типа эквивалентности между произвольными объектами, обозначаемыми тремя различными предикатами эквивалентности , реляционными операторами для проверки равенства, eq?, eqv? и equal?:

• eq? оценивается как #f если только его параметры не представляют один и тот же объект данных в памяти;
• eqv? вообще то же самое, что и eq? но обрабатывает примитивные объекты (например, символы и числа) особым образом, чтобы числа, представляющие одно и то же значение, eqv? даже если они не относятся к одному и тому же объекту;
• equal? сравнивает структуры данных, такие как списки, векторы и строки, чтобы определить, имеют ли они конгруэнтную структуру и eqv? содержание.(С5РС п. 6.1)

В Scheme также существуют операции эквивалентности, зависящие от типа: string=? и string-ci=? сравнить две строки (последняя выполняет сравнение независимо от регистра); char=? и char-ci=? сравнивать персонажей; = сравнивает числа.

Комментарии

См. Также: Комментарий (компьютерное программирование)

До стандарта R5RS стандартным комментарием в Scheme была точка с запятой, что делало остальную часть строки невидимой для Scheme. Многочисленные реализации поддерживают альтернативные соглашения, позволяющие расширять комментарии более чем на одну строку, а стандарт R6RS допускает два из них: все s-выражение можно превратить в комментарий (или «закомментировать»), предварив его #; (введено в SRFI 62 ), а многострочный комментарий или «блочный комментарий» можно создать, окружив текст значками #| и |#.

Ввод/вывод

Ввод и вывод схемы основаны на типе данных порта . (R5RS раздел 6.6) R5RS определяет два порта по умолчанию, доступные с помощью процедур current-input-port и current-output-port, которые соответствуют понятиям Unix о стандартном вводе и стандартном выводе . Большинство реализаций также предоставляют current-error-port. Перенаправление ввода и стандартного вывода поддерживается в стандарте с помощью стандартных процедур, таких как with-input-from-file и with-output-to-file. Большинство реализаций предоставляют строковые порты с аналогичными возможностями перенаправления, позволяя выполнять многие обычные операции ввода-вывода над строковыми буферами вместо файлов, используя процедуры, описанные в SRFI 6. Стандарт R6RS определяет гораздо более сложные и функциональные процедуры порта, а также множество новых типов портов.

Следующие примеры написаны по строгой схеме R5RS.

Пример 1: с выходом по умолчанию (текущий-выходной порт):

(let ((hello0 (lambda() (display "Hello world") (newline))))
  (hello0))

Пример 2: Как 1, но с использованием дополнительного аргумента порта для процедур вывода.

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (hello1 (current-output-port)))

Пример 3: Как 1, но вывод перенаправляется во вновь созданный файл.

;; NB: with-output-to-file is an optional procedure in R5RS
(let ((hello0 (lambda () (display "Hello world") (newline))))
  (with-output-to-file "helloworldoutputfile" hello0))

Пример 4: Как 2, но с явным открытием файла и закрытием порта для отправки вывода в файл.

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p)))
      (output-port (open-output-file "helloworldoutputfile")))
  (hello1 output-port)
  (close-output-port output-port))

Пример 5: Как 2, но с использованием вызова с выходным файлом для отправки вывода в файл.

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (call-with-output-file "helloworldoutputfile" hello1))

Аналогичные процедуры предусмотрены для ввода. Схема R5RS предоставляет предикаты input-port? и output-port?. Для ввода и вывода символов write-char, read-char, peek-char и char-ready? предоставляются. Для записи и чтения выражений Scheme Scheme предоставляет read и write. При операции чтения возвращаемым результатом является объект конца файла, если входной порт достиг конца файла, и это можно проверить с помощью предиката eof-object?.

В стандарте SRFI 28 также определена базовая процедура форматирования, напоминающая процедуру Common Lisp. format функция, в честь которой она названа.

Переопределение стандартных процедур

В Scheme процедуры привязаны к переменным. В R5RS стандарт языка формально требовал, чтобы программы могли изменять привязки переменных встроенных процедур, фактически переопределяя их. (R5RS «Изменение языка») Например, + может быть расширен для приема строк, а также чисел, переопределив его:

(set! +
      (let ((original+ +))
        (lambda args
          (apply (if (or (null? args) (string? (car args)))
                     string-append
                     original+)
                 args))))
(+ 1 2 3)
===> 6
(+ "1" "2" "3")
===> "123"

В R6RS каждая привязка, включая стандартные, принадлежит какой-либо библиотеке, и все экспортированные привязки являются неизменяемыми. (R6RS раздел 7.1) По этой причине переопределение стандартных процедур путем мутации запрещено. Вместо этого можно импортировать другую процедуру под именем стандартной, что по сути аналогично переопределению.

Номенклатура и соглашения об именах

В стандартной схеме процедуры, преобразующие один тип данных в другой, содержат в своем имени строку символов «->», предикаты заканчиваются знаком «?», а процедуры, изменяющие значение уже выделенных данных, заканчиваются знаком «!». Программисты Scheme часто следуют этим соглашениям.

В формальных контекстах, таких как стандарты Scheme, слово «процедура» используется вместо слова «функция» для обозначения лямбда-выражения или примитивной процедуры. В обычном использовании слова «процедура» и «функция» используются как взаимозаменяемые. Применение процедуры иногда формально называют комбинацией .

Как и в других Лиспах, термин « thunk » используется в Scheme для обозначения процедуры без аргументов. Термин «правильная хвостовая рекурсия» относится к свойству всех реализаций Scheme, заключающемуся в том, что они выполняют оптимизацию хвостовых вызовов, чтобы поддерживать неопределенное количество активных хвостовых вызовов .

Форма наименований документов стандартов начиная с Р3РС, «Пересмотренная». ^н Отчет о схеме алгоритмического языка» — это ссылка на заголовок стандартного документа АЛГОЛ 60 «Пересмотренный отчет об алгоритмическом языке Алгол 60». Страница «Сводка» R3RS очень похожа на страницу «Сводка» отчета АЛГОЛ 60.

Обзор стандартных форм и процедур

Язык формально определен в стандартах R5RS (1998). и R6RS (2007). Они описывают стандартные «формы»: ключевые слова и сопровождающий их синтаксис, которые обеспечивают структуру управления языком, а также стандартные процедуры, выполняющие общие задачи.

Стандартные формы

В этой таблице описаны стандартные формы в Scheme. Некоторые формы появляются более чем в одной строке, поскольку их нелегко классифицировать как одну функцию в языке.

Формы, отмеченные буквой «L» в этой таблице, классифицируются в стандарте как производные «библиотечные» формы и часто реализуются как макросы с использованием более фундаментальных форм на практике, что значительно упрощает задачу реализации, чем в других языках.

Стандартные формы на языке R5RS Scheme

Цель	Формы
Определение	определять
Связывающие конструкции	лямбда, do (L), пусть (L), пусть* (L), letrec (L)
Условная оценка	если, условие (L), случай (L) и (L) или (L)
Последовательная оценка	начинать (*)
Итерация	лямбда, do (L), по имени let (L)
Синтаксическое расширение	определить-синтаксис, let-синтаксис, letrec-синтаксис, синтаксические правила (R5RS), синтаксический регистр (R6RS)
Цитирование	quote('), unquote(,), квазицитата(`), unquote-splicing(,@)
Назначение	набор!
Отложенная оценка	задержка (Л)

Пока begin определяется как библиотечный синтаксис в R5RS, расширитель должен знать об этом, чтобы реализовать функцию сращивания. В R6RS это больше не библиотечный синтаксис.

Стандартные процедуры

В следующих двух таблицах описаны стандартные процедуры схемы R5RS. R6RS гораздо более обширен, и краткое изложение такого типа было бы непрактично.

Некоторые процедуры появляются более чем в одной строке, поскольку их нелегко классифицировать в одной функции языка.

Стандартные процедуры на языке R5RS Scheme

Цель	Процедуры
Строительство	вектор, make-вектор, make-строка, список
Предикаты эквивалентности	eq?, eqv?, равно?, строка=?, строка-ci=?, символ=?, символ-ci=?
Преобразование типов	вектор->список, список->вектор, число->строка, строка->число, символ->строка, строка->символ, символ->целое число, целое число->символ, строка->список, список->строка
Числа	См. отдельную таблицу
Струны	строка?, make-string, строка, длина строки, ссылка на строку, набор строк!, строка=?, строка-ci=?, строка<? строка-ci<?, строка<=? строка-ci<=?, строка>? строка-ci>?, строка>=? строка-ci>=?, подстрока, добавление строки, строка->список, список->строка, копирование строки, заполнение строки!
Персонажи	char?, char=?, char-ci=?, char<? char-ci<?, char<=? char-ci<=?, char>? char-ci>?, char>=? char-ci>=?, char-алфавит?, char-цифра?, char-пробел?, char-прописной регистр?, char-нижний регистр?, char->целое число, целое число->char, char-upcase, символ в нижнем регистре
Векторы	сделать-вектор, вектор, вектор?, длина вектора, ссылка на вектор, набор векторов!, вектор->список, список->вектор, векторная заливка!
Символы	символ->строка, строка->символ, символ?
Пары и списки	пара?, минусы, автомобиль, cdr, set-car!, set-cdr!, ноль?, список?, список, длина, добавление, обратный ход, список-хвост, список-ref, memq. мемв. член, assq, assv, assoc, список->вектор, вектор->список, список->строка, строка->список
Предикаты идентичности	логическое значение?, пара?, символ?, число?, символ?, строка?, вектор?, порт?, процедура?
Продолжение	вызов с текущим продолжением (вызов/cc), значения, вызов со значениями, динамический ветер
Окружающая среда	eval, схема-отчет-среда, нулевая-среда, среда взаимодействия (необязательно)
Ввод/вывод	отображение, новая строка, чтение, запись, чтение-символ, запись-символ, просмотр-символ, готовность к символу?, eof-объект? открыть-входной-файл, открыть-выходной-файл, закрыть-входной-порт, закрыть-выходной-порт, входной-порт?, выходной-порт?, текущий-входной-порт, текущий-выходной-порт, вызов-с- входной файл, вызов с выходным файлом, с вводом из файла (необязательно), с выводом в файл (необязательно)
Системный интерфейс	загрузка (необязательно), включение транскрипта (необязательно), выключение транскрипта (необязательно)
Отложенная оценка	сила
Функциональное программирование	процедура?, применить, карта, для каждого
логические значения	логическое значение? нет

Строковые и символьные процедуры, содержащие «-ci» в своих именах, выполняют сравнение своих аргументов независимо от регистра: версии одного и того же символа в верхнем и нижнем регистре считаются равными.

Стандартные числовые процедуры на языке R5RS Scheme

Цель	Процедуры
Основные арифметические операторы	+, -, *, /, абс, частное, остаток, по модулю, НОД, НЦМ, эксп, кврт
Рациональные числа	числитель, знаменатель, рационально?, рационализировать
Приближение	пол, потолок, обрезанный, круглый
Точность	неточно->точно, точно->неточно, точно?, неточно?
Неравенства	<, <= , >, >=, =
Разные предикаты	ноль?, отрицательный?, положительный? странный? даже?
Максимум и минимум	макс, мин
Тригонометрия	грех, потому что, загар, соль, акос, раб
Экспоненты	опыт, журнал
Комплексные числа	make-прямоугольный, make-полярный, действительная часть, imag-часть, величина, угол, комплекс?
Ввод-вывод	число->строка, строка->число
Типовые предикаты	целое число?, рациональное?, вещественное?, комплексное?, число?

Реализации - и /, которые принимают более двух аргументов, определены, но оставлены необязательными в R5RS.

Запросы на реализацию схемы

Основная статья: Запросы на реализацию схемы

Из-за минимализма Scheme многие общие процедуры и синтаксические формы не определены стандартом. Чтобы сохранить небольшой размер основного языка, но облегчить стандартизацию расширений, сообщество Scheme имеет процесс «Запроса на реализацию схемы» (SRFI), с помощью которого библиотеки расширений определяются путем тщательного обсуждения предложений по расширениям. Это способствует переносимости кода. Многие из SRFI поддерживаются всеми или большинством реализаций Scheme.

К SRFI с достаточно широкой поддержкой в ​​различных реализациях относятся:

• 0: конструкция условного расширения на основе функций
• 1: список библиотеки
• 4: однородные числовые векторные типы данных
• 6: базовые строковые порты
• 8: получение, привязка к нескольким значениям
• 9: определение типов записей
• 13: библиотека струн
• 14: библиотека набора символов
• 16: синтаксис процедур переменной арности
• 17: обобщенный набор!
• 18: Поддержка многопоточности
• 19: типы и процедуры временных данных
• 25: примитивы многомерных массивов
• 26: обозначение для специализации параметров без каррирования
• 27: источники случайных битов
• 28: строки базового формата
• 29: локализация
• 30: вложенные многострочные комментарии.
• 31: специальная форма для рекурсивного вычисления.
• 37: args-fold: процессор аргументов программы.
• 39: объекты параметров
• 41: потоки
• 42: жадное понимание
• 43: векторная библиотека
• 45: примитивы для выражения итеративных ленивых алгоритмов
• 60: целые числа в виде битов
• 61: более общее условие
• 66: векторы октетов
• 67: сравнить процедуры

Реализации

Основная категория: Реализации Scheme (языка программирования)

Элегантный минималистичный дизайн сделал Scheme популярной целью для языковых дизайнеров, любителей и преподавателей, а из-за своего небольшого размера (размера типичного интерпретатора ) он также является популярным выбором для встроенных систем и сценариев . Это привело к множеству реализаций, большинство из которых настолько отличаются друг от друга, что портировать программы из одной реализации в другую довольно сложно, а небольшой размер стандартного языка означает, что написание полезной программы любой большой сложности на стандартной переносимой Scheme практически невозможно. Стандарт R6RS определяет гораздо более широкий язык в попытке сделать его более привлекательным для программистов.

Почти все реализации предоставляют традиционный цикл чтения-оценки-печати в стиле Лиспа для разработки и отладки. Многие также компилируют программы Scheme в исполняемый двоичный файл. Поддержка встраивания кода Scheme в программы, написанные на других языках, также распространена, поскольку относительная простота реализаций Scheme делает его популярным выбором для добавления возможностей сценариев в более крупные системы, разработанные на таких языках, C. как Интерпретаторы Gambit Scheme компилируют Scheme в C , Chicken и Bigloo , что значительно упрощает встраивание. Кроме того, компилятор Bigloo можно настроить для генерации байт-кода для виртуальной машины Java (JVM) и имеет экспериментальный генератор байт-кода для .NET .

Некоторые реализации поддерживают дополнительные функции. Например, Kawa и JScheme обеспечивают интеграцию с классами Java , а компиляторы Scheme to C часто упрощают использование внешних библиотек, написанных на C, вплоть до встраивания кода C в исходный код Scheme. Другим примером является Pvts, который предлагает набор визуальных инструментов, поддерживающих обучение Scheme.

Использование

Схема широко используется несколькими школы; в частности, в нескольких вводных курсах информатики используется Scheme в сочетании с учебником «Структура и интерпретация компьютерных программ» (SICP). За последние 12 лет PLT реализовала проект ProgramByDesign (ранее TeachScheme!), в рамках которого около 600 учителей средних школ и тысячи старшеклассников познакомились с элементарным программированием Scheme. Старый вводный курс программирования 6.001 Массачусетского технологического института преподавался на Scheme. Хотя курс 6.001 был заменен более современными курсами, SICP продолжает преподаваться в Массачусетском технологическом институте. Аналогичным образом, вводный курс в Калифорнийском университете в Беркли , CS 61A, до 2011 года полностью преподавался на схеме, за исключением небольших отклонений на логотип для демонстрации динамического объема. Сегодня, как и Массачусетский технологический институт, Беркли заменил учебную программу на более современную версию, которая в основном преподается на Python 3 , но текущая программа по-прежнему основана на старой учебной программе, и некоторые части занятий по-прежнему преподаются на Scheme.

Учебник «Как разрабатывать программы» Матиаса Феллейзена, который в настоящее время учится в Северо-Восточном университете, используется некоторыми высшими учебными заведениями для вводных курсов по информатике. И Северо-Восточный университет , и Вустерский политехнический институт используют Scheme исключительно для своих вводных курсов «Основы информатики» (CS2500) и «Введение в разработку программ» (CS1101) соответственно. Роуз-Халман использует Scheme в своем более продвинутом курсе «Концепции языка программирования». Основной курс Университета Брандейса «Структура и интерпретация компьютерных программ» (COSI121b) также преподается исключительно на Scheme ученым-теоретиком Гарри Мейрсоном . Вводный курс C211 Университета Индианы полностью преподается по схеме. Версия курса для самостоятельного обучения CS 61AS продолжает использовать Scheme. Вводные курсы информатики в Йельском и Гриннелл-колледже также преподаются на Scheme. Парадигмы проектирования программирования, обязательный курс для аспирантов по информатике в Северо-Восточном университете , также широко использует Scheme. Бывший вводный курс информатики в Университете Миннесоты - Города-побратимы, CSCI 1901, также использовал Scheme в качестве основного языка, за которым следовал курс, знакомивший студентов с языком Java; однако, следуя примеру Массачусетского технологического института, кафедра заменила 1901 на CSCI 1133 на базе Python, а функциональное программирование подробно рассматривается в третьем семестре курса CSCI 2041.

Схема также использовалась/использовалась для следующего:

• Язык семантики и спецификации стилей документа (DSSSL), который предоставляет метод определения SGML таблиц стилей , использует подмножество Scheme.
• Известный с открытым исходным кодом редактор растровой графики GIMP использует TinyScheme в качестве языка сценариев .
• Guile был принят проектом GNU в качестве официального языка сценариев, и эта реализация Scheme встроена в такие приложения, как GNU LilyPond и GnuCash, в качестве языка сценариев для расширений. Точно так же Guile раньше был языком сценариев для среды рабочего стола GNOME . и у GNOME все еще есть проект, который предоставляет привязки Guile к стеку библиотек. Существует проект по включению Guile в GNU Emacs , флагманскую программу GNU, заменив текущий интерпретатор Emacs Lisp .
• Elk Scheme используется Synopsys в качестве языка сценариев для своих технологических инструментов CAD (TCAD).
• Сиро Каваи, старший программист фильма Final Fantasy: The Spirits Within , использовал Scheme в качестве языка сценариев для управления движком рендеринга в реальном времени.
• Google App Inventor для Android использует Scheme, где Kawa используется для компиляции кода Scheme в байт-коды для виртуальной машины Java, работающей на устройствах Android.

См. также

• Основы языков программирования , учебник, использующий Scheme в качестве основы

Дальнейшее чтение

• Введение в схему и ее реализация ( зеркало )
• Кристофер Т. Хейнс (22 июня 1999 г.). «Опыт стандартизации языка программирования Scheme» .
• Гай Л. Стил младший , Ричард П. Гэбриел . «Эволюция Лиспа» (PDF) . Архивировано из оригинала (PDF) 11 июня 2016 г.
• Джеральд Джей Сассман и Гай Льюис Стил-младший (декабрь 1975 г.). Схема: интерпретатор расширенного лямбда-исчисления   . Том. AI Memo 349. Лаборатория искусственного интеллекта Массачусетского технологического института . CiteSeerX   10.1.1.128.80 — через Wikisource .

Внешние ссылки

• Схема в Керли
• Schemers.org предоставляет ссылки на несколько ресурсов Scheme, включая спецификации.
• Схемное программирование в Wikibooks
• Введение в схему
• Напишите себе схему за 48 часов в Wikibooks
• СМИ, связанные со схемой (языком программирования) на Викискладе?
• Схема Еженедельно
• Букмарклет, добавляющий интерактивную схему REPL на любой веб-сайт.