w

32

Рис. 3.28: Уравнение 9C = 5(F - 32), выраженное в виде сети ограничений.

F

y

9

5

а + b = c, (multiplier x y z) выражает ограничение xy = z, а (constant 3.14 x) говорит, что значение x обязано равняться 3.14.

Наш язык предоставляет средства комбинирования элементарных ограничений, чтобы с их помощью выражать более сложные отношения. Сочетания образуют сети ограничений (constraint networks), в которых ограничения связаны соединителями (connectors). Соединитель - это объект, который «содержит» значение, способное участвовать в одном или нескольких ограничениях. К примеру, мы знаем, что связь между температурами по Цельсию и по Фаренгейту выглядит как 9C = 5(F - 32) Такое ограничение можно изобразить в виде сети, состоящей из элементарных ограничений - сумматора, умножителей и констант (рисунок 3.28). На этом рисунке слева мы видим блок умножителя с тремя выводами, обозначенными ml, m2 и p. Вывод ml присоединен к соединителю C, который будет хранить температуру по Цельсию. Вывод m2 присоединен к соединителю w, который, кроме того, связан с блоком-константой, содержащим 9. Вывод p, про который блок-умножитель говорит, что он должен быть произведением ml и m2, связан с выводом p другого блока-умножителя, чей вывод m2 связан с константой 5, а ml присоединен к одному из слагаемых суммы.

Вычисления в такой сети происходят следующим образом: когда соединителю дается значение (пользователем либо блоком-ограничением, с которым он связан), соединитель пробуждает все связанные с ним ограничения (кроме того, которое само его пробудило), и сообщает им, что у него появилось значение. Каждый пробужденный блок-ограничение опрашивает свои выводы, чтобы определить, достаточно ли у него информации, чтобы найти значение для какого-нибудь еще соединителя. Если да, блок присваивает соединителю значение, и тогда уже он пробуждает связанные с ним ограничения, и так далее. Например, при преобразовании между градусами Цельсия и Фаренгейта, значения 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, подобной той, которая следила за сигналами в проводах в разделе 3.3.4. Установка тестера на соединителе ведет к тому, что каждый раз, когда он получает значение, печатается сообщение:

(probe "по Цельсию" C) (probe "по Фаренгейту" F)

Затем мы присваиваем значение 25 соединителю C. (Третий аргумент процедуры set-value! сообщает C, что директива исходит от пользователя.)

(set-value! C 25 user) Тестер: по Цельсию = 25 Тестер: по Фаренгейту = 77 done

Тестер на 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 Тестер: по Цельсию = 100 done

Это новое значение, распространяясь по сети, заставляет C получить значение 100, и тестер на C это регистрирует. Заметим, что одна и та же сеть используется и для того, чтобы на основе F получить C и для того, чтобы на основе C получить F. Эта ненаправленность вычислений является отличительной чертой систем, основанных на ограничениях.

Реализация системы ограничений

Система ограничений реализована на основе процедурных объектов с внутренним состоянием, очень похоже на модель цифровых схем из раздела 3.3.4. Хотя базовые объекты системы с ограничениями несколько более сложны, система в целом проще за счет того, что незачем заботиться о планах действий и логических задержках.

Базовые операции над соединителями таковы:

•(has-value? (соединитель))сообщает, есть ли у соединителя значение.

•(get-value (соединитель))возвращает текущее значение соединителя.

•(set-value! (соединитель) (новое-знач) (информант)) сообщает соединителю, что информант требует установить в нем новое значение.

•(forget-value! (соединитель) (отказник)) сообщает соединителю, что отказник просит его забыть значение.

•(connect (соединитель) (новое-огр)) говорит соединителю, что он участвует в новом ограничении.

Соединители общаются с ограничениями при помощи процедур inform-about-value, которая говорит ограничению, что у соединителя есть значение, и inform-about-no-value, которая сообщает ограничению, что соединитель утратил значение.

Adder порождает ограничение-сумматор между соединителями-слагаемыми a1 и a2 исоединителем-суммой sum. Сумматор реализован в виде процедуры с внутренним состоянием (процедура me):