Lab 12: Macros

lab12.zip

Due at 11:59pm on Friday, 8/9/2019.

Starter Files

Download lab12.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

To receive credit for this lab, you must complete the required questions and submit through OK.

Topics

Macros

So far we've been able to define our own procedures in Scheme using the define special form. When we call these procedures, we have to follow the rules for evaluating call expressions, which involve evaluating all the operands.

We know that special form expressions do not follow the evaluation rules of call expressions. Instead, each special form has its own rules of evaluation, which may include not evaluating all the operands. Wouldn't it be cool if we could define our own special forms where we decide which operands are evaluated? Consider the following example where we attempt to write a function that evaluates a given expression twice:

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

Since twice is a regular procedure, a call to twice will follow the same rules of evaluation as regular call expressions; first we evaluate the operator and then we evaluate the operands. That means that woof was printed when we evaluated the operand (print 'woof). Inside the body of twice, the name f is bound to the value undefined, so the expression (begin f f) does nothing at all!

The problem here is clear: we need to prevent the given expression from evaluating until we're inside the body of the procedure. This is where the define-macro special form, which has identical syntax to the regular define form, comes in:

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

define-macro allows us to define what's known as a macro, which is simply a way for us to combine unevaluated input expressions together into another expression. When we call macros, the operands are not evaluated, but rather are treated as Scheme data. This means that any operands that are call expressions or special form expression are treated like lists.

If we call (twice (print 'woof)), f will actually be bound to the list (print 'woof) instead of the value undefined. Inside the body of define-macro, we can insert these expressions into a larger Scheme expression. In our case, we would want a begin expression that looks like the following:

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

As Scheme data, this expression is really just a list containing three elements: begin and (print 'woof) twice, which is exactly what (list 'begin f f) returns. Now, when we call twice, this list is evaluated as an expression and (print 'woof) is evaluated twice.

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

To recap, macros are called similarly to regular procedures, but the rules for evaluating them are different. We evaluated lambda procedures in the following way:

Evaluate operator
Evaluate operands
Apply operator to operands, evaluating the body of the procedure

However, the rules for evaluating calls to macro procedures are:

Evaluate operator
Apply operator to unevaluated operands
Evaluate the expression returned by the macro in the frame it was called in.

Quasiquote

Recall that the quote special form prevents the Scheme interpreter from executing a following expression. We saw that this helps us create complex lists more easily than repeatedly calling cons or trying to get the structure right with list. It seems like this form would come in handy if we are trying to construct complex Scheme expressions with many nested lists.

Consider that we rewrite the twice macro as follows:

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

This seems like it would have the same effect, but since the quote form prevents any evaluation, the resulting expression we create would actually be (begin f f), which is not what we want.

The quasiquote allows us to construct literal lists in a similar way as quote, but also lets us specify if any sub-expression within the list should be evaluated.

At first glance, the quasiquote (which can be invoked with the backtick ` or the quasiquote special form) behaves exactly the same as ' or quote. However, using quasiquotes gives you the ability to unquote (which can be invoked with the comma , or the unquote special form). This removes an expression from the quoted context, evaluates it, and places it back in.

By combining quasiquotes and unquoting, we can often save ourselves a lot of trouble when building macro expressions.

Here is how we could use quasiquoting to rewrite our previous example:

(define-macro (twice f)
  `(begin ,f ,f))

Important Note: quasiquoting isn't necessarily related to macros, in fact it can be used in any situation where you want to build lists non-recursively and you know the structure ahead of time. For example, instead of writing (list x y z) you can write `(,x ,y ,z) for 100% equivalent behavior

Let Special Form

The let special form allows you to create local bindings within Scheme. The let special form consists of two elements: a list of two element pairs, and a body expression. Each of the pairs contains a symbol and an expression to be bound to the symbol.

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

When evaluating a let expression, a new frame local to the let expression is created. In this frame, each variable is bound to the value of its corresponding expression at the same time. Then, the body expression is evaluated in this frame using the new bindings.

(let ((a 1)
      (b (* 2 3)))
     (+ a b)) ; This let expression will evaluate to 7

Let expressions allow us to simplify our code significantly. Consider the following implementation of filter, seen in Lab 10:

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

Now consider this alternate expression using 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)))))

Although there are more lines of code for filter, by assigning the car and cdr to the variables first and rest, the recursive calls are much cleaner.

let expressions also prevent us from evaluating an expression multiple times. For example, the following code will only print out x once, but without let we would print it twice.

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

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

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

WWSD (required)

Q1: WWSD: Macros

One thing to keep in mind when doing this question, builtins get rendered as so

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

If evaluating an expression causes an error, type SchemeError. If nothing is displayed, type Nothing.

Use Ok to test your knowledge with the following "What Would Scheme Display?" questions:
python3 ok -q wwsd-macros -u

scm> +
______
#[+]
scm> list
______
#[list]
scm> (define-macro (f x) (car x))
______
f
scm> (f (2 3 4)) ; type SchemeError for error, or Nothing for nothing
______
2
scm> (f (+ 2 3))
______
#[+]
scm> (define x 2000)
______
x
scm> (f (x y z))
______
2000
scm> (f (list 2 3 4))
______
#[list]
scm> (f (quote (2 3 4)))
______
SchemeError
scm> (define quote 7000)
______
quote
scm> (f (quote (2 3 4)))
______
7000

