1.1.4 Составные процедуры

Мы нашли в Лиспе некоторые из тех элементов, которые должны присутствовать в любом мощном языке программирования:

•Числа и арифметические операции представляют собой элементарные данные и процедуры.

•Вложение комбинаций дает возможность комбинировать операции.

•Определения, которые связывают имена со значениями, дают ограниченные возможности абстракции.

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

Для начала рассмотрим, как выразить понятие «возведения в квадрат». Можно сказать так: «Чтобы возвести что-нибудь в квадрат, нужно умножить его само на себя». Вот как это выражается в нашем языке:

(define (square x) (* x x))

Это можно понимать так:

(define(squarex)*x x))

Чтобы возвести в квадрат что-л. умножь это само на себя

Здесь мы имеем составную процедуру (compound procedure), которой мы дали имя square. Эта процедура представляет операцию умножения чего-либо само на себя. Та вещь, которую нужно подвергнуть умножению, получает здесь имя x, которое играет ту же роль, что в естественных языках играет местоимение. Вычисление этого определения создает составную процедуру и связывает ее с именем square.12

Общая форма определения процедуры такова:

(define ({имя) (формальные-параметры)) (тело))

(Имя) - это тот символ, с которым нужно связать в окружении определение процедуры.13 (Формальные-параметры) - это имена, которые в теле процедуры используются для отсылки к соответствующим аргументам процедуры.

иногда называют синтаксическим сахаром (syntactic sugar), используя выражение Питера Ланди-на. По сравнению с пользователями других языков, программистов на Лиспе, как правило, мало волнует синтаксический сахар. (Для контраста возьмите руководство по Паскалю и посмотрите, сколько места там уделяется описанию синтаксиса). Такое презрение к синтаксису отчасти происходит от гибкости Лиспа, позволяющего легко изменять поверхностный синтаксис, а отчасти из наблюдения, что многие «удобные» синтаксические конструкции, которые делают язык менее последовательным, приносят в конце концов больше вреда, чем пользы, когда программы становятся большими и сложными. По словам Алана Перлиса, «Синтаксический сахар вызывает рак точки с запятой».

12Заметьте, что здесь присутствуют две различные операции: мы создаем процедуру, и мы даем ей имя square. Возможно, и на самом деле даже важно, разделить эти два понятия: создавать процедуры, никак их не называя, и давать имена процедурам, уже созданным заранее. Мы увидим, как это делается, в разделе 1.3.2.

13На всем протяжении этой книги мы будем описывать обобщенный синтаксис выражений, используя курсив в угловых скобках - напр. {имя), чтобы обозначить «дырки» в выражении, которые нужно заполнить, когда это выражение используется в языке.

(Тело) - это выражение, которое вычислит результат применения процедуры, когда формальные параметры будут заменены аргументами, к которым процедура будет применяться.14 (Имя) и (формальные-параметры) заключены в скобки, как это было бы при вызове определяемой процедуры.

Теперь, когда процедура square определена, мы можем ее использовать:

(square 21) 441

(square (+ 2 5)) 49

(square (square 3)) 81

Кроме того, мы можем использовать square при определении других процедур. Например, x2 + y2 можно записать как

(+ (square x) (square y)))

Легко можно определить процедуру sum-of-squares, которая, получая в качестве аргументов два числа, дает в результате сумму их квадратов:

(define (sum-of-squares x y) (+ (square x) (square y)))

(sum-of-squares 3 4) 25

Теперь и sum-of-squares мы можем использовать как строительный блок при дальнейшем определении процедур:

(define (f a)

(sum-of-squares (+ a 1) (* a 2)))

(f 5)

136

Составные процедуры используются точно так же, как элементарные. В самом деле, глядя на приведенное выше определение sum-of-squares, невозможно выяснить, была ли square встроена в интерпретатор, подобно + и *, или ее определили как составную процедуру.

1.1.5 Подстановочная модель применения процедуры

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

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

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

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

Чтобы проиллюстрировать этот процесс, вычислим комбинацию

(f 5)

где f - процедура, определенная в разделе 1.1.4. Начинаем мы с того, что восстанавливаем тело f:

(sum-of-squares (+ a 1) (* a 2))

Затем мы заменяем формальный параметр a на аргумент 5: (sum-of-squares (+ 5 1) (* 5 2))

Таким образом, задача сводится к вычислению комбинации с двумя операндами и оператором sum-of-squares. Вычисление этой комбинации включает три подзадачи. Нам нужно вычислить оператор, чтобы получить процедуру, которую требуется применить, а также операнды, чтобы получить аргументы. При этом (+5 1) дает 6, а (* 5 2) дает 10, так что нам требуется применить процедуру sum-of-squares к 6 и 10. Эти значения подставляются на место формальных параметров x и y в теле sum-of-squares, приводя выражение к

(+ (square 6) (square 10))

Когда мы используем определение square, это приводится к (+ (* 6 6) (* 10 10))

что при умножении сводится к

(+ 36 100)

и, наконец, к

136

Только что описанный нами процесс называется подстановочной моделью (substitution model) применения процедуры. Ее можно использовать как модель, которая определяет «смысл» понятия применения процедуры, пока рассматриваются процедуры из этой главы. Имеются, однако, две детали, которые необходимо подчеркнуть:

•Цель подстановочной модели - помочь нам представить, как применяются процедуры, а не дать описание того, как на самом деле работает интерпретатор. Как правило, интерпретаторы вычисляют применения процедур к аргументам без манипуляций с текстом процедуры, которые выражаются в подстановке значений для формальных параметров. На практике «подстановка» реализуется с помощью локальных окружений для формальных параметров. Более подробно мы обсудим это в главах 3 и 4, где мы детально исследуем реализацию интерпретатора.