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)

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

$ gambsc 
Gambit Version 4.0 beta 12

> (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: // где-то видел мнемоническую историю...

(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 существует сокращенные варианты записи:

вместо (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) ; получить "хвост" третьего элемента, то есть "никого нет" или символ "()".

Продолжение будет ...