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

; The grammar of object programs

(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)

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

; Try: (eval-big test-expr)

(trace eval-big)

; Step function (operational semantics)

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

(define-struct eval (e c) #:transparent)
(define-struct apply (c n) #:transparent)

(define step
  (lambda (s)
    (match s
      ((struct eval ((struct lit (n)) c))
       (make-apply c n))
      ((struct eval ((struct sub (e1 e2)) c))
       (make-eval e1 (make-sub1 c e2)))
      ((struct apply ((struct done ()) n))
       n)
      ((struct apply ((struct sub1 (c e2)) n))
       (make-eval e2 (make-sub2 n c)))
      ((struct apply ((struct sub2 (n1 c)) n))
       (make-apply c (- n1 n)))
      (_
       #f))))

(define steps
  (lambda (s0)
    (match (step s0)
      (#f s0)
      (s (steps s)))))

(define eval-small
  (lambda (e)
    (steps (make-eval e (make-done)))))

; Try: (eval-small test-expr)

(trace steps)