The ExpLemmaLib

Status

The current release covers all aspects of the ExpLemma paper.

History

• 4 March 2008 -- Library support for distributive laws added.
• 6 February 2008 -- ExpLemmaLib goes online.

Authors

Ralf Lämmel and Ondrej Rypacek

Abstract

ExpLemmaLib is a Haskell library that supports dualizable programming in the sense that one can encode operations on data in a way that both a functional program and an OO program can be derived. The library and the accompanying samples are meant to illustrate the expression lemma. The main idea is to represent operations as distributive laws of a functor over a functor, where one of these functors models the data at hand, and the other functor models the types of the operations. In the general case, these functors also involve monadic capabilities based on the free monad or the cofree comonad. The library provides various combinators to construct distributive laws and to deploy them as functional or object-oriented programs. The namespace ExpSample develops an extended example which is structured as follows. The modules in the namespace ExpSample/Data define a type of arithmetic expressions. For illustrative purposes, different styles of type definition are exercised. The module ExpSample/Baseline defines a number of functions on arithmetic expressions in the style of general recursion. The functions are chosen to exercise the different idioms that can be encountered in dualizable programming. The modules in the namespace ExpSample/Catas encode some of the sample functions in terms of the normal fold operation for arithmetic expressions. The folds are worked out for the different styles of type definition. More importantly, classic fold-based programming is compared with programming based on distributive laws. The modules in the namespace ExpSample/Duality illustrate the dualization of a simple functional program to an OO program, or vice versa. Dualization is shown for different styles of type definition. The library support for dualizable programming based on distributive laws is also illustrated. Ultimately, the modules in the namespace ExpSample/Idioms discipline and generalize the freewheeling programming style with the normal fold operation such that all baseline functions can be encoded in a dualizable manner.

Download

• Archive [.zip]

Table of contents

• ExpLemmaLib
  • Main: The union of the following modules
  • Prelude: Trivia
  • Functor: Basic polynomial functor framework
  • HigherOrderFunctor: Higher-order functor combinators
  • Recursion: Functorial recursion schemes
  • Free: The free monad
  • CoFree: The cofree comonad
  • Distributivity: Programming with distributive laws

• ExpSample
  • Data: Different type declarations for arithmetic expression forms
    • DataType: Use a closed, recursive algebraic datatype
    • NewType: Use a newtype to tie recursion
    • NominalFunctor: Designate a (new) type to the (open) functor
    • HigherOrderFunctor: Define functor in terms of HO combinators

  • Baseline: Sample functions for folds and OO dualization

  • Modulets: Smallest components of the sample functions

  • Catas: Different styles of folds for the sample functions
    • NewType: See module ExpSample.Data.NewType
    • NominalFunctor: See module ExpSample.Data.NominalFunctor
    • HigherOrderFunctor: See module ExpSample.Data.HigherOrderFunctor
    • Distributivity: Leverage library support for distributive laws

  • Duality: Different styles of FP/OOP dualization
    • NewType: See module ExpSample.Data.NewType
    • NominalFunctor: See module ExpSample.Data.NominalFunctor
    • HigherOrderFunctor: See module ExpSample.Data.HigherOrderFunctor
    • Distributivity: Leverage library support for distributive laws

  • Idioms: Illustration of idioms for dualizable folds
    • Public: Objects without encapsulation
    • Void: Void folds
    • Natural: Natural folds
    • Paramorphic: Paramorphic folds
    • Tupling: Tupling folds
    • Free: Free monadic folds
    • Stream: Streaming folds
    • CoFree: Cofree comonadic folds

---

Website maintained by Ralf Lämmel (Email: rlaemmel@gmail.com)