#lang scheme
(require (only-in mzlib/trace trace))

; The grammar of object programs -- same as in initial.ss

(define-struct lit (num) #:transparent)
(define-struct sub (e1 e2) #:transparent)

(define test-expr
  (make-sub (make-sub (make-lit 6) (make-lit 1))
            (make-sub (make-lit 3) (make-lit 2))))

; Evaluator (denotational semantics) in continuation-passing style
; (i.e., higher-order tail-form evaluator)

(define eval-big-c
  (lambda (e c)
    (match e
      ((struct lit (n))
       (c n))
      ((struct sub (e1 e2))
       (eval-big-c e1 (lambda (n1)
        (eval-big-c e2 (lambda (n2)
         (c (- n1 n2))))))))))

; Try: (eval-big-c test-expr (lambda (n) n))

(trace eval-big-c)

; Evaluator passing defunctionalized continuations
; (i.e., first-order tail-form evaluator)
; -- the definition of contexts (using define-struct) is same as in initial.ss

(define-struct done () #:transparent)
(define-struct sub1 (c e2) #:transparent)
(define-struct sub2 (n1 c) #:transparent)

(define eval
  (lambda (e c)
    (match e
      ((struct lit (n))
       (apply c n))
      ((struct sub (e1 e2))
       (eval e1 (make-sub1 c e2))))))

(define apply
  (lambda (c n)
    (match c
      ((struct done ())
       n)
      ((struct sub1 (c e2))
       (eval e2 (make-sub2 n c)))
      ((struct sub2 (n1 c))
       (apply c (- n1 n))))))

; Try: (eval test-expr (make-done))

(trace eval apply)