Thursday, December 30, 2010

Differential programming and sandwich structures

I recently commented (to the Swiss F# User Group):
  • The zipper structure and the notion of data differentiation is the key to functional programming. You need to use this concept over and over until you can think of algorithms both in terms of the original type as in terms of its "differential" zipper form (see http://en.wikipedia.org/wiki/Zipper_(data_structure) ).
Yesterday evening I had the great example of this truth: I wanted to to add types to an AST (Abstract Syntax Tree) and I did this by layering the type information on the tree's "edges" not on the nodes. Had I tried to add the type on the nodes I would have needed to change my code or use active pattern matching (which I do not like). Instead I upgraded the AST type to refer to the sub-trees as a generic type. I then instantiate the AST type with sub-trees as a tuplet of a type and an AST type. The AST is then layered, alternating between AST nodes and type nodes: it looks like layers of ham and cheese. If then the algorithms on the AST have been implemented "in a differential form" (which is really about traversal and mappings) then you can compose the traversal of the AST and the traversal of the type node in to one traversal without too much difficulty.

The result is that my latest functional language prototype can now be typed inferred incrementally because now I have the type associated to the AST.

(Having written this, I searched google and found this blog which is somewhat Haskell specific as it uses functors (which F# does not have))

No comments: