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

Хьюго Дум заметил, что apply-generic может пытаться привести аргументы к типу друг друга даже тогда, когда их типы и так совпадают. Следовательно, решает он, нам нужно вставить в таблицу приведения процедуры, которые «приводят» аргументы каждого типа к нему самому. Например, в дополнение к приведению scheme-number->complex, описанному выше, он бы написал еще:

(define (scheme-number->scheme-number n) n) (define (complex->complex z) z) (put-coercion scheme-number scheme-number scheme-number->scheme-number) (put-coercion complex complex complex->complex)

a.Если установлены процедуры приведения типов, написанные Хьюго, что произойдет, когда apply-generic будет вызвана с двумя аргументами типа scheme-number или двумя аргументами типа complex для операции, которая не находится в таблице для этих типов? Допустим, например, что мы определили обобщенную процедуру возведения в степень:

(define (exp x y) (apply-generic exp x y))

и добавили процедуру возведения в степень в пакет чисел Scheme и ни в какой другой:

;; следующие строки добавляются в пакет scheme-number (put exp (scheme-number scheme-number)

(lambda (x y) (tag (expt x y)))) ;используется

;элементарная expt

Что произойдет, если мы позовем exp с двумя комплексными числами в качестве аргументов?

b.Прав ли Хьюго, что нужно что-то сделать с приведением однотипных аргументов, или все и так работает правильно?

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

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

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

отношения между различными типами сущностей (то, что философы называют «онтологией»), оказывается невероятно сложным делом. Основная разница между той путаницей, которая была десять лет назад, и той, которая есть сейчас, состоит в том, что теперь множество неадекватных онтологических теорий оказалось воплощено в массе соответственно неадекватных языков программирования. Например, львиная доля сложности объектно-ориентированных языков программирования - и мелких невразумительных различий между современными объектно-ориентированными языками, - сосредоточена в том, как рассматриваются обобщенные операции над взаимосвязанными типами. Наше собственное описание вычислительных объектов в главе 3 полностью избегает этих вопросов. Читатели, знакомые с объектно-ориентированным программированием, заметят, что нам есть, что сказать в главе 3 о локальном состоянии, но мы ни разу не упоминаем «классы» или «наследование». Мы подозреваем, что на самом деле эти проблемы нельзя рассматривать только в терминах проектирования языков программирования, без обращения к работам по представлению знаний и автоматическому логическому выводу.

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

Предположим, что Вы разрабатываете обобщенную арифметическую систему для работы с башней типов, показанной на рис. 2.25: целые, рациональные, действительные, комплексные. Для каждого из типов (кроме комплексного), разработайте процедуру, поднимающую объект на один уровень в башне. Покажите, как ввести обобщенную операцию raise, которая будет работать для всех типов (кроме комплексных чисел).

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

Используя операцию raise из упражнения 2.83, измените процедуру apply-generic так, чтобы она приводила аргументы к одному типу путем последовательного подъема, как описано в этом разделе. Потребуется придумать способ проверки, какой из двух типов выше по башне. Сделайте это способом, «совместимым» с остальной системой, так, чтобы не возникало проблем при добавлении к башне новых типов.

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

В этом разделе упоминался метод «упрощения» объекта данных путем спуска его по башне насколько возможно вниз. Разработайте процедуру drop, которая делает это для башни, описанной в упражнении 2.83. Ключ к задаче состоит в том, что надо решить некоторым общим способом, можно ли понизить объект в типе. Например, комплексное число 1.5 + 0i можно опустить до real, комплексное число 1 + 0i до integer, а комплексное число 2 + 3i никуда понизить нельзя. Вот план того, как определить, можно ли понизить объект: для начала определите обобщенную операцию project, которая «сталкивает» объект вниз по башне. Например, проекция комплексного числа будет состоять в отбрасывании его мнимой части. Тогда число можно сдвинуть вниз в том случае, если, спроецировав его, а затем подняв обратно до исходного типа, мы получаем нечто, равное исходному числу. Покажите как реализовать эту идею в деталях, написав процедуру drop, которая опускает объект как можно ниже. Потребуется разработать различные операции проекции53 и установить project в системе в качестве обобщенной операции. Вам также потребуется обобщенный предикат равенства, подобный описанному в упражнении 2.79. Наконец, используя drop, перепишите apply-generic из упражнения 2.84, чтобы она «упрощала» свои результаты.

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

Допустим, нам хочется работать с комплексными числами, чьи действительные и мнимые части, модули и аргументы могут быть обыкновенными числами, рациональными числами либо любыми другими, какие нам захочется добавить к системе. Опишите и реализуйте изменения в системе, которые потребуются, чтобы добавить такую возможность. Вам придется определить операции вроде sine (синус) и cosine (косинус), обобщенные на обыкновенные и рациональные числа.

2.5.3 Пример: символьная алгебра

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

53Действительное число можно спроецировать на целое при помощи примитива round, который возвращает целое число, ближайшее к своему аргументу.

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

x2 sin(y2 + 1) + cos 2у + cos(y3 - 2y2)

можно рассматривать как многочлен по x с коэффициентами, которые являются тригонометрическими функциями многочленов по у, чьи коэффициенты, в свою очередь, целые числа.

Здесь мы не будем пытаться разработать полную систему для работы с алгебраическими выражениями. Такие системы - очень сложные программы, использующие глубокие математические знания и элегантные алгоритмы. Мы собираемся описать только одну простую, но важную часть алгебраических операций - арифметику многочленов. Мы проиллюстрируем типы решений, которые приходится принимать разработчику подобной системы, и то, как применить идеи абстракции данных и обобщенных операций, чтобы с их помощью организовать работу.

Арифметика многочленов

Первая задача при разработке системы для проведения арифметических операций над многочленами - решить, что именно представляет собой многочлен. Обычно многочлены определяют по отношению к тем или иным переменным. Ради простоты, мы ограничимся многочленами только с одной переменной.54 Мы определяем многочлен как сумму термов, каждый из которых представляет собой либо коэффициент, либо переменную, возведенную в степень, либо произведение того и другого. Коэффициент определяется как алгебраическое выражение, не зависящее от переменной многочлена. Например,

5x2 + 3x + 7 есть простой многочлен с переменной x, а

(у2 + 1)x3 + (2y)x +1

есть многочлен по x, коэффициенты которого - многочлены по у.

Уже здесь мы сталкиваемся с несколькими неудобными деталями. Является ли первый из приведенных многочленов тем же объектом, что 5у2 + 3у + 7? Разумный ответ на этот вопрос таков: «если мы рассматриваем многочлен как чисто математическую функцию, то да, но если как синтаксическую форму, то нет». Второй пример алгебраически эквивалентен многочлену по у, коэффициенты которого - многочлены по x. Должна ли наша система распознавать

54С другой стороны, мы разрешаем многочлены, коэффициенты которых сами по себе являются многочленами от других переменных. По существу, это дает нам такую же выразительную силу, что и у полной системы со многими переменными, хотя и ведет к проблемам приведения, как это обсуждается ниже.