Scheme [skiːm] — функциональный язык программирования, один из трёх наиболее популярных диалектов Лиспа (наряду с Common Lisp и Clojure). Создан в середине 1970-х годов исследователями Массачусетского технологического институтаГаем Стилом (англ. Guy L. Steele) и Джеральдом Сассменом (англ. Gerald Jay Sussman).
Обладает минималистичным дизайном, содержит минимум примитивных конструкций и позволяет выразить всё необходимое путём надстройки над ними. Например, использует всего два механизма организации циклов — хвостовую рекурсию и итеративный подход (в котором используются временные переменные для сохранения промежуточного результата).
Язык начинался с попытки реализовать модель акторов Карла Хьюитта, для чего Стил и Сассман написали «крошечный интерпретатор Лиспа», а затем «добавили механизм создания акторов и посылки сообщений». Scheme стал первым диалектом Лиспа, применяющим исключительно статические (а не динамические) области видимости переменных, что гарантировало оптимизацию хвостовой рекурсии и обеспечило поддержку булевского типа (#t
и #f
вместо традиционных T
и NIL
). Также стал одним из первых языков с поддержкой продолжений. Начиная со спецификации R⁵RS, язык приобрёл средство для записи макросов на основе шаблонов синтаксического преобразования с «соблюдением гигиены» (англ. hygienic macro). Предусматривается «сборка мусора» (автоматическое освобождение памяти от неиспользуемых более объектов).
В качестве базовых структур данных язык использует списки и одномерные массивы («векторы»). В соответствии с декларируемым минимализмом, (пока) нет стандартного синтаксиса для поддержки структур с именованными полями, а также средств ООП — все это может быть реализовано программистом по его предпочтению, хотя большинство реализаций языка предлагают готовые механизмы.
Первоначальное название языка — Schemer, было изменено из-за ограничения на длину имён файлов в ITS ; (англ. schemer — «авантюрист», «комбинатор»; видимо, намёк на другие лиспообразные языки, вышедшие из MIT — Planner (в одном из значений — «прожектёр») и Conniver («потворщик»)). Значительный вклад в популяризацию языка внесла книга Абельсона и Сассмана «Структура и интерпретация компьютерных программ», длительное время использовавшаяся как базовый учебник программирования в Массачуссетском технологическом институте.
ПримерыПравить
Простые математические операции:
(+ 2(* 22))>6(+ 1234)>10
Вызов каждой операции (или функции) представляется списком, в котором символ операции (который, в сущности, является именем функции) всегда занимает начальную позицию.
Предикаты типа:
(number? 5)(number? "foo")(string? "foo")
По соглашению, имена всех предикатов заканчиваются символом ?
.
Проверки на равенство:
(equal? "foo""bar")(eqv? 5(+ 23))(eq? 'a'A)
Определение макросов для традиционных операций push и pop:
(define-syntax push!(syntax-rules ()((push!xl)(set! l(cons xl)))))(define-syntax pop!(syntax-rules ()((pop!l)(let ((x(car l)))(set! l(cdr l))x))))
Определение функций:
;; факториал в (неэффективном) рекурсивном стиле(define (factx)(if (< x2)1(* (fact(- x1))x)));; функция Фибоначчи — требует параллельной рекурсии(define (fibn)(cond ((= n0)0)((= n1)1)(else (+ (fib(- n1))(fib(- n2))))));; сумма элементов списка в характерном для Scheme стиле;; (вспомогательная функция loop выражает цикл с помощью;; хвостовой рекурсии и переменной-аккумулятора)(define (sum-listx)(let loop((xx)(n0))(if (null? x)n(loop(cdr x)(+ (car x)n)))))(fact14)(fib10)(sum-list'(68100))(sum-list(map fib'(1234)))
Определение функции должно соответствовать следующему прототипу:
(define имя-функции(lambda (аргументы)(реализация-функции)))
хотя на практике чаще используют сокращённую форму:
(define (имя-функцииаргументы)(реализация-функции))
Ввод-выводПравить
Для ввода и вывода в Scheme используется тип «порт» (port
, R5RS sec 6.6)[1]. R5RS определяет два стандартных порта, доступные как current-input-port
и current-output-port
, отвечающие стандартным потокам ввода-вывода Unix. Большинство реализаций также предоставляют current-error-port
. Перенаправление ввода-вывода поддерживается в стандарте с помощью процедур with-input-from-file
и with-output-to-file
. У реализаций также имеются строковые порты, с помощью которых многие операции ввода-вывода могут выполняться со строковым буфером вместо файла, используя процедуры из SRFI 6[2]. Стандарт R6RS определяет более сложные процедуры для работы с портами и много новых типов портов.
Следующие примеры написаны на R5RS Scheme.
(write (+ (read)(read)))
Вывод в порт по умолчанию (current-output-port):
(let ((hello0(lambda()(display "Hello world")(newline))))(hello0))
Передача порта в качестве аргумента:
(let ((hello1(lambda (p)(display "Hello world"p)(newline p))))(hello1(current-output-port)))
Перенаправление вывода в файл:
(let ((hello0(lambda ()(display "Hello world")(newline))))(with-output-to-file "outputfile"hello0))
Явное открытие файла и закрытие порта:
(let ((hello1(lambda (p)(display "Hello world"p)(newline p)))(output-port(open-output-file "outputfile")))(hello1output-port)(close-output-port output-port))
call-with-output-file:
(let ((hello1(lambda (p)(display "Hello world"p)(newline p))))(call-with-output-file "outputfile"hello1))
Подобные процедуры есть и для ввода. R5RS Scheme предоставляет предикаты input-port?
и output-port?
. Для символьного ввода и вывода существуют write-char
, read-char
, peek-char
и char-ready?
. Для чтения и записи выражений Scheme используются процедуры read
и write
. Если порт достиг конца файла при операции чтения, возвращается eof-объект, который может быть распознан предикатом eof-object?
.
SRFIПравить
Из-за минимализма языка многие общие процедуры и синтаксические формы не определены в стандарте. Для того, чтобы сохранить ядро языка малым и способствовать стандартизации расширений, в сообществе Scheme принят процесс «Scheme Request for Implementation» (запрос на реализацию), с помощью которого предлагаемые расширения проходят тщательное обсуждение. Это способствует переносимости кода. Многие SRFI поддерживаются всеми или большинством реализаций Scheme.
Достаточно широко поддерживаются реализациями следующие SRFI[3]:
- 0: проверка наличия расширений с помощью
cond-expand
- 1: библиотека для списков
- 4: гомогенные числовые векторы
- 6: строковые порты
- 8:
receive
: привязка к нескольким значениям - 9: record типы
- 13: библиотека для строк
- 14: библиотека наборов символов
- 16: синтаксис для процедур переменной арности
- 17: обобщенный
set!
- 18: поддержка многопоточности
- 19: типы данных и процедуры работы со временем
- 25: многомерные массивы
- 26: нотация для фиксации аргументов процедуры без каррирования
- 27: источники случайных битов
- 28: базовое форматирование строк
- 29: локализация
- 30: вложенные многострочные комментарии
- 31: специальная форма рекурсивного выполнения
- 37:
args-fold
: процессор аргументов программы - 39: parameter objects
- 41: потоки данных
- 42: eager comprehensions
- 43: библиотека векторов
- 45: примитивы для выражения ленивых итерационных алгоритмов
- 60: битовые операции
- 61: более общий
cond
- 66: векторы октетов
- 67: процедуры сравнения
Основные реализацииПравить
GNU Guile — язык расширений проекта GNU — интерпретатор Scheme, реализованный как библиотека, позволяющая приложениям создавать внутренний интерпретатор Scheme.
Язык Racket изначально являлся реализацией Scheme (первое наименование — PLT Scheme).
MIT Scheme — свободная (GPL) реализация для платформы x86 под Linux, FreeBSD, IBM OS/2, и Win32. Chicken Scheme — интерпретатор, поддерживающий трансляцию в Си. JScheme — интерпретатор, написанный на Java; Kawa — компилятор Scheme в байт-код JVM. Компилятор Chez Scheme длительное время поставлялся как коммерческий продукт, с 2016 года стал свободно распространяемым (Apache).
Всего существует большое количество реализаций языка для разных платформ, в частности, есть интерпретатор Armpit Scheme для микроконтроллеров на базе архитектуры ARM[4].
ПримечанияПравить
- ↑Richard Kelsey; William Clinger; Jonathan Rees; Rozas, G.J.; Adams Iv, N.I.; Friedman, D.P.; Kohlbecker, E.; Steele Jr., G.L.; Bartley, D.H.Revised5 Report on the Algorithmic Language Scheme (англ.) // Higher-Order and Symbolic Computation : journal. — 1998. — August (vol. 11, no. 1). — P. 7—105. — doi:10.1023/A:1010051815785.
- ↑William D Clinger.SRFI 6: Basic String Ports . The SRFI Editors, schemers.org (1 июля 1999). Дата обращения: 9 августа 2012.Архивировано 21 октября 2021 года.
- ↑Scheme Systems Supporting SRFIs . The SRFI Editors, schemers.org (30 августа 2009). Дата обращения: 9 августа 2012.Архивировано 20 июня 2021 года.
- ↑A Scheme Interpreter for ARM Microcontrollers . Дата обращения: 30 декабря 2014.Архивировано 30 декабря 2014 года.
ЛитератураПравить
- Structure and Interpretation of Computer Programs (англ.)
- Видео-лекции «Structure and Interpretation of Computer Programs», Harold Abelson и Gerald Jay Sussman (англ.)
- The Scheme Programming Language, R. Kent Dybvig (англ.)
- Учебник HtDP (How to Design Programs, Second Edition)
СсылкиПравить
- A large collection of Scheme resources. Большая коллекция ресурсов по Scheme.
- Сообщество schemewiki.org