# Lab 11: Macros

*Due at 11:59pm on Friday, 4/19/2019.*

## Starter Files

Download lab11.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

# Checkoff 7 (Optional)

### Q1: Infix

Recall the fact that Scheme uses prefix notation (i.e., the operators precede the operands in call expressions) and the following Calculator function:

```
>>> def calc_eval(exp):
... """Evaluates a Calculator expression represented as a Pair."""
... if isinstance(exp, Pair): # Call expressions
... fn = calc_eval(exp.first)
... args = list(exp.second.map(calc_eval))
... return calc_apply(fn, args)
... elif exp in OPERATORS: # Names
... return OPERATORS[exp]
... else: # Numbers
... return exp
```

How would we modify this function if we changed Calculator so that it uses infix notation? For example, instead of `(+ 1 2)`

we would now do `(1 + 2)`

(the operator no longer **pre**cedes the operands but is instead now **in** between the operands). Ignore order of operations, and assume that `calc_apply`

will correctly apply `fn`

to a list of evaluated `args`

.

```
>>> def calc_eval(exp):
... """Evaluates a Calculator expression represented as a Pair."""
... if isinstance(exp, Pair): # Call expressions
... first_arg = calc_eval(exp.first)
... if exp.second is not nil:
... fn = calc_eval(exp.second.first)
... second_arg = calc_eval(exp.second.second)
... return calc_apply(fn, [first_arg, second_arg])
... else:
... return first_arg
... elif exp in OPERATORS: # Names
... return OPERATORS[exp]
... else: # Numbers
... return exp
```

# WWSD (required)

### Q2: WWSD: Macros

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

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

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 (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
```

### Q3: WWSD: Quasiquote

Use Ok to test your knowledge with the following "What Would Scheme Display?" questions:

`python3 ok -q wwsd-quasiquote -u`

```
scm> '(1 2 3)
______(1 2 3)
scm> `(1 2 3)
______(1 2 3)
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)
______SchemeError
scm> `,(+ 1 x 3)
______6
scm> `(1 (,x) 3)
______(1 (2) 3)
scm> `(1 ,(+ x) 3)
______(1 2 3)
```

# Required Problems

### Q4: Scheme def

Implement `def`

, which simulates a python `def`

statement, allowing you to write code like
`(def f(x y) (+ x y))`

.

Hint: 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`

### Q5: Or macro

Implement `or-macro`

, which takes in two expressions and `or`

's them together (applying short-circuiting rules). However, do this without using the `or`

special form. You may also assume the name `v1`

doesn't appear anywhere outside this macro.

```
(define-macro (or-macro expr1 expr2)
`(let ((v1 ____________))
`(let ((v1 ,expr1)) (if _____ _____ _____)))
(if v1 v1 ,expr2)))
```

Use Ok to test your code:

`python3 ok -q or-macro`

# Optional Problem

### 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 lab11.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.