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

Схема

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

Схема является минималистским говором из Лиспа семейства языков программирования . Схема состоит из небольшого стандартного ядра с несколькими инструментами для расширения языка.

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

Язык Scheme стандартизирован в официальном IEEE стандарте и де - факто стандарт называется Пересмотренный ^п Отчет о языке Scheme алгоритмического (R п RS). Наиболее широко применяемый стандарт - R5RS (1998). Самый последний стандарт, R7RS, предоставляет «малую» и «большую» версии языка схемы; «маленький» языковой стандарт был ратифицирован в 2013 году. Scheme имеет разнообразную пользовательскую базу из-за его компактности и элегантности, но его минималистская философия также вызвала большое расхождение между практическими реализациями, так что Руководящий комитет Scheme назвал его «самым лучшим в мире». «непереносимый язык программирования» и « семейство диалектов», а не единый язык.

История

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

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

R6RS

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

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

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

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

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

R7RS

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

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

Отличительные черты

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

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

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

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

Основные конструктивные особенности

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

Минимализм

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

Основные формы : define, lambda, quote, if, define-syntax, let-syntax, letrec-syntax, syntax-rules, set!

Производные формы : do, let, let *, letrec, cond, case и, or, begin, named let, 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 был не сознательной целью дизайна, а скорее непреднамеренным результатом процесса проектирования. «На самом деле мы пытались построить что-то сложное и случайно обнаружили, что мы случайно разработали что-то, что соответствовало всем нашим целям, но было намного проще, чем мы планировали ... мы поняли, что лямбда-исчисление - небольшой простой формализм - может служить ядром мощного и выразительного языка программирования ».

Лексический объем

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

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

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

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

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

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

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

Структура блока

Схема унаследовала свою блочную структуру от более ранних языков с блочной структурой, особенно от ALGOL . На схеме, блоки реализуются три обязательных конструкций : 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 форма обеспечивают поддержку итерации с использованием хвостовой рекурсии.

;; 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) для захвата текущего продолжения, упаковывая его как процедуру выхода, привязанную к формальному аргументу в процедуре, предоставленной программистом. (R5RS, раздел 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 функции и данные имеют отдельные пространства имен, что позволяет функции и переменной иметь одно и то же имя и требует специальной нотации для ссылки на функция как значение. Иногда это называют различием « Лисп-1 против Лисп-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, реализующая обещание как процедура без аргументов ( преобразователь ) и использующая мемоизацию, чтобы гарантировать, что она будет вычисляться только один раз, независимо от того, сколько раз forceвызывается (R5RS раздел 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

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

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

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

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

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

Оценка 1

Оценка 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процедуры, которая повсеместно используется в других Lisp, хотя первая Lambda Paper описывалась evaluateкак «аналогичная LISP-функции EVAL», а в первом пересмотренном отчете 1978 года эта процедура была заменена на enclose, в которой использовались два аргумента. . Во втором, третьем и четвертом пересмотренных отчетах не было никаких эквивалентов eval.

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

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

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

R5RS устраняет эту путаницу, определяя три процедуры, возвращающие среды, и предоставляя процедуру, evalкоторая принимает s-выражение и среду и оценивает выражение в предоставленной среде. (R5RS раздел 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, который записывается как '(), оцениваются как истинное значение в логическом выражении. (R5RS раздел 6.3.1)

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

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

В схеме примитивные типы данных не пересекаются. Только один из следующих предикатов может быть справедливо для любого объекта схемы: 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?содержанию (R5RS, раздел 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, но с использованием call-with-output-file для отправки вывода в файл.

(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 определяет базовую процедуру форматирования, напоминающую formatфункцию Common Lisp , после чего она названа.

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

В схеме процедуры привязаны к переменным. В 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 для обозначения процедуры без аргументов. Термин «правильная хвостовая рекурсия» относится к свойству всех реализаций схемы, что они выполняют оптимизацию хвостового вызова, чтобы поддерживать неопределенное количество активных хвостовых вызовов .

Форма названий документов по стандартизации с момента R3RS, «Пересмотренный ^п Отчет о языке Scheme алгоритмической», является ссылкой на название Алгол 60 стандартного документа «Пересмотренный отчет об алгоритмическом языке Алгол 60» Сводка страницы R3RS подробно смоделирован на странице «Сводка» отчета ALGOL 60.

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

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

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

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

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

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

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

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

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

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

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

Схема запросов на реализацию

Из-за минимализма Scheme многие общие процедуры и синтаксические формы не определены стандартом. Чтобы сделать базовый язык небольшим, но упростить стандартизацию расширений, сообщество Scheme разработало процесс «Scheme Request for Implementation» (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 популярной целью для языковых дизайнеров, любителей и преподавателей, а из-за своего небольшого размера, как у типичного интерпретатора , он также является популярным выбором для встроенных систем и сценариев . Это привело к появлению множества реализаций, большинство из которых настолько отличаются друг от друга, что перенос программ из одной реализации в другую довольно затруднен, а небольшой размер стандартного языка означает, что написание полезной программы любой большой сложности в стандарте Переносная схема практически невозможна. Стандарт R6RS определяет гораздо более широкий язык в попытке сделать его более привлекательным для программистов.

Почти все реализации предоставляют традиционный цикл чтения-оценки-печати в стиле Лиспа для разработки и отладки. Многие также компилируют программы Scheme в исполняемый двоичный файл. Поддержка для встраивания Схемы коды в программах , написанных на других языках , также распространена, так как относительная простота реализации Scheme делает его популярным выбором для добавления возможности создания сценариев крупных систем , разработанных на таких языках, как C . В Гамбит , курицы и Bigloo переводчики Схема компиляции Схемы С, что делает особенно легко вложение. Кроме того, компилятор Bigloo можно настроить для генерации байт-кода JVM , а также в нем есть экспериментальный генератор байт-кода для .NET .

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

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

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

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

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

• Язык семантики и спецификации стилей документа (DSSSL), который предоставляет метод определения таблиц стилей SGML , использует подмножество схем.
• Хорошо известный редактор растровой графики с открытым исходным кодом 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.

Смотрите также

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

использованная литература

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

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

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

• Схема в Curlie
• Программирование схем в Викиучебнике
• Напишите себе схему за 48 часов в Викиучебнике
• СМИ, связанные со схемой (языком программирования) на Викискладе?
• Букмарклет, добавляющий интерактивную схему REPL на любой веб-сайт