MP 6 A Transition Semantics Evaluator for CPS Solution

 
Change Log




1.0 Initial Release.




 
Objectives and Background




The purpose of this MP is to help the student master:




Understand how an interpreter can be implemented based of transition semantics Understand the link between Continuation Passing Style and transition semantics.

Another purpose of MPs and MLs in general is to provide a framework to study for the exam. Several of the questions on the exam will appear similar to the MP and ML problems. By the time of the exam, your goal is to be able to solve any of the following problems with pen and paper in less than 2 minutes.




 
Overview




In MP5, you saw how to write an interpreter for PicoML based on Natural Semantics. The general form of evaluation (for nonrecursive entities) was to walk the abstract syntax tree (in a mostly forward-recursive fashion) gathering up values for all the sub-trees as we went to form a cummulative value to return for the given expression. To use transition semantics as the basis of our evalutor, again we generally need to walk the abstract syntax trees, but this time we are looking only for the single next step of computation to be performed. However, we have actually performed that precise activity once before, in MP3, when we transformed PicoML abstract syntax into CPS. So, rather than replicating that work again in this MP, let’s use it. Instead of implementing a transition semantics for PicoML, we will use our translation of PicoML into CPS, and implement a transition semantics for CPS instead. The advantage to doing the transition semantics on CPS is that the CPS is explicitly designed so that “the next single step of computation” is specified immediately at the root of the abstract syntax tree of an expression, and there is no need to structurally recurse through the abstract syntax tree to find the next unit of work.




As before, we will make use of the lexer, parser and type inferencer you wrote in earlier MPs, but we will add in the CPS transformation you wrote in ML3 - revised to handle exceptions, as well as normal computations. In this assignment, you are to write a function that will perform one step of transition for the transition semantics for the CPS expressions. This function will be called repeatedly by a loop until it returns a value. As in MP6, once you supply the function for performing one step of transition semantics, you will be able to build an interactive top-level loop to test out evaluating PicoML programs, picomlIntPar and picomlIntParSol.










1
 
Types




The basic language for which we are implementing transition semantics is that of CPS terms, extended with continua-tions for handling exceptions. The type in OCaml for the abstract syntax of this language are given as follows:

type cont_var = Kvar (* _k *)




type cps_cont =




External

| ContVarCPS of cont_var (* _k *)

| FnContCPS of string * exp_cps (* FN x - exp_cps *)

| ExnMatch of exn_cont (* i1 |- ec1; ... in |- ecn *)




and exp_cps =

VarCPS of cps_cont * string

| ConstCPS of cps_cont * const

| MonOpAppCPS of cps_cont * mon_op * string * exn_cont

 
BinOpAppCPS of cps_cont * bin_op * string * string * exn_cont

 
IfCPS of string * exp_cps * exp_cps




 
AppCPS of cps_cont * string * string * exn_cont




 
FunCPS of cps_cont * string * cont_var * int * exp_cps




 
FixCPS of cps_cont * string * string * cont_var * int * exp_cps




and exn_cont =




ExnContVarCPS of int




| EmptyExnContCPS

| UpdateExnContCPS of (int option * exp_cps) list * exn_cont




This is an extension of the type exp cps and its auxiliary types that we used in ML3. It has been extended by adding a type exn cont of exception continuations for handling raised exceptions, and by expanding the arguments of those constructs in exp cps that could directly raise an exception to include an exn cont to handle any such exception raised. These include plain application and application of monadic (head or tail of an empty list) and binary operators (division by zero). Plain and recursive functions are expanded not only to take a second argument for their continuation as before, but also a third argument for their exception handler continuations.




In MP5, we had a type of values that included closures and recursive closures, each of which included an expression from PicoML for the body of the function represented. Since we are evaluating starting with CPS expressions, we need to revise our closures to use CPS expressions as their bodies, and to take the extra arguments for continuations and exception handler continuations the CPS functions now take. They also need to take a new kind of environment for supplying functions with their continuations and interpreting (integer) variables ranging over exception continuations. The environments we put in closures and recursive closures for continuations and exceptions continuations will store enough information with each return result to be able to resolve any free variables in the result. For other values, there are no free variables. For continuations and exception handler continuations we store a memory along with the continuation so that it is essentially a closed entity, not requiring any external information for interpretation.




Another change to our type of values is that, for the most part, we no longer need to segregate exceptions as a separate case of values; instead they will be ordinary values handed to an exception handler continuation instead of the main continuation. Our new types of value and cps env entry then are:







type value =




