Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 50
Текст из файла (страница 50)
Теперь у НОД целые коэффициенты, но они больше, чем коэффициенты P1 . Измените gcdterms, чтобы она убирала общий множитель из коэффициентов ответа путем деления всех коэффициентов на их (целочисленный) НОД.Итак, вот как привести рациональную функцию к наименьшему знаменателю:• Вычислите НОД числителя и знаменателя, используя версию gcd-terms изупражнения 2.96.• Когда Вы получаете НОД, домножьте числитель и знаменатель на множитель целости, прежде чем делить на НОД, чтобы при делении не получить дробных коэффициентов. В качестве множителя можно использовать старший коэффициент НОД,возведенный в степень 1 + O1 − O2 , где O2 – порядок НОД, а O1 — максимум из порядков числителя и знаменателя.
Так Вы добьетесь того, чтобы деление числителя изнаменателя на НОД не привносило дробей.• В результате этой операции Вы получите числитель и знаменатель с целыми коэффициентами. Обычно из-за всех множителей целости коэффициенты окажутся оченьбольшими, стало быть, на последнем шаге следует избавиться от лишних множителей,вычислив (целый) наибольший общий делитель числителя и знаменателя и поделив нанего все термы.Упражнение 2.97.а. Реализуйте этот алгоритм как процедуру reduce-terms, которая принимает в качествеаргументов два списка термов n и d и возвращает список из nn и dd, которые представляют собойn и d, приведенные к наименьшему знаменателю по вышеописанному алгоритму.
Напишите, крометого, процедуру reduce-poly, подобную add-poly, которая проверяет, чтобы два poly имелиодну и ту же переменную. Если это так, reduce-poly откусывает эту переменную и передаетоставшуюся часть задачи в reduce-terms, а затем прикрепляет переменную обратно к двумспискам термов, которые получены из reduce-terms.б. Определите процедуру, аналогичную reduce-terms, которая делает то, что делала для целых чисел исходная make-rat:(define (reduce-integers n d)(let ((g (gcd n d)))(list (/ n g) (/ d g))))Глава 2. Построение абстракций с помощью данных210и определите reduce как обобщенную операцию, которая вызывает apply-generic и диспетчирует либо к reduce-poly (если аргументы — многочлены), либо к reduce-integers (дляаргументов типа scheme-number). Теперь Вы легко можете заставить пакет рациональной арифметики приводить дроби к наименьшему знаменателю, потребовав от make-rat звать reduceпрежде, чем сочетать данные числитель и знаменатель в процессе порождения рационального числа.
Теперь система обрабатывает рациональные выражения и для целых чисел, и для многочленов.Чтобы проверить программу, попробуйте пример, который приведен в начале этого расширенногоупражнения:(define(define(define(definep1p2p3p4(make-polynomial(make-polynomial(make-polynomial(make-polynomial’x’x’x’x’((1’((3’((1’((21)(0 1))))1)(0 -1))))1))))1)(0 -1))))(define rf1 (make-rational p1 p2))(define rf2 (make-rational p3 p4))(add rf1 rf2)Посмотрите, удалось ли Вам получить правильный ответ, правильно приведенный к наименьшемузнаменателю.Вычисление НОД находится в центре всякой системы, работающей с рациональнымичислами. Алгоритм, который мы использовали в тексте, хотя математически он естествен, работает очень медленно. Медлительность эта проистекает отчасти из большогоколичества операций деления, а отчасти из огромного размера промежуточных коэффициентов, которые порождаются в ходе псевдоделения.
Одна из активно разрабатываемыхобластей в теории систем алгебраических манипуляций – построение более быстрыхалгоритмов для вычисления НОД многочленов62.62 Изящный и чрезвычайно эффективный метод вычисления НОД многочленов был открыт Ричардом Зиппелем (Zippel 1979). Этот метод — вероятностный алгоритм, подобно быстрому тесту на простоту числа,описанному в главе 1.
Книга Зиппеля Zippel 1993 описывает этот метод, а также другие способы нахожденияНОД многочленов.ГЛАВА 3МОДУЛЬНОСТЬ,ОБЪЕКТЫ И СОСТОЯНИЕMetabllon napaÔetai(Изменяясь, оно остается неподвижным)ГераклитPlus ça change, plus c’est la même choseАльфонс КаррВ предыдущих главах мы ввели основные элементы, из которых строятся программы.Мы видели, как элементарные процедуры и элементарные данные, сочетаясь, образуют составные сущности; мы стали понимать, что без абстракции нельзя справиться сосложностью больших систем.
Однако этих инструментов недостаточно для разработкипрограмм. Для эффективного синтеза программ требуются также организационные принципы, которые помогали бы нам сформулировать общий проект программы. В частности,нам нужны стратегии для построения больших программ по принципу модульности(modularity): чтобы программы «естественным» образом делились на логически цельныекуски, которые можно разрабатывать и поддерживать независимо друг от друга.Существует мощная стратегия разработки, которая особенно хорошо подходит дляпостроения программ, моделирующих физические системы: воспроизводить в структурепрограммы структуру моделируемой системы.
Для каждого объекта в системе мы строимсоответствующий ему вычислительный объект. Для каждого действия в системе определяем в рамках нашей вычислительной модели символьную операцию. Используя этустратегию, мы надеемся, что расширение нашей модели на новые объекты или действияне потребует стратегических изменений в программе, а позволит обойтись только добавлением новых символьных аналогов этих объектов или действий. Если наша организациясистемы окажется удачной, то для добавления новых возможностей или отладки старыхнам придется работать только с ограниченной частью системы.Таким образом, способ, которым мы организуем большую программу, в значительнойстепени диктуется нашим восприятием моделируемой системы.
В этой главе мы исследуем две важных организационных стратегии, которые соответствуют двум достаточноразличным взглядам на мир и структуру систем. Первая из них сосредотачивается наобъектах (objects), и большая система рассматривается как собрание индивидуальныхобъектов, поведение которых может меняться со временем. Альтернативная стратегиястроится вокруг потоков (streams) информации в системе, во многом подобно тому, какв электронике рассматриваются системы обработки сигналов.Как подход, основанный на объектах, так и подход, основанный на потоках, высвечивают важные вопросы, касающиеся языков программирования. При работе с объектами212Глава 3. Модульность, объекты и состояниенам приходится думать о том, как вычислительный объект может изменяться и приэтом сохранять свою индивидуальность.
Из-за этого нам придется отказаться от подстановочной модели вычислений (раздел 1.1.5) в пользу более механистичной и в то жевремя менее привлекательной теоретически модели с окружениями (environment model).Сложности, связанные с объектами, их изменением и индивидуальностью являются фундаментальным следствием из потребности ввести понятие времени в вычислительныемодели. Эти сложности только увеличиваются, когда мы добавляем возможность параллельного выполнения программ.
Получить наибольшую отдачу от потокового подходаудается тогда, когда моделируемое время отделяется от порядка событий, происходящих в компьютере в процессе вычисления. Мы достигнем этого при помощи метода,называемого задержанными вычислениями (delayed evaluation).3.1. Присваивание и внутреннее состояние объектовОбычно мы считаем, что мир состоит из отдельных объектов, и у каждого из них естьсостояние, которое изменяется со временем. Мы говорим, что объект «обладает состоянием», если на поведение объекта влияет его история. Например, банковский счет обладает состоянием потому, что ответ на вопрос «Могу ли я снять 100 долларов?» зависитот истории занесения и снятия с него денег. Состояние объекта можно описать наборомиз одной или более переменных состояния (state variables), которые вместе содержатдостаточно информации, чтобы определить текущее поведение объекта.
В простой банковской системе состояние счета можно охарактеризовать его текущим балансом, вместотого, чтобы запоминать всю историю транзакций с этим счетом.Если система состоит из многих объектов, они редко совершенно независимы другот друга. Каждый из них может влиять на состояние других при помощи актов взаимодействия, связывающих переменные состояния одного объекта с переменными другихобъектов. На самом деле, взгляд, согласно которому система состоит из отдельных объектов, полезнее всего в том случае, когда ее можно разделить на несколько подсистем,в каждой из которых внутренние связи сильнее, чем связи с другими подсистемами.Такая точка зрения на систему может служить мощной парадигмой для организациивычислительных моделей системы.
Чтобы такая модель была модульной, ее требуетсяразделить на вычислительные объекты, моделирующие реальные объекты системы. Каждый вычислительный объект должен содержать собственные внутренние переменныесостояния (local state variables), описывающие состояние реального объекта. Посколькуобъекты в моделируемой системе меняются со временем, переменные состояния соответствующих вычислительных объектов также должны изменяться. Если мы решаем, чтопоток времени в системе будет моделироваться временем, проходящим в компьютере, тонам требуется способ строить вычислительные объекты, поведение которых меняется помере выполнения программы.
В частности, если нам хочется моделировать переменныесостояния обыкновенными символическими именами в языке программирования, в языке должен иметься оператор присваивания (assignment operator), который позволял быизменять значение, связанное с именем.3.1. Присваивание и внутреннее состояние объектов2133.1.1. Внутренние переменные состоянияЧтобы показать, что мы имеем в виду, говоря о вычислительном объекте, состояние которого меняется со временем, давайте промоделируем ситуацию снятия денег сбанковского счета.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
