Tutorial 5 CSC324--F02 Eric Joanis
This week is Thanksgiving, so there is no tutorial. These notes cover
material that we would have seen in tutorial this week, and which can be
useful for the project. Some of this material will be reviewed in class
or in tutorial next week, as necessary.
apply/eval/regular procedure call
We've seen regular procedure calls in class. Now, what if I want to
call + on a list of numbers?
We can use eval:
(define lst '(1 2 3 4))
(eval (cons + lst) ()) => 10
(cons + lst) constructs the expression (+ 1 2 3 4), and then eval
evaluates it.
Alternatively, we can use the higher-order procedure apply (see Dybvig
p. 85), which is built in to Scheme. apply takes two arguments, a
procedure and a list, and applies the procedure with the elements of
the list as its arguments. For example:
(apply + '(1 2 3 4)) => 10
So if you need to apply a procedure and you already have the arguments
in a list, instead of reconstructing the correct expression and use
eval, you can call apply and it will do the work for you.
I called apply a higher-order procedure above because it takes a
procedure as one of its arguments, and applies it in some way. map is
another higher-order procedure we saw in class.
To summarize. Normal procedure application:
(+ 1 2 3 4) - use this under most circumstances
(apply + '(1 2 3 4)) - use this if the arguments are already in a list
(eval (cons + '(1 2 3 4)) ()) - use this only if you need to make a
more complicated construct, e.g., when you
need to dynamically build an expression based
on some input from the user, and then
evaluate it, as in the project.
map
We saw map in class. For a couple more examples, have a look at the
solutions to PS2, and read Dybvig p. 92 (section 5.5). We'll talk
about map and higher-order procedures more in next week's tutorial.
When you get comfortable using map, you will find that you can write
more elegant and concise code.
Another example: We can rewrite deep-properlist? using map:
(define deep-properlist?
(lambda (lst)
(cond ((pair? lst) (and (list? lst)
(applyand (map deep-properlist? lst))))
(else #t))))
; (applyand lst) returns true iff all the elements of lst are true
; Pre: lst is a list
(define applyand
(lambda (lst)
(eval (cons 'and lst) ())))
Try to answer these questions about this code:
- Why did I write a helper procedure applyand instead of simply using
apply and passing it "and", as we did with + above?
- Why does it work?
To help answer this one, by hand or using (trace deep-properlist?)
and (trace applyand), trace these calls:
(deep-properlist? '(1 2))
(deep-properlist? '(1 . 2))
(deep-properlist? '(1 2 (3 4) (5 (6 . 7) 8)))
(deep-properlist? '(1 2 (3 4) (5 (6 7) 8)))
let/let*/letrec
The syntactic forms let, let*, and letrec all allow you to define
variables that will be visible in the body of the let expression.
Syntax:
(let ((var1 value1)
(var2 value2)
...
)
body ; body can make use of var1, var2, ...
)
For example:
(let ((x 5) (y 7)) (+ x y)) => 12
A more interesting example: say you want to write f(x) + (f(x))^2 in
Scheme. We don't want to call f three times, so
(+ (f x) (* (f x) (f x)))
is not a good idea. Instead, we can use:
(let ((fx (f x))) (+ fx (* fx fx)))
Have a look at the second solution to deep-swap-first-third on Problem
Set 2 for another practical use of let.
When let is evaluated, value1, value2, ... are evaluated first, and
then the results are mapped to var1, var2, etc. This means that the
values can't depend on the vars. If you need to use the vars in the
values, use let* or letrec.
- With let*, the values are evaluated in order, and one value can access
the vars that were defined beforehand. Use let* if you have
dependencies between your variables, or if the values must be evaluated
in order.
For example:
(let* ((x 5) (y (+ x 7)) (z (* x y)))
(list x y z)
)
returns:
(5 12 60)
whereas if you try this with let instead of let*, you get the error
message "Unbound variable: y", since y doesn't exist when you are
evaluating (* x y) (and neither does x).
- With letrec, circular dependencies are allowed, so that you can define
recursive (and mutually recursive) procedures.
Example: A very inefficient way to write a predicate (odd? x) is to use
mutually recursive odd? and even? predicates. This can all be embedded
in a letrec:
; (odd? x) returns true of x is odd
; Pre: x >= 0 is an integer.
(define odd?
(lambda (x)
(letrec ((odd (lambda (x) (if (= x 1) #t (not (even (- x 1))))))
(even (lambda (x) (if (= x 0) #t (not (odd (- x 1)))))))
(odd x))))
Example: the helper procedure to fast-fib can be hidden using letrec.
We saw this code for fast-fib last week--we used with an accumulator to
make the code more efficient.
; (fast-fib p1 p2 i n) returns the nth Fibonacci number
; Pre: n>=0 is an integer, 0<=i<=n is an integer, p1 is the (i-1)th
; Fibonnaci number (or 0 if i is 0), and p2 is the ith Fib number.
(define fast-fib
(lambda (p1 p2 i n)
(if (= i n)
p2
(fast-fib p2 (+ p1 p2) (+ i 1) n))))
; (fib n) returns the nth Fibonacci number
; Pre: n is a non-negative integer
(define fib
(lambda (n)
(fast-fib 0 1 0 n)))
The disadvantage of the above solution is that the helper procedure is
visible to anyone else, and we have to come up with a name that won't
conflict with helpers to other procedures.
We can rewrite the above two procedures in a single procedure using
letrec to define the helper procedure. This way, we don't have an
extra procedure name defined that won't be used for anything else, and
we don't clutter the namespace.
; (fib n) returns the nth Fibonacci number
; Pre: n is a non-negative integer
(define fib
(lambda (n)
(letrec ((helper (lambda (p1 p2 i n)
(if (= i n)
p2
(helper p2 (+ p1 p2) (+ i 1) n)))))
(helper 0 1 0 n))
)
)