In Praise of s-Expressions

OCaml is a wonderful language. But as with any language, there are certain features you would like to see.

The obvious one in OCaml is the lack of type-classes, specifically the lack of Haskell’s Show. There is no more useful debugging tool than printf, and it is a pain trying to debug complex types when you can’t see them.

This is where s-expressions come in. Specifically, Jane Street‘s s-expression library.

It provides a camlp4 pre-processor that lets you take a datatype:

type nat
  = Zero
  | Succ of nat

and tell the pre-processor to generate s-expression support functions:

open Sexplib
open Sexp

type nat
  = Zero
  | Succ of nat
  with sexp

Now in your code you have access to two new functions, with the types:

sexp_of_nat : nat -> Sexp.t
nat_of_sexp : Sexp.t -> nat

We can throw these together with some useful sexplib library functions:

string_of_sexp : Sexp.t -> string
sexp_of_string : string -> Sexp.t

And we have a string representation of our data-type. Easy!

Pretty printing s-expressions

We can use the built-in human-format pretty printer, that does nice line indenting. Here’s a full example file, Tree.ml:

TYPE_CONV_PATH "Succ"
open Sexplib
open Sexp

type tree = Leaf of int | Branch of tree * tree with sexp

let a = Branch ((Leaf 1), (Leaf 2)) in
let b = Branch (a, a) in
let c = Branch (b, a) in
let d = Branch (c, Leaf 3) in
let sexp = sexp_of_tree d in
Format.fprintf Format.std_formatter "%a@n" Sexp.pp_hum sexp

We compile using the sexplib pre-processor and linking against the sexp library:

ocamlfind ocamlc -linkpkg -package sexplib 
  -pp "camlp4o -I `ocamlfind query type-conv` -I `ocamlfind query sexplib` 
    pa_type_conv.cmo pa_sexp_conv.cmo" 
  Tree.ml

Then we run and the output is:

$ ./a.out
(Branch
 (Branch (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 1) (Leaf 2)))
  (Branch (Leaf 1) (Leaf 2)))
 (Leaf 3))

Reading in s-expressions

Now let’s read in the s-expression for our natural numbers, add one, and then pretty-print the result:

TYPE_CONV_PATH "Succ"
open Sexplib
open Sexp

type nat = Zero | Succ of nat with sexp

let () =
  let sexp = input_sexp stdin in
  let number = Succ (nat_of_sexp sexp) in
  let new_sexp = sexp_of_nat number in
  Format.fprintf Format.std_formatter "%a@n" Sexp.pp_hum new_sexp

Note the use of a new function, input_sexp : in_channel -> Sexp.t. This reads an s-expression from an input channel. We can compile and run this program as before:

$ echo '(Succ Zero)' | ./a.out 
(Succ (Succ Zero))

So now we not only have an equivalent to Haskell’s Show, but also to Read. And all we had to do is add with sexp to our data type!

Tags:
1 Comment
  • mfp

    June 27, 2009 at 10:26 am

    You can also compile with

    ocamlfind ocamlc -package sexplib.syntax -syntax camlp4o Tree.ml -linkpkg

    -syntax camlp4o lets ocamlfind build the required -pp option.

Post a Comment