Итоговый проект курса · Исполняемый конвейер

Проведите одну идею от абстрактных данных к явному состоянию машины.

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

Вопрос для размышления

Может ли каждый уровень изменять представление, не меняя значение, наблюдаемое учащимся?

Создание данных выражений через процедуру-конструктор
Чтение представления через селекторы
Вычисление имен в явном окружении
Компиляция выражения в инструкции для стека
Запуск явных pc и stack с сохранением состояния замыкания

make-sum создает одно абстрактное выражение. evaluate следует его селекторам и ищет x и y в предоставленном окружении. compile использует тот же интерфейс, но формирует две инструкции load с последующей add.

run многократно применяет step к состоянию, содержащему pc и stack. make-pipeline сохраняет скомпилированный код и изменяемое количество запусков, поэтому второй вызов повторно использует код и сообщает следующее значение счетчика.

Код SICP1,719 из 1,048,576 байт UTF-8

(begin
  (define (make-sum left right) (list 'sum left right))
  (define (left-operand expression) (cadr expression))
  (define (right-operand expression) (caddr expression))
  (define (lookup name environment)
    (cdr (assoc name environment)))
  (define (evaluate expression environment)
    (if (symbol? expression)
        (lookup expression environment)
        (+ (evaluate (left-operand expression) environment)
           (evaluate (right-operand expression) environment))))
  (define (compile expression)
    (if (symbol? expression)
        (list (list 'load expression))
        (append (compile (left-operand expression))
                (append (compile (right-operand expression))
                        '(add)))))
  (define (step code environment state)
    (let ((pc (car state))
          (stack (cadr state)))
      (let ((instruction (list-ref code pc)))
        (if (pair? instruction)
            (list (+ pc 1)
                  (cons (lookup (cadr instruction) environment)
                        stack))
            (list (+ pc 1)
                  (cons (+ (cadr stack) (car stack))
                        (cddr stack)))))))
  (define (run code environment state)
    (if (= (car state) (length code))
        state
        (run code environment (step code environment state))))
  (define (make-pipeline expression)
    (let ((code (compile expression))
          (runs 0))
      (lambda (environment)
        (set! runs (+ runs 1))
        (list (evaluate expression environment)
              (run code environment (list 0 '()))
              runs))))
  (let ((pipeline (make-pipeline (make-sum 'x 'y))))
    (list (pipeline '((x . 4) (y . 5)))
          (pipeline '((x . 2) (y . 10))))))

(begin
  (define (make-sum left right) (list 'sum left right))
  (define (left-operand expression) (cadr expression))
  (define (right-operand expression) (caddr expression))
  (define (lookup name environment)
    (cdr (assoc name environment)))
  (define (evaluate expression environment)
    (if (symbol? expression)
        (lookup expression environment)
        (+ (evaluate (left-operand expression) environment)
           (evaluate (right-operand expression) environment))))
  (define (compile expression)
    (if (symbol? expression)
        (list (list 'load expression))
        (append (compile (left-operand expression))
                (append (compile (right-operand expression))
                        '(add)))))
  (define (step code environment state)
    (let ((pc (car state))
          (stack (cadr state)))
      (let ((instruction (list-ref code pc)))
        (if (pair? instruction)
            (list (+ pc 1)
                  (cons (lookup (cadr instruction) environment)
                        stack))
            (list (+ pc 1)
                  (cons (+ (cadr stack) (car stack))
                        (cddr stack)))))))
  (define (run code environment state)
    (if (= (car state) (length code))
        state
        (run code environment (step code environment state))))
  (define (make-pipeline expression)
    (let ((code (compile expression))
          (runs 0))
      (lambda (environment)
        (set! runs (+ runs 1))
        (list (evaluate expression environment)
              (run code environment (list 0 '()))
              runs))))
  (let ((pipeline (make-pipeline (make-sum 'x 'y))))
    (list (pipeline '((x . 4) (y . 5)))
          (pipeline '((x . 2) (y . 10))))))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Программа возвращает ((9 (3 (9)) 1) (12 (3 (12)) 2)). В каждом результате значение прямого вычисления равно значению на финальном стеке машины, pc 3 отмечает завершение трех инструкций, а последнее поле подсчитывает вызовы конвейера.

На что обратить внимание в трассе

Найдите вызовы конструкторов и селекторов, поиск в окружении, compile перед каждым выполнением конвейера, изменения pc от 0 до 3, обновления stack и присваивание сохраненной переменной runs. Полная трасса выполнения содержит 630 событий для этой программы при фиксированных ограничениях среды выполнения.

Повторение

Пять проверок по всему конвейеру

Где скрыто представление выражения?

Ответ make-sum создает его, а evaluate и compile обращаются к left-operand и right-operand вместо прямой зависимости от позиций в списке.

Почему различаются два значения прямого вычисления?

Ответ Одно и то же выражение получает два окружения с различными связываниями для x и y.

Почему каждое финальное состояние машины имеет pc 3?

Ответ Компилятор формирует две инструкции load и одну инструкцию add, и run останавливается после выполнения всех трех.

Какое состояние сохраняется между двумя вызовами конвейера?

Ответ Замыкание сохраняет скомпилированный код и изменяемое связывание runs, наблюдаемые значения которого увеличиваются с 1 до 2.

Что подтверждает этот итоговый проект?

Ответ Он фиксирует точное соответствие между отображаемыми выражениями, окружениями, состояниями машины и двумя вызовами конвейера.