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