Scheme

Scheme

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

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

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

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

Первоначальное название языка — Schemer, было изменено из-за ограничения на длину имён файлов в ITS[en]; (англ. 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[en] — интерпретатор, поддерживающий трансляцию в Си. JScheme — интерпретатор, написанный на Java; Kawa — компилятор Scheme в байт-код JVM. Компилятор Chez Scheme длительное время поставлялся как коммерческий продукт, с 2016 года стал свободно распространяемым (Apache).

Всего существует большое количество реализаций языка для разных платформ, в частности, есть интерпретатор Armpit Scheme для микроконтроллеров на базе архитектуры ARM[4].

ПримечанияПравить

  1. 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.
  2. William D Clinger.SRFI 6: Basic String Ports. The SRFI Editors, schemers.org (1 июля 1999). Дата обращения: 9 августа 2012.Архивировано 21 октября 2021 года.
  3. Scheme Systems Supporting SRFIs. The SRFI Editors, schemers.org (30 августа 2009). Дата обращения: 9 августа 2012.Архивировано 20 июня 2021 года.
  4. A Scheme Interpreter for ARM Microcontrollers. Дата обращения: 30 декабря 2014.Архивировано 30 декабря 2014 года.

ЛитератураПравить

СсылкиПравить

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