Scheme

Scheme

Файл:Lambda lc.svg
Семантика:	функциональный
Тип исполнения:	интерпретатор или компилятор
Появился в:	1970 г.
Автор(ы):	Гай Стил и Джеральд Сассмен
Типизация данных:	строгая, динамическая
Основные реализации:	PLT Scheme, MIT Scheme, Scheme48, Guile, JScheme
Диалекты:	множество
Испытал влияние:	Lisp, ALGOL
Повлиял на:	Common Lisp

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

Введение

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

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

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

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

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

Примеры

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

<source lang="scheme"> (+ 2 (* 2 2)) (+ 1 2 3 4) </source> Вызов каждой операции (или функции) представляется списком, в котором символ операции (который, в сущности, является именем функции) всегда занимает начальную позицию.

Предикаты типа

<source lang="scheme"> (number? 5) (number? "foo") (string? "foo") </source>

По соглашению, имена всех предикатов заканчиваются символом ?.

Проверки на равенство

<source lang="scheme"> (equal? "foo" "bar") (eqv? 5 (+ 2 3)) (eq? 'a 'A) </source>

Определение макросов для традиционных операций push/pop

<source lang="scheme"> (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))))

</source>

Определение функций

<source lang="scheme">

факториал в (неэффективном) рекурсивном стиле

(define (fact x)

 (if (< x 3)
     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 '(6 8 100)) (sum (map fib '(1 2 3 4))) </source>

Определение функции должно соответствовать следующему прототипу: <source lang="scheme"> (define имя_функции (lambda (список_аргументов) (реализация_функции))), </source>

хотя на практике чаще используют сокращённую форму: <source lang="scheme"> (define (имя_функции аргументы) (реализация_функции)). </source>

Ввод / Вывод

<source lang="scheme"> (write (+ (read) (read))) </source>

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

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

Ссылки

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

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

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

• A large collection of Scheme resources. Большая коллекция ресурсов по Scheme.
• MIT/GNU Scheme Свободная (GPL-licensed) реализация для платформы x86 под GNU/Linux, FreeBSD, IBM OS/2, и Win32.
• Chez Scheme Бесплатный интерпретатор Scheme, платный компилятор для Microsoft Windows и нескольких UNIX systems.
• Chicken Интерпретатор Scheme, поддерживающий трансляцию в C.
• Gauche Интерпретатор Scheme
• Guile «Официальный» язык расширений проекта GNU. Этот интерпретатор Scheme реализован как библиотека, позволяющая приложениям создавать внутренний интерпретатор Scheme.
• The PLT Scheme suite Пакет программ для Scheme, для Windows, Mac, и Unix платформ. Включает интерпретатор (MzScheme), графические утилиты (MrEd), учебно-ориентированный графический редактор (DrScheme), и ряд других компонентов, в том числе COM и ODBC библиотеки.
• Kawa Программа для Scheme, написанная на Java, которая компилирует тексты Scheme программ в Java bytecode. Любая Java библиотека может быть легко использована в Kawa.
• Сообщество schemewiki.org