Lab 10: Arithmetic Expressions

Part 1

In this problem you will define operations over a small programming language: the language of basic arithmetic expressions.

;; An Op is one of
;; - "+"
;; - "-"
;; - "*"
;; - "/"

(define-struct const [val])
(define-struct expr [op left right])

;; An Expr is one of:
;; (make-const Number)
;; (make-expr Op Expr Expr)
;; Represents an arithmetic expression

(define EEXPR0 (make-const 0))
(define EEXPR1 (make-expr '+ (make-const 1) (make-expr '- (make-const 3) (make-const 2))))

Be sure to follow the DR for the following problems.

Define a function eval that evaluates an arithmetic expression a number (with each operator mapped to its usual meaning).
Not all expressions actually can be evaluated. Define a predicate div0? that determines if an arithmetic expression ever divides by 0.
Define a function show-work that produces a list including all intermediate expressions computed during evaluation. Your function may include duplicate expressions. For example, when evaluating (- (* 3 (+ 1 2)) (/ 25 5)), your function might output a list with the following entries (depending on your traversal order):
```
(- (* 3 (+ 1 2)) (/ 25 5))
(- (* 3 3) (/ 25 5))
(- 9 (/ 25 5))
(- 9 5)
4
```

Part 2

We will now modify our arithmetic expression tree to include variables that can reference some value. We will use the hash-tables library we used in Lab 08. Example: (* "x" (+ 1 "y"))

Modify your data definition to include variables.
Write the template for expressions and two examples.

In order to evaluate expression trees with variables we have to define a mapping between variables and values.

Modify the function eval such that it takes in a mapping and an expression tree and evaluates the expression.

In real programming languages, you can have variables reference other variables as well.

Modify the variable mapping appropriately so that your variables can reference the values stored in other variables.
Modify eval appropriately.