Camlp4 - Example

Example

The following example defines a syntax extension of OCaml. It provides a new keyword, memo, which can be used as a replacement for function and provides automatic memoization of functions with pattern matching. Memoization consists in storing the results of previous computations in a table so that the actual computation of the function for each possible argument occurs at most once.

This is pa_memo.ml, the file which defines the syntax extension:

let unique = let n = ref 0 in fun -> incr n; "__pa_memo" ^ string_of_int !n EXTEND GLOBAL: Pcaml.expr; Pcaml.expr: LEVEL "expr1" [ [ "memo"; OPT "|"; pel = LIST1 match_case SEP "|" -> let tbl = unique in let x = unique in let result = unique in <:expr< let $lid:tbl$ = Hashtbl.create 100 in fun $lid:x$ -> try Hashtbl.find $lid:tbl$ $lid:x$ with [ Not_found -> let $lid:result$ = match $lid:x$ with in do { Hashtbl.replace $lid:tbl$ $lid:x$ $lid:result$; $lid:result$ } ] >> ] ]; match_case: [ ; "->"; e = Pcaml.expr -> (p, w, e) ] ]; END

Example of program using this syntax extension:

let counter = ref 0 (* global counter of multiplications *) (* factorial with memoization *) let rec fac = memo 0 -> 1 | n when n > 0 -> (incr counter; n * fac (n - 1)) | _ -> invalid_arg "fac" let run n = let result = fac n in let count = !counter in Printf.printf "%i! = %i number of multiplications so far = %i\n" n result count let _ = List.iter run

The output of the program is as follows, showing that the fac function (factorial) only computes products that were not computed previously:

5! = 120 number of multiplications so far = 5 4! = 24 number of multiplications so far = 5 6! = 720 number of multiplications so far = 6