Benefits of OCaml

Symbolic manipulation

The expr type

Symbolic expressions are easily represented in OCaml using a variant type:

# type expr =
  | Add of expr * expr
  | Mul of expr * expr
  | Int of int
  | Var of string;;
type expr =
    Add of expr * expr
  | Mul of expr * expr
  | Int of int
  | Var of string

and some functions to compose arithmetic operators:

# let rec ( +: ) f g = match f, g with
    | Int n, Int m -> Int (n + m)
    | Int 0, f | f, Int 0 -> f
    | f, Add(g, h) -> f +: g +: h
    | f, g when f > g -> g +: f
    | f, g -> Add(f, g)
val ( +: ) : expr -> expr -> expr = <fun>
# let rec ( *: ) f g = match f, g with
    | Int n, Int m -> Int (n * m)
    | Int 0, _ | _, Int 0 -> Int 0
    | Int 1, f | f, Int 1 -> f
    | f, Mul(g, h) -> f *: g *: h
    | f, g when f > g -> g *: f
    | f, g -> Mul(f, g);;
val ( *: ) : expr -> expr -> expr = <fun>

Note that these functions rotate the abstract syntax tree to ensure that sequences of additions and multiplications are left-associative, i.e. a*b*c is represented as (a*b)*c and not as a*(b*c). This can then be used as an assumption to simplify other functions, such as a pretty printer.

For example, the expression 1 + 2 x can be represented by the following value of type expr:

# let expr = Int 1 +: Int 2 *: Var "x";;
val expr : expr = Add (Mul (Int 2, Var "x"), Int 1)

Pretty printing

In the interests of clarity, we can install a pretty printer for our expr type:

# open Format;;
# let rec print_expr ff = function
  | Int n -> fprintf ff "%d" n
  | Var v -> fprintf ff "%s" v
  | Add(f, g) -> fprintf ff "%a +@;<1 2>%a" print_expr f print_expr g
  | Mul(Add _ as f, g) ->
      fprintf ff "(@[%a@])@;<1 2>%a" print_expr f print_expr g
  | Mul(f, g) -> fprintf ff "%a@;<1 2>%a" print_expr f print_expr g;;
val print_expr : Format.formatter -> expr -> unit = <fun>
# #install_printer print_expr;;

The example expression is then displayed as:

# expr;;
- : expr = 2 x + 1

Differentiation

Pattern matching provides an elegant way to rewrite such symbolic expressions. For example a function d to compute the symbolic derivative of a given expression f with respect to a variable x may be written:

# let rec d f x = match f with
  | Var y when x=y -> Int 1
  | Int _ | Var _ -> Int 0
  | Add(f, g) -> d f x +: d g x
  | Mul(f, g) -> f *: d g x +: g *: d f x;;
val d : expr -> string -> expr = <fun>

For example, given the expression a x2 + b x + c:

# let a = Var "a" and b = Var "b" and c = Var "c" and x = Var "x";;
val a : expr = a
val b : expr = b
val c : expr = c
val x : expr = x
# let expr = a *: x *: x +: b *: x +: c;;
val expr : expr = a x x + b x + c

The symbolic derivative is determined to be:

# d expr "x";;
- : expr = a x + a x + b

The subexpression a x + a x could be simplified to 2 a x using a variety of different techniques. Perhaps the simplest solution is to alter the +: operator so that it accumulates multiples of each term. A more sophisticated approach might represent sequences of consecutive additions in a tree.