Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 61
Текст из файла (страница 61)
(См., например, упражнение 3.30.)В сущности, наша имитация дает инструмент, с помощью которого строится языкописания схем. Принимая общую точку зрения на языки, с которой мы приступилик изучению Лиспа в разделе 1.1, можно сказать, что элементарные функциональныеэлементы являются примитивами языка, связывание их проводами представляет собойсредство комбинирования, а определение шаблонных схем в виде процедур служит средством абстракции.Элементарные функциональные элементы.Элементарные функциональные элементы изображают «силы», через посредство которых изменение сигнала в одном проводе влечет изменение сигнала в других проводах.Для построения функциональных элементов мы будем пользоваться следующими операциями над проводами:26 Сумматор — основной элемент схем, используемых для сложения двоичных чисел.
Здесь A и B — битына соответствующих позициях двух складываемых чисел, а Сin — бит переноса из позиции на одну правее.Схема генерирует SUM, бит суммы для соответствующей позиции, и Cout , бит переноса для распространенияналево.264Глава 3. Модульность, объекты и состояние• (get-signal hпроводi) возвращает текущее значение сигнала в проводе.• (set-signal! hпроводi hновое-значениеi) заменяет значение сигнала впроводе на указанное.• (add-action! hпроводi hпроцедура без аргументовi) указывает, чтобыпроцедура-аргумент вызывалась каждый раз, когда сигнальный провод изменяет значение. Такие процедуры служат передаточным механизмом, с помощью которого изменениезначения сигнала в одном проводе передается другим проводам.
В дополнение, мы будем пользоваться процедурой after-delay, которая принимает значение задержки ипроцедуру. Она выполняет процедуру после истечения задержки.При помощи этих процедур можно определить элементарные функции цифровой логики. Чтобы соединить вход с выходом через инвертор, мы используем add-action!и ассоциируем со входным проводом процедуру, которая будет вызываться всякий раз,когда сигнал на входе элемента изменит значение. Процедура вычисляет logical-not(логическое отрицание) входного сигнала, а затем, переждав inverter-delay, устанавливает выходной сигнал в новое значение:(define (inverter input output)(define (invert-input)(let ((new-value (logical-not (get-signal input))))(after-delay inverter-delay(lambda ()(set-signal! output new-value)))))(add-action! input invert-input)’ok)(define (logical-not s)(cond ((= s 0) 1)((= s 1) 0)(else (error "Неправильный сигнал" s))))И-элемент устроен немного сложнее.
Процедура-действие должна вызываться, когда меняется любое из значений на входе. Она при этом через процедуру, подобнуюlogical-not, вычисляет logical-and (логическое И) значений сигналов на входных проводах, и затем требует, чтобы изменение значения выходного провода произошлоспустя задержку длиной в and-gate-delay.(define (and-gate a1 a2 output)(define (and-action-procedure)(let ((new-value(logical-and (get-signal a1) (get-signal a2))))(after-delay and-gate-delay(lambda ()(set-signal! output new-value)))))(add-action! a1 and-action-procedure)(add-action! a2 and-action-procedure)’ok)3.3. Моделирование при помощи изменяемых данныхA1 B1C1A2 B2C2A3 B3FAFAC3FA265An nCn =0FACC1S1C2S2SC n-1SnРис. 3.27. Каскадный сумматор для n-битных чисел.Упражнение 3.28.Определите ИЛИ-элемент как элементарный функциональный блок. Ваш конструктор or-gateдолжен быть подобен and-gate.Упражнение 3.29.Еще один способ создать ИЛИ-элемент — это собрать его как составной блок из И-элементови инверторов.
Определите процедуру or-gate, которая это осуществляет. Как время задержкиИЛИ-элемента выражается через and-gate-delay и inverter-delay?Упражнение 3.30.На рисунке 3.27 изображен каскадный сумматор (ripple-carry adder), полученный выстраиваниемв ряд n сумматоров. Это простейшая форма параллельного сумматора для сложения двух n-битныхдвоичных чисел. На входе мы имеем A1 , A2 , A3 ,. . . An и B1 , B2 , B3 , . .
. Bn — два двоичных числа, подлежащих сложению (каждый из Ak и Bk имеет значение либо 0, либо 1). Схема порождаетS1 , S2 , S3 , . . . Sn — первые n бит суммы, и C – бит переноса после суммы. Напишите процедуруriple-carry-adder, которая бы моделировала эту схему. Процедура должна в качестве аргументов принимать три списка по n проводов в каждом (Ak , Bk и Sk ), а также дополнительныйпровод C. Главный недостаток каскадных сумматоров в том, что приходится ждать, пока сигналраспространится. Какова задержка, требуемая для получения полного вывода n-битного каскадного сумматора, выраженная в зависимости от задержек И-, ИЛИ-элементов и инверторов?Представление проводовПровод в нашей имитации будет вычислительным объектом с двумя внутреннимипеременными состояния: значение сигнала signal-value (вначале равное 0) и наборпроцедур-действий action-procedures, подлежащих исполнению, когда сигнал изменяется.
Мы реализуем провод в стиле с передачей сообщений, как набор локальныхпроцедур плюс процедура диспетчеризации, которая выбирает требуемую внутреннююоперацию. Точно так же мы строили объект-банковский счет в разделе 3.1.1.(define (make-wire)(let ((signal-value 0) (action-procedures ’()))(define (set-my-signal! new-value)Глава 3. Модульность, объекты и состояние266(if (not (= signal-value new-value))(begin (set! signal-value new-value)(call-each action-procedures))’done))(define (accept-action-procedure! proc)(set! action-procedures (cons proc action-procedures))(proc))(define (dispatch m)(cond ((eq? m ’get-signal) signal-value)((eq? m ’set-signal!) set-my-signal!)((eq? m ’add-action!) accept-action-procedure!)(else (error "Неизвестная операция -- WIRE" m))))dispatch))Внутренняя процедура set-my-signal! проверяет, отличается ли новое значение сигнала в проводе от старого.
Если да, то она запускает все процедуры-действия при помощипроцедуры call-each, которая по очереди вызывает элементы списка безаргументныхпроцедур:(define (call-each procedures)(if (null? procedures)’done(begin((car procedures))(call-each (cdr procedures)))))Внутренняя процедура accept-action-procedure! добавляет процедуру-аргумент ксписку действий, а затем один раз запускает новую процедуру. (См. упражнение 3.31.)Располагая вышеописанной процедурой dispatch, мы можем написать следующиепроцедуры для доступа к внутренним операциям над проводами27 :(define (get-signal wire)(wire ’get-signal))(define (set-signal! wire new-value)((wire ’set-signal!) new-value))(define (add-action! wire action-procedure)((wire ’add-action!) action-procedure))Провода, которые содержат меняющиеся со временем сигналы и могут подсоединятьсяк одному объекту за другим, — типичный образец изменяющихся объектов. Мы смоде27 Эти процедуры — всего лишь синтаксический сахар, который позволяет нам работать с внутренними процедурами объектов, используя обычный синтаксис процедурного вызова.
Поразительно, что мы так простоможем менять местами роли процедур и данных. Например, когда мы пишем (wire ’get-signal), мыпредставляем себе провод wire как процедуру, вызываемую с сообщением get-signal на входе. С другойстороны, запись (get-signal wire) поощряет нас думать о wire как об объекте данных, который поступает на вход процедуре get-signal. Истина состоит в том, что в языке, где с процедурами можно работатькак с объектами, никакого фундаментального различия между «процедурами» и «данными» не существует, имы имеем право выбирать такой синтаксический сахар, который позволит программировать в удобном для насстиле.3.3. Моделирование при помощи изменяемых данных267лировали их в виде процедур с внутренними переменными состояния, которые изменяются присваиванием. При создании нового провода создается новый набор переменныхсостояния (в выражении let внутри make-wire), а также порождается и возвращается новая процедура dispatch, которая захватывает окружение с новыми переменнымисостояния.Провода разделяются между различными устройствами, к ним подсоединенными.
Таким образом, изменение, произведенное при взаимодействии с одним устройством, скажется на всех других устройствах, связанных с этим проводом. Провод передает изменение своим соседям, вызывая процедуры-действия, зарегистрированные в нем в моментустановления соединения.План действийТеперь для завершения модели нам остается только написать after-delay.
Здесьидея состоит в том, чтобы организовать структуру данных под названием план действий (agenda), где будет храниться расписание того, что нам надо сделать. Для плановдействий определены следующие операции:• (make-agenda) возвращает новый пустой план действий.• (empty-agenda? hплан-действийi) истинно, если план пуст.• (first-agenda-item hплан-действийi)возвращает первый элемент плана.• (remove-first-agenda-item! hплан-действийi) модифицирует план, убирая из него первый элемент.• (add-to-agenda! hвремяi hдействиеi hплан-действийi)модифицируетплан, добавляя указанную процедуру-действие, которую нужно запустить в указанноевремя.• (current-time hплан-действийi) возвращает текущее время модели.Экземпляр плана, которым мы будем пользоваться, будет обозначаться the-agenda.Процедура after-delay добавляет новый элемент в план the-agenda:(define (after-delay delay action)(add-to-agenda! (+ delay (current-time the-agenda))actionthe-agenda))Имитация управляется процедурой propagate, которая работает с theagenda, поочереди выполняяпроцедуры, содержащиеся в плане.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
