Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 63
Текст из файла (страница 63)
Сочетания образуют сети ограничений (constraint networks), в которых ограничения связаны соединителями (connectors).Соединитель — это объект, который «содержит» значение, способное участвовать в одном или нескольких ограничениях. К примеру, мы знаем, что связь между температурамипо Цельсию и по Фаренгейту выглядит как 9C = 5(F − 32) Такое ограничение можноизобразить в виде сети, состоящей из элементарных ограничений — сумматора, умножителей и констант (рисунок 3.28).
На этом рисунке слева мы видим блок умножителяс тремя выводами, обозначенными m1, m2 и p. Вывод m1 присоединен к соединителюC, который будет хранить температуру по Цельсию. Вывод m2 присоединен к соединителю w, который, кроме того, связан с блоком-константой, содержащим 9. Вывод p,про который блок-умножитель говорит, что он должен быть произведением m1 и m2,связан с выводом p другого блока-умножителя, чей вывод m2 связан с константой 5, аm1 присоединен к одному из слагаемых суммы.31 Распространение ограничений появилось в системе SKETCHPAD Айвена Сазерленда (Sutherland 1963),невероятно опередившей свое время. Изящная система распространения ограничений, основанная на языкеSmalltalk, была разработана Аланом Борнингом (Borning 1977) в исследовательском центре компании Xeroxв Пало Альто.
Сассман, Столлман и Стил применили распространение ограничений к анализу электрическихцепей (Sussman and Stallman 1975; Sussman and Steele 1980). TK!Solver (Konopasek and Jayaraman 1984)представляет собой богатую среду моделирования, основанную на ограничениях.3.3. Моделирование при помощи изменяемых данных273Вычисления в такой сети происходят следующим образом: когда соединителю даетсязначение (пользователем либо блоком-ограничением, с которым он связан), соединительпробуждает все связанные с ним ограничения (кроме того, которое само его пробудило),и сообщает им, что у него появилось значение. Каждый пробужденный блок-ограничениеопрашивает свои выводы, чтобы определить, достаточно ли у него информации, чтобынайти значение для какого-нибудь еще соединителя.
Если да, блок присваивает соединителю значение, и тогда уже он пробуждает связанные с ним ограничения, и так далее.Например, при преобразовании между градусами Цельсия и Фаренгейта, значения w,x и y сразу устанавливаются блоками-константами соответственно в 9, 5 и 32. Соединители пробуждают умножители и сумматор, которые убеждаются, что у них нехватает информации, чтобы продолжить. Если пользователь (или какая-то другая частьсети) установит значение C в 25, пробудится левый умножитель, и сделает u равным25 · 9 = 225.
Затем u разбудит второй умножитель, который присвоит v значение 45, а vразбудит сумматор, и тот сделает значение F равным 77.Использование системы ограниченийЧтобы при помощи системы ограничений провести вышеописанное вычисление, сначала мы порождаем два соединителя, C и F, вызовами конструктора make-connector,и связываем C и F в требуемую нам сеть:(define C (make-connector))(define F (make-connector))(celsius-fahrenheit-converter C F)okПроцедура, создающая сеть, определяется так:(define (celsius-fahrenheit-converter c f)(let ((u (make-connector))(v (make-connector))(w (make-connector))(x (make-connector))(y (make-connector)))(multiplier c w u)(multiplier v x u)(adder v y f)(constant 9 w)(constant 5 x)(constant 32 y)’ok))Эта процедура порождает внутренние соединители u, v, w, x и y, а затем связывает их,как показано на рис.
3.28, при помощи элементарных ограничений adder, multiplierи constant. Как и при моделировании цифровых схем в разделе 3.3.4, способность выражать комбинации базовых элементов в виде процедур автоматически сообщает нашемуязыку средство абстракции для составных объектов.Чтобы наблюдать сеть в действии, мы подсоединим тестеры к соединителям C и Fпри помощи процедуры probe, подобной той, которая следила за сигналами в проводах274Глава 3.
Модульность, объекты и состояниев разделе 3.3.4. Установка тестера на соединителе ведет к тому, что каждый раз, когдаон получает значение, печатается сообщение:(probe "по Цельсию" C)(probe "по Фаренгейту" F)Затем мы присваиваем значение 25 соединителю C. (Третий аргумент процедуры setvalue! сообщает C, что директива исходит от пользователя.)(set-value! C 25 ’user)Тестер: по Цельсию = 25Тестер: по Фаренгейту = 77doneТестер на C просыпается и печатает значение. Кроме того, C распространяет значение посети, как описано выше.
В результате F становится равным 77, и тестер на F об этомсообщает.Теперь можно попробовать присвоить F новое значение, скажем, 212:(set-value! F 212 ’user)Ошибка! Противоречие (77 212)Соединитель жалуется, что обнаружил противоречие: его значение равно 77, а при этомкто-то пытается установить его в 212. Если мы и вправду хотим снова воспользоватьсясетью с новыми значениями, можно попросить C забыть свое старое значение:(forget-value! C ’user)Тестер: по Цельсию = ?Тестер: по Фаренгейту = ?doneС видит, что user, который изначально присвоил ему значение, отменяет его, так что Cсоглашается потерять значение, как показывает тестер, и информирует об этом остальную сеть. Эта информация в конце концов добирается до F, и у F уже не остаетсяпричин считать, что его значение равно 77.
Так что F тоже теряет значение, и тестер этоотображает.Теперь, когда у F больше нет значения, мы можем установить его в 212:(set-value! F 212 ’user)Тестер: по Фаренгейту = 212Тестер: по Цельсию = 100doneЭто новое значение, распространяясь по сети, заставляет C получить значение 100, итестер на C это регистрирует. Заметим, что одна и та же сеть используется и длятого, чтобы на основе F получить C и для того, чтобы на основе C получить F. Этаненаправленность вычислений является отличительной чертой систем, основанных наограничениях.3.3. Моделирование при помощи изменяемых данных275Реализация системы ограниченийСистема ограничений реализована на основе процедурных объектов с внутреннимсостоянием, очень похоже на модель цифровых схем из раздела 3.3.4.
Хотя базовыеобъекты системы с ограничениями несколько более сложны, система в целом проще засчет того, что незачем заботиться о планах действий и логических задержках.Базовые операции над соединителями таковы:• (has-value? hсоединительi)сообщает, есть ли у соединителя значение.• (get-value hсоединительi)возвращает текущее значение соединителя.• (set-value! hсоединительi hновое-значi hинформантi) сообщает соединителю,что информант требует установить в нем новое значение.• (forget-value! hсоединительi hотказникi) сообщает соединителю, что отказник просит его забыть значение.• (connect hсоединительi hновое-огрi) говорит соединителю, что он участвует вновом ограничении.Соединители общаются с ограничениями при помощи процедур inform-aboutvalue, которая говорит ограничению, что у соединителя есть значение, и informabout-no-value, которая сообщает ограничению, что соединитель утратил значение.Adder порождает ограничение-сумматор между соединителями-слагаемыми a1 и a2исоединителем-суммой sum.
Сумматор реализован в виде процедуры с внутренним состоянием (процедура me):(define (adder a1 a2 sum)(define (process-new-value)(cond ((and (has-value? a1) (has-value? a2))(set-value! sum(+ (get-value a1) (get-value a2))me))((and (has-value? a1) (has-value? sum))(set-value! a2(- (get-value sum) (get-value a1))me))((and (has-value? a2) (has-value? sum))(set-value! a1(- (get-value sum) (get-value a2))me))))(define (process-forget-value)(forget-value! sum me)(forget-value! a1 me)(forget-value! a2 me)(process-new-value))(define (me request)(cond ((eq? request ’I-have-a-value)(process-new-value))((eq? request ’I-lost-my-value)(process-forget-value))276Глава 3. Модульность, объекты и состояние(else(error "Неизвестный запрос -- ADDER" request))))(connect a1 me)(connect a2 me)(connect sum me)me)Adder связывает новый сумматор с указанными соединителями и возвращает его в качестве значения.
Процедура me, которая представляет сумматор, работает как диспетчердля внутренних процедур. Для доступа к диспетчеру используются следующие «синтаксические интерфейсы» (см. примечание 27 в разделе 3.3.4):(define (inform-about-value constraint)(constraint ’I-have-a-value))(define (inform-about-no-value constraint)(constraint ’I-lost-my-value))Внутренняя процедура сумматора process-new-value вызывается, когда сумматорусообщают, что один из его соединителей получил значение. Сумматор проверяет, имеютли значения одновременно a1 и a2.
Если да, то он говорит sum, чтобы тот установилзначение в сумму двух слагаемых. Аргумент informant процедуры set-value! равенme, то есть самому объекту-сумматору. Если неверно, что и a1 и a2 имеют значения,то сумматор проверяет, имеют ли одновременно значения a1 и sum. Если да, то онустанавливает a2 в их разность. Наконец, если значения есть у a2 и sum, это даетсумматору достаточно информации, чтобы установить a1. Если сумматору сообщают, чтоодин из соединителей потерял значение, то он просит все свои соединители избавитьсяот значений. (На самом деле будут отброшены только значения, установленные самимсумматором.) Затем он зовет process-new-value. Смысл этого последнего шага втом, что один или более соединителей по-прежнему могут обладать значением (то есть,у соединителя могло быть значение, не установленное сумматором), и эти значенияможет быть необходимо распространить через сумматор.Умножитель очень похож на сумматор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
