Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 43
Текст из файла (страница 43)
В apply-generic значением op являетсяпервый аргумент вызова apply-generic, а значением args список остальных аргументов.Кроме того, apply-generic пользуется элементарной процедурой apply, которая принимает два аргумента: процедуру и список. Apply вызывает процедуру, используя элементы списка как аргументы. Например,(apply + (list 1 2 3 4))возвращает 10.2.4. Множественные представления для абстрактных данных183Заметим, что они не изменяются, если в систему добавляется новое представление.Кроме того, мы можем из той же таблицы получать конструкторы, которые будут использоваться программами, внешними по отношению к пакетам, для изготовления комплексных чисел из действительной и мнимой части либо из модуля и аргумента.
Как ив разделе 2.4.2, мы порождаем декартово представление, если нам дают действительнуюи мнимую часть, и полярное, если дают модуль и аргумент:(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))Упражнение 2.73.В разделе 2.3.2 описывается программа, которая осуществляет символьное дифференцирование:(define (deriv exp var)(cond ((number? exp) 0)((variable? exp) (if (same-variable? exp var) 1 0))((sum? exp)(make-sum (deriv (addend exp) var)(deriv (augend exp) var)))((product? exp)(make-sum(make-product (multiplier exp)(deriv (multiplicand exp) var))(make-product (deriv (multiplier exp) var)(multiplicand exp))))hЗдесь можно добавить еще правилаi(else (error "неизвестный тип выражения -- DERIV" exp))))Можно считать, что эта программа осуществляет диспетчеризацию по типу выражения, котороетребуется продифференцировать.
В этом случае «меткой типа» элемента данных является символалгебраической операции (например, +), а операция, которую нужно применить – deriv. Эту программу можно преобразовать в управляемый данными стиль, если переписать основную процедурувзятия производной в виде(define (deriv exp var)(cond ((number? exp) 0)((variable? exp) (if (same-variable? exp var) 1 0))(else ((get ’deriv (operator exp)) (operands exp)var))))(define (operator exp) (car exp))(define (operands exp) (cdr exp))а.
Объясните, что происходит в приведенном фрагменте кода. Почему нельзя включить в операцию выбора, управляемого данными, предикаты number? и variable??б. Напишите процедуры для вычисления производных от суммы и произведения, а также дополнительный код, чтобы добавить их к таблице, которой пользуется приведенный фрагмент.184Глава 2. Построение абстракций с помощью данныхв. Выберите еще какое-нибудь правило дифференцирования, например для возведения в степень(упражнение 2.56), и установите его в систему.г. В этой простой алгебраической системе тип выражения — это алгебраическая операция верхнего уровня.
Допустим, однако, что мы индексируем процедуры противоположным образом, такчто строка диспетчеризации в deriv выглядит как((get (operator exp) ’deriv) (operands exp) var)Какие изменения потребуются в системе дифференцирования?Упражнение 2.74.Insatiable Enterprises, Inc. — децентрализованная компания-конгломерат, которая состоит из большого количества независимых подразделений, раскиданных по всему миру. Недавно вычислительные мощности компании были связаны умной вычислительной сетью, создающей для пользователяиллюзию, что он работает с единым компьютером. Президент компании, когда она в первый разпытается воспользоваться способностью системы осуществлять доступ к файлам подразделений, сизумлением и ужасом обнаруживает, что, несмотря на то, что все эти файлы реализованы в видеструктур данных на Scheme, конкретная структура данных отличается от подразделения к подразделению.
Спешно созывается совещание менеджеров подразделений, чтобы найти стратегию,которая позволила бы собрать файлы в единую систему для удовлетворения нужд главного офиса,и одновременно сохранить существующую автономию подразделений.Покажите, как такую стратегию можно реализовать при помощи программирования, управляемого данными. К примеру, предположим, что сведения о персонале каждого подразделенияустроены в виде единого файла, который содержит набор записей, проиндексированных по именислужащего. Структура набора данных от подразделения к подразделению различается.
Более того,каждая запись сама по себе — набор сведений (в разных подразделениях устроенный по-разному),в котором информация индексируется метками вроде address (адрес) или salary (зарплата). Вчастности:а. Для главного офиса реализуйте процедуру get-record, которая получает запись, относящуюся к указанному служащему, из указанного файла персонала. Процедура должна быть применимак файлу любого подразделения. Объясните, как должны быть структурированы файлы отдельныхподразделений.
В частности, какую информацию о типах нужно хранить?б. Для главного офиса реализуйте процедуру get-salary, которая возвращает зарплату указанного служащего из файла любого подразделения. Как должна быть устроена запись, чтобымогла работать эта процедура?в. Для главного офиса напишите процедуру find-employee-record. Она должна искать вфайлах всех подразделений запись указанного служащего и возвращать эту запись. Предположим, что в качестве аргументов эта процедура принимает имя служащего и список файлов всехподразделений.г.
Какие изменения требуется внести в систему, чтобы внести в центральную систему информацию о новых служащих, когда Insatiable поглощает новую компанию?Передача сообщенийОсновная идея программирования, управляемого данными, состоит в том, чтобы работать с обобщенными операциями в программах при помощи явных манипуляций стаблицами операций и типов, вроде таблицы на рисунке 2.22. В стиле программирования, который мы применяли в разделе 2.4.2, диспетчеризация по типу организуется2.4. Множественные представления для абстрактных данных185внутри каждой операции, и каждая операция должна сама заботиться о своей диспетчеризации. Это, в сущности, разбивает таблицу операций и типов на строки, и каждаяобобщенная операция представляет собой строку таблицы.Альтернативой такой стратегии реализации будет разбить таблицу по столбцам ивместо «умных операций», которые диспетчируют по типам данных, работать с «умными объектами данных», которые диспетчируют по именам операций.
Мы можем этогодобиться, если устроим все так, что объект данных, например комплексное число в декартовом представлении, будет представляться в виде процедуры, которая в качествевхода воспринимает имя операции и осуществляет соответствующее ей действие. Притакой организации можно написать make-from-real-imag в виде(define (make-from-real-imag x y)(define (dispatch op)(cond ((eq? op ’real-part) x)((eq? op ’imag-part) y)((eq? op ’magnitude)(sqrt (+ (square x) (square y))))((eq? op ’angle) (atan y x))(else(error "Неизвестная оп.
-- MAKE-FROM-REAL-IMAG" op))))dispatch)Соответствующая процедура apply-generic, которая применяет обобщенную операцию к аргументу, просто скармливает имя операции объекту данных и заставляет егоделать всю работу48 :(define (apply-generic op arg) (arg op))Обратите внимание, что значение, возвращаемое из make-from-real-imag, являетсяпроцедурой — это внутренняя процедура dispatch.
Она вызывается, когда applygeneric требует выполнить обобщенную операцию.Такой стиль программирования называется передача сообщений (message passing).Имя происходит из представления, что объект данных — это сущность, которая получает имя затребованной операции как «сообщение». Мы уже встречались с примеромпередачи сообщений в разделе 2.1.3, где мы видели, как cons, car и cdr можно определить безо всяких объектов данных, с одними только процедурами. Теперь мы видим,что передача сообщений не математический трюк, а полезный метод организации систем с обобщенными операциями.
В оставшейся части этой главы мы будем продолжатьпользоваться программированием, управляемым данными, а не передачей сообщений, ирассмотрим обобщенные арифметические операции. Мы вернемся к передаче сообщенийв главе 3, и увидим, что она может служить мощным инструментом для структурирования моделирующих программ.Упражнение 2.75.Реализуйте в стиле передачи сообщений конструктор make-from-mag-ang. Он должен бытьаналогичен приведенной выше процедуре make-from-real-imag.48 Утакой организации есть ограничение: она допускает обобщенные процедуры только от одного аргумента.Глава 2. Построение абстракций с помощью данных186Программы, использующие числаadd sub mul divПакет обобщенной арифметикиadd-rat sub-ratmul-rat div-ratРациональнаяарифметикаadd-complex sub-complex+ - * /mul-complex div-complexКомплексная арифметикаДекартоваОбыкновеннаяарифметикаПолярнаяСписковая структура и элементарная арифметика машиныРис. 2.23.
Обобщенная арифметическая истема.Упражнение 2.76.Когда большая система с обобщенными операциями развивается, могут потребоваться новые типыобъектов данных или новые операции. Для каждой из трех стратегий — обобщенные операции сявной диспетчеризацией, стиль, управляемый данными, и передача сообщений, – опишите, какиеизменения нужно произвести в системе, чтобы добавить новый тип или новую операцию.
Какаяорганизация лучше подходит для системы, в которую часто добавляются новые типы? Какая длясистемы, где часто появляются новые операции?2.5. Системы с обобщенными операциямиВ предыдущем разделе мы увидели, как проектировать системы, где объекты данных могут быть представлены более чем одним способом. Основная идея состоит в том,чтобы связать код, который определяет операции над данными, и многочисленные реализации данных, при помощи обобщенных процедур интерфейса. Теперь мы увидим, чтоту же самую идею можно использовать не только для того, чтобы определять обобщенные операции для нескольких реализаций одного типа, но и для того, чтобы определятьоперации, обобщенные относительно нескольких различных типов аргументов.
Мы ужевстречались с несколькими различными пакетами арифметических операций: элементарная арифметика (+, -, *, /), встроенная в наш язык, арифметика рациональных чисел(add-rat, sub-rat, mul-rat, div-rat) из раздела 2.1.1 и арифметика комплексныхчисел, которую мы реализовали в разделе 2.4.3. Теперь мы, используя методы программирования, управляемого данными, создадим пакет арифметических операций, которыйвключает все уже построенные нами арифметические пакеты.На рисунке 2.23 показана структура системы, которую мы собираемся построить.Обратите внимание на барьеры абстракции. С точки зрения человека, работающего с«числами», есть только одна процедура add, которая работает, какие бы числа ей нидали.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
