This page describes a bonus implementation exercise of ICL-2025 lab
2. The goal is to implement the extensions to the While
language described in the pen-and-paper exercises
sheet. In particular, we want to extend the the big-step interpreter
to cope with repeat..until loop and pairs. This exercise
also serves as a warm up for next week lab, where you have to implement
an interpreter for a more serious programming language.
To help you building this extensions, we provide the basic structure
(as a set of OCaml files together with dune), to be
downloaded here: while.tar.gz.
Once uncompressed (with tar zxvf while.tar.gz), you get
a directory while/ with the following files:
| ast.ml |
abstract syntax of While (complete)
|
| interp.ml | interpreter (to be completed) |
| while.ml | main file (complete) |
| dune | to automate the building process (complete) |
The code compiles, using dune build, but it is
incomplete. You have to complete interp.ml.
To run your solution do dune exec ./while.exe.
This exercises proposes you to add the cases of pair construction and
projections to the expr function, the interpreter of pure
expressions. This function is of the following type:
val expr : env -> expr -> valueRecall that function expr takes as arguments an
environment, of type env, and an expression of type
expr. It returns the value that corresponds to the result
of fully evaluating such an expression.
Complete the case EValue (VPair (_, _)) of the
expr function. A value of the form
VPair (v1, v2) stands for a fully-evaluated pair with
v1 and v2 as first and second component,
respectively. Given the recursive nature of type value, a
v1 or v2 can also be nested pairs.
Complete the case EPair (_, _) of the expr
function. A value of the form EPair (e1, e2) stands for a
pair where components e1 and e2 are not yet
fully-evaluated expressions.
Complete the case EFst e of the expr
function. This case stands for a call to the fst
projection, returning the first component of expression e,
which should thus evaluate into a VPair. If that is not the
case, signal this error at runtime via a failwith
message.
Complete the case ESnd e of the expr
function. This case stands for a call to the snd
projection, returning the second component of expression e,
which should thus evaluate into a VPair. If that is not the
case, signal this error at runtime via a failwith
message.
This exercises proposes you to add the case of evaluation of the
repeat..until construction to the stmt
function, the interpreter of statements. This function is of the
following type:
val stmt : env -> stmt -> unitRecall that function stmt takes as arguments an
environment, of type env, and a statement of type
stmt. Since the environment is represented as mutable data
structure (an hash table), there is no need to return its value. One
just needs to use the same variable (which in reality stores a
pointer) that was initially passed as an argument to function
stmt.
Complete the case SRepeat of the stmt
expression. This case stands for the use of a
repeat s until e construction, meaning that one should
execute first statement s and then repeat its execution
until e evaluates down to the VBool true
value.
[Hint]: as noted in the pen-and-paper exercises sheet, the
repeat..until construction does not really extend the
expressiveness of the While language. Hence, you are free
to define the interpretation of such a loop by translating it into a
previously existing statement. To do so, it might come in handy to use
the unary negation to get the opposite of a Boolean value. This
operation is already included in the language:
UNeg of type unop stands for the
negation unary operation;EUnop of type expr stands for a call
of a unary operation on an pure expression