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.