UnitVal




 
BoolVal of bool




 
IntVal of int




 
FloatVal of float




 
StringVal of string







2
 
PairVal of value * value

 
ListVal of value list




 
CPSClosureVal



of
string
*
cont_var
*
int *
exp_cps
* (cps_env_entry list)
|
CPSRecClosureVal












of
string
*
string *
cont_var
*
int *
exp_cps * (cps_env_entry list)
and
cps_env_entry
=












ValueBinding
of (string
* value)




 
ContBinding of (cont_var * (cps_cont * (cps_env_entry list)))

 
ExnContBinding of (int * (exn_cont * cps_env_entry list))




We will associate values with identifier names in environments, as in previous MPs. We use integers for vari-ables for exception handler continuations. We will use a form of environment that incorporates each of these using lists of cps env entry. We include the following look-up functions for retrieving results from this new type of environment, or memory:







val lookup_value : cps_env_entry list - string - value option = <fun val lookup_cont :




cps_env_entry list - cont_var - (cps_cont * cps_env_entry list) option = <fun val lookup_exn_cont :

cps_env_entry list - int - (exn_cont * cps_env_entry list) option = <fun




An exception to the remark that we no longer “need” exceptions as a separate class of values arises in the handling of primitive (monadic and binary) operators. Here it will be useful to distinguish an integer as an ordinary value from its use as a code for an exception. To restore this ability for this limited case, we have added the type val or exn used by monOpApply and binOpApply.







type val_or_exn = Value of value | Exn of int




We have included the appropriately modified versions of monOpApply and binOpApply in mp6common.ml.




Their new types are:




val binOpApply : bin_op - value - value - val_or_exn = <fun




val monOpApply : mon_op - value - val_or_exn = <fun




One last type we need is for the result of a single step in the transition semantics. This calls for a separate type because we must account of several kinds of results. In general, a single step in the transition semantics will move us from a CPS expression in some value environment, continuation environment and exception environment, to a new CPS expression in a new value environment, new continuation environment and new exception environment. However, there is also the desirable possibility that we transition to a final value. There are additionally the two less fortunate cases, the first where we transition to an exception for which there is no handler, and thus we want to signal the user that an exception was raised, and the least undesirable case where evaluation has just gone wrong because we tried to access the value of a variable for which we have none, or some other reason why we have no ability to transition. This last case could be dealt with by using the option type, but our pattern matching will be a little easier if we incorporate it into the step result type:







type step_result =

Intermediate of (cps_env_entry list * exp_cps)

| Final of value




 
UncaughtException of int




 
Failed













3
 
Compiling, etc...




For this MP, you will only have to modify mp6.ml, adding the functions requested. To test your code, type make and the three needed executables will be built: picomlIntPar, picomlIntParSol and grader. The first two are explained below. As usual, grader checks your implementation against the solution for a fixed, minimal set of test cases as given in the tests file. Again, as usual, you are encouraged to add your own tests to the tests file




You may also work interactively with your code in OCaml. To facilitate your doing this, and because there are more files than usual to load than usual, we have included in mp6 a file .ocamlinit that is executed by ocaml every time it is started in the directory mp6. The contents of the file are:




#load "mp6common.cmo";;




#load "picomlparse.cmo";;




#load "picomllex.cmo";;




#load "solution.cmo";;




open Mp6common;;




#use "mp6.ml";;




let parse s = Picomlparse.main Picomllex.token (Lexing.from_string s);;







5.1 Running PicoML




The given Makefile builds executables called picomlIntPar and picomlIntParSol. The first is an exe-cutable for an interactive loop for the evaluator built from your solution to the assignment and the second is built from the standard solution. If you run ./picomlIntPar or ./picomlIntParSol, you will get an interactive screen, much like the OCaml interactive screen. You can type in PicoML declarations (followed by a double semicolon), and they will be evaluated, and the resulting binding will be displayed.




At the command prompt, the programs will be evaluated (or fail evaluation) starting from the initial memory, which is empty. Each time, if evaluation is successful, the resulting memory will be displayed. Note that a program can fail at any of several stages: lexing, parsing, type inferencing, or evaluation itself. Evaluation itself will tend to fail until you have solved at least some of the problems to come.




 
Notation




Your main assignment in this MP in to implement the function




val one_step_exp_cps_eval : cps_env_entry list - exp_cps - step_result = <fun




You will be given a specification of the function as a set of transition semantics rules for CPS terms. In our interpreter, we only have abstract syntax for our CPS terms, while the rules will be expressed in a form of concrete syntax. In giving the rules we will use the following conventions:




