5.5.8 · От дерева к командам

Компиляция дерева выражений в команды

Компилятор урока может превращать дерево выражений в команды стека, которые отдельная машина выполняет позже.

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

Как дерево выражений превращается в линейную последовательность команд?

Генерация команд констант и арифметики из синтаксических данных
Сохранение порядка операндов в коде для стека
Разделение компиляции и выполнения на машине

Процедура compile генерирует код левого операнда, затем код правого операнда и в конце одну арифметическую команду. Рекурсия разворачивает вложенное выражение в линейный список.

Процедура execute помещает константы в стек. Арифметическая команда извлекает правое и левое значения, объединяет их и помещает результат в стек. Когда кода не остается, вершина стека становится значением программы.

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

(begin
  (define (operator-instruction operator)
    (cond ((eq? operator '+) 'add)
          ((eq? operator '-) 'sub)
          ((eq? operator '*) 'mul)))
  (define (compile expression)
    (if (number? expression)
        (list (list 'const expression))
        (append (compile (cadr expression))
                (append (compile (caddr expression))
                        (list (operator-instruction (car expression)))))))
  (define (execute code stack)
    (if (null? code)
        (car stack)
        (let ((instruction (car code)))
          (if (pair? instruction)
              (execute (cdr code) (cons (cadr instruction) stack))
              (let ((right (car stack)) (left (cadr stack)))
                (execute
                  (cdr code)
                  (cons (cond ((eq? instruction 'add) (+ left right))
                              ((eq? instruction 'sub) (- left right))
                              ((eq? instruction 'mul) (* left right)))
                        (cddr stack))))))))
  (let ((code (compile '(+ (* 3 4) 5))))
    (list code (execute code '()))))

(begin
  (define (operator-instruction operator)
    (cond ((eq? operator '+) 'add)
          ((eq? operator '-) 'sub)
          ((eq? operator '*) 'mul)))
  (define (compile expression)
    (if (number? expression)
        (list (list 'const expression))
        (append (compile (cadr expression))
                (append (compile (caddr expression))
                        (list (operator-instruction (car expression)))))))
  (define (execute code stack)
    (if (null? code)
        (car stack)
        (let ((instruction (car code)))
          (if (pair? instruction)
              (execute (cdr code) (cons (cadr instruction) stack))
              (let ((right (car stack)) (left (cadr stack)))
                (execute
                  (cdr code)
                  (cons (cond ((eq? instruction 'add) (+ left right))
                              ((eq? instruction 'sub) (- left right))
                              ((eq? instruction 'mul) (* left right)))
                        (cddr stack))))))))
  (let ((code (compile '(+ (* 3 4) 5))))
    (list code (execute code '()))))

Примеры

Результат—

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

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

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

Первая программа возвращает пять сгенерированных команд и вычисленное значение 17.

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

Отделите рекурсивные вызовы compile от последующих вызовов execute. Во время выполнения каждая команда считывает код, изменяя стек.

Попробуйте сами

Измените программу и сравните результат.

Скомпилируйте (+ 1 (* 2 (+ 3 4))). Запишите список команд перед тем, как выполнить его.

Показать подсказку

Каждое число генерирует const. Каждое составное выражение генерирует свой оператор после обоих операндов.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%