Tom Verhoeff: From FP to OO


Event Details


This work got started while teaching a functional programming course, where I tried to make the abstract concept of F-(co-)algebras more concrete by stating that, in Java terms, these are just classes that implement a specific kind of generic interface. To make this even more concrete, I tried to implement this idea, together with the corresponding (co-)inductive type, that is, (terminal/)initial F-(co)-algebra. Somewhat to my surprise this worked out quite nicely. I present a systematic way of translating inductive types with their catamorphisms (folds) from those types, and co-inductive types with their anamorphisms (unfolds) into those types, expressed as functional programs (say in Haskell), into elegant object-oriented code (say in Java). Even types that are inductive and co-inductive can be handled, allowing for hylomorphisms (fold after unfold) that are lazy. It turns out that there is a nice way of matching disjoint sums (co-products), argument patterns, and F-(co-)algebras on the FP side with inheritance, polymorphism+overriding+dynamic dispatch, and generic interfaces on the OO side. What also struck me is that this translation provides a legitimate use case for inheritance, which is often abused (where composition would be more appropriate). I will illustrate this approach through some examples (trees, streams, and lists), while introducing the relevant FP and OO concepts. This serves as a Rosetta stone involving the three formalisms of Haskell, Category Theory, and Java. Even if you know only one of these, you should be able to grasp the others. The OO implementation allows for some useful trade-offs: memory versus time, safety and easy reasoning versus efficiency and hard reasoning (think: immutable versus mutable). I am working on a FP library for Java based on these ideas. Finally (when time permits), I will reflect on this translation and compare (qualities of) the input FP code with (those of) the resulting OO code, and with (those of) traditional OO code for the same functionality. I touch upon such qualities as performance, code size, maintainability, and flexibility.