Description
Lab goals
This lab will explore the interpreter that we wrote in lecture and
extend it a bit. This is based on “denotational semantics”. This is a
mechanism for defining the semantics of imperative programs in which
the meaning of a program is seen as a state transformation function.
You can read more about denotational semantics in the paper
[“The Denotational Semantics of Programming Languages”](https://github.umn.edu/umn-csci-2041-S18/public-class-repo/blob/master/Resources/Denotational_Semantics_Tennent.pdf) by
R. D. Tennent. This paper is also in the Resources directory in the
public class repository.
## Getting started.
Copy the file “interpreter.ml“ from either the
“Sample Programs/Sec_01_1:25pm“ or
“Sample Programs/Sec_10_3:35pm“ directory of
the public class repository into a
new directory named “Lab_12“. Name the copy of this file
“interpreter.ml“.
## Review
Open the file and familiarize your self with the data types and the
functions “eval“ and “exec“.
Run “exec program_while []“. And enter “10“. How many times does
“sum“ appear in the final state?
Create a let-binding in your file of the from
“`
let num_sum = …
“`
where “…“ is replaced by the number of times that “sum“ appears
in the final state.
## Add a conditional statement — if-then-else
Add a new constructor of the following form to “stmt“:
“`
| IfThenElse of expr * stmt * stmt
“`
Then write to clause for this new constructor in the “match“
expression in “exec“.
Next, add a modulus operator constructor to “expr“:
“`
| Mod of expr * expr
“`
Then write the clause for this new constructor in the “match“
expression in “eval“.
Hint: in OCaml, “mod“ is the infix operator for modulus. Try it out
in “utop“.
## Another program
Construct a new program of type “stmt“ named
“program_while_ifthenelse“. It should correspond to the following
comment already in “interpreter.ml“. Note how “program_seq“ and
“program_while“ both have similar comments for them. You need to
construct a let-binding for “program_while_ifthenelse“ that
corresponds to the program in the comment below:
“`
(* read x;
i = 0;
sum_evens = 0;
sum_odds = 0;
while (i < x) {
write i;
if i mod 2 = 0 then
sum_evens = sum_evens + i;
else
sum_odds = sum_odds + i;
i = i + 1
}
write sum_evens;
write sum_odds
*)
“`
## Test your extended “exec“
Run “exec program_while_ifthenelse []“ and enter “8“ when prompted to enter a
number.
It should print out the integers from 0 to 7 and the print 12 and then
16.
Run “exec program_while_ifthenelse []“ and enter “15“ when prompted. Then
create the following let-bindings in your file:
“`
let val_sum_evens =
let val_sum_odds =
let num_sum_evens =
let num_sum_odds =
“`
+ give “val_sum_evens“ the value of “sum_evens“ in the final state
+ give “val_sum_odds“ the value of “sum_odds“ in the final state
+ give “num_sum_evens“ the number of times “sum_evens“ appears in
the final state
+ give “num_sum_odds“ the number of times “sum_odds“ appears in
the final state
## Create a testable version of “program_while_ifthenelse“
Define “program_while_ifthenelse_test“ in your file to be the same as
“program_while_ifthenelse“, but replace
“`
ReadNum “x”
“`
with
“`
Assign (“x”, Val (Int 12))
“`
The following should evaluate to “Int 30“
“`
lookup “sum_evens” (exec program_while_ifthenelse_test [])
“`
## Add a skip statement
Add the following constructor to “stmt“:
“`
| Skip
“`
This is a “skip” statement that does nothing. It is like “pass“ in
Python or a “noop” in assembly language.
Complete the implementation of “exec“ to handle this new
construct.
Also, re-implement the “IfThen“ construct based on the
observation that executing “if …cond… then …stmt…” is the same
as executing “if …cond… then …stmt… else skip”.
Next, define “program_ifthen“ to correspond to to the following comment:
“`
(* y = 0;
if x mod 2 = 0 then y = y + 2;
if x mod 3 = 0 then y = y + 3;
if x mod 4 = 0 then y = y + 4;
*)
“`
Now try “exec program_ifthen [ (“x”,Int 4) ]“.
For example “lookup “y” (exec program_ifthen [ (“x”,Int 4) ])“ should
evaluate to “Int 6“.
## Add a for loop
Next, add the following “stmt“ constructor
“`
| For of string * expr * expr * stmt
“`
that represents a for-loop with a name of the integer counter (the “string“)
and the lower and upper bounds (the two “expr“ components) and the
body of the loop (the “stmt“).
Complete the implementation of “exec“ to handle this new
construct.
Define “program_for“ to be
“`
For (“i”, Val (Int 1), Val (Int 5), WriteNum (Var “i”))
“`
When run, this will print out the values 1, 2, 3, 4, and 5. You can
see the bounds are inclusive.
Add the following declaration to your file:
“`
let program_sum_10 =
(* sum = 0
for i = 1 to 10
sum = sum + i
write sum
*)
Seq (Assign (“sum”, Val (Int 0)),
Seq (For (“i”, Val (Int 1), Val (Int 10),
Assign(“sum”, Add (Var “sum”, Var “i”))),
WriteNum (Var “sum”)
) )
“`
Run it to check that “55“ is displayed.
Consider this alternate version. It should print out “55“ two
times. Why is that? Ensure that your implementation of the for-loop
gives this same behavior.
“`
let program_sum_10_n =
(* n = 10
sum = 0
for i = 1 to n
sum = sum + i
n = sum
write sum
write n
*)
Seq (Assign (“n”, Val (Int 10)),
Seq (Assign (“sum”, Val (Int 0)),
Seq (For (“i”, Val (Int 1), Var “n”,
Seq (Assign(“sum”, Add (Var “sum”, Var “i”)),
Assign(“n”, Var “sum”)
)
),
Seq(WriteNum (Var “sum”),
WriteNum (Var “n”)
) ) ) )
“`
## Repeat-until
If time allows, attempt this optional task. Add a repeat-until loop.
It consists of a “stmt“ and “expr“. It executes the loop body
first, then does the check. It keeps looping until the “expr“
evaluates to true.
You might use this as the constructor in “stmt“:
“`
| Repeat of stmt * expr
“`
## Push your work.
Now be sure to commit and push your work. Check the feedback file
that should be generated each time you push this work.
