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

1.1 Элементы программирования

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

элементарные выражения, представляющие минимальные сущности, с которыми язык имеет дело;

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

средства абстракции, с помощью которых сложные объекты можно называть и обращаться с ними как с единым целым.

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

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

4Называть числа «простыми данными» - это бесстыдный блеф. На самом деле работа с числами является одной из самых сложных и запутанных сторон любого языка программирования. Вот некоторые из возникающих при этом вопросов: Некоторые компьютеры отличают целые числа (integers), вроде 2, от вещественных (real numbers), вроде 2.71. Отличается ли вещественное число 2.00 от целого 2? Используются ли одни и те же арифметические операции для целых и для вещественных чисел? Что получится, если 6 поделить на 2: 3 или 3.0? Насколько большие числа мы можем представить? Сколько десятичных цифр после запятой мы можем хранить? Совпадает ли диапазон целых чисел с диапазоном вещественных? И помимо этих вопросов, разумеется, существует множество проблем, связанных с ошибками округления - целая наука численного анализа. Поскольку в этой книге мы говорим о проектировании больших программ, а не о численных методах, все эти проблемы мы будем игнорировать. Численные примеры в этой главе будут демонстрировать такое поведение при округлении, какое можно наблюдать, если использовать арифметические операции, сохраняющие при работе с вещественными числами ограниченное число десятичных цифр после запятой.

1.1.1 Выражения

Самый простой способ начать обучение программированию - рассмотреть несколько типичных примеров работы с интерпретатором диалекта Лиспа Scheme. Представьте, что Вы сидите за терминалом компьютера. Вы печатаете выражение (expression), а интерпретатор отвечает, выводя результат вычисления (evaluation) этого выражения.

Один из типов элементарных выражений, которые Вы можете вводить - это числа. (Говоря точнее, выражение, которое Вы печатаете, состоит из цифр, представляющих число по основанию 10.) Если Вы дадите Лиспу число

486

интерпретатор ответит Вам, напечатав5 486

Выражения, представляющие числа, могут сочетаться с выражением, представляющим элементарную процедуру (скажем, + или *), так что получается составное выражение, представляющее собой применение процедуры к этим числам. Например:

(+ 137 349)

486

(- 1000 334)

666

(* 5 99)

495

(/ 10 5) 2

(+ 2.7 10) 12.7

Выражения такого рода, образуемые путем заключения списка выражений в скобки с целью обозначить применение функции к аргументам, называются комбинациями (combinations). Самый левый элемент в списке называется оператором (operator), а остальные элементы - операндами (operands). Значение комбинации вычисляется путем применения процедуры, задаваемой оператором, к аргументам (arguments), которые являются значениями операндов.

Соглашение, по которому оператор ставится слева от операндов, известно как префиксная нотация (prefix notation), и поначалу оно может сбивать с толку, поскольку существенно отличается от общепринятой математической записи. Однако у префиксной нотации есть несколько преимуществ. Одно из них состоит в том, что префиксная запись может распространяться на процедуры с произвольным количеством аргументов, как в следующих примерах:

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

(+ 21 35 12 7)

75

(* 25 4 12) 1200

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

Второе преимущество префиксной нотации состоит в том, что она естественным образом расширяется, позволяя комбинациям вкладываться (nest) друг в друга, то есть допускает комбинации, элементы которых сами являются комбинациями:

(+ (* 3 5) (- 10 6))

19

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

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

а интерпретатор с готовностью вычисляет его и дает ответ 57. Мы можем облегчить себе задачу, записывая такие выражения в форме

(+ (* 3

(+ (*2 4)

(+3 5)))

(+ (- 107)

6))

Эти правила форматирования называются красивая печать (pretty printing). Согласно им, всякая длинная комбинация записывается так, чтобы ее операнды выравнивались вертикально. Получающиеся отступы ясно показывают структуру выражения.6

Даже работая со сложными выражениями, интерпретатор всегда ведет себя одинаковым образом: он считывает выражение с терминала, вычисляет его и печатает результат. Этот способ работы иногда называют циклом чтение-вычисление-печать (read-eval-print loop). Обратите особое внимание на то, что не нужно специально просить интерпретатор напечатать значение выражения.7

1.1.2 Имена и окружение

Одна из важнейших характеристик языка программирования - какие в нем существуют средства использования имен для указания на вычислительные

6Как правило, Лисп-системы содержат средства, которые помогают пользователям форматировать выражения. Особенно удобны две возможности: сдвигать курсор на правильную позицию для красивой печати каждый раз, когда начинается новая строка и подсвечивать нужную левую скобку каждый раз, когда печатается правая.

7Лисп следует соглашению, что у всякого выражения есть значение. Это соглашение, вместе со старой репутацией Лиспа как неэффективного языка, послужило источником остроумного замечания Алана Перлиса (парафразы из Оскара Уайльда), что «Программисты на Лиспе знают значение всего на свете, но ничему не знают цену».