Scheme/Tutorial/3

Третья часть рассказа. Наверное, самая сложная, но если что-то будет неясно — ничего страшного, в следующих частях всё постепенно прояснится.

6 Несколько замечаний про функции

В прошлый раз было подробно рассказано, как описываются функции. Несколько полезных замечаний:

1. У длинного определения (define f (lambda (x y) ... )) есть более короткая форма (define (f x y) ... ) если процедура без аргументов, то определение в упрощённой форме будет выглядеть как: (define (f) ... )

2. Процедура является таким же полноправным типом данных, как и числа и строки, поэтому их можно как передавать в качестве аргумента, так и возвращать в качестве ответа. Вот, например, как можно было бы определить функцию «модуль числа»: (define (abs x) ((if (< x 0) - +) x))

3. Дополнение к предыдущему. Если вас не смущает сведение выражения:

(define a (+ 1 2))
(* a 5)

к:

(* (+ 1 2) 5)

то не должно смущать и сведение:

(define f (lambda (x) (+ x x))
(g f)

к:

(g (lambda (x) (+ x x)))

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

7 О символах

Из чего сделана переменная? Переменная — это некоторое «имя» и «связь» между этим именем и каким-то объектом, и прежде всего именно «связь» (связи может не быть, а имена есть всегда). То есть можно рассматривать по отдельности: отдельно имя, и отдельно некоторая таблица, которая ставит соответствие между именами и объектами, на которые они ссылаются.

(define a 4)

Это значит, есть имя a и оно ссылается на объект — число 4.

Когда интерпретатор видит выражение (define b a), он обнаруживает наличие имени a, а потом производит поиск в своей таблице имён, отмечает, что a ссылается на объект — число 4 и производит подстановку, после которой выражение приобретает вид (define b 4).

А что если мы хотим получить просто «имя»? Тогда мы говорим интерпретатору: пожалуйста, не надо размышлять над следующим выражением, дай мне его «как есть» — эта процедура носит имя quote. (define b (quote a)) назначит «имени» b уже не 4, а просто «имя» a.

«имена» являются одним из типов данных схемы и называются символами. У длинного варианта записи (quote объект) существует сокращенный: 'объект — то есть можно написать так: (define b 'a)

Чтобы ещё лучше прочувствовать символы, запустим интерпретатор. Мы будем вводить выражения, а он будет писать, во что они проинтерпретировались (пакет gambit):

$ gsc 
Gambit v4.5.3

> (define a 5)
> 5
5
> a
5
> 'a
a
>
> b
*** ERROR IN (console)@5.1 -- Unbound variable: b
1> 
> 'b
b
>

Обратите внимание на то, что переменной b нет (точнее, связи нет), но «имя» b без связи с чем-либо замечательно интерпретируется.

Не сильно огорчайтесь, если что-то сейчас неясно — всё прояснится, когда мы чуть глубже поймём, как работает интерпретатор.

8 Универсальный клей

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

Scheme предлагает только один способ сделать составной тип — объединение двух объектов в пару. Делается это так:

(cons 3 4) ; "создать пару из 3 и 4"
(cons "aaa" "bbb")

Доступ к первому и второму элементу пар обеспечивают функции car и cdr: // CAR (Contents of Address Register), CDR (Contents of Decrement Register). На этих регистрах вычислительной машины IBM 605 автор Лиспа Джон Маккарти хранил голову и хвост списка в первой реализации Лисп-системы.

(define a (cons 'first 'second))
(car a) ; получить первый элемент пары, то есть "имя" "first"
(cdr a) ; получить второй элемент пары, то есть "имя" "second"

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

Вот, например, так создаётся список из двух элементов, содержащих 3 и 4:

(define elem2 (cons 4 '() )) ; второй элемент содержит 4 и ссылается на "никого больше нет"
(define elem1 (cons 3 elem2)) ; первый элемент содержит 3 и ссылается на второй

В «развернутом виде» это выглядит так: (define elem1 (cons 3 (cons 4 '())))

Если захотим сделать список из трёх элементов 1, 2 и 3, то надо написать: (cons 1 (cons 2 (cons 3 '())))

Как видно, конструкция очень громоздкая, поэтому есть более короткий вариант: (list 1 2 3)

Поскольку список склеен из пар, то и работать с ним можно при помощи при помощи тех же car и cdr. (define a (list 1 2 3))

(car a) ; получить содержимое первого элемента
(cdr a) ; получить "хвост", то есть ссылку на второй элемент
(car (cdr a)) ; получить содержимое второго элемента
(cdr (cdr a)) ; получить "хвост" после второго элемента, то есть ссылку на третий элемент
(car (cdr (cdr a))) ; получить третий элемент

Опять-таки для веера из car и cdr существует сокращенные варианты записи:

вместо (car (car .. — (caar .. вместо (car (cdr .. — (cadr .. вместо (car (cdr (cdr … — (caddr .. вместо (car (car (cdr … — (caadr .. вместо (car (cdr (cdr (cdr .. — (cadddr ..

Надеюсь, уловили закономерность? Впрочем, пользоваться этим, скорее всего, не придётся. В нашем примере:

(cadr a) ; получить содержимое второго элемента
(caddr a) ; получить содержимое третьего элемента
(cdddr a) ; получить "хвост" третьего элемента, то есть ссылку на 
"никого нет" или символ "()".

далее>>