We won't try here to catch any type errors, such as attempts to add a `bool` to an `int`, or attempts to check whether a `bool` iszero. Neither will we try here to monadize anything: these will be implementations of a calculator with all the plumbing exposed. What we will do is add more and more features to the calculator.
-We'll switch over to using variable `g` for assignment functions, which is a convention many of you seem familiar with. As we mentioned a few times in week 9, for some purposes it's easier to implement environment or assignment functions as functions from `char`s to `int`s (or whatever variables are bound to), rather than as lists of pairs. However, we'll stick with this implementation for now. We will however abstract out the type that the variables are bound to. For now, we'll suppose that they're bound to the same types that terms can express.
+We'll switch over to using variable `g` for assignment functions, which is a convention many of you seem familiar with. As we mentioned a few times in [[week9]], for some purposes it's easier to implement environment or assignment functions as functions from `char`s to `int`s (or whatever variables are bound to), rather than as lists of pairs. However, we'll stick with this implementation for now. We will however abstract out the type that the variables are bound to. For now, we'll suppose that they're bound to the same types that terms can express.
type bound_value = expressed_value;;
type assignment = (char * bound_value) list;;
-Here's where we should be now. We expand some of the clauses in the `eval` function for clarity, and we rename a few variables:
+Here's where we should be now. We'll work with the language:
type term =
Intconstant of int
| First of term
;;
+Here is our evaluation function. We expand some of the clauses and rename a few variables for clarity. Our implementation should make it clear how to add additional constants or native predicates, such as a `Second` predicate for extracting the second element of a pair.
+
let rec eval (t : term) (g : assignment) = match t with
Intconstant x -> Int x
| Multiplication (t1, t2) ->
let rec eval (t : term) (g : assignment) (s : store) = match t with
Intconstant x -> (Int x, s)
...
- | Variable (var) -> (
+ | Variable (var) -> ((
(* we don't handle cases where g doesn't bind var to any value *)
match List.assoc var g with
| Nonrecursive value -> value
(* we update savedg to bind self_var to rec_closure here *)
let savedg' = (self_var, rec_closure) :: savedg
in Closure (arg_var, body, savedg')
- ), s
+ ), s)
...
| Lambda (arg_var, t2) -> (Closure (arg_var, t2, g), s)
...
...
| Newref (t1) ->
- let (starting_val, s') = eval t1 g s
+ let (value1, s') = eval t1 g s
(* note that s' may be different from s, if t1 itself contained any mutation operations *)
(* now we want to retrieve the next free index in s' *)
in let new_index = List.length s'
- (* now we want to insert starting_val there; the following is an easy but inefficient way to do it *)
- in let s'' = List.append s' [starting_val]
+ (* now we want to insert value1 there; the following is an easy but inefficient way to do it *)
+ in let s'' = List.append s' [value1]
(* now we return a pair of a wrapped new_index, and the new store *)
in (Mutcell new_index, s'')
| Deref (t1) ->
(* we don't handle cases where t1 doesn't evaluate to a Mutcell *)
let (Mutcell index1, s') = eval t1 g s
(* note that s' may be different from s, if t1 itself contained any mutation operations *)
- in let (new_value, s'') = eval t2 g s'
- (* now we create a list which is just like s'' except it has new_value in index1 *)
+ in let (value2, s'') = eval t2 g s'
+ (* now we create a list which is just like s'' except it has value2 in index1 *)
in let rec replace_nth lst m =
match lst with
| [] -> failwith "list too short"
- | x::xs when m = 0 -> new_value :: xs
+ | x::xs when m = 0 -> value2 :: xs
| x::xs -> x :: replace_nth xs (m - 1)
in let s''' = replace_nth s'' index1
(* we'll arbitrarily return Int 42 as the expressed_value of a Setref operation *)
(* we don't handle cases where t1 doesn't evaluate to a Pair *)
let (Pair (index1, index2), s') = eval t1 g s
(* note that s' may be different from s, if t1 itself contained any mutation operations *)
- in let (new_value, s'') = eval t2 g s'
- (* now we create a list which is just like s'' except it has new_value in index1 *)
+ in let (value2, s'') = eval t2 g s'
+ (* now we create a list which is just like s'' except it has value2 in index1 *)
in let rec replace_nth lst m =
match lst with
| [] -> failwith "list too short"
- | x::xs when m = 0 -> new_value :: xs
+ | x::xs when m = 0 -> value2 :: xs
| x::xs -> x :: replace_nth xs (m - 1)
in let s''' = replace_nth s'' index1
in (Int 42, s''')