Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 44
Текст из файла (страница 44)
Add является частью обобщенного интерфейса, который позволяет программам,2.5. Системы с обобщенными операциями187пользующимся числами, одинаковым образом обращаться к раздельным пакетам обыкновенной, рациональной и комплексной арифметики. Всякий конкретный арифметическийпакет (например, комплексная арифметика) сам по себе доступен через обобщенныепроцедуры (например, add-complex), которые связывают пакеты, предназначенные дляразличных реализаций (таких, как декартовы и полярные числа). Более того, структура системы аддитивна, так что можно проектировать отдельные арифметические пакетынезависимо и сочетать их, получая обобщенную арифметическую систему.2.5.1.
Обобщенные арифметические операцииЗадача проектирования обобщенных арифметических операций аналогична задачепроектирования обобщенных операций с комплексными числами. К примеру, нам быхотелось иметь обобщенную процедуру сложения add, которая действовала бы как обычное элементарное сложение + по отношению к обычным числам, как add-rat по отношению к рациональным числам и как add-complex по отношению к комплексным.Реализовать add и прочие обобщенные арифметические операции мы можем, следуя тойже стратегии, которую мы использовали в разделе 2.4.3 для обобщенных селекторовкомплексных чисел. К каждому числу мы прикрепим метку типа и заставим обобщенную процедуру передавать управление в нужный пакет в соответствии с типами своихаргументов.Обобщенные арифметические процедуры определяются следующим образом:(define(define(define(define(add(sub(mul(divxxxxy)y)y)y)(apply-generic(apply-generic(apply-generic(apply-generic’add’sub’mul’divxxxxy))y))y))y))Начнем с установки пакета для работы с обычными числами, то есть элементарнымичислами нашего языка.
Мы пометим их символом scheme-number. Арифметическиеоперации этого пакета — это элементарные арифметические процедуры (так что нетникакой нужды определять дополнительные процедуры для обработки непомеченныхчисел). Поскольку каждая из них принимает по два аргумента, в таблицу они заносятсяс ключом-списком (scheme-number scheme-number):(define (install-scheme-number-package)(define (tag x)(attach-tag ’scheme-number x))(put ’add ’(scheme-number scheme-number)(lambda (x y) (tag (+ x y))))(put ’sub ’(scheme-number scheme-number)(lambda (x y) (tag (- x y))))(put ’mul ’(scheme-number scheme-number)(lambda (x y) (tag (* x y))))(put ’div ’(scheme-number scheme-number)(lambda (x y) (tag (/ x y))))(put ’make ’scheme-number(lambda (x) (tag x)))’done)188Глава 2.
Построение абстракций с помощью данныхПользователи пакета Схемных чисел будут создавать (помеченные) элементарныечисла с помощью процедуры(define (make-scheme-number n)((get ’make ’scheme-number) n))Теперь, когда каркас обобщенной арифметической системы построен, мы можем безтруда добавлять новые типы чисел. Вот пакет, который реализует арифметику рациональных чисел. Обратите внимание, что благодаря аддитивности мы можем без изменений использовать код рациональной арифметики из раздела 2.1.1 в виде внутреннихпроцедур пакета:(define (install-rational-package);; внутренние процедуры(define (numer x) (car x))(define (denom x) (cdr x))(define (make-rat n d)(let ((g (gcd n d)))(cons (/ n g) (/ d g))))(define (add-rat x y)(make-rat (+ (* (numer x) (denom y))(* (numer y) (denom x)))(* (denom x) (denom y))))(define (sub-rat x y)(make-rat (- (* (numer x) (denom y))(* (numer y) (denom x)))(* (denom x) (denom y))))(define (mul-rat x y)(make-rat (* (numer x) (numer y))(* (denom x) (denom y))))(define (div-rat x y)(make-rat (* (numer x) (denom y))(* (denom x) (numer y))));; интерфейс к остальной системе(define (tag x) (attach-tag ’rational x))(put ’add ’(rational rational)(lambda (x y) (tag (add-rat x y))))(put ’sub ’(rational rational)(lambda (x y) (tag (sub-rat x y))))(put ’mul ’(rational rational)(lambda (x y) (tag (mul-rat x y))))(put ’div ’(rational rational)(lambda (x y) (tag (div-rat x y))))(put ’make ’rational(lambda (n d) (tag (make-rat n d))))’done)(define (make-rational n d)((get ’make ’rational) n d))2.5.
Системы с обобщенными операциями189Мы можем установить подобный пакет и для комплексных чисел, используя меткуcomplex. При создании пакета мы извлекаем из таблицы операции make-from-realimag и make-from-mag-ang, определенные в декартовом и полярном пакетах. Аддитивность позволяет нам использовать без изменений в качестве внутренних операцийпроцедуры add-complex, sub-complex, mul-complex и div-complex из раздела 2.4.1.(define (install-complex-package);; процедуры, импортируемые из декартова;; и полярного пакетов(define (make-from-real-imag x y)((get ’make-from-real-imag ’rectangular) x y))(define (make-from-mag-ang r a)((get ’make-from-mag-ang ’polar) r a));; внутренние процедуры(define (add-complex z1 z2)(make-from-real-imag (+ (real-part z1) (real-part z2))(+ (imag-part z1) (imag-part z2))))(define (sub-complex z1 z2)(make-from-real-imag (- (real-part z1) (real-part z2))(- (imag-part z1) (imag-part z2))))(define (mul-complex z1 z2)(make-from-mag-ang (* (magnitude z1) (magnitude z2))(+ (angle z1) (angle z2))))(define (div-complex z1 z2)(make-from-mag-ang (/ (magnitude z1) (magnitude z2))(- (angle z1) (angle z2))));; интерфейс к остальной системе(define (tag z) (attach-tag ’complex z))(put ’add ’(complex complex)(lambda (z1 z2) (tag (add-complex z1 z2))))(put ’sub ’(complex complex)(lambda (z1 z2) (tag (sub-complex z1 z2))))(put ’mul ’(complex complex)(lambda (z1 z2) (tag (mul-complex z1 z2))))(put ’div ’(complex complex)(lambda (z1 z2) (tag (div-complex z1 z2))))(put ’make-from-real-imag ’complex(lambda (x y) (tag (make-from-real-imag x y))))(put ’make-from-mag-ang ’complex(lambda (r a) (tag (make-from-mag-ang r a))))’done)Вне комплексного пакета программы могут создавать комплексные числа либо издействительной и мнимой части, либо из модуля и аргумента.
Обратите внимание, какнижележащие процедуры, которые были изначально определены в декартовом и полярном пакете, экспортируются в комплексный пакет, а оттуда во внешний мир.(define (make-complex-from-real-imag x y)((get ’make-from-real-imag ’complex) x y))Глава 2. Построение абстракций с помощью данных190complexrectangular34Рис. 2.24. Представление 3 + 4i в декартовой форме.(define (make-complex-from-mag-ang r a)((get ’make-from-mag-ang ’complex) r a))Здесь мы имеем двухуровневую систему меток. Типичное комплексное число, например 3 + 4i в декартовой форме, будет представлено так, как показано на рисунке 2.24.Внешняя метка (complex) используется, чтобы отнести число к пакету комплексныхчисел. Внутри комплексного пакета вторая метка (rectangular) относит число к декартову пакету.
В большой и сложной системе может быть несколько уровней, каждыйиз которых связан со следующим при помощи обобщенных операций. Когда объект данных передается «вниз», внешняя метка, которая используется для отнесения к нужномупакету, отрывается (при помощи вызова contents), и следующий уровень меток (еслитаковой имеется) становится доступным для дальнейшей диспетчеризации.В приведенных пакетах мы использовали add-rat, add-complex и другие арифметические процедуры ровно в таком виде, как они были написаны с самого начала.Но когда эти определения оказываются внутри различных процедур установки, отпадаетнеобходимость давать им различные имена: мы могли бы просто назвать их в обоихпакетах add, sub, mul и div.Упражнение 2.77.Хьюго Дум пытается вычислить выражение (magnitude z), где z — объект, показанный нарис.
2.24. К своему удивлению, вместо ответа 5 он получает сообщение об ошибке от applygeneric, гласящее, что у операции magnitude нет методов для типа (complex). Он показываетрезультат Лизе П. Хакер. Та заявляет: "Дело в том, что селекторы комплексных чисел для чисел сметкой complex определены не были, а были только для чисел с меткой polar и rectangular.Все, что требуется, чтобы заставить это работать — это добавить к пакету complex следующее:"(put(put(put(put’real-part ’(complex) real-part)’imag-part ’(complex) imag-part)’magnitude ’(complex) magnitude)’angle ’(complex) angle)Подробно опишите, почему это работает.
В качестве примера, проследите все процедуры, которыевызываются при вычислении (magnitude z), где z — объект, показанный на рис. 2.24. В частности, сколько раз вызывается apply-generic? На какую процедуру она диспетчирует в каждомслучае?Упражнение 2.78.В пакете scheme-number внутренние процедуры, в сущности, ничего не делают, только вызываютэлементарные процедуры +, -, и т.д. Прямо использовать примитивы языка не было возможности,2.5. Системы с обобщенными операциями191поскольку наша система меток типов требует, чтобы каждый объект данных был снабжен меткой.Однако на самом деле все реализации Лиспа имеют систему типов, которую они используют внутри себя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
