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

Внутренняя процедура accept-action-procedure!, определенная в make-wire, требует, чтобы в момент, когда процедура-действие добавляется к проводу, она немедленно исполнялась. Объясните, зачем требуется такая инициализация. В частности, проследите работу процедуры half-adder из этого текста и скажите, как отличалась бы реакция системы, если бы accept-action-procedure! была определена как

(define (accept-action-procedure! proc)

(set! action-procedures (cons proc action-procedures)))

Реализация плана действий

Наконец, мы описываем детали структуры данных плана действий, которая хранит процедуры, предназначенные для исполнения в будущем.

План состоит из временных отрезков (time segments). Каждый временной отрезок является парой, состоящей из числа (значения времени) и очереди (см. упражнение 3.32), которая содержит процедуры, предназначенные к исполнению в этот временной отрезок.

(define (make-time-segment time queue) (cons time queue))

(define (segment-time s) (car s))

(define (segment-queue s) (cdr s))

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

Сам по себе план действий является одномерной таблицей временных отрезков. От таблиц, описанных в разделе 3.3.3, он отличается тем, что сегменты отсортированы в порядке возрастания времени. В дополнение к этому мы храним текущее время (current time) (т. е. время последнего исполненного действия) в голове плана. Свежесозданный план не содержит временных отрезков, а его текущее время равно 0:28

(define (make-agenda) (list 0))

(define (current-time agenda) (car agenda))

(define (set-current-time! agenda time) (set-car! agenda time))

(define (segments agenda) (cdr agenda))

(define (set-segments! agenda segments) (set-cdr! agenda segments))

(define (first-segment agenda) (car (segments agenda)))

(define (rest-segments agenda) (cdr (segments agenda)))

28 Подобно таблицам из раздела 3.3.3, план действий - это список с заголовком, но, поскольку в заголовке хранится время, не нужно дополнительного заголовка-пустышки (вроде символа *table*, которым мы пользовались в таблицах).

План пуст, если в нем нет ни одного временного отрезка:

(define (empty-agenda? agenda) (null? (segments agenda)))

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

(define (add-to-agenda! time action agenda) (define (belongs-before? segments) (or (null? segments)

(< time (segment-time (car segments))))) (define (make-new-time-segment time action) (let ((q (make-queue))) (insert-queue! q action) (make-time-segment time q))) (define (add-to-segments! segments)

(if (= (segment-time (car segments)) time)

(insert-queue! (segment-queue (car segments)) action)

(let ((rest (cdr segments))) (if (belongs-before? rest) (set-cdr! segments

(cons (make-new-time-segment time action) (cdr segments))) (add-to-segments! rest))))) (let ((segments (segments agenda))) (if (belongs-before? segments) (set-segments! agenda

(cons (make-new-time-segment time action) segments)) (add-to-segments! segments))))

Процедура, которая убирает из плана первый элемент, уничтожает элемент в начале очереди первого отрезка времени. Если в результате отрезок становится пустым, мы изымаем его из списка отрезков:29

(define (remove-first-agenda-item! agenda)

(let ((q (segment-queue (first-segment agenda)))) (delete-queue! q) (if (empty-queue? q)

(set-segments! agenda (rest-segments agenda)))))

29Обратите внимание, что в этой процедуре выражение if не имеет {альтернативы). Такие «односторонние предложения if» используются, когда требуется решить, нужно ли какое-то действие, а не выбрать одно из двух выражений. Если предикат ложен, а {альтернатива) отсутствует, значение предложения if не определено.

Первый элемент плана находится в начале очереди в первом временном отрезке. Каждый раз, когда мы обращаемся к такому элементу, мы обновляем

30

текущее время:30

(define (first-agenda-item agenda) (if (empty-agenda? agenda)

(error "План пуст - FIRST-AGENDA-ITEM") (let ((first-seg (first-segment agenda)))

(set-current-time! agenda (segment-time first-seg)) (front-queue (segment-queue first-seg)))))

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

Процедуры, предназначенные к выполнению в каждом временном отрезке, хранятся в виде очереди. Таким образом, процедуры для каждого отрезка вызываются в том же порядке, в котором они были добавлены к плану (первый пришел, первый ушел). Объясните, почему требуется использовать именно такой порядок. В частности, проследите поведение И-элемента, входы которого меняются с 0 на 1 и с 1 на 0 одновременно и скажите, как отличалось бы поведение, если бы мы хранили процедуры отрезка в обыкновенном списке, добавляя и убирая их только с головы (последний пришел, первый ушел).

3.3.5 Распространение ограничений

Традиционно компьютерные программы организованы как однонаправленные вычисления, выполняющие вычисления над указанными аргументами и получающие указанные значения. С другой стороны, часто системы приходится моделировать в виде отношений между величинами. Например, математическая модель механической структуры может включать информацию, что деформация d металлического стержня связана уравнением dAE = FL с приложенной к нему силой F, его длиной L, поперечным сечением A и модулем упругости E. Такое уравнение не является однонаправленным. Имея любые четыре величины, мы можем вычислить пятую. Однако при переводе уравнения на традиционный компьютерный язык нам придется выбрать величину, которая вычисляется на основе остальных четырех, так что процедура для вычисления площади A не может быть использована для вычисления деформации d, хотя вычисление A и d основаны на одном и том же уравнении.31

В этом разделе мы набросаем эскиз языка, который позволит нам работать в терминах самих отношений. Минимальными составляющими этого языка будут служить элементарные ограничения (primitive constraints), которые говорят, что между величинами существуют определенные связи. Например, (adder a b c) означает, что величины a, b и c должны быть связаны уравнением

30Таким образом, текущее время всегда будет совпадать с временем последнего обработанного действия. Благодаря тому, что это время хранится в голове плана, оно всегда доступно, даже если соответствующий отрезок времени был уничтожен.

31 Распространение ограничений появилось в системе SKETCHPAD Айвена Сазерленда (Sutherland 1963), невероятно опередившей свое время. Изящная система распространения ограничений, основанная на языке Smalltalk, была разработана Аланом Борнингом (Borning 1977) в исследовательском центре компании Xerox в Пало Альто. Сассман, Столлман и Стил применили распространение ограничений к анализу электрических цепей (Sussman and Stallman 1975; Sussman and Steele 1980). TK!Solver (Konopasek and Jayaraman 1984) представляет собой богатую среду моделирования, основанную на ограничениях.