Scheme (язык программирования). Поддержка языка Scheme

Кен Дики (перевод Алексея Десятника)

Альтернативный взгляд на мир

Каждый язык программирования представляет собой определенное мировоззрение в понятиях, которые он позволяет (или не позволяет) использовать. Эта серия статей описывает взгляд на мир языка программирования Схема («Схематичное мировоззрение»). Данное мировоззрение содержит множество современных элементов программирования: поддержка различных парадигм программирования, легко сочетаемые, многократно используемые абстракции, возможность создания языка, «заточенного» под определенное применение, четкое различие между переносимыми и непереносимыми частями программы, масштабируемость, начиная от отдельных утилит и заканчивая серьезнейшими программными системами.

Схема начиналась как эксперимент в разработке языка программирования для тестирования некоторых фундаментальных положений в теории разработки программ. Сейчас же она получает расположение со стороны многих известных университетов (таких, как МТИ – Массачусетский Технический Институт) в качестве первого изучаемого языка программирования. Кроме того, Схема используется в промышленности такими компаниями, как DEC , Texas Instruments , Tektronix , Hewlett Packard и Sun .

Что такое Схема?

Схема – это маленький, исключительно «чистый» язык, который (что очень важно!) приятно использовать. Схема разрабатывалась таким образом, чтобы малое число универсальных конструкций можно было легко использовать в разных стилях программирования: функциональном, объектно-ориентированном и императивном. Стандарт языка занимает всего около 50 (!) страниц, включая формальное определение семантики. Схема основывается на формальной модели лямбда-вычислений, так что здесь полно особенностей, удобных для теоретиков; это позволяет достаточно легко построить умные средства разработки программ.

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

На что же похожа Схема? Ну, она сильно смахивает на Лисп. Пусть это вас не пугает: внешний вид Схемы можно изменить (и этим мы займемся в будущем). Что действительно важно, так это те концепции, которые положены в основу Схемы, и возможности их использовать. Итак, давайте сравним Схему и какой-нибудь «классический» язык программирования – скажем, Си. Возможно, вы уже знаете, что Схема использует префиксную запись, в отличие от инфиксной записи Си:

В Схеме все типы данных эквивалентны. Все, что можно сделать с одним типом данных, можно сделать со всеми остальными. Это резко отличается от большинства языков программирования, в которых есть специальные операции для некоторых типов данных, а применение некоторых других типов данных специально ограничено. В большинстве языков, например, числа имеют особые права: они могут быть использованы без присваивания им имен (вообразите, что, например, что в Бейсике каждому число надо было бы назначать имя перед его использованием!). Функции, наоборот, ограничены: они обязаны иметь имя.

В Схеме, функции без имени создаются с помощью ключевого слова lambda :

(lambd a (x) (* x x)); результат – функция!

