Scheme

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

Scheme — это функциональный язык программирования, один из двух наиболее популярных в наши дни диалектов языка Лисп (другой популярный диалект — это Common Lisp). Авторы языка Scheme — Гай Стил (англ. Guy L. Steele) и Джеральд Сассмен (англ. Gerald Jay Sussman) из Массачусетского технологического института — создали его в середине 1970-х годов.

Введение

При разработке Scheme упор был сделан на элегантность и простоту языка. Философия языка подчёркнуто минималистская. Его цель — не сваливать в кучу разные полезные конструкции и средства, а напротив — удалить слабости и ограничения, вызывающие необходимость добавления в язык новых возможностей. В результате, Scheme содержит минимум примитивных конструкций и позволяет выразить все, что угодно путём надстройки над ними. В качестве примера можно указать, что язык использует 2 механизма организации циклов:

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

Scheme начинался с попытки понять модель акторов Карла Хьюитта, для чего Стил и Суссман написали «крошечный интерпретатор Лиспа», а затем «добавили механизм создания акторов и посылки сообщений». Scheme был первым диалектом Лиспа, применяющим исключительно статические (а не динамические) области видимости переменных, гарантирующим оптимизацию хвостовой рекурсии и поддерживающим данные булевского типа (#t и #f вместо традиционных T и NIL). Он также был одним из первых языков, непосредственно поддерживающих продолжения. Начиная со спецификации R^5RS, язык приобрел исключительно мощное и удобное средство для записи макросов на основе шаблонов синтаксического преобразования с «соблюдением гигиены» (англ. hygienic macro). В Scheme также реализована «сборка мусора», то есть автоматическое освобождение памяти от неиспользуемых более объектов.

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

Как курьёз, можно отметить, что первоначальное название языка Schemer было изменено на настоящее из-за ограничения на длину имён файлов в ITS.

Примеры

Простые математические операции

(+ 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)
      x
      (* (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 используется тип порт (R5RS sec 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 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?.

SRFI

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

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

• 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: процедуры сравнения

Полный список принятых SRFI доступен на http://srfi.schemers.org/final-srfis.html

Основные реализации

• GNU Guile «Официальный» язык расширений проекта GNU. Этот интерпретатор Scheme реализован как библиотека, позволяющая приложениям создавать внутренний интерпретатор Scheme.
• MIT Scheme Свободная (GPL-licensed) реализация для платформы x86 под GNU/Linux, FreeBSD, IBM OS/2, и Win32.
• Chicken Scheme Интерпретатор Scheme, поддерживающий трансляцию в C.
• Gambit Scheme
• Racket (ранее PLT Scheme)
• JScheme

Проект Armpit Scheme реализует интерпретатор для микроконтроллеров на базе архитектуры ARM.

Литература. Учебники

• Structure and Interpretation of Computer Programs (англ.)
• Видео-лекции «Structure and Interpretation of Computer Programs», Harold Abelson и Gerald Jay Sussman (англ.)
• The Scheme Programming Language, R. Kent Dybvig (англ.)

Ссылки

На русском языке

• ru_scheme — сообщество в LiveJournal, посвящённое языку Scheme

На английском языке

• A large collection of Scheme resources. Большая коллекция ресурсов по Scheme.
• Chez Scheme Бесплатный интерпретатор Scheme, платный компилятор для Microsoft Windows и нескольких UNIX systems.
• Gauche Интерпретатор Scheme
• Kawa Программа для Scheme, написанная на Java, которая компилирует тексты Scheme программ в Java bytecode. Любая Java библиотека может быть легко использована в Kawa.
• Сообщество schemewiki.org