;; 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)
; Implementing laziness

; Changing the substitution-based FAE interpreter to lazy evaluation is trivial

; But we know about the disadvantages of substitution, hence let's think about
; environment-based lazy evaluation


; Consider the followig expression and let's reduce it by hand with both 
; substitution and environments

;{with {x {+ 4 5}}
;      {with {y {+ x x}}
;            {with {z y}
;                  {with {x 4}
;                        z}}}}

; we need expression closures

(define-type FAE/L
  [num (n number?)]
  [add (lhs FAE/L?) (rhs FAE/L?)]
  [id (name symbol?)]
  [fun (param symbol?) (body FAE/L?)]
  [app (fun-expr FAE/L?) (arg-expr FAE/L?)])

(define-type FAE/L-Value
  [numV (n number?)]
  [closureV (param symbol?) 
            (body FAE/L?)
            (env Env?)]
  [exprV (expr FAE/L?)
         (env Env?)])

(define-type Env
  [emptyEnv]
  [anEnv (name symbol?) (value FAE/L-Value?) (env Env?)])

(define (lookup v env)
  (type-case Env env
             [emptyEnv () (error 'lookup "unknown identifier")]
             [anEnv (name value rest)
                    (if (symbol=? v name)
                        value
                        (lookup v rest))]))

(define (strict value)
  (type-case FAE/L-Value value
             [exprV (expr env)
                      (let ((result (strict (interp expr env))))
                        (printf "forcing ~v to ~v~n" expr result)
                        result)]
             [else value]))

(define (interp expr env)
  (type-case FAE/L expr
             [num (n) (numV n)]
             [add (l r) (numV (+ (numV-n (strict (interp l env))) 
                                 (numV-n (strict (interp r env)))))]
             [id (v) (lookup v env)]
             [fun (bound-id bound-body)
                  (closureV bound-id bound-body env)]
             [app (fun-expr arg-expr)
                  (let ((fun-val (strict (interp fun-expr env)))
                        (arg-val (exprV arg-expr env)))
                    (interp (closureV-body fun-val)
                            (anEnv (closureV-param fun-val)
                                   arg-val
                                   (closureV-env fun-val))))]))


(define testprog
  (app (fun 'x 
            (app (fun 'y 
                      (app (fun 'z 
                                (app (fun 'x 
                                          (id 'z))
                                     (num 4)))
                           (id 'y)))
                 (add (id 'x) (id 'x))))
       (add (num 4) (num 5))))

(define test1 (app (fun 'x (add (id 'x) (id 'x))) (num 3)))

(define test2
  (app (fun 'x (add (id 'x) (id 'x))) (add (num 27) (num 55))))

; (interp testprog (emptyEnv))