Scheme

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:11, 8 июня 2016.
Scheme
100px
Спроектировано Гай Стил и Джеральд Сассмен
Печать дисциплины строгая, динамическая
Главная реализация
PLT Scheme, MIT Scheme, Scheme48, Guile, JScheme
Под влиянием
Lisp, ALGOL
Влияние
Common Lisp, JavaScript, R, Ruby, Dylan, Lua, Racket

Обзор

Scheme (произносится skiːm) и Common Lisp являются двумя основными диалектами языка Lisp. В отличие от Common Lisp, Scheme следует минималистский философии разработки, которая определяет небольшое стандартное ядро и мощные инструменты для расширения языка. Язык Scheme стандартизирован IEEE под названием Revisedn Report on the Algorithmic Language Scheme (RnRS). Наиболее широко применяется стандарт R5RS (1998); новый стандарт, R6RS, был ратифицирован в 2007 году. Scheme имеет обширную базу пользователей из-за своей компактности и элегантности, но его минималистская философия вызвала обсуждения между практическими реализациями, так, что Scheme Steering Committee называет его "самым непереносимым языком программирования в мире" и чаще как" семейством диалектов ", а не одним языком.

Отличительные особенности

Scheme, прежде всего, функциональный язык программирования. Он имеет много общего с другими членами семьи Lisp. Очень простой синтаксис Scheme основан на s-выражений. Программы Scheme, таким образом, состоят из последовательностей вложенных списков. Списки также основная структура данных в Scheme, что приводит к эквивалентности между исходным кодом и используемыми данными. Программы Scheme могут легко создавать и оценивать куски кода на Scheme. Зависимость от списков, как структуры данных, является общим для всех диалектов Lisp. Scheme наследует богатый набор функций обработки, таких как cons, car и cdr.

Минимализм

Scheme очень простой язык, гораздо более простой для реализации, чем многие другии языки, сравнимые по мощности. Эта простота объясняется возможностью использования лямбда-исчисления для получения большей части синтаксиса языка из более примитивных форм. Например из 23 S-выражений, на основе синтаксических конструкций, определенных в стандарте R5RS Scheme, 11 классифицируются как полученные, которые могут быть записаны в виде макросов, связанных с более фундаментальными формами. Основные формы: define, lambda, if, quote, unquote, unquote-splicing, quasiquote, define-syntax, let-syntax, letrec-syntax, syntax-rules, set! Библиотечные формы: do, let, let*, letrec, cond, case, and, or, begin, named let, delay Пример: макрос для реализации let как выражение с использованием лямбда выражения

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))

Лексическая область видимости

Как и большинство современных языков программирования Scheme лексически ограничен: все возможные привязки переменных в программном модуле могут быть проанализированы исходя из текста программного модуля. Это контрастирует с динамическим обзором, характерным для ранних диалектов Lisp.

Лямбда исчисления

Блочная структура

Scheme наследует блочную структуру от ранних блочно-структурированных языков, в частности ALGOL. В Scheme, блоки реализованы при помощи трех связывающих конструкций: let, let* and letrec. Например, следующая конструкция создает блок, в котором символ с именем var привязывается к значению 10:

(define var "goose")
;; Any reference to var here will be bound to "goose"
(let ((var 10))
  ;; statements go here.  Any reference to var here will be bound to 10.
  )
;; Any reference to var here will be bound to "goose"

Блоки могут быть вложенными, чтобы создать сколь угодно сложные блочные структуры. Применение блочного структурирования для создания локальных привязок облегчает риск возникновения проблем с пространствами имен.

Один из вариантов let, let*, позволяет ссылаться на переменные, определенные в этом же блоке

(let* ((var1 10)
       (var2 (+ var1 12)))
  ;; But the definition of var1 could not refer to var2
  )

Хвостовая рекурсия

В Scheme существует итерационная конструкция, do, но более идиоматически - использовать хвостовую рекурсию для реализации итераций. Стандартизированные реализации Scheme должны оптимизировать хвостовые вызовы так, чтобы поддерживать неограниченное их число.

;; Building a list of squares from 0 to 9:
;; Note: loop is simply an arbitrary symbol used as a label. Any symbol will do.

