For this lab, you may find it useful to refer to [this summary](core-ocaml.html) of the environment model rules. These rules cover the same subset of OCaml that you studied in the last lab. **Exercise**: evaluate the following expressions using the environment model. Double check that the values that you produce match those produced by OCaml. The first expression is done for you. - `(3 + 5) * 2` ``` <[], (3 + 5) * 2> ==> 16 because <[], (3 + 5)> ==> 8 because <[],3> ==> 3 and <[],5> ==> 5 and 3+5 is 8 and <[], 2> ==> 2 and 8*2 is 16 ``` - `let x = 2 + 2 in x + x` - `let x = 1 in let x = x + x in x + x` - `let f = fun x -> fun y -> x + y in let g = f 3 in g 2` - `let f = fst (let x = 3 in fun y -> x, 2) in f 0` (Update 11/19/15: the expressions above used to be paired with a statement about the number of lines in the evaluation. That was causing too much fixation on a *number*, rather than on *understanding of the semantics*. So we've removed those statements.) **Exercise**: Write down an environment model evaluation rule for evaluating `if` expressions. Use it to evaluate the expression `if 3 < 4 then 1 + 1 else 2 + 2` Dynamic scope ------------- Recall that dynamically scoped languages use the following broken evaluation rule for function application: ``` <env, e1 e2> ==> v if <env,e1> ==> {fun x -> e | newenv} and <env,e2> ==> v2 and <env[x->v2],e> ==> v ``` note that the environment stored in the closure is ignored and the local environment at the function application site is used instead. **Exercise**: use dynamic scope to evaluate the following expressions (you do not need to write down all of the evaluation steps unless you find it helpful). Compare your answers to the answers you would expect from a language with lexical scope. - ``` let x = 5 in let f y = x + y in let x = 4 in f 3 ``` - ``` let x = 5 in let f y = x + y in let g x = f x in let x = 4 in g 3 ``` - ``` let f y = x + y in let x = 3 in let y = 4 in f 2 ``` The answers are contained in an html comment: you can find them by using the "view source" feature of your web browser. <!-- answers: 7, 6, 5 --> Variants in OCalf ----------------- In A4, you will be implementing evaluation and type checking for variants in OCalf. These exercises will help you familiarize yourself with the representation of variants and their types as ASTs. **Exercise**: Download and unpack the code for A4. **Exercise**: Consider the following OCaml type definition: ``` type number = Hearts | Clubs | Diamonds | Spades ``` Give a value of type `TypedAst.variant_spec` that represents this type in OCalf. Note that every variant in OCalf must have a value associated with it; you can use `unit` as a placeholder. **Exercise**: Give a value of type `Ast.expr` that represents the value `Clubs`. **Exercise**: Give `TypedAst.variant_spec` values for the following OCaml types: - `type ('a,'b) choice = Left of 'a | Right of 'b` - `type 'a list = Nil | Cons of 'a * 'a list`