Combinators over Records and Unions

In the previous post, I discussed designing combinator libraries that compose some property over unions. It is only fitting to throw records in the mix.

type U =
    | A of int
    | B of float
    | C of string

let UFormat =
    (
        UnionCase A IntFormat <<
        UnionCase B FloatFormat <<
        UnionCase C StringFormat
    )
    |> Union (fun a b c x ->
        match x with
        | A x -> a x
        | B x -> b x
        | C x -> c x)

type R =
    {
        A : int
        B : float
        C : string
    }

let RFormat : Format<R> =
    (
        RecordField (fun r -> r.A) IntFormat <<
        RecordField (fun r -> r.B) FloatFormat <<
        RecordField (fun r -> r.C) StringFormat
    )
    |> Record (fun a b c -> { A = a; B = b; C = c })

With some simplifications, here is the code:

Combinators over Discrimated Unions in ML

Discriminated unions or sum types are a natural way to model logical OR. Often you have a property that distributes over OR. Say, in F# (used throughout the article, though the ideas should apply equally well to any ML), you can write a combinator of the type:

P<'T1> → P<'T2> → P<Choice<'T1,'T2>>

How to go from here to a nice set of combinators that would handle an arbitrary union? This question has been on my mind for a while, and finally I have an acceptable solution.

As a disclaimer, at the level of theory the question is completely trivial. The interest is in how to find a user-friendly ML interface. Even this, I suspect, has been solved before, and at a much more general level. I am aware for instance of Vesa Karvonen's Generics for the working ML'er, and a more recent Oleg Kiselyov's presentation of generics in OCaml. I am looking here at a much simpler setting, hopefully taking it to a more accessible, for-dummies-like-myself level.

Suppose you are designing binary format combinators to let users of your library construct values of the form:

type Format<'T> =
    {
        Read : BinaryReader → 'T
        Write : BinaryWriter → 'T → unit
    }

Given an arbitrary union type and some primitive Format values, the user should be able to compose them. This involves projecting from sub-types to the parent union type, and matching backwards. After some experimentation, the design I have looks like this:

type U =
    | A of int
    | B of float
    | C of string

let UFormat =
    Union (fun a b c x →
        match x with
        | A x → a x
        | B x → b x
        | C x → c x)
    << Case A IntFormat
    << Case B FloatFormat
    << Case C StringFormat
    <| End

That's pretty much it. The magic is in the type of Case combinator that accumulates types so that the Union combinator can present N-way pattern matching as a single reasonably convenient to write function. Full code:

A Prettier Printer in ML

To try out something different, I took a shot at writing a pretty-printing module. Of all the papers I found on the subject, perhaps the most accessible is A prettier printer by Wadler. In particular the algebra of documents presented in the paper is very simple and therefore compelling.

I tried to implement these combinators in a OCaml. Unfortunately for OCaml, Wadler's code heavily relies on laziness for searching the exponentially large tree of possible printouts and selecting the optimal one by limited look-ahead and backtracking. The exact same behavior could be obtained in OCaml by mechanically injecting explicit "lazy" everywhere, but it will not be very pretty. I decided to play with a different approach and pre-compute enough information to make every decision on the spot.

The result is ocaml-pretty - see the link for the code and API docs. I tried to maintain the same behavior as in the paper, but have only checked consistency on some small examples. One obvious operational difference is memory use: since the document data structure is strict, pretty-printing cannot help but use O(N) memory in the size of the document. The published Haskell algorithm certainly does better. I did not find an obvious simple fix for this within the approach I adopted, and ended up deciding it does not matter for my purposes.

OCaml standard library has a Format module - this is what you should use for real-world OCaml pretty-printing. Its imperative interface avoids both the O(N) memory overhead and the lazy data structure allocation overhead, and it's always there for OCaml.

UPDATE: an adaptation of Wadler algorithm to strict languages, in particular OCaml, has already been published in the paper Strictly Pretty by Christian Lindig and Gartner Datensysteme Gbr, see 10.1.1.34.2200, as was kindly pointed out to me by its author. The critical insight is managing Group nodes explicitly to avoid the exponential search space.

Record Calculi. John C. Mitchell, Atsushi Ohori

Roman Cheplyaka pointed me to a good book (Foundations for Programming Languages) by John C. Mitchell. As a side effect, my eye was caught by the author's mention of object-oriented language foundations and record calculi. Record calculi? Really? A few more googles, yes indeed, there are ways to mathematically formalize operations on labeled records, providing for object-oriented languages what lambda calculus provides for functional. First hit on Google Scholar is a 1995 paper by Atsushi Ohori, "Polymorphic record calculus and its compilation"; Ohori in fact has plenty of interesting and publicly available papers. Apparently one use case of this lore is polymorphic type inference for record types in the ML family.