(define sq (lambda (x) (* x x))

(sq 9) ; 27

((lambda (x) (* x x)) 9) ; 27

((if (foo? x) * +) 2 3 4) ; если (foo? x) истинно ,

; то (* 2 3 4) ,

; иначе (+ 2 3 4)

(define (curried-add x) (lambda (y) (+ x y))

(define add3 (curried-add 3)) ; add3 - функция

(add3 7) ; 10

((curried-add 3) 7) ; 10

Основные моменты:

Переменная может содержать значение любого типа;

Имена обозначают значения; имена не обязательны;

Выражение – одна или несколько форм между скобками;

Для того, чтобы вычислить выражение, надо сначала вычислить значения всех форм между скобками, а затем применить значение первой формы ко всем остальным; вложенные выражения также считаются формами;

Комментарий начинается символом «точка с запятой» (;) и продолжается до конца строки;

Когда функция вычисляется, она «вспоминает» состояние «окружающей среды», в которой она создавалась (так что add 3 вспоминает, что X было равно трем в момент ее создания, т.е. в момент вычисления выражения ( lambda ( y ) (+ x y )) 7) ).

( define ( sq x ) (* x x )) – это всего лишь другая форма записи выражения

(define sq (lambda (x) (* x x))

Возможны семь видов выражений:

Константы: "foo#\Z3”строка”

Ссылки на переменные: foo joe a - long - name @#$!+-*/%<>

Создание функции: ( lambda ( z ) (* z z z ))

Применение процедуры: ( cube 37)

Условие: (if (< x 3) sqrt modulo)

Присваивание значения: ( set ! x 5)

Последовательность: ( begin ( write x ) ( write y ) ( newline ))

(разумеется, в этом списке перечислены далеко не все варианты выражений)

Схема имеет обычный набор типов данных:

Литеры (character): #\a #\A \#space #\newline

Строки (string ): ”строка текста”

Массивы (векторы – vector ): #(1 2 ”строка” #\ x 5)

Списки (list): (a little (list of) (lists))

Числа (numbers): 47 1/3 2.3 4.3e14 1+3i

Функции (function )

Логические значения (boolean , соотв. истина и ложь): # t # f

Порты (например, открытые файлы или сетевые соединения)

Символы (symbol , обычно используются для обозначения переменных): this - is - a - symbol foo a 32 > adfasf 23@#$%!<

Основные моменты:

Вектор может состоять из любых объектов данных;

Символ может содержать буквы английского алфавита, цифры и литеры + - . * / < = > ! ? : $ % _& ~ ^

Символы не чувствительны к регистру букв (т.е. символы SYMBOL и SyMboL идентичны)

Символы используются для обозначения переменных (но не только для этого!)

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

Числа особенно интересны в Схеме: каждое целое (integer ) является дробью (rational ), дробь – действительным числом (real ), а действительное число – комплексным (complex ). Числа классифицируются по признаку точности (точное или приблизительное – exact /inexact ):

(exact? 3); #t

(exact? 1/3); #t

(exact? 2.3##); #f

(+ 2/3 1/2 5/6); 2

(integer? 2); #t

(integer? 3/7); #f

(real? 2); #t

Философия Схемы

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

Для «разогрева» давайте построим структуру данных «пара» (pair ). Пара состоит из двух элементов, получаемых с помощью функций доступа FIRST и SECOND (соответственно ПЕРВЫЙ и ВТОРОЙ). Функция создания пары будет называться PAIR . Должны выполняться следующие соотношения: ( first ( pair 1 2)) равно 1, ( second ( pair 1 2)) равно 2. Для знающих Лисп в этом нет ничего необычного. Однако сколькими разными способами мы можем реализовать это трио: PAIR , FIRST , SECOND ?

; 1. Вектор

; можно и просто (define PAIR vector ) , но так стилистически лучше

(define (PAIR a b) (vector a b))

(define (FIRSTaPair) (vector-ref aPair 0))

(define (SECOND aPair) (vector-ref aPair 1))

; 2. Ф ункция выбора

; Не забывайте про лексическую область видимости:

; каждая функция, создаваемая функцией PAIR, будет помнить

; значения a и b в момент создания

(define (PAIR a b) (lambda (bool) (if bool a b)))

(define (FIRSTaPair) (aPair #t))

(define (SECOND aPair) (aPair #f))

; 3. Передача сообщений

(define (PAIR (a b)

(lambda (msg)

(case msg ; конструкция case для каждого значения msg

; выполняет соответствующее действие

((first ) a ) ; если сообщение – символ first ,

; возвратить a

((second) b))))

; апостроф (‘) перед символом запрещает вычислять его значение

; (без него была бы ошибка «отсутствует переменная»)

(define (FIRSTaPair) (aPair ‘first))

(define (SECOND aPair) (aPair ‘second))

; 4. Псевдонимы: в Схеме уже есть тип данных «пара»!

(define PAIRcons)

(define FIRSTcar)

(define SECOND cdr)

; 5. Лямбда-функции (передача функций как параметров другим

; функциям )

(define (PAIR a b) (lambda (proc) (proc a b)))

(define (FIRSTaPair) (aPair (lambda (x y) x)))

(define (SECOND aPair) (aPair (lambda (x y) y)))

Смысл всего вышеприведенного: даже простейшие вещи можно сделать совершенно по-разному.

Теперь, когда мы разогрелись, давайте взглянем на старый добрый факториал (напоминаю: факториал – произведение всех целых чисел от 1 до данного числа).

Для начала – рекурсивное определение:

(define (fact n)

(if (< n 2)

(* n (fact (- n 1)))

Когда я (Кен Дики) впервые изучал рекурсивные определения наподобие этого, самым сложным было понять, как скрытое состояние функции хранится на стеке. Небольшое преобразование кода делает стек видимым.

; функция identity просто возвращает свой аргумент

(define (identity value) value)

; сохраним форму функции fact

; (теперь она всего лишь вызывает функцию cfact )

(define (fact n) (cfact n identity))

; А функция cfact – вычисляет факториал

(define (cfact n k)

(if (< n 2)

(k 1)

(cfact (- n 1)

(lambda (result) (k (* n result))))))

Функция cfact – версия функции fact , использующая «продолжения». Вместо возвращения результата каждый раз функция получает дополнительный аргумент, «продолжение», который и вызывается с результатом вычислений функции.

Давайте посмотрим, как будет преобразовываться вызов ( fact 3) :

(fact 3) становится (cfact 3 identity)

(cfact 3 identity) становится

(cfact 2

(lambda (result)

(identity (* 3 result)))) ; k’

Это в свою очередь преобразовывается в

(cfact 1

(lambda (result’) ;; k’’

((lambda (result)

(identity (* 3 result))) ; функция k"

(* 2 result ’)) ; аргумент, передаваемый k "

((lambda (result’) ;; k’’

((lambda (result)

(identity (* 3 result)))(* 2 result’))

) 1)

((lambda (result) (identity (* 3 result))) (* 2 1))

(identity (* 3 (* 2 1)))

(* 3 (* 2 1))

-> 6

Это – не пример того, как из простых вещей можно легко сделать ужасно сложные. Зачем же мы так сделали? Смысл в том, что мы можем управлять тем, что обычно спрятано на стеке. Это позволяет делать некоторые интересные вещи. Мы можем игнорировать одно «продолжение» и использовать вместо него другое. Мы можем контролировать, например, длительные вычисления. Если они занимают больше времени, чем ожидалось, мы можем сохранить наше продолжение («где мы сейчас») и попробовать другой подход к решению задачи. Если новый вариант еще хуже, мы можем вернуться к сохраненному «продолжению» и продолжить вычисления. Мы, конечно, сможем сохранить и наши попытки сделать лучше на тот случай, если действительно получилось лучше…

Таким образом, использование «продолжений» позволяет строить очень интересные, гибкие управляющие структуры. Давайте теперь посмотрим на факториал с другой стороны. Каждый рекурсивный вызов просто кладет на стек еще один множитель. Но мы можем и не использовать стек, если введем дополнительную переменную-«аккумулятор». Разумеется, перед началом вычислений аккумулятор должен быть равен 1 (так как x *1 = x ).

(define (fact n)

; определяем функцию вычисления факториала с аккумулятором

(define (cfact _n acc)

(if (< _n 2)

(cfact (- _n 1) (* _n acc))

; вызываем эту функцию с аккумулятором, равным 1

(cfact n 1)

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

Итак, мы преобразовали рекурсивную функцию в итеративную, циклическую. Есть формальный (теоретически «правильный») способ такого преобразования; но одна приятная особенность Схемы в том, что эти преобразования просты и наглядны. Правильно работающие программы могут быть написаны быстро, даже если поначалу они могут медленно работать и требовать много памяти. После отладки алгоритма их несложно преобразовать в намного более эффективные – и тоже правильно работающие! Преобразование программ для опытного программиста на Схеме становится второй натурой.

Схема имеет несколько важных преимуществ над другими языками. Ее элегантно простая, однородная структура и тривиальный синтаксис позволяет избегать разных «особых случаев». Ее выразительность позволяет не тратить время на поиск обходных путей: программист может сконцентрироваться на том, что ему нужно сделать, но не на том, как это сделать. Схема поддерживает несколько стилей программирования, включая модное сегодня объектно-ориентированное, – так что программист не должен приспосабливаться под Схему; он может использовать тот стиль или способ решения задач, к которому привык. Формальность Схемы делает доказательство правильности программ намного более простым. Мощные средства абстрагирования позволяют отделить части программы, которые можно повторно использовать, от частей, «заточенных» под конкретную проблему/реализацию языка/операционную систему. Легкость сочетания различных функций и создания на их основе новых конструкций позволяет создавать целые библиотеки хорошо отлаженных, универсальных компонентов.

Иначе говоря, если вы хотите писать сложные, корректные программы, но не хотите тратить на это годы, Схема – то, что нужно для успеха!

Краткий список наиболее известных реализаций Схемы.

Chez Scheme и MacScheme – одни из лучших коммерческих реализаций; однако существует множество бесплатных интерпретаторов и компиляторов Схемы как для учебных целей, так и для серьезной работы.

Одна из лучших систем для Windows и Linux – MzScheme , и построенные на ее основе MrEd (система создания переносимого графического интерфейса пользователя) и DrScheme (пожалуй, самая удобная среда разработки программ из существующих).

Введение

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

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

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

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

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

Примеры

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

(+ 2 (* 2 2 ) ) (+ 1 2 3 4 )

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

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

(number? 5 ) (number? "foo" ) (string ? "foo" )

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

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

(eq? "foo" "bar" ) (eq? 5 (+ 2 3 ) ) (eq? (eq? 2 3 ) (eq? 3 4 ) )

Определение макросов для традиционных операций 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 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 6 6 100 ) ) (sum (map fib "(1 2 3 4 ) ) )

Определение функции должно соответствовать следующему прототипу:

(define имя_функции (lambda (список_аргументов) (реализация_функции) ) ) ,

хотя на практике чаще используют сокращённую форму:

(define (имя_функции аргументы) (реализация_функции) ) .

Ввод / Вывод

(write (+ (read ) (read ) ) )

Ссылки

Русскоязычные ссылки

Англоязычные ссылки

Учебники на английском

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

Wikimedia Foundation . 2010 .

Смотреть что такое "Scheme (язык программирования)" в других словарях:

Язык программирования формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия,… … Википедия