Demo: Expression Evaluator

This demo evaluates arithmetic expressions represented as an AST with constructors for literals, addition, multiplication, and negation. Alongside evaluation, it computes expression depth and performs a small simplification pass, showing how one tree structure can support multiple independent recursive analyses and transformations.

Related reading: Abstract syntax tree.

The code defines one ADT (Expr) and then reuses it across three traversals: eval computes numeric meaning, depth computes structural height, and simplify_once applies a local rewrite rule for double negation. In the final expression block, two sample trees are built, one is simplified once, and the output tuple shows evaluation and depth results side-by-side.

type Expr = Lit i32 | Add Expr Expr | Mul Expr Expr | Neg Expr;

fn eval : Expr -> i32 = \e ->
  match e with {
    case Lit n -> n;
    case Add a b -> eval a + eval b;
    case Mul a b -> eval a * eval b;
    case Neg x -> 0 - eval x;
  };

fn depth : Expr -> i32 = \e ->
  match e with {
    case Lit _ -> 1;
    case Add a b ->
      if depth a > depth b then 1 + depth a else 1 + depth b;
    case Mul a b ->
      if depth a > depth b then 1 + depth a else 1 + depth b;
    case Neg x -> 1 + depth x;
  };

fn simplify_once : Expr -> Expr = \e ->
  match e with {
    case Neg (Neg x) -> x;
    case _ -> e;
  };

let
  expr1 = Add (Lit 2) (Mul (Lit 3) (Lit 4)),
  expr2 = Neg (Neg (Add (Lit 5) (Mul (Lit 1) (Lit 9))))
in
  let simplified = simplify_once expr2 in
  (eval expr1, depth expr1, eval simplified)