Lab Session 2: Big-Step Operational Semantics and Arith Language

In this Lab Session we are going to write in OCaml a small language of arithmetic expressions.
Start by downloading the arith.ml file. In this file, expressions are defined only for the addition. The goal of the exercises is to familiarize with OCAml language feature and syntax, with focus on algebraic data types, pattern matching and recursive functions.

Exercise 1. Multiplication.

Modify the preivous file or create a new file, e.g. "arith2.ml" in which you can import relevant parts of the code from arith_expr.ml and write exercises in the order below:
  1. Extend Binop type with a constructor representing multiplication.
  2. Construct a binary expression representing a number 2*(20 + 1).
  3. Define a square function that takes as input an expression and returns the expression representing the square of that input.
  4. Adapt the code of expr_to_string to the multiplication case. Pay attention to the parenthesis for multiplication.
  5. Extend the interpreter function to handle the multiplication case.
  6. Adapt a simplifier to handle the multiplication case, given that for any expression e we have e*0 = 0*e = 0 and e*1=1*e=e.
  7. Extend the check_validity function to handle the multiplication case.
  8. Write a function sum: int -> expr that takes a non-negative integer n as a parameter and returns the expression representing the value (0 + 1 + ... + n).
  9. Write a function fact: int -> expr that takes a positive integer n as a parameter and returns the expression representing the value (1 * ... * n).
solution for the exercise

Exercise 2. Division.

Modify the previous file or open a new file, e.g. "arith_expr3.ml" in which you can import relevant parts of the code from your file and write exercises in the order below.
  1. Extend Binop type from the previous exercise with a constructor representing euclidean division.
  2. Adapt the code of expr_to_string to handle the division case.
  3. Define DivByZero exception and extend the interpreter function to handle the division case, so that if you try to divide by zero, your code raises the exception.
  4. Adapt the code of simplifier to division, given that e / 1 = e.
  5. Adapt the code of print_expr to handle the division by zero case in cases where after simplifications the expression contains a node of the form e div 0.
solution for the exercise

return to the main page