scm> (define-macro (g x) (+ x 2))
______
g
scm> (g 2)
______
4
scm> (g (+ 2 3))
______
SchemeError
scm> (define-macro (h x) (list '+ x 2))
______
h
scm> (h (+ 2 3))
______
7

scm> (define-macro (if-else-5 condition consequent) `(if ,condition ,consequent 5))
______
if-else-5
scm> (if-else-5 #t 2)
______
2
scm> (if-else-5 #f 3)
______
5
scm> (if-else-5 #t (/ 1 0))
______
SchemeError
scm> (if-else-5 #f (/ 1 0))
______
5
scm> (if-else-5 (= 1 1) 2)
______
2

Q2: WWSD: Quasiquote

Use Ok to test your knowledge with the following "What Would Scheme Display?" questions:
python3 ok -q wwsd-quasiquote -u

scm> '(1 x 3)
______
(1 x 3)
scm> (define x 2)
______
x
scm> `(1 x 3)
______
(1 x 3)
scm> `(1 ,x 3)
______
(1 2 3)
scm> '(1 ,x 3)
______
(1 (unquote x) 3)
scm> `(,1 x 3)
______
(1 x 3)
scm> `,(+ 1 x 3)
______
6
scm> `(1 (,x) 3)
______
(1 (2) 3)
scm> `(1 ,(+ x 2) 3)
______
(1 4 3)
scm> (define y 3)
______
y
scm> `(x ,(* y x) y)
______
(x 6 y)
scm> `(1 ,(cons x (list y 4)) 5)
______
(1 (2 3 4) 5)

Required Problems

Q3: Repeatedly Cube

Implement the following function, which cubes the given value x some number n times, based on the given skeleton.

For information on how to use let, see the scheme spec or ask your TA or an academic intern in lab.

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

Use Ok to test your code:

python3 ok -q repeatedly-cube

Q4: Scheme def

Implement def, which simulates a python def statement, allowing you to write code like (def f(x y) (+ x y)).

The above expression should create a function with parameters x and y, and body (+ x y), then bind it to the name f in the current frame.

Note: the previous is equivalent to (def f (x y) (+ x y)).

(define-macro (def func bindings body)
    'YOUR-CODE-HERE)
    `(define ,func (lambda ,bindings ,body)))

Use Ok to test your code:

python3 ok -q scheme-def

Optional Problems

Q5: Switch

Define the macro switch, which takes in an expression expr and a list of pairs, cases, where the first element of the pair is some value and the second element is a single expression. switch will evaluate the expression contained in the list of cases that corresponds to the value that expr evaluates to.

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

You may assume that the value expr evaluates to is always the first element of one of the pairs in cases. Additionally, it is ok if your solution evaluates expr multiple times.

(define-macro (switch expr cases)
    'YOUR-CODE-HERE
             (cons 'cond 
                 (map (lambda (case) (cons `(equal? ,expr (quote ,(car case))) (cdr case)))
                      cases))
)

Use Ok to test your code:

python3 ok -q switch

Q6: Dragon

Implement dragon, which draws a dragon curve. The strategy for how to draw a dragon curve is as follows. First create a list of instructions for how to draw the dragon curve. To do this, we start with the list (f x) and apply the following rewrite rules repeatedly

x -> (x r y f r)
y -> (l f x l y)

First implement flatmap function, which takes in a function and a list, and concatentates the result of mapping the function to every element of the list.

Then implement expand, which should implement the above rules in terms of flatmap

and then execute the interpreter on each argument by the following rules

x or y: do nothing
f: move forward by dist
l: turn left 90 degrees
r: turn right 90 degrees

We have given you a definition of dragon in terms of the expand and interpret functions. Complete these functions to see the dragon curve!

To learn how to control the turtle, please check out the scheme specification.

(define (flatmap f x)
  'YOUR-CODE-HERE)
  (define (h z x)
    (if (null? x)
        z
        (h (append z (f (car x))) (cdr x))))
  (h nil x))
(define (expand lst)
  'YOUR-CODE-HERE)
  (flatmap (lambda (x)
             (cond
               ((equal? x 'x) '(x r y f r))
               ((equal? x 'y) '(l f x l y))
               (else          (list x))))
           lst))
(define (interpret instr dist)
  'YOUR-CODE-HERE)
  (if (null? instr)
      nil
      (begin (define inst (car instr))
             (cond
               ((equal? 'f inst) (fd dist))
               ((equal? 'r inst) (rt 90))
               ((equal? 'l inst) (lt 90)))
             (interpret (cdr instr) dist))))
(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))

To test your flatmap and expand functions, run the following command.

Use Ok to test your code:

python3 ok -q dragon

To create a dragon curve or visually debug your code, run (speed 0) (dragon 10 10). (The function (speed 0) makes the turtle move faster, if you don't do this it will take forever.)

Unfortunately, this will only run in the interpreter you launch with python3 scheme, so to test your code, run python3 scheme -i lab12_extra.scm and then the command (speed 0) (dragon 10 10).

Hint: if you are getting a RecursionError, reimplement flatmap and interpret to be tail recursive.