Scheme

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Scheme
Lambda lc.svg
Семантика:

функциональный

Класс языка:

язык программирования

Тип исполнения:

интерпретатор или компилятор

Появился в:

1975

Автор:

Гай Стил и Джеральд Сассмен

Расширение файлов:

.scm, .ss

Выпуск:

R7RS

Система типов:

строгая, динамическая

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

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). Авторы языка 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[en].

Примеры[править | править вики-текст]

Простые математические операции[править | править вики-текст]

(+ 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)[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")))
  (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:[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: процедуры сравнения

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

Основные реализации[править | править вики-текст]

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

Литература. Учебники[править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Richard Kelsey (August 1998). «Revised5 Report on the Algorithmic Language Scheme». Higher-Order and Symbolic Computation 11 (1): 7–105. DOI:10.1023/A:1010051815785. Проверено 2012-08-09.
  2. William D Clinger. SRFI 6: Basic String Ports. The SRFI Editors, schemers.org (1 июля 1999). Проверено 9 августа 2012.
  3. Scheme Systems Supporting SRFIs. The SRFI Editors, schemers.org (30 августа 2009). Проверено 9 августа 2012.
  4. A Scheme Interpreter for ARM Microcontrollers

Ссылки[править | править вики-текст]

На русском языке
  • ЖЖ-сообществоru_scheme — сообщество в LiveJournal, посвящённое языку Scheme
На английском языке
  • A large collection of Scheme resources. Большая коллекция ресурсов по Scheme.
  • Gauche Интерпретатор Scheme
  • Kawa Программа для Scheme, написанная на Java, которая компилирует тексты Scheme программ в Java bytecode. Любая Java библиотека может быть легко использована в Kawa.
  • Сообщество schemewiki.org