объекты. Мы говорим, что имя обозначает переменную (variable), чьим значением (value) является объект.

В диалекте Лиспа Scheme мы даем вещам имена с помощью слова define. Предложение

(define size 2)

заставляет интерпретатор связать значение 2 с именем size.8 После того, как имя size связано со значением 2, мы можем указывать на значение 2 с помощью имени:

size

2

(* 5 size) 10

Вот еще примеры использования define:

(define pi 3.14159)

(define radius 10)

(* pi (* radius radius)) 314.159

(define circumference (* 2 pi radius))

circumference 62.8318

Слово define служит в нашем языке простейшим средством абстракции, поскольку оно позволяет нам использовать простые имена для обозначения результатов сложных операций, как, например, вычисленная только что длина окружности - circumference. Вообще говоря, вычислительные объекты могут быть весьма сложными структурами, и было бы очень неудобно, если бы нам приходилось вспоминать и повторять все их детали каждый раз, когда нам захочется их использовать. На самом деле сложные программы конструируются методом построения шаг за шагом вычислительных объектов возрастающей сложности. Интерпретатор делает такое пошаговое построение программы особенно удобным, поскольку связи между именами и объектами могут создаваться последовательно по мере взаимодействия программиста с компьютером. Это свойство интерпретаторов облегчает пошаговое написание и тестирование программ, и во многом благодаря именно ему получается так, что программы на Лиспе обычно состоят из большого количества относительно простых процедур.

Ясно, что раз интерпретатор способен ассоциировать значения с символами и затем вспоминать их, то он должен иметь некоторого рода память, сохраняющую пары имя-объект. Эта память называется окружением (environment) (а точнее, глобальным окружением (global environment), поскольку позже мы увидим, что вычисление может иметь дело с несколькими окружениями).9

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

9В главе 3 мы увидим, что понятие окружения необходимо как для понимания работы интерпретаторов, так и для их реализации.

1.1.3 Вычисление комбинаций

Одна из наших целей в этой главе - выделить элементы процедурного мышления. Рассуждая в этом русле, примем во внимание, что интерпретатор, вычисляя значение комбинации, тоже следует процедуре:

•Чтобы вычислить комбинацию, требуется:

-Вычислить все подвыражения комбинации.

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

Даже в этом простом правиле видны несколько важных свойств процессов в целом. Прежде всего, заметим, что на первом шаге для того, чтобы провести процесс вычисления для комбинации, нужно сначала проделать процесс вычисления для каждого элемента комбинации. Таким образом, правило вычисления рекурсивно (recursive) по своей природе; это означает, что в качестве одного из своих шагов оно включает применение того же самого правила.10

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

(* (+2 (* 4 6)) (+3 5 7))

требуется применить правило вычисления к четырем различным комбинациям. Картину этого процесса можно получить, нарисовав комбинацию в виде дерева, как показано на рис. 1.1. Каждая комбинация представляется в виде вершины, а ее оператор и операнды - в виде ветвей, исходящих из этой вершины. Концевые вершины (то есть те, из которых не исходит ни одной ветви) представляют операторы или числа. Рассматривая вычисление как дерево, мы можем представить себе, что значения операндов распространяются от концевых вершин вверх и затем комбинируются на все более высоких уровнях. Впоследствии мы увидим, что рекурсия - это вообще очень мощный метод обработки иерархических, древовидных объектов. На самом деле форма правила вычисления «распространить значения наверх» является примером общего типа процессов, известного как накопление по дереву (tree accumulation).

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

•значением числовых констант являются те числа, которые они называют;

•значением встроенных операторов являются последовательности машинных команд, которые выполняют соответствующие операции; и

10Может показаться странным, что правило вычисления предписывает нам в качестве части первого шага вычислить самый левый элемент комбинации, - ведь до сих пор это мог быть только оператор вроде + или *, представляющий встроенную процедуру, например, сложение или умножение. Позже мы увидим, что полезно иметь возможность работать и с комбинациями, чьи операторы сами по себе являются составными выражениями.

390

*

7

*

6

4

Рис. 1.1: Вычисление, представленное в виде дерева.

• значением остальных имен являются те объекты, с которыми эти имена связаны в окружении.

Мы можем рассматривать второе правило как частный случай третьего, постановив, что символы вроде + и * тоже включены в глобальное окружение и связаны с последовательностями машинных команд, которые и есть их «значения». Главное здесь - это роль окружения при определении значения символов в выражениях. В таком диалоговом языке, как Лисп, не имеет смысла говорить о значении выражения, скажем, (+ x 1), не указывая никакой информации об окружении, которое дало бы значение символу x (и даже символу +). Как мы увидим в главе 3, общее понятие окружения, предоставляющего контекст, в котором происходит вычисление, будет играть важную роль в нашем понимании того, как выполняются программы.

Заметим, что рассмотренное нами правило вычисления не обрабатывает определений. Например, вычисление (define x 3) не означает применение define к двум аргументам, один из которых значение символа x, а другой равен 3, поскольку смысл define как раз и состоит в том, чтобы связать x со значением. (Таким образом, (define x 3) - не комбинация.)

Такие исключения из вышеописанного правила вычисления называются особыми формами (special forms). Define - пока что единственный встретившийся нам пример особой формы, но очень скоро мы познакомимся и с другими. У каждой особой формы свое собственное правило вычисления. Разные виды выражений (вместе со своими правилами вычисления) составляют синтаксис языка программирования. По сравнению с большинством языков программирования, у Лиспа очень простой синтаксис; а именно, правило вычисления для выражений может быть описано как очень простое общее правило плюс специальные правила для небольшого числа особых форм."

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