CSC 324 Tutorial Week 6
=======================
more about macros
=================
Question
--------
Pretend that `and' isn't defined, but `or' is. Define `and'.
Note: standard `and' actually returns last argument when none are #f,
but don't worry about that here
Answer
------
Want (and e1 ...) to be (not (or (not e1) ...))
- ... is smart here, repeats (not e1) for each of e1 ...
(define-syntax and
(syntax-rules ()
((and e1 ...)
(not (or (not e1) ...)))))
((and e1 e2 e3 ...)
(if e1 (and e2 e3 ...) #f))))
Question
--------
Pretend `not' isn't defined. Define it.
Answer
------
Always evaluates its argument, so procedure.
(define (not a) (if a #f #t))
Question (with answers mixed in)
--------------------------------
Consider:
(define-syntax s
(syntax-rules ()
((s e)
(let ((t 7)) e))))
Evaluate the following:
(s t) ; error: t undefined
- expanded to something like (let ((local-t 7)) t)
(let ((t 3)) (s t)) => 3 ; still `our' t
Question (with answers mixed in)
--------------------------------
Consider:
(define-syntax s
(syntax-rules ()
((s t e) ; notice t as pattern variable
(let ((t 7)) e))))
Evaluate the following:
(s v v) => 7
- expanded to (let ((v 7)) v) ; same v's, since we supplied them
(s t t) => 7
- expanded to (let ((t 7)) t) ; same t's, since we supplied them
(s v t) ; error, t undefined
- expanded to (let ((v 7)) t)
(let ((t 3)) (s v t)) => 3
Question (with answers mixed in)
--------------------------------
Consider:
(define-syntax s
(syntax-rules (t) ; notice t keyword
((s t e)
(let ((t 7)) e))))
Evaluate the following:
(s v v) ; syntax error, v doesn't match t
(s t t) ; t undefined (like (s t) earlier)
(s v t) ; syntax error, v doesn't match t
(let ((t 3)) (s v t)) => 3
This s is more similar to our first s than our second s, except it
requires a middle parameter called t.
Pattern matching with match
===========================
Recall: match.ss implements a
In DrScheme, choose one of the PLT languages that includes MzScheme.
Then to load the matching library:
(require (lib "match.ss"))
Question
--------
In the following (incomplete) expression,
(define e '(let ((x 1) (y 2)) (+ x y)))
(match e
(('let ((binding values) ...) exp)
<body>))
1. Does the e match the pattern? -yes
2. What are the bindings for binding, values and exp?
Answer
------
The ... is smart (just like in define-syntax rules!)
The variable bindings are:
binding = (x y)
values = (1 2)
exp = (+ x y)
Question
--------
Complete the above expression to fill in the <body> as a lambda expression.
Attempt 1
---------
(match e
(('let ((binding values) ...) exp)
'((lambda binding exp) values)))
=> ((lambda binding exp) values)
Oops, wrong quoting.
Answer
------
(match e
(('let ((binding values) ...) exp)
(cons (list 'lambda binding exp) values)))
=> ((lambda (x y) (+ x y)) 1 2)
That's better.
eval
====
Suppose we want to evaluate it now. How to convert from a list to its
Scheme evaluation? Use the built-in eval procedure.
eval is part of Scheme's read-eval-print loop.
(eval '((lambda (x y) (+ x y)) 1 2)) => 3
Remember, all expressions are evaluated, then first is applied to the rest.
So, if we defined a to be the result of the match call above,
a => ((lambda (x y) (+ x y)) 1 2)
(eval a) => 3
Named let
=========
Recall named let makes it easier to do some recursion.
Question
--------
Write a procedure divisors that takes an integer n and returns a list
of its nontrivial divisors (don't include 1 and n).
Idea: create a helper procedure f that takes an integer i and returns
a list of nontrivial divisors of n between i and n.
Answer
------
The procedure divisors defined below uses named let to compute the
nontrivial divisors of a nonnegative integer.
(define divisors
(lambda (n)
(let f ((i 2))
(cond
((>= i n) '())
((integer? (/ n i))
(cons i (f (+ i 1))))
(else (f (+ i 1)))))))
(divisors 5) => ()
(divisors 32) => (2 4 8 16)
The version above is non-tail-recursive when a divisor is found and
tail-recursive when a divisor is not found. Can we make it fully
tail-recursive? (which would give us performance benefits)
Recall: tail-recursion means procedure result is call to itself (probably
with different parameters)
Answer
------
The version below is fully tail-recursive. It builds up the list in
reverse order, but this is easy to remedy (exercise)
(define divisors
(lambda (n)
(let f ((i 2) (ls '()))
(cond
((>= i n) ls)
((integer? (/ n i))
(f (+ i 1) (cons i ls)))
(else (f (+ i 1) ls))))))
(Idea for exercise: either reverse the list on exit or start at
n - 1 and count down to 1.)
continuations
=============
Recall call-with-current-continuation (abbreviated call/cc).
call/cc creates a representation of the current point or moment
of execution (called the current continuation).
- this moment is "get the value of an expression, for use in a computation"
For example, want to compute (+ 1 ___). We put call/cc in the blank
to construct this continuation (i.e., a partial computation).
We need to grab ahold of this computation somehow... let's pass it as
a parameter to a procedure (we'll need to give this procedure to call/cc)
--> so we write (call/cc (lambda (k) ...))
k is the continuation. The continuation is looking for a value to
finish the computation. To specify that value to use, we call k with
that value.
Thus:
(+ 1 (call/cc (lambda (k) (k 3))))
-> evals to (<procedure:+> 1 ___), creates continuation
-> passes continuation to procedure, execution goes on
-> procedure calls k (the continuation) with 3
-> resume earlier computation, using 3 as the missing value
=> returns 4
Declaring a continuation globally can help one reuse it many times, which
makes the 'rest of the computation' available for reuse.
(define r #f)
(+ 1 (call/cc
(lambda (k)
(set! r k)
(k 3))))
=> 4, as before
But now we can call the continuation with any value:
(r 3) ==> 4
(r 10) ==> 11
(r 0.1) ==> 1.1
The critical thing to understand here is that, this is not a function but a
continuation. That can be illustrated by
(+ 3 (* 10 (r 5))) ==> 6
Calling the continuation abandons the context that surrounds it!
The current execution (or current continuation) is thrown away,
because we resume the old one.