Лаб. 11: Макросы

Макросы

До этого момента была возможность лишь определять собственные процедуры в Scheme с использованием особой формы define. При выполнении этих процедур интерпретатор следует правилам обработки вызывающих выражений, которые включают вычисление всех операндов.

Тебе уже известно, что особые формы не следуют правилам вычисления вызывающих выражений. Вместо этого каждая особая форма обрабатывается по своим правилам, которые могут требовать вычисления не всех аргументов. Не правда ли было бы круто иметь возможность объявлять свои собственные особые формы с собственными правилами вычисления. Посмотри на следующий пример, в котором осуществлена попытка создать функцию, вычисляющую заданное выражение дважды:

scm> (define (twice f) (begin f f))
twice
scm> (twice (print 'woof))
woof

Поскольку twice является обычной процедурой, её вызов будет выполняться по правилам для вызывающих выражений: сначала будет вычислено значение оператора, затем будут вычислены операнды. Это означает, что woof появится в выводе при вычислении операнда (print 'woof). Внутри тела twice имя f будет связано со значением undefined, так что при вычислении выражения (begin f f) ничего не произойдёт.

Как же это исправить? Нужно предотвратить вычисление выражения (print 'woof) до попадания в тело процедуры twice. Именно в таких случаях может помочь особая форма define-macro (её синтаксис в точности совпадает с формой define):

scm> (define-macro (twice f) (list 'begin f f))
twice

Особая форма define-macro позволяет определять макросы. Макрос — это сочетание невыполненных входных выражений с другими выражениями. При вызове макроса операнды не вычисляются, а рассматриваются как Scheme-данные. То есть операнды в виде вызывающих выражений или особых форм обрабатываются как Scheme-списки.

При вызове (twice (print 'woof)) символ f связан со списком (print 'woof), а не со значением undefined. Внутри тела define-macro эти выражения могут быть «вставлены» в другие Scheme-выражения. В рассматриваемом примере begin-выражение должно выглядеть так:

(begin (print 'woof) (print 'woof))

Если рассматривать это выражение с точки зрения данных, то это просто список с элементами begin, (print 'woof), (print 'woof). То есть это в точности значение выражения (list 'begin f f). Теперь при вызове twice этот список будет обработан как выражение — (print 'woof) напечатается два раза.

scm> (twice (print 'woof))
woof
woof

Подводя итог, макросы вызываются похожим с процедурами способом, но правила вычисления макросов отличаются. Например, лямбда-процедура вычисляется таким образом:

  • вычислить значение оператора;

  • вычислить значения операндов;

  • применить значение оператора к значениям операндов.

Правила же вычисления макросов таковы:

  • вычислить значение оператора;

  • применить значение оператора к невычисленным операндам;

  • вычислить значение выражения, возвращённого из макроса в фрейме, в котором был вызван макрос.

Квазицитирование

Припомни, что особая форма quote предотвращает выполнение интерпретатором Scheme указанного выражения. Похоже, цитаты удобно использовать при построении сложных Scheme-выражений со множеством вложенных списков.

Рассмотри другую версию макроса twice:

(define-macro (twice f)
  '(begin f f))

Казалось бы, этот вариант идентичен предыдущему, но это не так. Особая форма quote предотвращает любые вычисления, то есть результирующее выражение будет (begin f f). Это не то, что требуется.

Квазицитирование позволяет создавать списки похожим на quote способом, но эта форма дополнительно позволяет указывать, какие подвыражения следует вычислять, а какие нет.

То есть с первого взгляда особая форма quasiquote (или сокращённо `) ведёт себя ровно как quote (сокращённо '). Однако использование квазицитат позволяет для выбранных выражений делать расцитирование — особая форма unquote (или сокращённо ,). Расцитированное выражение вычисляется, и его значение вставляется в квазицитату.

Использование этих форм значительно облегчает создание макросов.

Последний вариант define-macro:

(define-macro (twice f)
  `(begin ,f ,f))
Квазицитирование относится не только к определению макросов. Его можно использовать в любой ситуации, где требуется нерекурсивно задавать списки, зная их структуру. Например, вместо (list x y z) можно смело писать (,x ,y ,z).

Особая форма let

Особая форма let позволяет создавать локальные связи. Она состоит из двух элементов: список двухэлементных пар и тело выражения. Каждая пара содержит символ и выражение, значение которого следует локально связать с символом.

(let ((var-1 expr-1)
      (var-2 expr-2)
      ...
      (var-n expr-n))
      body-expr)

При вычислении let-выражения создаётся новый локальный фрейм. В этом фрейме все указанные переменные одновременно связываются со значениями. Затем в этом фрейме вычисляется тело выражения.

(let ((a 1)
      (b (* 2 3)))
     (+ a b)) (1)
1 Результат этого выражения равен 7.

Особая форма let позволяет значительно упрощать код. Например, процедура filter определяется так:

(define (filter fn lst)
    (cond ((null? lst) nil)
          ((fn (car lst)) (cons (car lst) (filter fn (cdr lst))))
          (else (filter fn (cdr lst)))))

С использованием let так:

(define (filter fn lst)
    (if (null? lst)
        nil
        (let ((first (car lst))
              (rest (cdr lst)))
           (if (fn first)
               (cons first (filter fn rest))
               (filter fn rest)))))

Хотя строк стало больше, рекурсивная часть стала гораздо понятнее.

Также let позволяет не вычислять некоторые выражения дважды. Например, без let в следующем примере print-then-return вызывался бы дважды:

(define (print-then-return x)
   (begin (print x) x))

(define (print-then-double x)
   (let ((value (print-then-return x)))
       (+ value value)))

(print-then-double (+ 1 1))
; 2
; 4

Вопрос 1: Что выведет Scheme?

При выполнении этого задания помни, что встроенные процедуры выводятся так:

scm> +
#[+]
scm> list
#[list]
 
scm> +
______

scm> list
______

scm> (define-macro (f x) (car x))
______

scm> (f (2 3 4)) ; напиши SchemeError для обозначения ошибки, или Nothing для обозначения None
______

scm> (f (+ 2 3))
______

scm> (define x 2000)
______

scm> (f (x y z))
______

scm> (f (list 2 3 4))
______

scm> (f (quote (2 3 4)))
______

scm> (define quote 7000)
______

scm> (f (quote (2 3 4)))
______
scm> (define-macro (g x) (+ x 2))
______

scm> (g 2)
______

scm> (g (+ 2 3))
______

scm> (define-macro (h x) (list '+ x 2))
______

scm> (h (+ 2 3))
______
scm> (define-macro (if-else-5 condition consequent) `(if ,condition ,consequent 5))
______

scm> (if-else-5 #t 2)
______

scm> (if-else-5 #f 3)
______

scm> (if-else-5 #t (/ 1 0))
______

scm> (if-else-5 #f (/ 1 0))
______

scm> (if-else-5 (= 1 1) 2)
______

Вопрос 2: Что выведет Scheme?

scm> '(1 x 3)
______

scm> (define x 2)
______

scm> `(1 x 3)
______

scm> `(1 ,x 3)
______

scm> '(1 ,x 3)
______

scm> `(,1 x 3)
______

scm> `,(+ 1 x 3)
______

scm> `(1 (,x) 3)
______

scm> `(1 ,(+ x 2) 3)
______

scm> (define y 3)
______

scm> `(x ,(* y x) y)
______

scm> `(1 ,(cons x (list y 4)) 5)
______

Вопрос 3: Повторяющийся куб

Дополни следующую процедуру, которая возводит значение x в куб n раз.

(define (repeatedly-cube n x)
    (if (zero? n)
        x
        (let
            (_________________________)
            (* y y y))))

Вопрос 4: Scheme def

Создай макрос def, который эмулирует Python-инструкцию def, позволяя обрабатывать выражения такого вида: (def f(x y) (+ x y)).

Приведённое выражение должно задать процедуру с параметрами x, y и телом (+ x y) и связать её с именем f в текущем фрейме.

Приведённое выражение эквивалентно (def f (x y) (+ x y)).
Настоятельно рекомендуется прорешать вопросы 1 и 2 перед продумыванием этого вопроса. 
(define-macro (def func bindings body)
    ;ТВОЙ-КОД-ЗДЕСЬ
    nil)

Вопрос 5: switch

Определи макрос switch, который принимает выражение expr и список пар cases. Первый элемент пары — некоторое значение, второй элемент пары — простое выражение. Макрос switch должен вычислить выражение (второй элемент) из той пары, значение (первый элемент) которой совпадёт со значением выражения expr.

scm> (switch (+ 1 1) ((1 (print 'a))
                      (2 (print 'b))
                      (3 (print 'c))))
b

Можешь считать, что значение expr обязательно встречается хотя бы в одной паре из cases. Кроме того, твоё решение может несколько раз вычислять значение expr.

(define-macro (switch expr cases)
      ;ТВОЙ-КОД-ЗДЕСЬ
    nil
)

Вопрос 6: Дракон

Допиши dragon так, чтобы рисовалась кривая дракона.

Сперва создай список действий для отрисовки кривой дракона. Для этого начни со списка (f x) и применяй следующие правила перезаписи попеременно несколько раз:

  • x → (x r y f r)

  • y → (l f x l y)

Создай процедуру flatmap, принимающую функцию и список, которая создаёт плоский список из результатов применения функции к элементам исходного списка.

Затем создай процедуру expand, которая должна реализовывать приведённые выше правила в терминах flatmap.

После этого, пробегая по результату, выполняй в интерпретаторе действия:

  • x или y — ничего не делать;

  • f — движение вперёд на расстояние dist;

  • l — поворот на 90 градусов налево;

  • r — поворот на 90 градусов направо.

Определение процедуры dragon в терминах expand и interpret приведено. Дополни эти функции, чтобы всё заработало!

(define (flatmap f x)
    ;ТВОЙ-КОД-ЗДЕСЬ
    nil)

(define (expand lst)
    ;ТВОЙ-КОД-ЗДЕСЬ
    nil)

(define (interpret instr dist)
    ;ТВОЙ-КОД-ЗДЕСЬ
    nil)

(define (apply-many n f x)
  (if (zero? n)
      x
      (apply-many (- n 1) f (f x))))

(define (dragon n d)
  (interpret (apply-many n expand '(f x)) d))

Для получения кривой дракона или визуальной отладки кода запусти (speed 0) (dragon 10 10). Вызов (speed 0) заставит черепашку бегать побыстрее (иначе на отрисовку уйдёт вечность).

Если возникнет исключение RecursionError, переопредели flatmap и interpret с использованием хвостовой рекурсии.