== Small-Step Semantics ==
Create folder “interpreter” in the main directory of the project (not in the folder interpreter_bigstep)
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 step also raises the OCaml exception Eval_error when applied to a value, i.e. step True => Eval_error
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
IMPORTANT: TESTS ARE NUMBERED AND MUST BE PASSED SEQUENTIALLY TO OBTAIN THE SCORE BELOW.
Score:
Succeding tests 1-5 = 0.66
Succeding tests 6-9 = 0.67
Succeding tests 10-15 = 0.68
Succeding tests 16-20 = 0.69