C311 script2.txt -- 1/20/97

HIGHER-ORDER (FIRST-CLASS) PROCEDURES (Section 1.3.2)

Passing procedures as arguments (passed downward). Example:

(define add2 (lambda (n) (+ n 2)))
(map add2 '(1 2 3)) --> (3 4 5)

or using an "anonymous procedure":

(map (lambda (n) (+ n 2)) '(1 2 3))

Can do this kind of thing with "second-class procedures", say in Pascal.

---

But consider:

(define c+
  (lambda (n1)
    (lambda (n2)
      (+ n1 n2))))

(map (c+ 2) '(1 2 3))
(map (c+ 3) '(1 2 3)) --> (4 5 6)

c+ is a function that returns a function as its result.  It is
higher-order functional programming, with first-class procedures.

---

Currying

> (define curry2
    (lambda (proc)
      (lambda (x)
	(lambda (y)
	  (proc x y)))))
		
> (define c+ (curry2 +))
> (define add2 (c+ 2))
> (define proc -)
> (let ((x 4))
    (map add2 '(1 2)))
(3 4)

---

STATIC (APARENT FROM TEXT) PROPERTIES OF VARIABLES (Section 2.3)

The SCOPE of a declaration of a variable, X, is that part of the program
within which references to variable X refer to the declaration.  

Scheme (and most modern languages) use LEXICAL, or STATIC, SCOPE: the
association between variable references and declarations is static -- it
does not depend on program execution.

Static properties are easier for programmers and compilers to reason with.

Tempting to say that the scope of a lambda-bound variable is the body of
the lambda expression.  But consider:

(lambda (x)
  ((lambda (x) (+ x 2))
   x))

We need precise terminology for concepts related to scope.

---

A REGION is associated with every declaration.  The SCOPE of a
declaration of a variable X is its region, less the regions of any
contained declarations of X.

Each variable reference is associated with the nearest lexically 
enclosing declaration of the same name (not the "nearest" one in the 
text), as in the last example.

Arrow drawing exercise, above and

(let ((x 5) (y 2))
  (let ((x (lambda (x) (+ x 3))))
    (+ x y)))

What is the meaning of the procedure (lambda (y) (proc x y))?
Procedures must record the values of variables that occur FREE.

---

A variable is BOUND in an expression if its declaration is part of the
expression.  A variable is FREE if it is not bound.

BOUND and FREE variable references, e.g. (f (lambda (x) (g x)))

OCCURS BOUND and OCCURS FREE

Value of an expression depends on the values of variables that occur
free in the expression, as well as the expression itself.

A variable may occur free in one context and bound in another.

Combinators: no free variables.  E.g. (lambda (x) x) and compose

(lambda (f g)
  (lambda (x)
    (f (g x))))

Any computation can be expressed using combinators.

---

For simplicity, study the simplest language that has first-class procedure:
the lambda calculus

Specify using BNF (inductive definition)

<exp> --> <var> | (lambda (<var>) <exp>) | (<exp> <exp>)
      ::=

syntactic categories <var> and <exp>

also \ <var> . <exp>

A sublanguage of Scheme, by Church, Turing-complete

Scheme syntax helps us write programs that process \-calculus programs

<var> as variable reference and formal paramter.

---

A variable x OCCURS FREE in an expression E if and only if

1. E is a variable reference and E is the same as x; or

2. E is of the form (lambda (y) E'), where y is different from x and
x occurs free in E'.

3. E is of the form (E1 E2) and x occurs free in E1 or E2; or

(2 and 3 reversed in book)

Definition easily extends for other binding constructs; treat their 
region like E' in (3).  Recurse on all other subexpressions, as in (2) and (3).

---

E.g.: first part of Exercise 2.3.2

(free? 'x '(lambda (y) (x y))) --> #t

> (define free?
    (lambda (var exp)
      (cond
	((symbol? exp) (eq? var exp))
	((eq? (car exp) 'lambda)
	 (and (not (eq? var (caadr exp)))
	   (free? var (caddr exp))))
	(else (or (free? var (car exp))
		(free? var (cadr exp)))))))

> (free? 'x '(lambda (x) (x y)))
#f
> (free? 'y '(lambda (x) (x y)))
#t

> (define variable? symbol?)
> (define lambda?
    (lambda (exp)
      (eq? (car exp) 'lambda)))

> (define free?
    (lambda (var exp)
      (cond
	((variable? exp) (eq? var exp))
	((lambda? exp)
	 (let ((formals (cadr exp))
	       (body (caddr exp)))
	   (and (not (eq? var (car formals)))
	     (free? var body))))
	(else ; application
	  (let ((rator (car exp))
		(rand (cadr exp)))
	    (or (free? var rator) (free? var rand)))))))

> (define rator car)
> (define rand cadr)

> (define free?
    (lambda (var exp)
      (cond
	((variable? exp) (eq? var exp))
	(else
	  (record-case exp
	    (lambda (formals body)	    
	      (and (not (eq? var (car formals)))
		(free? var body)))
	    (else
	      (or (free? var (rator exp))
		(free? var (rand exp)))))))))

---

add if

---

> (define free-vars
    (lambda (exp)
      (cond
	((variable? exp) (list exp))
	(else
	  (record-case exp
	    (lambda (formals body)
	      (remove (car formals) (free-vars body)))
	    (else
	      (union (free-vars (rator exp)) (free-vars (rand exp)))))))))

> (define union append) ; doesn't remove duplicates, see assignment 1

> (define free-vars
    (lambda (exp vars)
      (cond
	((variable? exp)
	 (if (member exp vars)
	   '()
	   (list exp)))
	(else
	  (record-case exp
	    (lambda (formals body)
	      (free-vars body
		(cons (car formals) vars)))
	    (else
	      (union (free-vars (rator exp) vars)
		(free-vars (rand exp) vars))))))))

---

Assignment: bound?, bound-vars, lexical-distance.

---

A variable x OCCURS BOUND in an expression E if and only if

1. E is of the form (E1 E2) and x occurs bound in E1 or E2; or

2. E is of the form (lambda (y) E1), wheee x occurs bound in E1 or x and y
are the same variable.

(delete "and y occurs free in E'" from (2) in text)

---

All bullet exercises are recommended, whether assigned or not.

---

Let is syntactic sugar for a call in which the operator is a lambda expression:

(let ((v1 e1) (v2 e2) ...) body) ==>

((lambda (v1 v2 ...) body)
 e1
 e2
 ...
 )

We see that the region of a let expression is its body, and does not
include its declaration expressions (e1, e2, ... above).

The region of a letrec expression includes its body and its declaration
expressions. 

---

Region bounderies are referred to as CONTOURS.

Consider

(let ((x 5))
  (let ((y 2) (z 0))
    (let ((z (lambda (x) (+ x z))))
      (+ x y))))

The number of contours between a variable reference and its associated 
declaration is its LEXICAL DEPTH.  The position of a variable declaration 
in a group of declarations having the same region is its LEXICAL POSITION.
The lexical depth and position of a variable define its LEXICAL ADDRESS, 
with which a variable reference may be replaced.  (Compilers do this.)
E.g. for example above, expressing lexical addresses as DEPTH:POSITION 
(zero based indexing)

(let ((x 5))
  (let ((y 2) (z 0))
    (let ((z (lambda (x) (2:0 0:0 1:0))))
      (3:0 2:0 1:0))))

---

Lexical position not necessary in the lambda calculus, so lambda calculus 
expressions can be represented with the syntax

<exp> --> <depth number> | \ <exp> | (<exp> <exp>)

Since names don't matter, we can change the names of bound variables.

---

ALPHA-CONVERSION: change the name of a variable declaration and all 
variable references associated with the declaration to the same name.

Precaution:  the new name must not be the name of a variable that occurs 
free in the expression.  E.g.

(lambda (x) (+ x 3)) -/-> (lambda (+) (+ + 3))

Also be careful about holes in the scope of the declaration being changed.

(lambda (x) (lambda (x) x))  -/->  (lambda (y) (lambda (x) y))

Write exp[y/x], read "exp with y for x", for substitution of y for all 
free occurances of x in exp.

ALPHA-CONVERSION RULE: (lambda (var) exp) <-> (lambda (var') exp[var'/var])
where var' does not occur free in exp.

---

FUNCTIONAL ABSTRACTION: hides details of computation.

DATA ABSTRACTION: hides details of data representation (ENCAPSULATION).

-- MODULARITY: grouping of procedures that operate on data

-- INFORMATION HIDING: only those procedures have access to the data

-- Result: REPRESENTATION INDEPENDENCE: dependence on the representation of 
   a type of data is isolated to the operations of an ABSTRACT DATA TYPE (ADT).

---

ADT has an INTERFACE and an IMPLEMENTATION.

For example, finite functions ADT interface: create-empty-ff, extend-ff*,
apply-ff (book starts with extend-ff).

E.g., Let's implement the finite function represented in mathematical
notation as {(a,1),(b,2),(c,3)}.

    > (define abc-ff 
	(extend-ff* '(a) '(1)
	  (extend-ff* '(b c) '(2 3)
	    (create-empty-ff))))
    > (apply-ff abc-ff 'b)
    2

---

Functional representation:

> (define create-empty-ff
    (lambda ()
      (lambda (symbol) 
	(error 'empty-ff "no association for symbol: ~s" symbol))))

> (define extend-ff*
    (lambda (sym-list val-list ff)
      (lambda (symbol)
	(let ((x (memq symbol sym-list)))
	  (if (not x)
            (apply-ff ff symbol)
            (list-ref val-list (- (length sym-list) (length x))))))))

> (define apply-ff
    (lambda (ff symbol) 
      (ff symbol)))

---

Record representation: one record for each lambda expression that 
represents a finite function, with the record fields recording the values 
of the free variables.

In EOPL style:

(define-record empty-ff ())
(define-record extended-ff* (sym-list val-list ff))

(define create-empty-ff
  (lambda ()
    (make-empty-ff)))

(define extend-ff*
  (lambda (sym-list val-list ff)
    (make-extended-ff* sym-list val-list ff)))

(define apply-ff
  (lambda (ff symbol)
    (variant-case ff
      (empty-ff ()
        (error "empty-ff: no association for symbol" symbol))
      (extended-ff* (sym-list val-vector ff)
        (let ([val (ribassoc symbol sym-list val-vector '*fail*)])
          (if (eq? val '*fail*)
              (apply-ff ff symbol)
              val)))
      (else (error "apply-ff: Invalid finite function" ff)))))

---

    > (define ff2 (extend-ff* '(a b c) '(1 2 3) (create-empty-ff)))
    > (define ff3 (extend-ff* '(d e) '(4 5) ff2))
    > ff3
    #(extended-ff* (d e) #(4 5)
       #(extended-ff* (a b c) #(1 2 3) 
	  #(empty-ff)))

---

In our record-case style:

> (define empty-ff '(empty-ff))

> (define extend-ff*
    (lambda (sym-list val-list ff)
      (list 'extended-ff* sym-list val-list ff)))

> (define apply-ff
    (lambda (ff symbol)
      (record-case ff
	(empty-ff ()
	  (error "empty-ff: no association for symbol" symbol))
	(extended-ff* (sym-list val-vector ff)
	  (let ([val (ribassoc symbol sym-list val-vector '*fail*)])
	    (if (eq? val '*fail*)
              (apply-ff ff symbol)
              val)))
	(else (error "apply-ff: Invalid finite function" ff)))))

---    

Alternate "rib structure" representation:

(((d e) . #(4 5))
 ((a b c) . #(1 2 3)))

Exercise 3.6.1: implement the ADT with rib-structure representation.

---

Abstract vs. concrete syntax.

Data representation of parse trees:
  a record for each node
  non-terminal nodes have a record field for each subtree
  terminal nodes have record field for any scanner information

Specify:
    variant record name for each production rule (not syntactic category)
    a unique name to each record field (occurance of a non-terminals,
      or piece of terminal information)

---

In book (and using the record.ss file):

(define-record <record name> (<field name_1> ... <field name_n>))

creator procedure: make-<record name>

record predicate: <record name>?

field selection procedures:
  <record name>-><field name_1>, ..., <record name>-><field name_n>

records represented as vectors

---

E.g., lambda calculus

(define-record varref (var))
(define-record lambda (var body))
(define-record app (rator rand))

(define parse
  (lambda (x)
    (cond ((symbol? x) (make-varref x))
          ((eq? (car x) 'lambda) (make-lambda (caadr x) (parse (caddr x))))
          (else (make-app (parse (car x)) (parse (cadr x)))))))

not robust.

Record selectors and predicates usually used in a pattern that is 
abstracted by the variant-case syntactic extension.

(define free?
  (lambda (var1 exp)
    (variant-case exp
      (varref (var) (eq? var var1))
      (lambda (var body)
        (and (not (eq? var var1))
             (free? var1 body)))
      (app (rator rand)
           (or (free? var1 rator)
               (free? var1 rand))))))

expands to

(let ((e exp))
  (cond ((varref? e) (let ((var (varref->var e))) (eq? var var1)))
        ((lambda? e) (let ((var (lambda->var e)) (body (lambda->body e)))
                       ...))
        ...))

---

END

---