4.1.8 · Данные как программы

Построение, преобразование и вычисление программы

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

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

Что становится возможным, когда вычислитель принимает те же списочные структуры, которые обычные процедуры могут конструировать и преобразовывать?

Конструирование применения lambda как обычных символьных списочных данных
Проверка структуры сгенерированного оператора, параметров и тела перед выполнением
Вычисление сгенерированных данных процедуры в явном окружении
Преобразование каждого свободного вхождения одного символа в арифметическом выражении
Разделение преобразования программы и вычислителя, который затем ее выполняет

Процедура make-linear-program возвращает список ((lambda (x) (+ (* 3 x) 2)) 5). Перед вычислением обычные селекторы car, cadr и списочные процедуры могут проверить или переписать эту структуру. Затем tiny-eval интерпретирует те же данные: lambda создает представленную составную процедуру, а применение расширяет сохраненное окружение связыванием x = 5.

Вторая программа рассматривает квадратное выражение как данные и рекурсивно заменяет символ x на 3. Преобразование сохраняет арифметику как символьные данные. Затем arithmetic-eval интерпретирует + и * и дает 16. Учебный вычислитель обрабатывает перечисленные арифметические формы через то же явное представление, общее для генератора и преобразователя.

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

(begin
  (define (make-linear-program slope intercept input)
    (list
      (list 'lambda
            '(x)
            (list '+
                  (list '* slope 'x)
                  intercept))
      input))
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend parameters arguments environment)
    (if (null? parameters)
        environment
        (cons (cons (car parameters) (car arguments))
              (extend (cdr parameters)
                      (cdr arguments)
                      environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (tiny-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let* ((procedure (tiny-eval (car expression) environment))
                  (arguments
                    (map (lambda (operand)
                           (tiny-eval operand environment))
                         (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((eq? (car procedure) 'compound)
                    (tiny-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +) (cons '* *)))
  (define program (make-linear-program 3 2 5))
  (list program
        (car (car program))
        (cadr (car program))
        (tiny-eval program primitive-environment)))

(begin
  (define (make-linear-program slope intercept input)
    (list
      (list 'lambda
            '(x)
            (list '+
                  (list '* slope 'x)
                  intercept))
      input))
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend parameters arguments environment)
    (if (null? parameters)
        environment
        (cons (cons (car parameters) (car arguments))
              (extend (cdr parameters)
                      (cdr arguments)
                      environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (tiny-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let* ((procedure (tiny-eval (car expression) environment))
                  (arguments
                    (map (lambda (operand)
                           (tiny-eval operand environment))
                         (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((eq? (car procedure) 'compound)
                    (tiny-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +) (cons '* *)))
  (define program (make-linear-program 3 2 5))
  (list program
        (car (car program))
        (cadr (car program))
        (tiny-eval program primitive-environment)))

Примеры

Результат—

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

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

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

Запуск сгенерированной программы возвращает (((lambda (x) (+ (* 3 x) 2)) 5) lambda (x) 17). Запуск со специализацией возвращает ((+ (+ (* x x) (* 2 x)) 1) (+ (+ (* 3 3) (* 2 3)) 1) 16).

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

Отделяйте конструирование списка и замену символов от последующего вычисления. В tiny-eval проследите за переходом сгенерированной lambda в составную запись и сгенерированного применения в одно расширенное окружение. В arithmetic-eval убедитесь, что во время числовой интерпретации замена символов не происходит.

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

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

Сгенерируйте аффинную программу с двумя параметрами (+ (* slope x) (* offset y)), проверьте ее список параметров и вычислите ее. Затем специализируйте только x в сгенерированном теле, оставив y символьным.

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

Генерация программы должна возвращать только данные. Процедура extend связывает параметры и аргументы по порядку, а специализация может повторно использовать replace-symbol перед вычислением.

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

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