Skip to content

Latest commit

 

History

History
62 lines (46 loc) · 2.85 KB

w3_3.1_symbolic_arithmetic.md

File metadata and controls

62 lines (46 loc) · 2.85 KB
Raw

SYMBOLIC MANIPULATION OF ARITHMETIC EXPRESSIONS (44 points possible)

Abstract syntax trees are a convenient way to represent a syntactic expression in a structured way. Let us consider arithmetic expressions formed by the following rules:

  • an integer is an arithmetic expression
  • if lhs and rhs are arithmetic expressions then lhs + rhs is an arithmetic expression
  • if lhs and rhs are arithmetic expressions then lhs * rhs is an arithmetic expression

Such an expression can be represented by a value of type exp as defined in the given prelude (as well as the definition of 1 + 2 * 3 as an example).

  1. Write the expression 2 * 2 + 3 * 3 in a variable my_example.

  2. Write a function eval : exp -> int that computes the value of an arithmetic expression. The evaluation rules are:

    • If the expression is an integer x, the evaluation is x
    • If the expression is lhs + rhs and lhs evaluates to x and rhs evaluates to y, then the evaluation is x + y
    • If the expression is lhs * rhs and lhs evaluates to x and rhs evaluates to y, then the evaluation is x * y

  3. If an expression is of the form a * b + a * c then a * (b + c) is a factorized equivalent expression. Write a function factorize : exp -> exp that implements this transformation on its input exp if it has the shape a * b + a * c or does nothing otherwise.

  4. Write the reverse transformation of factorize, expand : exp -> exp, which turns an expression of the shape a * (b + c) into a * b + a * c.

  5. Implement a function simplify: exp -> exp which takes an expression e and:

    • If e is of the shape e * 0 or 0 * e, returns the expression 0
    • If e is of the shape e * 1 or 1 * e, returns the expression e
    • If e is of the shape e + 0 or 0 + e, returns the expression e and does nothing otherwise.

Remarks:

The symbols (a, b, c and e) can match any expressions, not just integers. these are a syntactical rewritings, so two expressions are considered equal if and only if they are exactly the same expressions (simply use the = operator to check that). The rewritings have to be done on the first level of the expression only, not recursively and not deeper in the expression. If the toplevel expression does not match the expected pattern, simply return the expression untouched.

THE GIVEN PRELUDE

type exp =
  | EInt of int
  | EAdd of exp * exp
  | EMul of exp * exp

let example =
  EAdd (EInt 1, EMul (EInt 2, EInt 3))

YOUR OCAML ENVIRONMENT

let my_example =
  "Replace this string with your example." ;;

let eval e =
  "Replace this string with your implementation." ;;

let factorize e =
  "Replace this string with your implementation." ;;

let expand e =
  "Replace this string with your implementation." ;;

let simplify e =
  "Replace this string with your implementation." ;;