ICL 2025 - LAB 1 - OCaml Refreshment

Through small programming exercises, you are supposed to get familiar with the OCaml syntax, compiler, and, most of all, the programming style. Each exercise is supposed to illustrate/exercise some specific features of the OCaml language that are of interest for the upcoming compilers lab sessions and project.

For each exercise, you are supposed to download a tarball file named XXX.tar.gz. After downloading, you should uncompress it using tar zxvf XXX.tar.gz, which creates a directory named XXX. In that directory, you shall find the main file named XXX.ml, together with a dune file. In order to compile the exercise, you should run dune build and then dune exec ./XXX.exe to execute your implementation.

For each exercise, you are asked to complete the definition of some functions or variables. These are marked in the source code with assert false (* TODO *). Of course, you are free (and encouraged) to write auxiliary functions whenever you find suitable.

Exercise 1: Copying a file

This exercise proposes you to write a simple program that reads the name of two files from the standard input, f1 and f2, and then copies the contents of f1 into f2. The skeleton implementation can be downloaded here: copy_file.tar.gz.

Your goal is to complete the definition of function copy, which has the following type:

  val copy : string -> string -> unit

The first argument of type string is the name of input file, let’s call it f1, while the second argument is the name of the output file, let’s call it f2. The return value is of type unit, indicating that this function does not return any value, simply because all it does is to output something into a file.

Function copy should first open the two files, one for input the other for output, using the following standard library functions:

  val open_in : string -> in_channel

  val open_out : string -> out_channel

Then, the main job of copy is to implement a loop that reads the contents of f1 and writes it to f2. For such, you can use either the functions

  val input_char : in_channel -> char

  val output_char : out_channel -> char -> unit

which, respectively, reads a character from an input channel and writes a character into an output channel, or you can use

  val input_line : in_channel -> string

  val output_string : out_channel -> string -> unit

where input_line reads the contents of an input channel line by line and output_string writes a string into an output channel.

To write the main fetch-and-write loop, you should write a recursive function loop (), whose body is a block of the form

  try
    ...
  with End_of_file ->
    ...

where the End_of_file exception, from the standard library, is raised whenever we reach the end of file f1. Upon completion, i.e., after reading the whole contents of f1 into f2, you should close both channels using the following functions:

  val close_in : in_channel -> unit

  val close_out : out_channel -> unit

  dune exec ./copy_file.exe <XXX> <YYY>

where <XXX> and <YYY> should be replace with the names of the input and output files, respectively.

Exercise 2: Reversing the order of lines in a text

This exercise proposes you to write a simple program that reads some lines of text from the standard input and prints them on standard output, but in reverse order. The skeleton implementation can be downloaded here: reverse_text.tar.gz.

Your goal is to complete the definition of variable lines and function print, which have the following types:

  val lines : string

  val print : string list -> unit

In OCaml, one can write arbitrary code, even within the definition of a global value like lines. In particular, you should complete the definition of the loop function to read the contents of standard input until the Ctrl + D combination is issued to signal the end of input. You should read the text line by line using the following function:

  val read_line : unit -> string

The text local reference serves as accumulator for what you read from standard input, which you should update using OCaml references assignment. The following are the most useful functions when it comes to reference manipulation:

  val ref : 'a -> 'a ref
  (** [ref v] creates a reference with contents [v] *)

  val (!) : 'a ref -> 'a
  (** [!r] returns the contents of reference [r] *)

  val (:=) : 'a ref -> 'a -> unit
  (** [r := v] updates the contents of reference [r] with value [v] *)

Finally, print is a recursive function that traverses its argument l, of type string list, and prints the string on each list element into the standard output. For printing, use the following function:

  val print_endline : string -> unit

Exercise 3: Quad trees

In this exercise, you are asked to implement a small library of Quad trees. The skeleton implementation can be downloaded here: quad.tar.gz. We will be using the OCaml Graphics library to draw images using a simple graphical interface. In order to install this library on your machine, do

  opam install graphics

Quad trees are a simple data structure that allows one to encode and manipulate black-and-white square images of size 2ⁿ × 2ⁿ. If an image is completely black or white, it is represented using a constant denoting its color. Otherwise, it is decomposed into four subimages, each of size 2^n − 1 × 2^n − 1, according to the following order:

An image is, thus, the union of the four sub-images. In our program, the following type quad corresponds to this representation:

  type quad = White | Black | Node of quad * quad * quad * quad

The constants White and Black respectively denote an image that is either completely white or completely black. The constructor Node corresponds to an image decomposed into four sub-images, which are the four arguments of this constructor.

Node (Node (Black, Black, Black, White),
      Black,
      Node (Black, Black, Black, White),
      White)

The following asks you to implement some functions that manipulate and/or build quad trees. To help you test your solutions, a draw function is provided, which has the following type:

  val draw : int -> int -> int -> quad -> unit

