The top portion of the file contains datatype definitions for representing MinML programs. For reference I am also providing:

1. an executable version of the static semantics in form of function typeOf, and
2. an outline of a datatype definition for representing the mframes of the E machine. Each kind of frame is represented by one of the variants of that datatype. The stack of the E machine is a frame list.
   

This is exactly the same setup that we had for homework 5.

structure MinML = struct

    (* variables represented simply as strings *)
    type var = string

    (* in general, an environment is a mapping from variables to something *)
    type 'a env = var -> 'a

    (* extend e by binding variable x to v *)
    fun bind (a, x: var, e) y = if x = y then a else e y
    (* the empty environment simply complains *)
    fun empty (x: var) = raise Fail ("unbound variable: " ^ x)

    (* *** The MinML language *** *)

    (* primitive operators: *)
    datatype operator = PLUS | TIMES | MINUS | EQUAL | LESS

    (* simple types *)
    datatype typ =
	     INTt
	   | BOOLt
	   | FUNt of typ * typ

    (* base values (values that are not functions) *)
    datatype basevalue =
	     NUM of int
	   | TRUE
	   | FALSE

    (* primitive operators operate on base values: *)
    fun b'primop (PLUS, NUM i, NUM j) = NUM (i+j)
      | b'primop (TIMES, NUM i, NUM j) = NUM (i*j)
      | b'primop (MINUS, NUM i, NUM j) = NUM (i-j)
      | b'primop (EQUAL, NUM i, NUM j) = if i = j then TRUE else FALSE
      | b'primop (LESS, NUM i, NUM j) = if i < j then TRUE else FALSE
      | b'primop _ = raise Fail "primop: numeric argument expected"

    (* syntactic values: *)
    datatype value =
	     BVAL of basevalue
	   | FUN of function
    (* expressions: *)
	 and exp =
	     VAR of var
	   | VAL of value
	   | PRIM of operator * exp * exp
	   | IF of exp * exp * exp
	   | APPLY of exp * exp

    (* recursive "lambda" terms: "fun f(x:argt):rest is body" *)
    withtype function = { f: var, x: var, argt: typ, rest: typ, body: exp }

Your task is to

1. Fill in the definition of function bigstep'env which implements the environment-based big-step semantics.
2. Fill in the remaining cases of the datatype for machine frames.
3. Fill in the definition of function E'machine.

The E machine maps (closed) expressions to their corresponding machine values by looping through the appropriate sequence of E machine states. The states themselves are represented by calls of the functions "estate" and "vstate".

• A call of "estate(K,E,e)" represents the situation where the current expression to be evaluated in environment E is e and the work to be done later after e is finished is represented by K. This corresponds to the state (K,E,e) as discussed in class. Hint: estate should dispatch on the possible shapes of e. In each case it should make a "transition" in form of a tail-call to either another instance of estate or to an instance of vstate.

• A call of "vstate(V,K)" represents the situation where the current expression has been reduced to a machine value V which is about to be "passed up" to the next pending action represented by the topmost frame of K. This corresponds to the state (V,K) as discussed in class.

A correct solution should not have redundant or non-exhaustive matches (i.e., it should precisely handle all the situations that can be expressed using the datatypes for expressions, values, and frames).

Notice that unlike in the C machine, where encountering a variable meant that the original expression was not closed, both the big-step semantics and the E machine have to deal with variables.

First, write a function bigstep'env that implements the environment-based big-step semantics:

    datatype mvalue =
             MBVAL of basevalue
           | MCLOSURE of function * mvenv

    withtype mvenv = mvalue env

    (* primop function that works on mvalues (as opposed to base values) *)
    fun m'primop (opr, MBVAL a, MBVAL b) = MBVAL (b'primop (opr, a, b))
      | m'primop _ = raise Fail "primop: numeric argument expected"

    (* given environment E, convert value v to an mvalue: *)
    fun value2mvalue (BVAL b, _) = MBVAL b
      | value2mvalue (FUN f, E) = MCLOSURE (f, E)

    (* Your task: write a function bigstep'env that implements
     * the environment-based big-step semantics: *)

    fun bigstep'env e = let (* e should be closed here *)

	in eve (e, empty)
	end

    (*************
     * E-machine *
     *************)

    datatype mframe =

    fun E'machine e = let

	in estate ([], empty, e)
	end
end