Chapter 3 : Going Further (and more)
Primary resource: The Scheme Programming Language, by Dybvig.
Additional reference sources: Compilers: Principles, Techniques and Tools, by Aho, Sethi and Ullman. Scheme and the Art of Programming, by Springer and Friedman.
Recursion and let bindings
What will happen when you execute this expression?
(let ((last
(lambda (ls)
(if (null? (cdr ls))
(car ls)
(last (cdr ls))))
))
(last '(3 4 6 1))
)
Problem: recursive call appears before binding is complete.
Solution alternatives:
Flat versus deep recursion
The above is example of flat recursion
Flat recursion:
Deep recursion:
Example of deep recursion: count-all
(define count-all
(lambda (ls)
(cond
((null? ls) 0)
((pair? (car ls))
(+ (count-all (car ls)) (count-all (cdr ls))))
(else (+ 1 (count-all (cdr ls))))
)))
Recall definition of first-class object (see end of notes for chapter 7).
Such an object can be:
Scheme procedures are first class.
Above is example of assigning procedure to a variable.
Following are examples of the other two.
Passing procedures as parameters
Example is the
map procedure
Takes two parameters: a procedure (of one parameter) and a list
Its result is the list after the procedure has been applied to all members
Code:
(define map
(lambda (proc ls)
(if (null? ls)
'()
(cons (proc (car ls)) (map proc (cdr ls)))
)
))
Informal explanation:
apply proc to car of list, recursively map proc to cdr of list, then apply cons to result of the two.
Example use: (map (lambda (n) (+ 1 n)) '(1 2 3 4))
What is result?
Map is a recursive procedure. Is this flat recursion, or deep recursion?
Returning a procedure as procedure value
Example is currying
Currying: writing a two parameter procedure as a one parameter procedure tha returns a one parameter procedure. Can generalize to more than two params.
Named after logician Haskell Curry
Usefulness: hold one parameter constant while varying the other
Simple example:
(define curried+
(lambda (m)
(lambda (n)
(+ m n))))
Example use:
(define add5 (curried+ 5)) (define add8 (curried+ 8)) (add5 7)
An example that demonstrates all three: compose
Procedure compose takes two procedures as parameters and returns another procedure that is a composition of the two.
Code:
(define compose
(lambda (f g)
(lambda (x)
(f (g x)))))
The value of compose is: (lambda (x) (f (g x)))
Examples of its use:
(define h (compose sqrt add1))
(define k (compose add1 sqrt))
(h 8)
What is the result?
(k 9)
What is the result?
Higher-order Procedures
Definition depends on information resource; here is a sampling:
Named Let
a. global version: (already studied)
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1)))
)))
b. letrec version, restricted scope:
(letrec ((factorial (lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1)))
))
))
(factorial 5)
)
c. named let version:
(define factorial
(lambda (n)
(let fact ((i n))
(if (= i 0)
1
(* i (fact (- i 1)))
)
)))
d. named let, with local variable a (accumulator) to hold intermediate products
(define factorial
(lambda (n)
(let fact ((i n) (a 1))
(if (= i 0)
a
(fact (- i 1) (* a i))
)
)))
Factorial in part d defined by n*(n-1)*(n-2)* ... * 1, rather than n * (n-1)!
Fibonacci
Lazy Evaluation, Pass-by-name, and Thunk!
What do these terms mean, and what do they have in common?
Lazy Evaluation: computation is evaluated only once, and not until needed.
Pass-by-name:
Thunk: a parameterless procedure used to implement both of the above.
Q: What do lazy evaluation and pass-by-name have in common?
A: In both cases, expressions are not evaluated until needed.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Pass by Name
- argument is not evaluated at the time of the call!
- evaluated only when encountered during execution of the called procedure.
- evaluation based on environment of calling procedure
- thunk used to evaluate argument, has access link to calling environment
- Example:
float doublit(float val) // imagine pass-by-name
{
return val * 2.0;
}
example call, using pass by name:
a = doublit(c + 3.2 * b);
the function body becomes:
return (c + 3.2*b)*2.0;
- parentheses added to assure integrity of argument
- thunk is used to get values of b and c.
- Another Example:
void swap(int x, y) // imagine this is pass by name
{
int temp;
temp = x;
x = y;
y = temp;
}
Now, call it with:
swap(i, a[i]); where a is an array of integers.Under pass by name, the function body becomes:
temp = i;
i = a[i];
a[i] = temp;
when the l-value for
a[i] is computed in the third statement, i has changed!
- Macro expansion, such as in C or C++, has same limitation, e.g.
#define a i
#define b a[i]
. . .
temp = a;
a = b;
b = temp;
. . .
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Lazy Evaluation
For example, see pp 43-44 of Dybvig.
Procedure
lazy- takes thunk (parameterless procedure) as parameter
- maintains two local variables,
val and flag.-
val: will be set to value of thunk, the first time lazy is applied.-
flag: will be set to #t, the first time lazy is applied.- first time
lazy is applied, thunk is evaluated, value is saved in val and returned- at each subsequent application, value saved in
val is returned.
Syntactic Extension
Simple Example:
(reference-library "synrule.ss" "standard")
(define-syntax tribe
(syntax-rules ()
((_) "wahoo") ; first rule, usage is (tribe)
((_ e) (+ e 1)) ; usage (tribe exp)
((_ e1 e2) (* e1 e2)) ; usage (tribe exp1 exp2)
))
Another Example:
; Primitive loop form. Use with 2 expressions: #iterations, and
; expression to evaluate. Will repeatedly evaluate it.
(reference-library "synrule.ss" "standard")
(define-syntax loop
(syntax-rules ()
((_ e1 e2)
(let rec-loop ((i e1))
(if (<= i 1)
e2
(begin e2 (rec-loop (- i 1)))
))
)))
Pages 51 and 52 show examples for
let and and. Use ellipses (...) to indicate variable number of expressions.
Box-and-Pointer Representation
Will cover this in conjunction with textbook chapter 8 on pointers.
Continuations
Will cover this in conjunction with textbook chapter 12 on concurrency.