|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[164] Мы использовали тот факт, что сохранять информацию необязательно. Если бы мы до этого не додумались, можно было бы реализовать eval-sequence так, что все выражения в последовательности обрабатываются одинаково - сохранение регистров, вычисление выражения, возврат с сохранением регистров, 27 и повторение до тех пор, пока не вычислятся все выражения:27 ev-sequence (test (op no-more-exps?) (reg unev)) (branch (label ev-sequence-end)) (assign exp (op first-exp) (reg unev)) (save unev) (save env) (assign continue (label ev-sequence-continue)) (goto (label eval-dispatch)) ev-sequence-continue (restore env) (restore unev) (assign unev (op rest-exps) (reg unev)) (goto (label ev-sequence)) ev-sequence-end (restore continue) (goto (reg continue)) Может показаться, что это мелкое изменение в предыдущем коде для выполнения последовательности: единственная разница состоит в том, что мы проходим через цикл сохранения-восстановления для последнего выражения последовательности так же, как и для остальных. Интерпретатор по-прежнему будет возвращать для всех выражений то же самое значение. Однако такое изменение теряет свойство хвостовой рекурсии, поскольку теперь после вычисления последнего выражения в последовательности нам придется возвращаться и отменять (бесполезные) сохранения регистров. Эти дополнительные сохранения будут накапливаться в гнезде рекурсивных вызовов. Следовательно, процессы вроде sqrt-iter потребуют памяти пропорционально количеству итераций, а не фиксированного объема. Такая разница может быть существенна. Например, при наличии хвостовой рекурсии можно выразить бесконечный цикл с помощью одного только механизма вызова процедур: (define (count n) (newline) (display n) (count (+ n 1))) Без хвостовой рекурсии такая процедура рано или поздно исчерпает место в стеке, а итерацию придется выражать с помощью какого-то другого механизма помимо вызовов процедур. 5.4.3 Условные выражения, присваивания и определения Как и в метациклическом интерпретаторе, особые формы обрабатываются путем частичного выполнения частей выражения. В выражении if нам нужно 27Можно определить no-more-exps? как (define (no-more-exps? seq) (null? seq)) вычислить предикат, а затем на основании его значения решить, требуется нам выполнять следствие или альтернативу. Прежде чем вычислять предикат, мы сохраняем само выражение if, поскольку позже из него потребуется извлекать следствие либо альтернативу. Кроме того, мы сохраняем окружение, которое потребуется при вычислении следствия или альтернативы, и continue, который потребуется нам при возврате значения выражению, ждущему результата if. ev-if (save exp); сохраняем выражение (save env) (save continue) (assign continue (label ev-if-decide)) (assign exp (op if-predicate) (reg exp)) (goto (label eval-dispatch)) ; вычисляем предикат Вернувшись после вычисления предиката, мы смотрим, является ли его значение истиной или ложью, в зависимости от этого переносим в регистр exp следствие либо альтернативу, и идем на eval-dispatch. Заметим, что после восстановления env и continue eval-dispatch будет выполняться в правильном окружении и вернется после вычисления выражения в правильное место. ev-if-decide (restore continue) (restore env) (restore exp) (test (op true?) (reg val)) (branch (label ev-if-consequent)) ev-if-alternative (assign exp (op if-alternative) (reg exp)) (goto (label eval-dispatch)) ev-if-consequent (assign exp (op if-consequent) (reg exp)) (goto (label eval-dispatch)) Присваивания и определения Присваивания обрабатываются по метке ev-assignment, на которую переход происходит из eval-dispatch с выражением-присваиванием в регистре exp. Код ev-assignment сначала вычисляет значение присваиваемого выражения, а затем заносит это значение в окружение. Предполагается, что set-variable-value! дана как машинная операция. ev-assignment (assign unev (op assignment-variable) (reg exp)) (save unev); сохранить переменную (assign exp (op assignment-value) (reg exp)) (save env) (save continue) (assign continue (label ev-assignment-1)) (goto (label eval-dispatch)) ; вычислить присваиваемое значение ev-assignment-1 (restore continue) (restore env) (restore unev) (perform (op set-variable-value!) (reg unev) (reg val) (reg env)) (assign val (const ok)) (goto (reg continue)) Подобным образом обрабатываются и определения: ev-definition (assign unev (op definition-variable) (reg exp)) (save unev); сохранить переменную (assign exp (op definition-value) (reg exp)) (save env) (save continue) (assign continue (label ev-definition-1)) (goto (label eval-dispatch)) ; вычислить значение переменной ev-definition-1 (restore continue) (restore env) (restore unev) (perform (op define-variable!) (reg unev) (reg val) (reg env)) (assign val (const ok)) (goto (reg continue)) Упражнение 5.23. Расширьте вычислитель так, чтобы обрабатывались производные выражения cond, let и тому подобные (раздел 4.1.2). Можно «сжульничать» и считать, что синтаксические трансформации вроде cond->if имеются как машинные операции.28 Упражнение 5.24. Реализуйте cond как новую особую форму, не сводя его к if. Придется организовать цикл, проверяющий предикаты последовательных ветвей cond, пока один не окажется истинным, а затем с помощью ev-sequence выполнять действия этой ветви. Упражнение 5.25. Измените вычислитель так, чтобы он использовал нормальный порядок вычислений, на основе ленивого интерпретатора из раздела 4.2. 5.4.4 Запуск вычислителя Реализовав вычислитель с явным управлением, мы подходим к концу сюжета, начатого в главе 1 - построения все более точных моделей для процесса вычисления. Мы начали с относительно неформальной подстановочной модели, затем в главе 3 расширили ее до модели с окружениями, позволившей работать с состоянием и его изменением. В метациклическом интерпретаторе из 28На самом деле это не жульничество. В настоящей реализации, построенной с нуля, мы бы на синтаксическом этапе, происходящем раньше собственно выполнения, интерпретировали при помощи вычислителя с явным управлением Scheme-программу, которая производит трансформации исходного кода вроде cond->if. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||