e = CPS expression




x; y; z; f = identifier/variable




b = boolean valued variable




c = constant




v = value




= continuation




k = continuation variable (cont var)










4



 
= an exception handler continuation (exn cont)







ek = an exception handler continuation variable (int)




= memory stored as a cps env entry list







The following table is intended to allow you to translate from concrete syntax to the corresponding abstract syntax for CPS terms, and values.




concrete syntax
abstract syntax
( x)
VarCPS( ; x)
( c)
ConstCPS( ; c)
( ( x)=")
MonOpAppCPS( ; ; x; ")
( (x y)=")
BinOpAppCPS( ; ; x; y; ")
(IF b THEN e1 ELSE e2)
IfCPS(b; e1; e2)
(f x =")
AppCPS( ; f; x; ")
( (FUN x - fn k; ek = e))
FnCPS( ; x; k; ek; e)
( (FIX f: FUN x - fn k; ek = e))
FixCPS( ; f; x; k; ek; e)



A CPS expression represents the evaluation that is to compute one step of a total computation, either yielding a new CPS expression in the case of a conditional, or yielding a value that is passed to a continuation. In turn, a continuation represents a function that receives a value and generates the next CPS expression. The act of “applying” a continuation to the corresponding value in the memory will be written as vj . We will use hx; k; ek; e; i for closures and hhf; x; k; ek; e; ii for recursive closures.




 
Problems




These problems ask you to create an evaluator for PicoML by writing the functions app cont to value and one step exp cps eval as specified. The evaluator works first by lexing, parsing, type checking and translating the user’s code into CPS form (a exp cont). From here, one step exp cps eval is repeatedly called until a result other than an Intermediate (hopefully a Final value) is returned.




The functions you are to implement,




val app_cont_to_value :




cps_env_entry list - cps_cont - value - step_result = <fun and







val one_step_exp_cps_eval :




cps_env_entry list - exp_cps - step_result = <fun




take a memory (a.k.a a cps env entry list) giving values for the various different sorts of identifiers possibly occurring in the other arguments to the functions. The function app cont to value additionally takes a continua-tion and a value and generates the net result of applying the continuation to the value in the given context. It implements ( v)j . In addition to the memory given as a cps env entry list, the function one step exp cps eval takes a CPS expression and using the function app cont to value computes the result of taking one step of eval-uation.




For each problem, you should refer to the list of rules given as part of the problem. The rules specify how evaluation should be carried out, using transition semantics for CPS expressions. Transition semantics were covered in class; see the lecture notes for details. If any expression raises an exception n that is not caught by any exception handler, then UncaughtException(n) should be returned. All other cases that the rules fail to cover should return Failed.




The problems are ordered such that simpler and more fundamental concepts come first. For this reason, it is recommended that you solve the problems in the order given. Doing so may make it easier for you to test your solution before it is completed.







5



You are allowed, and even encouraged to create and use helper functions in this MP. In particular, you may want to create functions that implement some of the auxiliary math notation, and some of the implicit coercions.




As mentioned, you can test your code in the executable PicoML environment, or directly in OCaml. The problem statements that follow include some examples in PicoML. However, the problem statements also contain test cases that can be used to test your implementation in the OCaml environment. The former may be more useful in helping you gain an overall understanding of what is happening in this MP, while the latter are more likely to help you implement each individual section.




 
Continuation Application (12 pts)




Implement app cont to value. If the continuation is of the form External, you should return Final of the value. If it is a continuation variable, look it up in the environment and apply the resulting continuation. If the continuation is of the form FnContCPS(y; e), then create the one-step intermediate result given by adding to the memory the binding of y to the value, and bundling this with the CPS expression e. If the continuation is an exception handler continuation (ExnMatch), and the value is an integer, then apply the exception handler continuation to the integer to yield the result.




To apply an exception handler continuation (exn cont) that is an exception handler continuation variable, look the variable up in the environment and apply the resulting exception handler continuation to the integer. If the handler continuation is empty, the result is an UncaughtException. If the handler continuation is an update of an earlier handler continuation, ", by a partial mapping of integer options to exception continuations, and either the given integer or None is assigned an exception handler continuation by the partial mapping, then return the one-step intermediate result using the given memory and the first expression continuation just found. If no match exists in the partial mapping, then recursively apply ".







# app_cont_to_value [] External (IntVal 6);; - : Mp6common.step_result = Final (IntVal 6)










 
Constants (2 pts)




Extend one step exp cps eval to handle constants (i.e. integers, bools, real numbers, strings, nil, and unit). For this question you will need to use const to val: const - value, which is provided in mp6common.ml and is a function you implemented in the previous MP. This function takes a constant and re-turns the corresponding value.







(( c); )! ( (const to val(c)))j







A sample test case for the OCaml environment:




 
one_step_exp_cps_eval [] (ConstCPS(External, IntConst 2));; - : Mp6common.step_result = Final (IntVal 2)




In the PicoML environment, this enables




let x = 2;;




result:




x = 2










 
Identifiers (3 pts)




Extend one step exp cps eval to handle identifiers (i.e. variables).







6



(x) = v







(( x); )! ( v)j




Here is a sample test case.




 
one_step_exp_cps_eval [ValueBinding("x", IntVal 2)] (VarCPS(External, "x"));; - : Mp6common.step_result = Final (IntVal 2)




In the PicoML environment, if you have previously successfully done Problem 1 and run the sample code, you can test this problem with:




x;;




result:




_ = 2










 
Monadic Operator Application (7 pts)




Extend one step exp cps eval to handle application of monadic operators ˜, hd, tl, fst, snd and print string. For this question, you will want to use the function monOpApply: mon op - value - val or exn that is a modest modification of the function you implemented in the previous MP.









(x) = v monOpApply( ; v) = v0


(x) = v monOpApply( ; v) = Exn(n)


(( ( x)="); )! ( v0 )j


(( ( x)="); )! (" n)j
where is a monadic constant function value.




A sample test case in the OCaml environment:







 
one_step_exp_cps_eval [ValueBinding("x", IntVal 2)] (MonOpAppCPS(External, IntNegOp, "x", EmptyExnContCPS));;




- : Mp6common.step_result = Final (IntVal (-2))




A sample test case in the PicoML interpreter:




˜x;;




result:




_=˜2










 
Binary Operators (8 pts)




Extend one step exp cps eval to handle the application of binary operators. For this question, you need to use the binOpApply : bin op - value - value - val or exn function.







(x) = v1 (y) = v2 binOpApply( ; v1; v2) = v


(x) = v1 (y) = v2 binOpApply( ; v1; v2) = Exn(n)
(( (x y)=") )! ( v)j


(( (x y)="); )! (" n)j
A sample test case.













7



# one_step_exp_cps_eval [ValueBinding("b", IntVal 3);ValueBinding("a", IntVal 2)] (BinOpAppCPS(External, IntPlusOp, "a", "b", EmptyExnContCPS));;




- : Mp6common.step_result = Final (IntVal 5)




In the PicoML environment, you can test this problem with:




2+3;;




result:




_ = 5







 
If constructs (5 pts)




Extend one step exp cps eval to handle if constructs.







(b) = true
(b) = false






(IF b THEN e1 ELSE e2); )! (e1; )
(IF b THEN e1 ELSE e2); )! (e2; )



A sample test case.




 
one_step_exp_cps_eval [ValueBinding("a", BoolVal true)]




(IfCPS("a", ConstCPS(External,IntConst 1), ConstCPS(External,IntConst 0)));;




 
: Mp6common.step_result = Intermediate




([ValueBinding ("a", BoolVal true)], ConstCPS (External, IntConst 1))




In the PicoML environment,




if true then 1 else 0;;




result:




_ = 1







 
Functions (3 pts)




Extend one step exp cps eval to handle functions. You will need to create a CPSClosureVal represented by hx; k; ek; e; i in the rule below.







(((FUN x - fn k; ek = e); ); )! ( hx; k; ek; e; i)j




A sample test case.




 
one_step_exp_cps_eval [] (FunCPS (External, "x", Kvar, 0,




VarCPS (FnContCPS ("a",




ConstCPS (FnContCPS ("b",




BinOpAppCPS (ContVarCPS Kvar, IntPlusOp, "a", "b", ExnContVarCPS 0)), IntConst 5)),




"x")));;




8



 
: Mp6common.step_result = Final




(CPSClosureVal ("x", Kvar, 0, VarCPS




(FnContCPS ("a", ConstCPS




(FnContCPS ("b",




BinOpAppCPS (ContVarCPS Kvar, IntPlusOp, "a", "b", ExnContVarCPS 0)), IntConst 5)),




"x"),




[]))




In the PicoML environment,




let plus5 = fun x - x + 5;;




result:




plus5 = <some closure







 
Recursive Expressions (3 pts)




Extend one step exp cps eval to handle recursive CPS expressions (FixCPS). In this case, you will need to create a CPSRecClosureVal represented by hhf; x; k; ek; e; ii in the rule below.




(( (FIX f:FUN x - fn k; ek = e)); )! ( hhf; x; k; ek; e; i)j




A sample test case.




 
let e1 =




IfExp (BinOpAppExp (EqOp, VarExp "n", ConstExp (IntConst 0)), ConstExp (IntConst 1),




AppExp (VarExp "f",




BinOpAppExp (IntMinusOp, VarExp "n",




ConstExp (IntConst 1)))) in




let e1cps = cps_exp e1 (ContVarCPS Kvar) (ExnContVarCPS 0) in




one_step_exp_cps_eval []




(FixCPS(FnContCPS("f",VarCPS(External, "f")),"f","n",Kvar,0,e1cps));;




 
: Mp6common.step_result = Intermediate




([ValueBinding




("f",




CPSRecClosureVal ("f", "n", Kvar, 0,




ConstCPS




(FnContCPS ("e",




VarCPS




(FnContCPS ("g",




BinOpAppCPS




(FnContCPS ("a",




IfCPS ("a", ConstCPS (ContVarCPS Kvar, IntConst 1),




ConstCPS




(FnContCPS ("c",




VarCPS




9



(FnContCPS ("d",




BinOpAppCPS




(FnContCPS ("a",




VarCPS




(FnContCPS ("b",




AppCPS (ContVarCPS Kvar, "b", "a",




ExnContVarCPS 0)),




"f")),




IntMinusOp, "d", "c", ExnContVarCPS 0)), "n")),




IntConst 1))),




EqOp, "g", "e", ExnContVarCPS 0)),




"n")),




IntConst 0),




[]))],




VarCPS (External, "f"))




In the PicoML environment, you should now be able to do




let h = let rec f n = if n = 0 then 1 else f (n - 1) in f;;




result:




h = <some recvar










 
Function application (10 pts)




Extend one step exp cps eval to handle function application.







(f) = hy; k; ek; e; 0 i (x) = v







((f x ="); )! (e; ([y 7!v] + [k 7!( ; )] + [ek 7!("; )] + 0 ))




(f) = hhg; y; k; ek; e; 0 ii (x) = v







((f x ="); )! (e; ([y 7!v; g 7! hhg; y; k; ek; e; 0 ii] + [k 7!( ; )] + [ek 7!("; )] + 0 ))




Caution: In general, the order in which bindings are added to the environment matters, so you will be required to implement the order given by the rules, even though other orders would give equivalent semantics.




A sample test case.




# one_step_exp_cps_eval




[ValueBinding("plus5", (CPSClosureVal ("x", Kvar, 0, VarCPS




(FnContCPS ("a",




ConstCPS




(FnContCPS ("b",




BinOpAppCPS (ContVarCPS Kvar, IntPlusOp, "a", "b", ExnContVarCPS 0)), IntConst 5)),




"x"),




[])));




ValueBinding("c",IntVal 2)]




(AppCPS(External, "plus5", "c", EmptyExnContCPS));; - : Mp6common.step_result =







10



Intermediate




([ValueBinding ("x", IntVal 2);




ContBinding




(Kvar,




(External,




[ValueBinding




("plus5",




CPSClosureVal ("x", Kvar, 0,




VarCPS




(FnContCPS ("a",




ConstCPS




(FnContCPS ("b",




BinOpAppCPS (ContVarCPS Kvar, IntPlusOp, "a", "b", ExnContVarCPS 0)),




IntConst 5)),




"x"),




[]));




ValueBinding ("c", IntVal 2)]));




ExnContBinding




(0,




(EmptyExnContCPS,




[ValueBinding




("plus5",




CPSClosureVal ("x", Kvar, 0,




VarCPS




(FnContCPS ("a",




ConstCPS




(FnContCPS ("b",




BinOpAppCPS (ContVarCPS Kvar, IntPlusOp, "a", "b", ExnContVarCPS 0)),




IntConst 5)),




"x"),




[]));




ValueBinding ("c", IntVal 2)]))],




VarCPS




(FnContCPS ("a",




ConstCPS




(FnContCPS ("b",




BinOpAppCPS (ContVarCPS Kvar, IntPlusOp, "a", "b", ExnContVarCPS 0)), IntConst 5)),




"x"))




In the PicoML environment,




plus5 2;;




result:




_ = 7




Final Remark: Please add numerous test cases to the test suite. Try to cover obscure cases.













11