CSSE 304 Day 12 Free and bound variables
occurs-bound?
Lexical address Efficient rotate reverse and reverse!
lambda-calculus expressions
(lambda (
(
We call these three types of expressions • variableuses,
• abstractions,and
• applications.
Is this language too restrictive?
Derive ((lambda (x) (x y)) z)
For now we just treat expressions as a syntactic construct. We will consider the meanings of these expressions later.
1
Occurs free and occurs bound
For now, treat these as strictly syntactic properties. Variable x occurs free in the LcExp e iff
one of the following is true:
F1. e is a variable, and e is the same as x.
F2. e is an abstraction (λ (y) e’), where y is different from x and x occurs free in e’.
F3. e is an application (e1 e2) where x occurs free in e1 or in e2. Variable x occurs bound in the LcExp e iff
one of the following is true:
B1. e is an abstraction (λ (y) e’), where x occurs bound in e’, or
x and y are the same variable and x occurs free in e’.
B2. e is an application (e1 e2) where x occurs bound in e1 or in e2.
Variable x occurs free in the LcExp e iff
one of the following is true:
F1. eisavariable,andeisthesameasx.
F2. e is an abstraction (λ (y) e’), where y is different from x
and x occurs free in e’.
F3. e is an application (e1 e2) where x occurs free in e1 or in e2.
Variable x occurs bound in the LcExp e iff
one of the following is true:
B1. e is an abstraction (λ (y) e’), where x occurs bound in e’, or
x and y are the same variable and x occurs free in e’. B2. e is an application (e1 e2) where x occurs bound in e1 or in e2.
Does x occur free/bound in …
• x • (lambda (x) (x t))
•t
• (x t)
• ((lambda (x) x) x)
• (lambda (x) (lambda (t) (t x)))
Which rules in the above definitions tell us the answers?
For now, this is mainly about applying recursive rules
2
When dealing with the syntax or meaning of a program, we
Follow the _grammar_
Occurs free and occurs bound
Variable x occurs bound in the LcExp e iff
one of the following is true:
B1. e is an abstraction (λ (y) e’), where x occurs bound in e’,
or
x and y are the same variable and x occurs free in e’.
B2. e is an application (e1 e2) where x occurs bound in e1 or in e2. Let’s follow the grammar to write
(occurs-bound? sym exp)
(lambda (
(
3
lexical depth and lexical address
• What are they?
• What are they good for?
lexical depth and lexical address
• The lexical depth of a bound variable occurrence is the number of levels of nested declarations between it and its declaration.
• In(lambda(z) (lambda (x)
(lambda (y) (x y))))
the occurrence of y has depth 0 and the occurrence of x has depth 1. There are no occurrences of z.
• This is used by the Scheme run-time system when looking up a local variable’s value.
• More on that later.
4
lexical depth and lexical address
• Besides lexical depth, the other part of a variable’s lexical address is its position within a declaration list.
• In(lambda(xz) (lambda (y)
((x y) z)))
The occurrence of x has depth 1 and position 0. The occurrence of y has depth 0 and position 0. The occurrence of z has depth 1 and position 1.
lexical address example
(lexical-address ‘(lambda (a b c) (if (eq? b c)
((lambda (c) (cons a c))
a)
b)))
(lambda (a b c)
(if ((: free eq?) (: 0 1) (: 0 2))
((lambda (c) ((: free cons) (: 1 0)
You will write lexical- address as part of A10.
Also un-lexical-address.
(: 0 0)) (: 0 1)))
(: 0 0)))
5
lexical address exercise
(lexical-address ‘((lambda (x y)
(((lambda (z) (lambda (w y)
(+ x z w y))) (list w x y z))
(+ x y z)))
(y z)))
(lexical-address ‘(let ([a 3] [b 4])
(let ([a (+ b 2)] [c a]) (+ a b c))))
lexical address solution
(lexical-address ‘((lambda (x y)
(((lambda (z) (lambda (w y)
(+ x z w y))) (list w x y z))
(+ x y z)))
(y z)))
((lambda (x y) (((lambda (z)
(lambda (w y)
((: free +) (: 2 0) (: 1 0) (: 0 0) (: 0 1))))
((: free list) (: free w) (: 0 0) (: 0 1) (: free z))) ((: free +) (: 0 0) (: 0 1) (: free z))))
((: free y) (: free z)))
6
lexical address solution 2
(lexical-address ‘(let ([a 3] [b 4])
(let ([a (+ b 2)] [c a]) (+abc))))
(let ((a 3) (b 4))
(let ((a ((: free +) (: 0 1) 2))
(c (: 0 0)))
((: free +) (: 0 0) (: 1 1) (: 0 1))))
• What is it?
• What is it good for?
lexical address
7
Rotate
• Consider this proposed solution
(define rotate ; rotate the last list
; element to the beginning
(lambda (los)
(let loop ([los los]
[sofar ‘()])
(cond
[(null? los) los]
[(null? (cdr los)) ;one-element list
(cons (car los) sofar)]
[else ; build up the “all but last” list
(loop (cdr los) (append sofar
(list (car los))))]))))
Rotate
• Consider another solution
(define rotate ; build up list in reverse ; order, then reverse it
(lambda (los)
(let loop ([los los]
[sofar ‘()])
(cond
[(null? los) los] [(null? (cdr los))
(cons (car los) (reverse sofar))] [else ; build “all but last” in reverse
(loop (cdr los)
(cons (car los)
sofar))]))))
8
Rotate – an experiment
(define make-long-list ; make a list of n different numbers.
(lambda (n) (if (zero? n) ‘()
(cons n (make-long-list (sub1 n))))))
> (define long (make-long-list 30000)) > (begin
(collect)(time (rotate-linear long)) (collect) (time (rotate long)) ‘done)
(time (rotate-linear long)) no collections
0 ms elapsed cpu time 2 ms elapsed real time 480040 bytes allocated
(time (rotate long)) 869 collections
3183 ms elapsed cpu time, including 127 ms collecting
3187 ms elapsed real time, including 204 ms collecting
3732622096 bytes allocated, including 3729785280 bytes reclaimed
done
>
A simpler rotate
(define rotate
(lambda (L)
(if (null? L)
‘()
(let ([rev (reverse L)])
(cons (car rev)
(reverse (cdr rev)))))))
9
Interlude
In-class exercise (if there is time)
• write reverse and reverse! procedures
• For reverse!, you will need to use set-cdr!
• Both should be O(n).
• These transcripts might help you to distinguish between them.
Do this with another student or two.
10
Solutions
Interlude
Assaf Razon wrote: >
> A few of my friends and I attended a wedding. Being from Israel, this
> is naturally a Jewish wedding, and one of my friends is an ex combat
> officer in the Army. >
> So we were talking about throwing the bouquet, and I said (being the
> insistent wedding-basher) that if one were thrown at me, I’d dodge it.
> So my friend said: “I’ll just throw it at you like the Palestinians
> throw rocks and bombs at us”,
> and I answered “you mean a ‘Mazeltov Cocktail’?”
http://www.netfunny.com/rhf/jokes/97/Sep/cocktail.html
11