(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
        res
        (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
=== > (0 1 4 9 16 25 36 49 64 81)

Продолжения

Продолжения в Scheme являются объектами первого класса. Scheme предоставляет функцию call-with-current-continuation (call/cc) для реализации. Продолжения первого класса позволяют программисту создать нелокальные конструкции управления, такие как итераторы, со-рутины, и механизм отката.

Продолжение может быть использовано для эмуляции поведения return выражений в императивных языках программирования. Функция find-first, данная функция func и список lst, возвращает элемент x в lst так же как (func x) возвращает true.

(define (find-first func lst)
  (call-with-current-continuation
   (lambda (return-immediately)
     (for-each (lambda (x)
		 (if (func x)
		     (return-immediately x)))
	       lst)
     #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
=== > 7
(find-first zero? '(1 2 3 4))
=== > #f

Общее пространство имен для процедур и переменных

;; Variable bound to a number:
(define f 10)
f
=== > 10
;; Mutation (altering the bound value)
(set! f (+ f f 6))
f
=== > 26
;; Assigning a procedure to the same variable:
(set! f (lambda (n) (+ n 12)))
(f 6)
=== > 18
;; Assigning the result of an expression to the same variable:
(set! f (f 1))
f
=== > 13
;; functional programming:
(apply + '(1 2 3 4 5 6))
=== > 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
=== > (101 102 103)

Обзор стандартных форм и процедур

Язык формально определяется в R5RS (1998) и R6RS (2007) стандартах. Они описывают стандартные "формы": ключевые слова и сопроводительный синтаксис, которые обеспечивают структуру управления на языке, а так же стандартные процедуры общего назначения.

Стандартные формы

Эта таблица описывает стандартные формы в Scheme. Некоторые формы появляются в более чем одной строке, так как они не могут быть легко разделены. Пометка "L" означает, что эта форма является "библиотечной", и как правило реализована при помощи макросов.

Стандартные формы в R5RS Scheme
Назначение Формы
Определение define
Конструкции привязки lambda, do (L), let (L), let* (L), letrec (L)
Условные вычисления if, cond (L), case (L), and (L), or (L)
Последовательные вычисления begin (*)
Итерации lambda, do (L), named let (L)
Расширения синтаксиса define-syntax, let-syntax, letrec-syntax, syntax-rules (R5RS), syntax-case (R6RS)
Квотирование quote('), unquote(,), quasiquote(`), unquote-splicing(,@)
Присвоение set!
Отложенные вычисления delay (L)

Обратите внимание, что begin определен как библиотечный в R5RS, в R6RS это уже не так.

Стандартные процедуры

Стандартные процедуры в R5RS Scheme
Назначение Процедуры
Конструкции vector, make-vector, make-string, list
Предикаты эквивалентности eq?, eqv?, equal?, string=?, string-ci=?, char=?, char-ci=?
Преобразование типов vector->list, list->vector, number->string, string->number, symbol->string, string->symbol, char->integer, integer->char, string->list, list->string
Числа См. след. таблицу
Строки string?, make-string, string, string-length, string-ref, string-set!, string=?, string-ci=?, string<? string-ci<?, string<=? string-ci<=?, string>? string-ci>?, string>=? string-ci>=?, substring, string-append, string->list, list->string, string-copy, string-fill!
Символы char?, char=?, char-ci=?, char<? char-ci<?, char<=? char-ci<=?, char>? char-ci>?, char>=? char-ci>=?, char-alphabetic?, char-numeric?, char-whitespace?, char-upper-case?, char-lower-case?, char->integer, integer->char, char-upcase, char-downcase
Векторы make-vector, vector, vector?, vector-length, vector-ref, vector-set!, vector->list, list->vector, vector-fill!
Symbols symbol->string, string->symbol, symbol?
Пары и списки pair?, cons, car, cdr, set-car!, set-cdr!, null?, list?, list, length, append, reverse, list-tail, list-ref, memq. memv. member, assq, assv, assoc, list->vector, vector->list, list->string, string->list
Предикаты идентичности boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?
Продолжения call-with-current-continuation (call/cc), values, call-with-values, dynamic-wind
Окружения eval, scheme-report-environment, null-environment, interaction-environment (optional)
Ввод\вывод display, newline, read, write, read-char, write-char, peek-char, char-ready?, eof-object? open-input-file, open-output-file, close-input-port, close-output-port, input-port?, output-port?, current-input-port, current-output-port, call-with-input-file, call-with-output-file, with-input-from-file(optional), with-output-to-file(optional)
Системный интерфейс load (optional), transcript-on (optional), transcript-off (optional)
Отложенные вычисления force
Функциональное программирование procedure?, apply, map, for-each
Булевы переменные boolean? not
Стандартные процедуры для работы с числами в R5RS Scheme
Цель Процедура
Базовые арифметические операторы +, -, *, /, abs, quotient, remainder, modulo, gcd, lcm, expt, sqrt
Вещественные числа numerator, denominator, rational?, rationalize
Приближения floor, ceiling, truncate, round
Точность inexact->exact, exact->inexact, exact?, inexact?
Неравенства <, <= , >, >=, =
Различные предикаты zero?, negative?, positive? odd? even?
Максимум и минимум max, min
Тригонометрия sin, cos, tan, asin, acos, atan
Экспоненты exp, log
Комплексные числа make-rectangular, make-polar, real-part, imag-part, magnitude, angle, complex?
Ввод\вывод number->string, string->number
Предикаты типа integer?, rational?, real?, complex?, number?

Ссылки