A call draw x y w q draws the quad tree q in a graphical window with the position (x, y) being the bottom-left corner of the image, and w the side length of the square.

Question 3.1: build a checkerboard

  val checker_board : int -> quad

Function checker_board takes as input an integer value n and builds a quad tree that represents a 2ⁿ × 2ⁿ checkerboard. As an example, the return value of checker_board 3 corresponds to the following image:

To implement checker_board, we proceed by recursion on the value of n, as follows:

Question 3.2: rotate an image

  val rotate : quad -> quad

Question 3.3: mirror of an image

  val mirror : quad -> quad

This function constructs the mirror symmetry along the vertical axis of an image represented by a quad tree. Thus, the function mirror allows switching between the following two images:

[**] Question 3.4: from a quad tree to a string

  val unparse : quad -> string

This function builds a binary representation of a quad tree, encoded as a string. For instance, the following image

[***] Question 3.5: from string to a quad tree

  val parse : string -> quad

This function constructs a quad tree from a binary representation of an image, encoded as a string. It is the dual of the above unparse function.

[Hint]: assume that a binary representation of a quad tree is always a string of size 2ⁿ, for some n. In order to recursively build the four sub-images, you can start by spliting the initial string into two sub-strings of length 2^n − 1, and then each such sub-string into sub-strings of length 2^n − 2, and so on. To do so, you can use the following function

  val sub : string -> int -> int -> string

from the String module. A call sub s pos len returns a string of length len, containing the substring of s that starts at position pos and has length len. The length of a string s is given by String.length s.

Bonus Question: invariants

One may wish to guarantee the property that a quad tree is never made up of four leaves of the same color, since that would be an unnecessarily complicated representation. To enforce this invariant, as an alternative to the constructor Node, we must then provide a function node, defined so as to guarantee the invariant. This function as the following type:

  val node : (quad, quad, quad, quad) -> quad

If all elements in the tuple are of the same color c, it should just return c. Otherwise, return a value using the constructor Node and the four sub-quad trees given as arguments.

You can now use the node function within the definition of some of the previous quad tree manipulation functions.

Exercise 4: reading a musical score from a file

In this exercise, your goal is to extend the lecture demo program to play a musical score read from a file. The skeleton implementation can be downloaded here: music.tar.gz. To use the play command, you must first install the SoX package. You can follow the installation procedures described here.

Your goal for this exercise is to complete the definition of function file, with the following type:

  val file : string -> score

The argument of type string stands for the file name from which you should read the musical score.

A file description of a musical score shall specify the tempo of play and a list of symbols. For simplicity, let us consider that symbols can only be musical notes and not silences. Hence, we propose the following grammar for a musical score file:

The first line of the file contains the string TEMPO followed by character ‘:’ and then and integer value, which represents the tempo of the score. Then, the remaining of the file is a list of notes. Each line begins by the name of the note (rule s in the grammar above), followed by ‘:’, the value of the octave (O, an integer value), and finally the duration (rule d above).

In your implementation, you are expected to read the contents of a file following the above grammar, until the End_of_file exception is raised. After this first step, you need to parse the textual contents you just read. You are, thus, supposed to separate the different components of each line according to its semantics. To split a line based on some character, use the following function:

  val split_on_char : char -> string -> string list

This function is defined in the String module from the OCaml standard library. You can use by doing String.split_on_char.

  val trim : string -> string

We recommend you to first implement a fully-working solution that assumes the file to be syntactically well-formed, i.e., it obeys the given grammar. Afterwards, try to refine your implementation to include some error signaling. For instance, to signal that the first line of the file is not of the form "TEMPO" : N, or that a name of a note is not in the list Do ... Si. For each kind of error, exit your program with a different error code. To do so, use the following function:

  val exit : int -> 'a

Before exiting, it might be interesting to produce an error message. You can proceed in two ways: either print a message on the standard error before exiting, or raise an exception to be caught in the main function that executes your program.

A new exception in OCaml is easily defined in OCaml, as a global name, as follows:

  exception Syntax_error

  raise Syntax_error

For each kind of exceptions, an error message is expected to be produced on the standard error file. To do so, use the following function:

  val eprintf : ('a, Format.formatter, unit) format -> 'a

The type of this function is certainly not very nice. But worry not, its usage is quite easy in fact. This is as simple as follows:

  Format.eprintf "Syntax error@."

where the @. sign is used to flush the standard error and print the newline character.

  dune exec ./music.exe <XXX>

where <XXX> should be replace with the name of the file containing the score description. As an example, we provide the file frere_jacques in the tarball, which describes the Frère Jacques song, as shown during lecture. You can run your solution to read this file as follows:

  dune exec ./music.exe frere_jacques