1.1.5 Подстановочная модель применения процедуры
Вычисляя комбинацию, оператор которой называет составную процедуру, интерпретатор осуществляет, вообще говоря, тот же процесс, что и для комбинаций, операторы которых называют элементарные процедуры — процесс, описанный в разделе 1.1.3. А именно, интерпретатор вычисляет элементы комбинации и применяет процедуру (значение оператора комбинации) к аргументам (значениям операндов комбинации).
Мы можем предположить, что механизм применения элементарных процедур к аргументам встроен в интерпретатор. Для составных процедур процесс протекает так:
- Чтобы применить составную процедуру к аргументам, требуется вычислить тело процедуры, заменив каждый формальный параметр соответствующим аргументом.
Чтобы проиллюстрировать этот процесс, вычислим комбинацию
(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, где мы детально исследуем реализацию интерпретатора.
- На протяжении этой книги мы представим последовательность усложняющихся моделей того, как работает интерпретатор, завершающуюся полным воплощением интерпретатора и компилятора в главе 5. Подстановочная модель — только первая из них, способ начать формально мыслить о моделях вычисления. Вообще, моделируя различные явления в науке и технике, мы начинаем с упрощенных, неполных моделей. Подстановочная модель в этом смысле не исключение. В частности, когда в главе 3 мы обратимся к использованию процедур с «изменяемыми данными», то мы увидим, что подстановочная модель этого не выдерживает и ее нужно заменить более сложной моделью применения процедур1.
Аппликативный и нормальный порядки вычисления
В соответствии с описанием из раздела 1.1.3, интерпретатор сначала вычисляет оператор и операнды, а затем применяет получившуюся процедуру к получившимся аргументам. Но это не единственный способ осуществлять вычисления. Другая модель вычисления не вычисляет аргументы, пока не понадобится их значение. Вместо этого она подставляет на место параметров выражения-операнды, пока не получит выражение, в котором присутствуют только элементарные операторы, и лишь затем вычисляет его. Если бы мы использовали этот метод, вычисление
(f 5)
прошло бы последовательность подстановок
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)) )
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
за которыми последуют редукции
(+ (* 6 6) (* 10 10))
(+ 36 100)
136
Это дает тот же результат, что и предыдущая модель вычислений, но процесс его получения отличается. В частности, вычисление (+ 5 1) и (* 5 2) выполняется здесь по два раза, в соответствии с редукцией выражения
(* x x)
где x заменяется, соответственно, на (+ 5 1) и (* 5 2).
Альтернативный метод «полная подстановка, затем редукция» известен под названием нормальный порядок вычислений (normal-order evaluation), в противоположность методу «вычисление аргументов, затем применение процедуры», которое называется аппликативным порядком вычислений (applicative-order evaluation). Можно показать, что для процедур, которые правильно моделируются с помощью подстановки (включая все процедуры из первых двух глав этой книги) и возвращают законные значения, нормальный и аппликативный порядки вычисления дают одно и то же значение. (См. упражнение 1.5, где приводится пример «незаконного» выражения, для которого нормальный и аппликативный порядки вычисления дают разные результаты.)
В Лиспе используется аппликативный порядок вычислений, отчасти из-за дополнительной эффективности, которую дает возможность не вычислять многократно выражения вроде приведенных выше (+ 5 1) и (* 5 2), а отчасти, что важнее, потому что с нормальным порядком вычислений становится очень сложно обращаться, как только мы покидаем область процедур, которые можно смоделировать с помощью подстановки. С другой стороны, нормальный порядок вычислений может быть весьма ценным инструментом, и некоторые его применения мы рассмотрим в главах 3 и 42.
1. Несмотря на простоту подстановочной модели, дать строгое математическое определение процессу подстановки оказывается удивительно сложно. Проблема возникает из-за возможности смешения имен, которые используются как формальные параметры процедуры, с именами(возможно, с ними совпадающими), которые ↩
используются в выражениях, к которым процедура может применяться. Имеется долгая история неверных определений подстановки(substitution) в литературе по логике и языкам программирования. Подробное обсуждение подстановки можно найти в Stoy 1977.
2. В главе 3 мы описываем обработку потоков(stream processing), которая представляет собой способ об- работки структур данных, кажущихся «бесконечными», с помощью ограниченной формы нормального порядка вычислений. В разделе 4.2 мы модифицируем интерпретатор Scheme так, что получается вариант языка с нормальным порядком вычислений. ↩