This is a simplified version of the code at ...
You can use this code as follows:
- 1. First, use a text editor to fill in the uncompleted portions.
+ 1. First, use a text editor to fill in the (* COMPLETE THIS *) portions
2. Then see if OCaml will compile it, by typing `ocamlc -c untyped_evaluator.ml` in a Terminal.
3. If it doesn't work, go back to step 1.
4. If it does work, then you can start up the OCaml toplevel using `ocaml -I DIRECTORY`,
| Var(var_ident) ->
var_ident = ident
| App(head, arg) ->
- free_in ident head || free_in ident arg
+ (* COMPLETE THIS *)
| Lambda(bound_ident, body) ->
- bound_ident <> ident && free_in ident body
+ (* COMPLETE THIS *)
| Let(bound_ident, arg, body) ->
- free_in ident arg || (bound_ident <> ident && free_in ident body)
+ free_in ident arg || (* COMPLETE THIS *)
| If(test, yes, no) ->
free_in ident test || free_in ident yes || free_in ident no
| Closure _ -> assert false
(match reduce_head_once arg env with
| AlreadyResult _ ->
(* if arg was not reducible, we can substitute *)
- ReducedTo (substitute bound_var arg body)
+ (* COMPLETE THIS *)
| StuckAt _ as outcome -> outcome (* propagate Stuck subterm *)
| ReducedTo arg' -> ReducedTo (App(head, arg')))
(match reduce_head_once head env with
| AlreadyResult _ -> (* head was not reducible, was arg? *)
(match reduce_head_once arg env with
- | ReducedTo arg' -> ReducedTo (App(head, arg'))
+ | ReducedTo arg' -> (* COMPLETE THIS *)
(* reducible cases of App(result, result) were caught above; so here we're stuck *)
| AlreadyResult _ -> StuckAt term
| StuckAt _ as outcome -> outcome) (* propagate Stuck subterm *)
| StuckAt _ as outcome -> outcome (* propagate Stuck subterm *)
- | ReducedTo head' -> ReducedTo (App(head', arg)))
+ | ReducedTo head' -> (* COMPLETE THIS *))
bound to the result of evaluating arg under the
current env *)
let arg' = eval arg env in
- let env' = push bound_var arg' env in
- eval body env'
+ let env' = (* COMPLETE THIS *)
| App(head, arg) ->
(match eval head env with
(* evaluate body under saved_env to govern its free
variables, except that we add a binding of
bound_var to arg' *)
- let saved_env' = push bound_var arg' saved_env in
- eval body saved_env'
+ let saved_env' = (* COMPLETE THIS *)
| head' -> raise (Stuck(App(head',arg))))