Scheme
Семантика	функциональный
Класс языка	язык программирования, мультипарадигмальный, язык функционального программирования, процедурный язык программирования и язык метапрограммирования[вд]
Тип исполнения	интерпретатор или компилятор
Появился в	1975
Автор	Гай Стил и Джеральд Сассмен
Расширение файлов	.scm, .ss
Выпуск	R7RS-small (2013)[1]
Система типов	строгая, динамическая
Основные реализации	PLT Scheme, MIT Scheme, Scheme48, Guile, JScheme
Диалекты	T[англ.]
Испытал влияние	Lisp, ALGOL
Повлиял на	Common Lisp, JavaScript, R, Ruby, Dylan, Lua, Hop[англ.], Racket
Сайт	scheme-reports.org (англ.)
Медиафайлы на Викискладе

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 (* 2 2))
> 6
(+ 1 2 3 4)
> 10

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

Предикаты типа:

(number? 5)
(number? "foo")
(string? "foo")

По соглашению, имена всех предикатов заканчиваются символом ?.

Проверки на равенство:

(equal? "foo" "bar")
(eqv? 5 (+ 2 3))
(eq? 'a 'A)

Определение макросов для традиционных операций push и pop:

(define-syntax push!
  (syntax-rules ()
    ((push! x l)
     (set! l (cons x l)))))

(define-syntax pop!
  (syntax-rules ()
    ((pop! l)
     (let ((x (car l)))
       (set! l (cdr l))
       x))))

Определение функций:

;; факториал в (неэффективном) рекурсивном стиле
(define (fact x)
  (if (< x 2)
      1
      (* (fact (- x 1)) x)))

;; функция Фибоначчи — требует параллельной рекурсии
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

;; сумма элементов списка в характерном для Scheme стиле
;; (вспомогательная функция loop выражает цикл с помощью
;; хвостовой рекурсии и переменной-аккумулятора)
(define (sum-list x)
  (let loop ((x x) (n 0))
    (if (null? x)
        n
        (loop (cdr x) (+ (car x) n)))))

(fact 14)
(fib 10)
(sum-list '(6 8 100))
(sum-list (map fib '(1 2 3 4)))

Определение функции должно соответствовать следующему прототипу:

(define имя-функции (lambda (аргументы) (реализация-функции)))

хотя на практике чаще используют сокращённую форму:

(define (имя-функции аргументы) (реализация-функции))

Для ввода и вывода в Scheme используется тип «порт» (port, R5RS sec 6.6)^[2]. R5RS определяет два стандартных порта, доступные как current-input-port и current-output-port, отвечающие стандартным потокам ввода-вывода Unix. Большинство реализаций также предоставляют current-error-port. Перенаправление ввода-вывода поддерживается в стандарте с помощью процедур with-input-from-file и with-output-to-file. У реализаций также имеются строковые порты, с помощью которых многие операции ввода-вывода могут выполняться со строковым буфером вместо файла, используя процедуры из SRFI 6^[3]. Стандарт 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")))
  (hello1 output-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?.

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

Достаточно широко поддерживаются реализациями следующие SRFI^[4]:

• 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^[5].

• 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

Лисп
Характеристики	M-выражения (уст.) REPL Self-hosting compiler S-выражения Автоматическое управление памятью Ветвления Деревья (структуры данных) Динамическая типизация Рекурсия Связные списки Функции высшего порядка Объектные системы systems Common Lisp Object System (CLOS) CommonLoops Flavors
Реализации	Стандарты Common Lisp Allegro Common Lisp Armed Bear Common Lisp (ABCL) CLISP Clozure CL CMU Common Lisp (CMUCL) Corman Common Lisp Embeddable Common Lisp (ECL) GNU Common Lisp (GCL) LispWorks Macintosh Common Lisp Mocl Movitz Poplog Steel Bank Common Lisp (SBCL) Symbolics Common Lisp Scheme История Bigloo Chez Scheme Chicken Gambit Ikarus JScheme Kawa Larceny MIT/GNU Scheme Pocket Scheme Racket RScheme Scheme 48 SCM SIOD T TinyScheme ISLISP OpenLisp Нестандартные Лого NetLogo StarLogo UCBLogo Apple Dylan Arc AutoLISP BBN LISP Clojure Dylan Emacs Lisp EuLisp Franz Lisp, PC-LISP Game Oriented Assembly Lisp (GOAL) Hy Interlisp Knowledge Engineering Environment *Lisp LeLisp LFE Lisp Machine Lisp Maclisp MDL MLisp newLISP NIL PC-LISP PicoLisp Portable Standard Lisp RPL S-1 Lisp SKILL Spice Lisp Zetalisp Операционная система Common Lisp Interface Manager, McCLIM Genera Scsh
Аппаратное обеспечение	Лисп-машины TI Explorer
Сообщество	Стандарты Scheme Requests for Implementation Common Lisp HyperSpec X3J13 Образование Книги Common Lisp the Language How to Design Programs (HTDP) On Lisp Куррикулум ProgramByDesign Разработчики Apple Computer Bolt, Beranek and Newman Harlequin Lucid Inc. MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) Stanford Artificial Intelligence Laboratory Symbolics Xanalys Калифорнийский университет в Беркли Массачусетский технологический институт (MIT) Люди Edmund Berkeley Daniel G. Bobrow William Clinger R. Kent Dybvig Matthias Felleisen Wally Feurzeig Robert Bruce Findler Matthew Flatt Phyllis Fox Richard P. Gabriel Richard Greenblatt Timothy P. Hart Louis Hodes Shriram Krishnamurthi Mike Levin David Luckham David A. Moon David Park Kent Pitman Steve Russell Cynthia Solomon Guy L. Steele, Jr. Gerald Jay Sussman Julie Sussman Daniel Weinreb Гарольд Абельсон Пол Грэм Джон Маккарти Роберт Тэппэн Моррис Сеймур Пейперт Ричард Столлман Скотт Фалман
Категория Категория Список