Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 62
Текст из файла (страница 62)
В общем случае, при работе моделив план добавляются новые элементы, а propagate продолжает работу, пока план нестановится пустым:(define (propagate)(if (empty-agenda? the-agenda)’done(let ((first-item (first-agenda-item the-agenda)))(first-item)(remove-first-agenda-item! the-agenda)(propagate))))Глава 3. Модульность, объекты и состояние268Пример работы моделиСледующая процедура, которая навешивает на провод «тестер», показывает имитационную модель в действии. Тестер говорит проводу, что, каждый раз, когда сигнализменяет значение, нужно напечатать новое значение сигнала, а также текущее время иимя провода:(define (probe name wire)(add-action! wire(lambda ()(newline)(display name)(display " ")(display (current-time the-agenda))(display " New-value = ")(display (get-signal wire)))))Сначала мы инициализируем план действий и указываем задержки для элементарныхфункциональных элементов:(define(define(define(definethe-agenda (make-agenda))inverter-delay 2)and-gate-delay 3)or-gate-delay 5)Затем мы создаем четыре провода и к двум из них подсоединяем тестеры:(define(define(define(defineinput-1 (make-wire))input-2 (make-wire))sum (make-wire))carry (make-wire))(probe ’sum sum)sum 0 New-value = 0(probe ’carry carry)carry 0 New-value = 0Затем мы связываем провода, образуя схему полусумматора (как на рис.
3.25), устанавливаем сигнал на входе input-1 в 1, и запускаем модель:(half-adder input-1 input-2 sum carry)ok(set-signal! input-1 1)done(propagate)sum 8 New-value = 1done3.3. Моделирование при помощи изменяемых данных269Сигнал sum становится 1 в момент времени 8. Мы находимся в 8 единицах от началаработы модели. В этот момент мы можем установить сигнал на входе input-2 в 1 идать изменению распространиться:(set-signal! input-2 1)done(propagate)carry 11 New-value = 1sum 16 New-value = 0doneСигнал carry становится равным 1 в момент 11, а sum становится 0 в момент 16.Упражнение 3.31.Внутренняя процедура accept-action-procedure!, определенная в make-wire, требует, чтобы в момент, когда процедура-действие добавляется к проводу, она немедленно исполнялась.
Объясните, зачем требуется такая инициализация. В частности, проследите работу процедуры halfadder из этого текста и скажите, как отличалась бы реакция системы, если бы accept-actionprocedure! была определена как(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, он отличается тем, что сегменты отсортированы впорядке возрастания времени. В дополнение к этому мы храним текущее время (currenttime) (т. е. время последнего исполненного действия) в голове плана. Свежесозданныйплан не содержит временных отрезков, а его текущее время равно 028 :28 Подобно таблицам из раздела 3.3.3, план действий — это список с заголовком, но, поскольку в заголовке хранится время, не нужно дополнительного заголовка-пустышки (вроде символа *table*, которым мыпользовались в таблицах).270Глава 3.
Модульность, объекты и состояние(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)))План пуст, если в нем нет ни одного временного отрезка:(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!3.3.
Моделирование при помощи изменяемых данных271agenda(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)))))Первый элемент плана находится в начале очереди в первом временном отрезке.Каждый раз, когда мы обращаемся к такому элементу, мы обновляем текущее время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. Распространение ограниченийТрадиционно компьютерные программы организованы как однонаправленные вычисления, выполняющие вычисления над указанными аргументами и получающие указанные значения. С другой стороны, часто системы приходится моделировать в виде отношений между величинами. Например, математическая модель механической структуры29 Обратитевнимание, что в этой процедуре выражение if не имеет hальтернативыi.
Такие «односторонние предложения if» используются, когда требуется решить, нужно ли какое-то действие, а не выбратьодно из двух выражений. Если предикат ложен, а hальтернативаi отсутствует, значение предложения if неопределено.30 Таким образом, текущее время всегда будет совпадать с временем последнего обработанного действия.Благодаря тому, что это время хранится в голове плана, оно всегда доступно, даже если соответствующийотрезок времени был уничтожен.Глава 3. Модульность, объекты и состояние272m1Cm2*pum1pva1*a2m2w+ sFy9532Рис. 3.28. Уравнение 9C = 5(F − 32), выраженное в виде сети ограничений.может включать информацию, что деформация d металлического стержня связана уравнением dAE = F L с приложенной к нему силой F , его длиной L, поперечным сечениемA и модулем упругости E.
Такое уравнение не является однонаправленным. Имея любыечетыре величины, мы можем вычислить пятую. Однако при переводе уравнения на традиционный компьютерный язык нам придется выбрать величину, которая вычисляетсяна основе остальных четырех, так что процедура для вычисления площади A не можетбыть использована для вычисления деформации d, хотя вычисление A и d основаны наодном и том же уравнении31 .В этом разделе мы набросаем эскиз языка, который позволит нам работать в терминахсамих отношений. Минимальными составляющими этого языка будут служить элементарные ограничения (primitive constraints), которые говорят, что между величинамисуществуют определенные связи. Например, (adder a b c) означает, что величиныa, b и c должны быть связаны уравнением a + b = c, (multiplier x y z) выражаетограничение xy = z, а (constant 3.14 x) говорит, что значение x обязано равняться3.14.Наш язык предоставляет средства комбинирования элементарных ограничений, чтобыс их помощью выражать более сложные отношения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
