;; 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-5

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

; Functions

; Often, "with" expressions are not enough

; "with" expressions must be given a value immediately

; Ex: {with {x 5} {+ x 3}}

; often, however, we want to *abstract* over the concrete value

; Ex: f(x) = x + 3

; this is what functions are for

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

; Adding functions to WAE

; Grammar:
; <F1WAE> ::= <num> 
;          | {+ <F1WAE> <F1WAE> }
;          | {with {<id> <F1WAE> } <F1WAE> }
;          | <id>
;          | {<id> <F1WAE>}


(define-type F1WAE
  [num (n number?)]
  [plus (lhs F1WAE?) (rhs F1WAE?)]
  [with (x symbol?) (e1 F1WAE?) (e2 F1WAE?)]
  [id (x symbol?)]
  [app (f symbol?) (a F1WAE?)])

; We also need a datatype to store functions

(define-type FunDef 
  [fundef (name symbol?) (arg symbol?) (body F1WAE?)])

(fundef 'double 'n (plus (id 'n) (id 'n)))

; We'll skip the parser this time

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


; Let's write the interpreter for that language

; This is its signature:

; interp : F1WAE listof(fundef) -> number

(define (lookup-function name defs)
  (if (empty? defs) 
      (error 'lookup-function "function not found")
      (if (symbol=? name (fundef-name (first defs)))
          (first defs)
          (lookup-function name (rest defs)))))
      

(define (subst e1 x e2)
  (type-case F1WAE e1
     [num (n) e1]
     [plus (l r) (plus (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))]
     [app (f a) (app f (subst a x e2))]))

(define (interp expr fun-defs)
   (type-case F1WAE expr
       [num (n) n]
       [plus (l r) (+ (interp l fun-defs) (interp r fun-defs))]
       [with (bound-id named-expr bound-body) 
              (interp (subst bound-body bound-id 
                             (num (interp named-expr fun-defs)))
                      fun-defs)]
       [id (v) (error 'interp "unknown identifier")]
       [app (fun-name arg-expr) 
            (local ([define the-fun-def (lookup-function fun-name fun-defs)])
              (interp (subst (fundef-body the-fun-def)
                             (fundef-arg the-fun-def)
                             (num (interp arg-expr fun-defs)))
                             fun-defs))]))


; Here is test:

(interp (app 'double (app 'double (num 10))) 
        (list (fundef 'double
                      'n
                      (plus (id 'n) (id 'n)))))




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

; Environments

; Substitutions are inefficient and impractical! (why?)

; How can we improve the efficiency?

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



; An environment is a mapping from names to values

(define-type Env
  [emptyEnv]
  [anEnv (name symbol?) (value number?) (rest Env?)])

; A lookup function will prove useful

(define (lookup name env)
  (type-case Env env
    [emptyEnv () (error 'lookup "name not found")]
    [anEnv (n value rest)
           (if (symbol=? n name)
               value
               (lookup name rest))]))




; Now let's rewrite the interpreter to take the environment into account


(define (interpenv expr fun-defs env)
   (type-case F1WAE expr
       [num (n) n]
       [plus (l r) (+ (interpenv l fun-defs env) 
                      (interpenv r fun-defs env))]
       [with (bound-id named-expr bound-body) 
              (interpenv bound-body
                         fun-defs
                         (anEnv bound-id 
                                (interpenv named-expr fun-defs env)
                                env))]
       [id (v) (lookup v env)]
       [app (fun-name arg-expr) 
            (local ([define the-fun-def (lookup-function fun-name fun-defs)])
              (interpenv (fundef-body the-fun-def)
                         fun-defs
                         (anEnv 
                             (fundef-arg the-fun-def)
                             (interpenv arg-expr fun-defs env)
                             (emptyEnv))))])) ; replace with "env" to switch to dynamic scoping


; Let's test:

(interpenv (app 'double (app 'double (num 10)))
           (list (fundef 'double
                         'n
                         (plus (id 'n) (id 'n))))
           (emptyEnv))



; the following two tests should both fail

;(interp (with 'n (num 5) (app 'f (num 10)))
;           (list (fundef 'f
;                         'p
;                         (id 'n)))
;           )
;
;(interpenv (with 'n (num 5) (app 'f (num 10)))
;           (list (fundef 'f
;                         'p
;                         (id 'n)))
;           (emptyEnv))





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

; Static scope: In a language with static scope, the scope of an identifier's
; binding is a syntactically delimited region

; Dynamic scope: In a language with dynamic scope, the scope of an 
; identifier's binding is the entire remainder of the execution 
; until it is overriden by a later binding

; Dynamic scope was (and is) available in some variants of Lisp
; (but not Scheme), and is nowadays widely considered a bad idea


; Let's change the interpreter to static scoping: