Create the file interpreter.ml with the following data type:
type exp =
| True
| False
| If of exp * exp * exp
| Num of int
| IsZero of exp
| Plus of exp * exp
| Mult of exp * exp
and exception
exception Eval_error
Create the two functions:
step : exp -> exp
multi-step : exp -> exp
let rec step (e : exp) = … insert code …
let rec multi-step (e : exp) = … insert code …
The function step takes in input an expression and returns the expression that results from computing one step of the expression in input, or raises the OCaml exception Eval_error if the computation fails.
The function multi-step takes in input an expression and iterates the function step in order to evaluate the expression one step at a time until it returns a value, or raises the OCaml exception Eval_error if the computation fails.
Test multi-step with the following inputs:
1) true => true
(multi-step True)
Output: True
2) false => false
(multi-step False)
Output: False
3) 0 => 0
(multi-step (Num 0))
Output: (Num 0)
4) iszero(0) => true
(multi-step (IsZero (Num 0)))
Output: True
5) iszero(1 + 1) => false
(multi-step (IsZero (Plus (Num 1, Num 1))))
Output: False
6) iszero((2 + -1) + 1) => false
(multi-step (IsZero (Plus (Plus (Num 2, Num (-1)), Num 1))))
Output: False
7) (-1 + 1) + (-1 + 1) => 0
(multi-step (Plus (Plus (Num (-1), Num 1), Plus (Num (-1), Num 1))))
Output: (Num 0)
8) -1 + ((2 * 2) + 1) => 4
(multi-step (Plus (Num (-1), Plus (Mult (Num 2, Num 2), Num 1))))
Output: (Num 4)
9) (((2 + -1) + 1) + -1) => 1
(multi-step (Plus (Plus (Plus (Num 2, Num (-1)), Num 1), Num (-1))))
Output: (Num 1)
10) iszero(-1 + 1) + 1 => Eval_error
(multi-step (Plus (IsZero (Plus (Num (-1), Num 1)), Num 1)))
Output: Eval_error
11) iszero(if iszero(0) then true else 0) => Eval_error
(multi-step (IsZero (If (IsZero (Num 0), True, Num 0))))
Output: Eval_error
12) iszero(if iszero(5 * 0) then (if false then 0 else iszero(-1 + 0)) else 0) => Eval_error
(multi-step
(IsZero
(If
( IsZero (Mult (Num 5, Num 0))
, If (False, Num 0, IsZero (Plus (Num (-1), Num 0)))
, Num 0 ))))
Output: Eval_error
13) if iszero(-1 + 1) then 2 else true => 2
(multi-step (If (IsZero (Plus (Num (-1), Num 1)), Num 2, True)))
Output: (Num 2)
14) if (if iszero((1 + -1) * 1) then false else true) then 1 * 2 else true => true
(multi-step
(If
( If (IsZero (Mult (Plus (Num 1, Num (-1)), Num 1)), False, True)
, Mult (Num 1, Num 2)
, True )))
Output: True
15) if (if iszero(0 * 0) then iszero(2) else 0) then 2 * (1 * 1) else ((((if iszero(0) then 1 else 0) + -1) + 1) + -1) + 1 => 1
(multi-step
(If
( If (IsZero (Mult (Num 0, Num 0)), IsZero (Num 2), Num 0)
, Mult (Num 2, Mult (Num 1, Num 1))
, Plus
( Plus
( Plus
( Plus (If (IsZero (Num 0), Num 1, Num 0), Num (-1))
, Num 1 )
, Num (-1) )
, Num 1 ) )))
Output: (Num 1)
16) if true then (if true then (if false then 0 else 1) * 1 else 5) else (4 * 1) + 1 => 1
(multi-step
(If
( True
, If (True, Mult (If (False, Num 0, Num 1), Num 1), Num 5)
, Plus (Mult (Num 4, Num 1), Num 1) )))
Output: (Num 1)
17) if iszero(if iszero(-1 + 2) then 0 else 1) then (if true then (if false then 0 * 6) else 5) else 5 => 5
(multi-step
(If
( IsZero (If (IsZero (Plus (Num (-1), Num 2)), Num 0, Num 1))
, If
( True
, If (False, Mult (Num 0, Num 6), Plus (Num 0, Num 1))
, Num 5 )
, Num 5 )))
Output: (Num 5)
18) if iszero(-1 + (1 + (-1 + 1))) then iszero(true) else 1 => Eval_error
(multi-step
(If
( IsZero (Plus (Num (-1), Plus (Num 1, Plus (Num (-1), Num 1))))
, IsZero True
, Num 1 )))
Output: Eval_error
19) 1 + (-1 + (if iszero(1 + (if true then 1 else 2)) then 1 + 2 else 2 * 2)) => 4
(multi-step
(Plus
( Num 1
, Plus
( Num (-1)
, If
( IsZero (Plus (Num 1, If (True, Num 1, Num 2)))
, Plus (Num 1, Num 2)
, Mult (Num 2, Num 2) ) ) )))
Output: (Num 4)
20) -1 + (if iszero(5 + -4) then 123 * (5 + -4) else iszero(0)) => Eval_error
(multi-step
(Plus
( Num (-1)
, If
( IsZero (Plus (Num 5, Num (-4)))
, Mult (Num 123, Plus (Num 5, Num (-4)))
, IsZero (Num 0) ) )))
Output: Eval_error