;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(planet plai/plai:1:5/lang/reader)

; Lecture Notes 
; Programming Languages
; 
; Instructor: Klaus Ostermann

; Use this file with DrScheme and the PLAI language level

; Based on PLAI Chap. 3

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


; Names and substitution

; Names are fundamental in both normal and computer languages:
; We can give a recurring complex expression a name and refer
; to the complex thing using the name

; Names are also useful for our AE language (where we will call 
; them *identifiers*)

; Example:
; {with {x {+ 5 5}} {+ x x}}
; should evaluate to 20

; Example:
; {with {x {+ 5 5}} 
;      {with {y {- x 3}}
;            {+ y y}}}
; should evaluate to 14

; But how does the evaluation work in general?

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; The grammar of our extended language, WAE, is:
; <WAE> ::= <num> 
;           | {+ <WAE> <WAE>}
;           | {- <WAE> <WAE>}
;           | {with {<id> <WAE>} <WAE>} 
;           | <id>


; Let's write a corresponding data type definition
;
(define-type WAE 
  [num (n number?)]
  [plus (l WAE?) (r WAE?)]
  [minus (l WAE?) (r WAE?)]
  [with (x symbol?) (e1 WAE?) (e2 WAE?)]
  [id (x symbol?)])

; and a parser

(define (parse sexp)
  (cond
      [(number? sexp) (num sexp)]
      [(symbol? sexp) (id sexp)]
      [(list? sexp)
       (case (first sexp)
         [(+) (plus (parse (second sexp)) (parse (third sexp)))]
         [(-) (minus (parse (second sexp)) (parse (third sexp)))]
         [(with) (with (first (second sexp))
                       (parse (second (second sexp)))
                       (parse (third sexp)))]
         )]))

; Now let's write the extended calculator!

(define (calc wae)
  (type-case WAE wae
     [num (n) n]
     [plus (l r) (+ (calc l) (calc r))]
     [minus (l r) (- (calc l) (calc r))]
     [with (x e1 e2) 
           (calc (subst e2 x (num (calc e1))))]
     [id (x) (error 'calc "unknown identifier")]))

(define (subst e1 x e2)
  (type-case WAE e1
     [num (n) e1]
     [plus (l r) (plus (subst l x e2) (subst r x e2))]
     [minus (l r) (minus (subst l x e2) (subst r x e2))]
     [with (z e3 e4) 
           (with z (subst e3 x e2) (subst e4 x e2)) ]
     [id (y) (if (symbol=? x y) e2 (id y))]))

(define ex1 '{with {x 5} {+ x y}})
(define ex2 '{with {x 5} {with {y 7} {+ x y}}})
(define ex3 '{with {x 5} {with {y 7} {+ x y}}})

; A *binding instance* of an identifier is the instance of
; the identifier that gives it its value. In WAE, the <id> position
; of a "with" expression is the only binding instance.

; The *scope* of a binding instance is the region of a program text in
; which instances of the identifier refer to the value bound by the 
; binding instance.

; An identifier is *bound* if it is contained within the scope of 
; a binding instance of its name.

; An identifier not contained in the scope of any binding instance
; of its name is *free*.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; What kind of redundancy do identifiers eleminate?
; - only static redundancy?
; - or also dynamic redundancy?


; These two variants correspond to two different calculators: eager
; and lazy

; Let's write the lazy calculator:

(define (lcalc wae)
  (type-case WAE wae
     [num (n) n]
     [plus (l r) (+ (lcalc l) (lcalc r))]
     [minus (l r) (- (lcalc l) (lcalc r))]
     [with (x e1 e2) 
           (lcalc (subst e2 x e1))]
     [id (x) (error 'lcalc "unknown identifier")]))



; Is the eager calculator always more efficient?

(define ex4 '{with {x y} {with {y 7} {+ x y}}})

; Do the eager and lazy calculators always produce the same result?

; Answer: No - the substitution algorithm does not work
; correctly in the lazy setting if the term that substitutes 
; the variable contains free variables, see (and try) ex4 above.
; This problem is known as "accidential name capture".