Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 8
Текст из файла (страница 8)
Для составных процедур процесс протекает так:• Чтобы применить составную процедуру к аргументам, требуется вычислить телопроцедуры, заменив каждый формальный параметр соответствующим аргументом.Чтобы проиллюстрировать этот процесс, вычислим комбинацию(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))34Глава 1. Построение абстракций с помощью процедурчто при умножении сводится к(+ 36 100)и, наконец, к136Только что описанный нами процесс называется подстановочной моделью (substitutionmodel) применения процедуры.
Ее можно использовать как модель, которая определяет«смысл» понятия применения процедуры, пока рассматриваются процедуры из этой главы. Имеются, однако, две детали, которые необходимо подчеркнуть:• Цель подстановочной модели — помочь нам представить, как применяются процедуры, а не дать описание того, как на самом деле работает интерпретатор. Как правило, интерпретаторы вычисляют применения процедур к аргументам без манипуляций стекстом процедуры, которые выражаются в подстановке значений для формальных параметров. На практике «подстановка» реализуется с помощью локальных окружений дляформальных параметров. Более подробно мы обсудим это в главах 3 и 4, где мы детальноисследуем реализацию интерпретатора.• На протяжении этой книги мы представим последовательность усложняющихсямоделей того, как работает интерпретатор, завершающуюся полным воплощением интерпретатора и компилятора в главе 5.
Подстановочная модель — только первая из них,способ начать формально мыслить о моделях вычисления. Вообще, моделируя различныеявления в науке и технике, мы начинаем с упрощенных, неполных моделей. Подстановочная модель в этом смысле не исключение. В частности, когда в главе 3 мы обратимся киспользованию процедур с «изменяемыми данными», то мы увидим, что подстановочнаямодель этого не выдерживает и ее нужно заменить более сложной моделью примененияпроцедур15 .Аппликативный и нормальный порядки вычисленияВ соответствии с описанием из раздела 1.1.3, интерпретатор сначала вычисляет оператор и операнды, а затем применяет получившуюся процедуру к получившимся аргументам. Но это не единственный способ осуществлять вычисления. Другая модельвычисления не вычисляет аргументы, пока не понадобится их значение. Вместо этогоона подставляет на место параметров выражения-операнды, пока не получит выражение, в котором присутствуют только элементарные операторы, и лишь затем вычисляетего.
Если бы мы использовали этот метод, вычисление(f 5)прошло бы последовательность подстановок15 Несмотря на простоту подстановочной модели, дать строгое математическое определение процессу подстановки оказывается удивительно сложно. Проблема возникает из-за возможности смешения имен, которыеиспользуются как формальные параметры процедуры, с именами (возможно, с ними совпадающими), которыеиспользуются в выражениях, к которым процедура может применяться. Имеется долгая история неверныхопределений подстановки (substitution) в литературе по логике и языкам программирования. Подробное обсуждение подстановки можно найти в Stoy 1977.1.1. Элементы программирования35(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))(+36100)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 и 416 .1.1.6.
Условные выражения и предикатыВыразительная сила того класса процедур, которые мы уже научились определять,очень ограничена, поскольку пока что у нас нет способа производить проверки и выполнять различные операции в зависимости от результата проверки. Например, мы неспособны определить процедуру, вычисляющую модуль числа, проверяя, положительное16 В главе 3 мы описываем обработку потоков (stream processing), которая представляет собой способ обработки структур данных, кажущихся «бесконечными», с помощью ограниченной формы нормального порядкавычислений. В разделе 4.2 мы модифицируем интерпретатор Scheme так, что получается вариант языка снормальным порядком вычислений.Глава 1. Построение абстракций с помощью процедур36ли это число, отрицательное или ноль, и предпринимая различные действия в соответствии с правилом x если x > 00 если x = 0|x| =−x если x < 0Такая конструкция называется разбором случаев (case analysis).
В Лиспе существуетособая форма для обозначения такого разбора случаев.Она называется cond (от английского слова conditional, «условный») и используется так:(define (abs x)(cond ((> x 0) x)((= x 0) 0)((< x 0) (- x))))Общая форма условного выражения такова:(cond (hp1 i he1 i)(hp2 i he2 i)...(hpn i hen i))Она состоит из символа cond, за которым следуют заключенные в скобки парывыражений (hpi hei), называемых ветвями (clauses). В каждой из этих пар первоевыражение — предикат (predicate), то есть выражение, значение которого интерпретируется как истина или ложь17 .Условные выражения вычисляются так: сначала вычисляется предикат hp1 i.
Если егозначением является ложь, вычисляется hp2 i. Если значение hp2 i также ложь, вычисляется hp3 i. Этот процесс продолжается до тех пор, пока не найдется предикат, значением которого будет истина, и в этом случае интерпретатор возвращает значение соответствующего выражения-следствия (consequent expression) в качестве значения всегоусловного выражения. Если ни один из hpi ни окажется истинным, значение условноговыражения не определено.Словом предикат называют процедуры, которые возвращают истину или ложь, атакже выражения, которые имеют значением истину или ложь. Процедура вычислениямодуля использует элементарные предикаты <,= и >18 .Они принимают в качестве аргументов по два числа и, проверив, меньше ли первоеиз них второго, равно ему или больше, возвращают в зависимости от этого истину илиложь.Можно написать процедуру вычисления модуля и так:17 «Интерпретируетсякак истина или ложь» означает следующее: в языке Scheme есть два выделенныхзначения, которые обозначаются константами #t и #f.
Когда интерпретатор проверяет значение предиката,он интерпретирует #f как ложь. Любое другое значение считается истиной. (Таким образом, наличие #tлогически не является необходимым, но иметь его удобно.) В этой книге мы будем использовать имена trueи false, которые связаны со значениями #t и #f, соответственно.18 Еще она использует операцию «минус» -, которая, когда используется с одним операндом, как в выражении (- x), обозначает смену знака.1.1. Элементы программирования37(define (abs x)(cond ((< x 0) (- x))(else x)))что на русском языке можно было бы выразить следующим образом: «если x меньшенуля, вернуть −x; иначе вернуть x».
Else — специальный символ, который в заключительной ветви cond можно использовать на месте hpi. Это заставляет cond вернуть вкачестве значения значение соответствующего hei в случае, если все предыдущие ветвибыли пропущены. На самом деле, здесь на месте hpi можно было бы использовать любоевыражение, которое всегда имеет значение истина.Вот еще один способ написать процедуру вычисления модуля:(define (abs x)(if (< x 0)(- x)x))Здесь употребляется особая форма if, ограниченный вид условного выражения. Егоможно использовать при разборе случаев, когда есть ровно два возможных исхода. Общая форма выражения if такова:(if hпредикатi hследствиеi hальтернативаi)Чтобы вычислить выражение if, интерпретатор сначала вычисляет его hпредикатi. Еслиhпредикатi дает истинное значение, интерпретатор вычисляет hследствиеi и возвращает его значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
