Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 47
Текст из файла (страница 47)
Потребуется придумать способ проверки, какой из двух типов выше по башне. Сделайте это способом, «совместимым» с остальной системой, так, чтобы не возникало проблем придобавлении к башне новых типов.Упражнение 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, который возвращаетцелое число, ближайшее к своему аргументу.2.5. Системы с обобщенными операциями199В символьной алгебре типичными абстракциями являются такие понятия, как линейнаякомбинация, многочлен, рациональная или тригонометрическая функция.
Мы можемрассматривать их как составные «типы», которые часто бывают полезны при управленииобработкой выражений. Например, выражениеx2 sin(y 2 + 1) + cos 2y + cos(y 3 − 2y 2 )можно рассматривать как многочлен по x с коэффициентами, которые являются тригонометрическими функциями многочленов по y, чьи коэффициенты, в свою очередь, целыечисла.Здесь мы не будем пытаться разработать полную систему для работы с алгебраическими выражениями. Такие системы — очень сложные программы, использующие глубокие математические знания и элегантные алгоритмы. Мы собираемся описать толькоодну простую, но важную часть алгебраических операций — арифметику многочленов.Мы проиллюстрируем типы решений, которые приходится принимать разработчику подобной системы, и то, как применить идеи абстракции данных и обобщенных операций,чтобы с их помощью организовать работу.Арифметика многочленовПервая задача при разработке системы для проведения арифметических операций надмногочленами — решить, что именно представляет собой многочлен.
Обычно многочленыопределяют по отношению к тем или иным переменным. Ради простоты, мы ограничимся многочленами только с одной переменной54. Мы определяем многочлен как суммутермов, каждый из которых представляет собой либо коэффициент, либо переменную,возведенную в степень, либо произведение того и другого. Коэффициент определяетсякак алгебраическое выражение, не зависящее от переменной многочлена. Например,5x2 + 3x + 7есть простой многочлен с переменной x, а(y 2 + 1)x3 + (2y)x + 1есть многочлен по x, коэффициенты которого — многочлены по y.Уже здесь мы сталкиваемся с несколькими неудобными деталями. Является ли первый из приведенных многочленов тем же объектом, что 5y 2 + 3y + 7? Разумный ответ наэтот вопрос таков: «если мы рассматриваем многочлен как чисто математическую функцию, то да, но если как синтаксическую форму, то нет». Второй пример алгебраическиэквивалентен многочлену по y, коэффициенты которого — многочлены по x.
Должнали наша система распознавать это? Наконец, существуют другие способы представления многочленов — например, как произведение линейных множителей, как множествокорней (для многочлена с одной переменной), или как список значений многочлена в за54 С другой стороны, мы разрешаем многочлены, коэффициенты которых сами по себе являются многочленами от других переменных. По существу, это дает нам такую же выразительную силу, что и у полной системысо многими переменными, хотя и ведет к проблемам приведения, как это обсуждается ниже.200Глава 2.
Построение абстракций с помощью данныхданном множестве точек55 . Мы можем обойти эти вопросы, решив, что в нашей системеалгебраических вычислений «многочлен» будет определенной синтаксической формой, ане ее математическим значением.Теперь пора подумать, как мы будем осуществлять арифметические операции надмногочленами. В нашей упрощенной системе мы рассмотрим только сложение и умножение. Более того, мы будем настаивать, чтобы два многочлена, над которыми проводитсяоперация, имели одну и ту же переменную.К проектированию системы мы приступим, следуя уже знакомой нам дисциплинеабстракции данных. Мы будем представлять многочлены в виде структуры данных подназванием poly, которая состоит из переменной и набора термов.
Мы предполагаем, чтоимеются селекторы variable и term-list, которые получают из poly эти данные, иконструктор make-poly, который собирает poly из переменной и списка термов. Переменная будет просто символом, так что для сравнения переменных мы сможем использовать процедуру same-variable? из раздела 2.3.2. Следующие процедуры определяютсложение и умножение многочленов:(define (add-poly p1 p2)(if (same-variable? (variable p1) (variable p2))(make-poly (variable p1)(add-terms (term-list p1)(term-list p2)))(error "Многочлены от разных переменных -- ADD-POLY"(list p1 p2))))(define (mul-poly p1 p2)(if (same-variable? (variable p1) (variable p2))(make-poly (variable p1)(mul-terms (term-list p1)(term-list p2)))(error "Многочлены от разных переменных -- MUL-POLY"(list p1 p2))))Чтобы включить многочлены в нашу обобщенную арифметическую систему, нам потребуется снабдить их метками типа.
Мы будем пользоваться меткой polynomial ивносить соответствующие операции над помеченными многочленами в таблицу операций. Весь свой код мы включим в процедуру установки пакета многочленов, подобнопакетам из раздела 2.5.1:(define (install-polynomial-package);; внутренние процедуры;; представление poly(define (make-poly variable term-list)(cons variable term-list))55 В случае многочленов с одной переменной задание значений многочлена в определенном множестве точекможет быть особенно удачным представлением.
Арифметика многочленов получается чрезвычайно простой.Чтобы получить, скажем, сумму двух представленных таким образом многочленов, достаточно сложить значения в соответствующих точках. Чтобы перейти обратно к более привычному представлению, можно использовать формулу интерполяции Лагранжа, которая показывает, как восстановить коэффициенты многочленастепени n, имея его значения в n + 1 точке.2.5. Системы с обобщенными операциями201(define (variable p) (car p))(define (term-list p) (cdr p))hпроцедуры same-variable? и variable? из раздела 2.3.2i;; представление термов и списков термовhпроцедуры adjoin-term ... coeff из текста нижеi(define (add-poly p1 p2) ...
)hпроцедуры, которыми пользуетсяadd-polyi(define (mul-poly p1 p2) ... )hпроцедуры, которыми пользуетсяmul-polyi;; интерфейс к остальной системе(define (tag p) (attach-tag ’polynomial p))(put ’add ’(polynomial polynomial)(lambda (p1 p2) (tag (add-poly p1 p2))))(put ’mul ’(polynomial polynomial)(lambda (p1 p2) (tag (mul-poly p1 p2))))(put ’make ’polynomial(lambda (var terms) (tag (make-poly var terms))))’done)Сложение многочленов происходит по термам. Термы одинакового порядка (то естьимеющие одинаковую степень переменной многочлена) нужно скомбинировать. Это делается при помощи порождения нового терма того же порядка, в котором коэффициентявляется суммой коэффициентов слагаемых.
Термы одного слагаемого, для которых нетсоответствия в другом, просто добавляются к порождаемому многочлену-сумме.Для того, чтобы работать со списками термов, мы предположим, что имеется конструктор the-empty-termlist, который возвращает пустой список термов, и конструктор adjoin-term, который добавляет к списку термов еще один.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
