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