Решение упражнения 2.6 из SICP

18 January, 2008 (21:20) | Решения упражнений

Мы уже сводили пары к процедурам и пары к числам в двух предыдущих упражнениях. Сейчас нам предстоит задача для истинных интеллектуальных гурманов: мы будем представлять числа как процедуры.

Имея определения zero и add-1 из условия упражнения

(define zero 
  (lambda (f) (lambda (x) x)))
(define (add-1 n) 
  (lambda (f) (lambda (x) (f ((n f) x))))) ,

вычислим one как подстановку (add-1 zero):

(add-1 zero) 
(add-1 (lambda (f) (lambda (x) x))) 
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x)))) 
(lambda (f) (lambda (x) (f ((lambda (x) x) x)))) 
(lambda (f) (lambda (x) (f x)))

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

(define one 
  (lambda (f) (lambda (x) (f x))))

Аналогичным образом вычислим two как подстановку (add-1 one):

(add-1 one) 
(add-1 (lambda (f) (lambda (x) (f x)))) 
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x)))) 
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x)))) 
(lambda (f) (lambda (x) (f (f x))))

В результате получили определение для two:

(define two 
  (lambda (f) (lambda (x) (f (f x)))))

Обобщая полученный результат, можно сказать, что натуральное число n представляется как процедура, принимающая как аргумент функцию одной переменной и применяющая эту функцию повторно к самой себе n раз. В случае с one (которой соответствует n=1) функция f применяется единожды. В случае с two (которой соответствует n=2) функция f применяется дважды и получаем (f (f x)). Случай с zero (n=0) вырожден и функция f вообще не применяется, то есть можно сказать, что в этом случае функция f применяется ноль раз.

Таким образом выражение ((n f) x) вычисляет f(n)(x). Под f(n)(x) я подразумеваю сокращенную запись для f(f(…f(x)…)), где f вызывается n раз.

Переходя к вычислению суммы двух “чисел” (на деле это не числа, а объекты, которые ведут себя как числа относительно элементарных арифметических операций) сформулируем, как же должен представляться результат сложения m и n. По введенному раньше определению, это будет процедура, принимающая как аргумент функцию одной переменной и применяющая эту функцию повторно к самой себе m+n раз.

Итак, ((n f) x) вычисляет f(n)(x). Аналогично выражение ((m f) t) вычисляет f(m)(t).

Тогда, обозначив f(n)(x) через t, получаем, что ((m f) ((n f) x)) вычисляет f(m)(f(n)(t)) = f(m+n)(t), то есть как раз тот результ, который нам нужен для суммы. Оформляя полученное в виде процедуры суммирования, получим следующее:

(define (+ m n) 
  (lambda (f) (lambda (x) (f ((m f) ((n f) x))))))

Красивый и компактный ответ. Мне это упражнение показалось весьма интересным.

Comments

Pingback from SICP по-русски » Blog Archive » Решение упражнения 2.7 из SICP
Date: January 18, 2008, 9:35 pm

[…] SICP по-русски Структура и интерпретация компьютерных программ: заметки и решения « Решение упражнения 2.6 из SICP […]

Comment from Dima
Date: June 22, 2008, 3:35 pm

Помойму в вашем + лишняя (f …), и он выдаёт n+m+1.

Comment from hub
Date: September 30, 2008, 10:24 am

Согласен. Вычислим 1 + 2 с помощью вышеуказанных процедур, предпологая, что f -> inc
x->0:
(code)
(((plus one two) inc) 0)
(/code)
Получаем 4, а должно быть 3. => одна f лишняя, т.е. должно быть следующее:
(code)
(define (plus n m)
(lambda (f) (lambda (x) ((m f) ((n f) x)))))
(/code)
При проверке, процедура выдает ожидаемый результат, т.е. 3

Comment from hub
Date: September 30, 2008, 10:27 am

Согласен. Вычислим 1 + 2 с помощью вышеуказанных процедур, предпологая, что f -> inc
x->0:

(((plus one two) inc) 0)

Получаем 4, а должно быть 3. => одна f лишняя, т.е. должно быть следующее:

(define (plus n m)
(lambda (f) (lambda (x) ((m f) ((n f) x)))))

При проверке, процедура выдает ожидаемый результат, т.е. 3

Comment from трор
Date: November 18, 2008, 8:53 am

Барендрегт, Ламбда исчисление, его синтаксис и семантика. Гл. 2, 3, 6 хотя бы почитайте. Очень советую. Там в том числе и про различные цифровые системы.
–трор

Comment from Aera
Date: February 24, 2014, 3:24 am

Посчитал (plus one two) вручную, методом подстановки:
(lambda (f) (lambda (x) (f (f (f x)))))

Comment from Irv
Date: January 22, 2016, 2:03 pm

Действительно, в решении автора f применяется лишний раз

(define zero (lambda(f) (lambda (x) x)))

(define (inc n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (inc zero))
(define two (inc one))
(define three (inc two))
(define four (inc three))

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

((zero square) 2)
((one square) 2)
((two square) 2)
((three square) 2)
((four square) 2)

(define (add n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

(((add one one) square) 2)
(((add one two) square) 2)
(((add one three) square) 2)

Write a comment