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

29 February, 2008 (21:45) | Решения упражнений

Начнем с обобщенной процедуры raise, которая будет поднимать объект на один уровень в башне типов. Она записывается абсолютно аналогично остальным обобщенным операциям:

(define (raise x) (apply-generic 'raise x))

Просто. Но для того, чтобы она заработала, необходимо определить конкретные реализации подъема типа в башне для всех типов, кроме последнего, самого верхнего в иерархии. Мне кажется, что помещать соответствующие процедуры подъема объекта типа А к находящемуся непосредственно над ним в башне типу В лучше в пакете, описывающем тип В, так как именно более общий тип должен заботиться о приведении к себе частных. Впрочем, возможно, есть и лучшее решение.

Итак, в пакет для работы с целыми числами (integer) мы не включаем ничего.

В пакет для работы с рациональными числами (rational) включаем строки:

(define (integer->rational n) 
  (make-rational n 1)) 
(put 'raise '(integer) integer->rational)

В пакет для работы с действительными числами (real) включаем:

(define (rational->real r) 
  (make-real (/ (numer r) (denom r)))) 
(put 'raise '(rational) rational->real)

Пакет комплексных чисел (complex) дополняем так:

(define (real->complex x) 
  (make-complex-from-real-imag x 0)) 
(put 'raise '(real) real->complex)

Все. Теперь подъем по иерархии типов с помощью raise будет работать.

Comments

Pingback from SICP по-русски » Решение упражнения 2.85 из SICP
Date: March 5, 2008, 10:06 pm

[…] Определение операции проецирования project похоже на определение операции raise. […]

Comment from thror
Date: May 6, 2009, 9:47 pm

и… Оказывается все это не работает:) Теперь объясню почему.

“…так как более общий тип должен заботиться о приведении к себе частных…”-это что, из книги-бреда типа буча или рамбо? Не слушайте вы их.

Сначала в общем объясню. Потом перейду к частностям. Итак. На самом деле процесс “поднятия” или “приведения” типа T к надтипу Х состоит из двух этапов, условно “анализ” и “синтез”. Под анализом мы понимаем выделение существенно важных составных частей цельного объекта типа Т. Под синтезом-непосредственно конструирование из них объекта надтипа Х. Существенно то, что фаза анализа должна проводиться той компонентой системы, которая знает о внутреннем устройстве типа Т-непосредственно или через экспортируемые селекторы…

Но беда вот в чем-поскольку приведение raise будет обычной обобщенной процедурой, внутри нее объект типа Т будет уже не помеченым тэгом типа-вспомните как работает apply-generic. Значит экспорт селекторов нам не поможет.

Вывод один-raise должна определяться внутри пакета для приводимого типа Т, и использовать его внутренние селекторы. Внутренние. И еще раз повторю-внутренние. И экспортируемый конструктор типа Х.

(возникает вопрос-что за numer и denom фигурируют у автора? Если обобщенные-то они не будут работать при такой схеме, ведь у числа передаваемого им уже не будет тега. Если внутренние для пакета рациональных чисел, то это нарушение принципа абстракции)

Comment from thror
Date: May 6, 2009, 9:56 pm

то есть, до тех пор, пока мы не вызывали raise при помощи apply-generic, мы могли помешать ее куда угодно, и пользоваться в ней экспортируемыми селекторами, позволяя им снимать тэг типа.

Но как только мы вызываем raise при помощи apply-generic, следует помнить, что тэг типа внутри raise будет уже снят, и обобщенными экспортированными селекторами нам уже не воспользоваться.

Comment from thror
Date: May 24, 2009, 9:11 pm

есть также отличный аргумент против того, чтоб raise была определена через apply-generic.

Предположим, что raise вызывает apply-generic, как советует автор. Но тогда в случае если raise не определена для типа ее аргумента, она будет пытаться привести аргумент к подходящему типу (как следует из кода apply-generic) то есть “поднять” свой аргумент при помощи той же raise-и конечно ее войдет в бесконечный цикл.

Разрешить этот вопрос мы можем лишь усложнив определение raise, добавив соответствующие проверки,но поверьте, после экспериментов я выяснил, что лучше уж в таком случае вообще никак не определять raise, а работать с ней в таком стиле

(let ((v (get-coercion 'raise (type-tag arg))))
(if v
...
...))

Comment from Максим
Date: December 22, 2014, 10:21 pm

Просто и со вкусом:
coercions (в отдельной таблице coercions, согласно секции по штуке на тип):


(define (scheme-num->rational x)
(make-rational x 1))
(define (rational->real x)
(make-real (/ (numer x) (denom x))))
(define (real->complex x)
(make-complex-from-real-imag x 0))
(put-coercion 'scheme-num 'rational scheme-num->rational)
(put-coercion 'rational 'real rational->real)
(put-coercion 'real 'complex real->complex)

Процедура raise:

(define (raise obj)
(let ((type-tag (type-tag obj)))
(let ((supertype (get 'raise type-tag)))
(if supertype
((get-coercion type-tag supertype) obj)
obj))))

Пакеты арифметики:

(put 'raise 'scheme-num 'rational)
(put 'raise 'rational 'real)
(put 'raise 'real 'complex)

Пока писал, вспомнил что процедура put вроде как оперирует лишь над операциями (судя по первому её представлению), ну надеюсь что в главе 3.3 окажется что туда можно и обычный символ положить. И вообще, написать процедуру которая будет просто возвращать символ не составляет труда.

Comment from Максим
Date: December 22, 2014, 10:53 pm

Thror, если мы определим глобальную make-real как:

(define (make-real x)
((get 'make 'real) x))

а в интерфейсе пакета вещественных чисел, для общения с глобальными операциями:

(put 'make 'real (lambda (x) (tag (make-real x)))
А также внутреннюю процедуру make-real:
(define (make-real x) (* x 1.0))

Тогда получим (пример с подстановкой):
(rational->real (rational 2 3))
(make-real(глоб.) (/ (numer (rational 2 3)) (denom (rational 2 3))))
Тут мы обнаружим что, аналогично комплексным числам, не прописали глобальные селекторы и не добавили их в интерфейс пакета рациональных чисел:

Интерфейс пакета (внутренние уже определены):
(put 'numer 'rational numer)
(put 'denom 'rational denom)
Глобальные селекторы:
(define (numer x) (apply-generic 'numer x))
(define (denom x) (apply-generic 'denom x))

По итогу глобальные числитель со знаменателем сорвут метку типа с нашего (rational 2 3) и дальше посчитают всё как по нотам.
В итоге получится: (make-real (/ 2 3)) = (real 0.666666667) или типа того.
Это просто как рука помощи тем, кто так же как и я заколебался терять нить что как и в какой пакет отправляет и каждый раз это от руки выводить.

Comment from Максим
Date: December 23, 2014, 4:15 pm

Вообще всё нормально должно работать, я подсмотрел в блогах что те, кто не просто “в уме” эту секцию решает а с помощью интерпретатора, реализуют operation-and-type table и coercion table через хэш-таблицы.
Вот код:

(define main-table (make-hash))
(define (put op type proc) (hash-set! (list op type) proc))
Книжный вариант get можно реализовать так:
(define (get op type)
(let ((pick-item (hash-ref mt (list op type) '())))
(if (null? pick-item)
#f
pick-item)))

Comment from Максим
Date: December 23, 2014, 4:17 pm

Ошибка:

(define (put op type proc) (hash-set! main-table (list op type) proc))
Необходимо указать в какую таблицу записываем данные

Comment from Максим
Date: December 23, 2014, 4:18 pm


(define (get op type)
(let ((pick-item (hash-ref main-table (list op type) '())))
(if (null? pick-item)
#f
pick-item)))

Comment from hi_artem
Date: April 2, 2015, 8:40 pm

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

(define (raise x) (apply-generic 'raise x))

;; add into scheme-number package
(put 'raise 'integer
(lambda (x) (make-rational x 1)))

;; add into rational package
(put 'raise 'rational
(lambda (x) (make-real (/ (numer x) (denom x)))))

;; add into real package
(put 'raise 'real
(lambda (x) (make-from-real-imag x 0)))

Отсюда: http://community.schemewiki.org/?sicp-ex-2.83

Write a comment