Discussion 13: Macros

disc13.pdf

This is an online worksheet that you can work on during discussions and tutorials. Your work is not graded and you do not need to submit anything.

Discussion 13 Vitamin

To encourage everyone to watch or attend discussion orientation, we have created small discussion vitamins. Each vitamin you complete will give you an extra credit point towards the course. Please answer all of the questions in this form after discussion orientation and before tutorial. If you have tutorial right after discussion, please complete within 3 hours after.

Macros

Previously, we've seen how we can create macro-like functions in Python using f-strings. Now let's talk about real macros, in Scheme. 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.

In the scheme project, we saw 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!

We have a problem here: 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.

Questions

Q1: 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.

The behavior of the or macro procedure is specified by the following doctests:

scm> (or-macro (print 'bork) (/ 1 0))
bork
scm> (or-macro (= 1 0) (+ 1 2))
3

Run in 61A Code

Q2: Replicate

Write a macro that takes an expression expr and a number n and repeats the expression n times. For example, (repeat-n expr 2) should behave the same as (twice expr) from the introduction section of this worksheet. It's possible to pass in a combination as the second argument (e.g. (+ 1 2)) as long as it evaluates to a number. Be sure that you evaluate this expression in your macro so that you don't treat it as a list.

Complete the implementation for repeat-n so that its behavior matches the doctests below.

scm> (repeat-n (print '(resistance is futile)) 3)
(resistance is futile)
(resistance is futile)
(resistance is futile)

scm> (repeat-n (print (+ 3 3)) (+ 1 1))  ; Pass a call expression in as n
6
6

You may find it useful to implement the replicate procedure, which takes in a value x and a number n and returns a list with x repeated n times. We've provided some examples for how replicate should function here:

scm> (replicate '(+ 1 2) 3)
((+ 1 2) (+ 1 2) (+ 1 2))

scm> (replicate (+ 1 2) 1)
(3)

scm> (replicate 'hi 0)
()

Hint: Feel free to check out Discussion 11 and copy over your implementation of replicate!

Hint 2: Consider which method to build your list (list, cons, or quasiquote) might help make your implementation simpler.

Run in 61A Code

Q3: List Comprehensions

Recall that list comprehensions in Python allow us to create lists out of iterables:

[<map-expression> for <name> in <iterable> if <conditional-expression>]

Define a procedure to implement list comprehensions in Scheme that can create lists out of lists. Specifically, we want a list-of macro that can be called as follows:

(list-of <map-expression> 'for <name> 'in <list> 'if <conditional-expression>)

The symbols for, in, and if must be quoted when calling list-of so that they will not be evaluated. The program will error if they have not been previously defined.

Calling list-of will return a new list constructed by doing the following for each element in <list>:

Bind <name> to the element.
If <conditional-expression> evaluates to a truth-y value, evaluate <map-expression> and add it to the result list.

Here are some examples:

scm> (list-of '(* x x) 'for 'x 'in ''(3 4 5) 'if '(odd? x))
(map (lambda (x) (* x x)) (filter (lambda (x) (odd? x)) (quote (3 4 5))))

scm> (eval (list-of '(* x x) 'for 'x 'in ''(3 4 5) 'if '(odd? x)))
(9 25)

scm> (list-of ''hi 'for 'x 'in ''(1 2 3 4 5 6) 'if '(= (modulo x 3) 0))
(map (lambda (x) (quote hi)) (filter (lambda (x) (= (modulo x 3) 0)) (quote (1 2 3 4 5 6))))

scm> (eval (list-of ''hi 'for 'x 'in ''(1 2 3 4 5 6) 'if '(= (modulo x 3) 0)))
(hi hi)

scm> (eval (list-of '(car e) 'for 'e 'in ''((10) 11 (12) 13 (14 15)) 'if '(list? e)))
(10 12 14)

Hint: You may use the built-in map and filter procedures. Check out the Scheme Built-ins reference for more information.

You may also find it helpful to look at the expression returned by list-of in the example above.

Run in 61A Code

Q4: List Comprehension Macro

We managed to create a version of list comprehension in scheme, but we had to add a few extra steps to our implementation. We needed to quote parameters, make an extra call to eval at the end to actually get our answer, and quote the symbols for, in, and if to prevent our program from throwing an Error.

To make things easier, we can use the define-macro special form to simplify this process.

Now use a macro to implement the list-of macro that can be called as follows:

(list-of <map-expression> for <name> in <list> if <conditional-expression>)

Calling list-of will return a new list constructed by doing the following for each element in <list>:

Bind <name> to the element.
If <conditional-expression> evaluates to a truth-y value, evaluate <map-expression> and add it to the result list.

Here are some examples:

scm> (list-of (* x x) for x in '(3 4 5) if (odd? x))
(9 25)

scm> (list-of 'hi for x in '(1 2 3 4 5 6) if (= (modulo x 3) 0))
(hi hi)

scm> (list-of (car e) for e in '((10) 11 (12) 13 (14 15)) if (list? e))
(10 12 14)

Hint: Again, you may use the built-in map and filter procedures. Check out the Scheme Built-ins reference for more information.

If you're having a hard time with the question revisit Question 7 (If Macro Scheme) from Discussion 12.

Run in 61A Code

Q5: Shapeshifting Macros (Tutorial)

When writing macros in Scheme, we often create a list of symbols that evaluates to a desired Scheme expression. In this question, we'll practice different methods of creating such Scheme lists.

We have executed the following code to define x and y in our current environment.

(define x '(+ 1 1))
(define y '(+ 2 3))

We want to use x and y to build a list that represents the following expression:

(begin (+ 1 1) (+ 2 3))

What would be the result of calling eval on a quoted version of the expression above?

(eval '(begin (+ 1 1) (+ 2 3)))

Now that we know what this expression should evaluate to, let's build our scheme list.

How would we construct the scheme list for the expression (begin (+ 1 1) (+ 2 3)) using quasiquotation?

How would we construct this scheme list using the list special form?

How would we construct this scheme list using the cons special form?

Q6: Max Macro (Tutorial)

Define the macro max, which takes in two expressions expr1 and expr2 and returns the maximum of their values. If they have the same value, return the first expression. For this question, it's okay if your solution evaluates expr1 and expr2 more than once. As an extra challenge, think about how you could use the let special form to ensure that expr1 and expr2 are evaluated only once.

scm> (max 5 10)
10
scm> (max 12 12)
12
scm> (max 100 99)
100

First, try using quasiquotation to implement this macro procedure.

Run in 61A Code

Now, try writing this macro using the list special form.

Run in 61A Code

Finally, write this macro using the cons special form.

Run in 61A Code

Q7: When Macro (Tutorial)

Using macros, let's make a new special form, when, that has the following structure:

(when <condition>
      (<expr1> <expr2> <expr3> ...))

If the condition is not false (a truthy expression), all the subsequent operands are evaluated in order and the value of the last expression is returned. Otherwise, the entire when expression evaluates to okay.

scm> (when (= 1 0) ((/ 1 0) 'error))
okay

scm> (when (= 1 1) ((print 6) (print 1) 'a))
6
1
a

Run in 61A Code