CSSE 304 Day 11
Your list-recur examples Lambda Calculus syntax Free and Bound Variables (if time) Lexical address
Student Questions?
path-to solution
• Notice that I avoided using append
1
list-recur abstracts list recursion
• From last time: Try to come up with at least one other procedure that is easy to write using list-recur. Hopefully something
that is not a clone of one that we wrote.
• And write it!
(define list-sum (list-recur 0 +)
(define list-prod (list-recur 1 *)
(define apply-to-all (lambda (proc)
(list-recur ′()
(lambda (x y)
(cons (proc x) y)))))
(define member?-c (lambda (item)
(list-recur #f (lambda (x y)
(or (equal? item x)
y)))))
(define length (list-recur 0 (lambda (x y) (+ 1 y))))
One of these may be a bad idea!
Your examples?
List of procedures problem
>(define a )
>(list ((car a) 4 7) ((cadr a) 4 7))
(11 28)
2
List of procedures problem
> (define a ′(+ *))
; Does this work?
> (list ((car a) 4 7) ((cadr a) 4 7))
(11 28)
List of procedures problem
> (define a (list + *) )
;fill it in!
> (list ((car a) 4 7)
((cadr a) 4 7))
(11 28)
3
BACK TO SYNTAX ANALYSIS
Variable Definitions and Uses
• In (define x (+ x 3)), the two places
that the symbol x appears are fundamentally different. l-value, r-value
• definition (binding) vs. use (occurrence).
• declaration vs. reference.
• the value named by a variable is that variable’sdenotation. Thevariable denotes the value.
• In Scheme, can determine the relationship between a variable reference and the declaration that bound it by looking at the code . static (lexical) scoping.
4
Scoping rules in C
#include
int x = 3; int y;
{
int x = 5;
y = x + 2; }
printf(“%d\n”, x+y); }
A lot like Scheme (lexical scope).
You can tell which definition goes with each use by
looking at the code; you do not have to consider what happens at run-time.
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.
5
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
6
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 (
(
7
lexical depth and lexical address
(If we have time today)
• Whatarethey?
• Whataretheygoodfor?
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.
8
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)))
9
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)))
10