Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Янин В.Л. "Новгородские акты XII-XV Хронологический комментарий" (История)

Майринк Г. "Белый доминиканец " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 2" (Художественная литература)

Петров Г.И. "Отлучение Льва Толстого " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 1 " (Художественная литература)
Реклама

Структура и интерпритация компьютерных программ - Абельсон Х.

Абельсон Х. Структура и интерпритация компьютерных программ — М.: Добросвет, 2006. — 608 c.
ISBN 978-5-98227-708-4
Скачать (прямая ссылка): strukturaiinterpretacii2006.pdf
Предыдущая << 1 .. 16 17 18 19 20 21 < 22 > 23 24 25 26 27 28 .. 269 >> Следующая


Напротив, второй процесс не растет и не сжимается. На каждом шаге при любом значении n необходимо помнить лишь текущие значения переменных product, counter и max-count. Такой процесс мы называем итеративным (iterative process).

1.2. Процедуры и порождаемые ими процессы

51

В общем случае, итеративный процесс — это такой процесс, состояние которого можно описать конечным числом переменных состояния (state variables) плюс заранее заданное правило, определяющее, как эти переменные состояния изменяются от шага к шагу, и плюс (возможно) тест на завершение, который определяет условия, при которых процесс должен закончить работу. При вычислении n! число шагов линейно растет с ростом n. Такой процесс называется линейно итеративным процессом (linear iterative process).

Можно посмотреть на различие этих двух процессов и с другой точки зрения. В итеративном случае в каждый момент переменные программы дают полное описание состояния процесса. Если мы остановим процесс между шагами, для продолжения вычислений нам будет достаточно дать интерпретатору значения трех переменных программы. С рекурсивным процессом это не так. В этом случае имеется дополнительная «спрятанная» информация, которую хранит интерпретатор и которая не содержится в переменных программы. Она указывает, «где находится» процесс в терминах цепочки отложенных операций. Чем длиннее цепочка, тем больше информации нужно хранить30.

Противопоставляя итерацию и рекурсию, нужно вести себя осторожно и не смешивать понятие рекурсивного процесса с понятием рекурсивной процедуры. Когда мы говорим, что процедура рекурсивна, мы имеем в виду факт синтаксиса: определение процедуры ссылается (прямо или косвенно) на саму эту процедуру. Когда же мы говорим о процессе, что он следует, скажем, линейно рекурсивной схеме, мы говорим о развитии процесса, а не о синтаксисе, с помощью которого написана процедура. Может показаться странным, например, высказывание «рекурсивная процедура fact-iter описывает итеративный процесс». Однако процесс действительно является итеративным: его состояние полностью описывается тремя переменными состояния, и чтобы выполнить этот процесс, интерпретатор должен хранить значение только трех переменных.

Различие между процессами и процедурами может запутывать отчасти потому, что большинство реализаций обычных языков (включая Аду, Паскаль и Си) построены так, что интерпретация любой рекурсивной процедуры поглощает объем памяти, линейно растущий пропорционально количеству вызовов процедуры, даже если описываемый ею процесс в принципе итеративен. Как следствие, эти языки способны описывать итеративные процессы только с помощью специальных«циклических конструкций» вроде do, repeat, until, for и while. Реализация Scheme, которую мы рассмотрим в главе 5, свободна от этого недостатка. Она будет выполнять итеративный процесс, используя фиксированный объем памяти, даже если он описывается рекурсивной процедурой. Такое свойство реализации языка называется поддержкой хвостовой рекурсии (tail recursion)*. Если реализация языка поддерживает хвостовую рекурсию, то итерацию можно выразить с помощью обыкновенного механизма вызова функций, так что специальные циклические конструкции имеют смысл только как синтаксический сахар31.

30Когда в главе 5 мы будем обсуждать реализацию процедур с помощью регистровых машин, мы увидим, что итеративный процесс можно реализовать «в аппаратуре» как машину, у которой есть только конечный набор регистров и нет никакой дополнительной памяти. Напротив, для реализации рекурсивного процесса требуется машина со вспомогательной структурой данных, называемойстек (stack).

* Словарь multitran.ru дает перевод «концевая рекурсия». Наш вариант, как кажется, изящнее и сохраняет метафору, содержащуюся в англоязычном термине. — прим. перев.

31 Довольно долго считалось, что хвостовая рекурсия — особый трюк в оптимизирующих компиляторах. Ясное семантическое основание хвостовой рекурсии было найдено Карлом Хьюиттом (Hewitt 1977), который выразил ее в терминах модели вычислений с помощью «передачи сообщений» (мы рассмотрим эту модель в

52

Глава 1. Построение абстракций с помощью процедур

Упражнение 1.9.

Каждая из следующих двух процедур определяет способ сложения двух положительных целых чисел с помощью процедур inc, которая добавляет к своему аргументу 1, и dec, которая отнимает от своего аргумента 1.

(define (+ a b)

(if ( = a 0) b

(inc (+ (dec a) b))))

(define (+ a b)

(if (= a 0) b

(+ (dec a) (inc b))))

Используя подстановочную модель, проиллюстрируйте процесс, порождаемый каждой из этих процедур, вычислив (+ 4 5). Являются ли эти процессы итеративными или рекурсивными?

Упражнение 1.10.

Следующая процедура вычисляет математическую функцию, называемую функцией Аккермана.

(define (A x y)

(cond ((= y 0) 0)

((= x 0) (* 2 y))

((= y 1) 2)

(else (A (- x 1)

(Ax (- y 1))))))

Каковы значения следующих выражений?

(A 1 10)

(A 2 4)

(A 3 3)

Рассмотрим следующие процедуры, где A — процедура, определенная выше:
Предыдущая << 1 .. 16 17 18 19 20 21 < 22 > 23 24 25 26 27 28 .. 269 >> Следующая