Scheme [] — функциональный язык программирования, один из трёх наиболее популярных диалектов Лиспа (наряду с Common Lisp и Clojure). Создан в середине 1970-х годов исследователями Массачусетского технологического института и Джеральдом Сассманом.
Обладает минималистичным дизайном, содержит минимум примитивных конструкций и позволяет выразить всё необходимое путём надстройки над ними. Например, использует всего два механизма организации циклов — хвостовую рекурсию и итеративный подход (в котором используются временные переменные для сохранения промежуточного результата).
Язык начинался с попытки реализовать модель акторов Карла Хьюитта, для чего Стил и Сассман написали «крошечный интерпретатор Лиспа», а затем «добавили механизм создания акторов и посылки сообщений». Scheme стал первым диалектом Лиспа, применяющим исключительно статические (а не динамические) области видимости переменных, что гарантировало оптимизацию хвостовой рекурсии и обеспечило поддержку булевского типа (#t и #f вместо традиционных T и NIL). Также стал одним из первых языков с поддержкой продолжений. Начиная со спецификации R⁵RS, язык приобрёл средство для записи макросов на основе шаблонов синтаксического преобразования с «соблюдением гигиены» (). Предусматривается «сборка мусора» (автоматическое освобождение памяти от неиспользуемых более объектов).
В качестве базовых структур данных язык использует списки и одномерные массивы («векторы»). В соответствии с декларируемым минимализмом, (пока) нет стандартного синтаксиса для поддержки структур с именованными полями, а также средств ООП — все это может быть реализовано программистом по его предпочтению, хотя большинство реализаций языка предлагают готовые механизмы.
Первоначальное название языка — 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). 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 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: процедуры сравнения
Основные реализации GNU Guile — язык расширений проекта GNU — интерпретатор Scheme, реализованный как библиотека, позволяющая приложениям создавать внутренний интерпретатор Scheme.
Язык Racket изначально являлся реализацией Scheme (первое наименование — PLT Scheme).
MIT Scheme — свободная (GPL) реализация для платформы x86 под Linux, FreeBSD, IBM OS/2, и Win32.
— интерпретатор, поддерживающий трансляцию в Си.
JScheme — интерпретатор, написанный на Java;
Kawa — компилятор Scheme в байт-код JVM.
Компилятор Chez Scheme длительное время поставлялся как коммерческий продукт, с 2016 года стал свободно распространяемым (Apache).
Всего существует большое количество реализаций языка для разных платформ, в частности, есть интерпретатор 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 Учебник HtDP (How to Design Programs, Second Edition)
Ссылки
A large collection of Scheme resources. Большая коллекция ресурсов по Scheme. Сообщество schemewiki.org
Категория:Языки программирования семейства Лиспа Категория:Языки программирования для образования Категория:Языки программирования с автоматическим управлением памятью *