Accumulate принимает в качестве аргументов те же описания термов и диапазона, что и sum с product, а еще процедуру combiner (двух аргументов), которая указывает, как нужно присоединить текущий терм к результату накопления предыдущих, и null-value, базовое значение, которое нужно использовать, когда термы закончатся. Напишите accumulate и покажите, как и sum, и product можно определить в виде простых вызовов accumulate.

b. Если Ваша процедура accumulate порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.

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

Можно получить еще более общую версию accumulate (упражнение 1.32), если ввести понятие фильтра (filter) на комбинируемые термы. То есть комбинировать только те термы, порожденные из значений диапазона, которые удовлетворяют указанному условию. Получающаяся абстракция filtered-accumulate получает те же аргументы, что и accumulate, плюс дополнительный одноаргументный предикат, который определяет фильтр. Запишите filtered-accumulate в виде процедуры. Покажите, как с помощью filtered-accumulate выразить следующее:

a.сумму квадратов простых чисел в интервале от a до b (в предположении, что процедура prime? уже написана);

b.произведение всех положительных целых чисел меньше n, которые просты по отношению к n (то есть всех таких положительных целых чисел i < n, что НОД(г, n) = 1).

1.3.2 Построение процедур с помощью lambda

Когда в разделе 1.3.1 мы использовали sum, очень неудобно было определять тривиальные процедуры вроде pi-term и pi-next только ради того, чтобы передать их как аргументы в процедуры высшего порядка. Было бы проще вместо того, чтобы вводить имена pi-next и pi-term, прямо определить «процедуру, которая возвращает свой аргумент плюс 4» и «процедуру, которая вычисляет число, обратное произведению аргумента и аргумента плюс 2». Это можно сделать, введя особую форму lambda, которая создает процедуры. С использованием lambda мы можем записать требуемое в таком виде:

(lambda (x) (+ x 4))

и

(lambda (x) (/ 1.0 (* x (+ x 2))))

Тогда нашу процедуру pi-sum можно выразить безо всяких вспомогательных

процедур:

(define (pi-sum a b)

(sum (lambda (x) (/ 1.0 (* x (+ x 2))))

a

(lambda (x) (+ x 4))

b))

Еще с помощью lambda мы можем записать процедуру integral, не определяя вспомогательную процедуру add-dx:

(define (integral f a b dx) (* (sum f

(+ a (/ dx 2.0)) (lambda (x) (+ x dx))

b)

dx))

В общем случае, lambda используется для создания процедур точно так же, как define, только никакого имени для процедуры не указывается:

(lambda ((формальные-параметры)) (тело))

Получается столь же полноценная процедура, как и с помощью define. Единственная разница состоит в том, что она не связана ни с каким именем в окружении. На самом деле

(define (plus4 x) (+ x 4))

эквивалентно

(define plus4 (lambda (x) (+ x 4))) Можно читать выражение lambda так:

(lambda(x)(+x4))

Процедура от аргумента x, которая складывает x и 4

Подобно любому выражению, значением которого является процедура, выражение с lambda можно использовать как оператор в комбинации, например

((lambda (x y z) (+ x y (square z))) 1 2 3) 12

Или, в более общем случае, в любом контексте, где обычно используется имя

53

процедуры.53

Создание локальных переменных с помощью let

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

f (x, y) = x(1 + xy)3 + y(1 - y) + (1 + xy)(1 - y) которую мы также могли бы выразить как

53Было бы более понятно и менее страшно для изучающих Лисп, если бы здесь использовалось более ясное имя, чем lambda, например make-procedure. Однако традиция уже прочно укоренилась. Эта нотация заимствована из А-исчисления, формализма, изобретенного математическим логиком Алонсо Чёрчем (Church 1941). Чёрч разработал А-исчисление, чтобы найти строгое основание для понятий функции и применения функции. А-исчисление стало основным инструментом математических исследований по семантике языков программирования.

b

f (x,y)

а

1 + xy 1 - У

ха2 + yb + аЬ

Когда мы пишем процедуру для вычисления f, хотелось бы иметь как локальные переменные не только x и y, но и имена для промежуточных результатов вроде а и b. Можно сделать это с помощью вспомогательной процедуры, которая связывает локальные переменные:

(define (f x y)

(define (f-helper a b) (+ (* x (square a))

(* y b) (* a b))) (f-helper (+ 1 (* x y)) (- 1 y)))

Разумеется, безымянную процедуру для связывания локальных переменных мы можем записать через lambda-выражение. При этом тело f оказывается просто вызовом этой процедуры.

(define (f x y) ((lambda (a b)

(+ (* x (square a))

(* y b) (* a b)))

(+ 1 (* x y))

(- 1 y)))

Такая конструкция настолько полезна, что есть особая форма под названием let, которая делает ее более удобной. С использованием let процедуру f можно записать так:

(define (f x y)

(let ((a (+ 1 (* x y)))

(b (- 1 y))) (+ (* x (square a))

(* y b) (* a b))))

Общая форма выражения с let такова:

(let (((nepi) (выр1)) ({nep2) (выр2))

((nepn) (вырп))) (тело))

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

Пусть (пер1) имеет значение (вг и (пер2) имеет значение (выр)

и (перп) имеет значение (вырп) в (теле)