The essence of "The essence of functional programming"

Code for all my Channel9 videos is now hosted here.

If "code is the essence", then this blog post is concerned with the essence of "The essence of functional programming" --- because the post matches a code distribution that is derived from P. Wadler's paper of just that title.

The code distribution has two branches: "origin" --- where it indeed stays close to the original code of the paper, and "overhaul" --- where it uses the Haskell's monad/monad transformer library to show some of the examples in modern style. This code has been initially prepared for a Channel9 lecture about monads. The code is available through the SourceForge project developers; browse the code here; see the slide deck for the Channel9 lecture here.

Here is a more complete reference to Wadler's paper:

P. Wadler: The essence of functional programming

http://doi.acm.org/10.1145/143165.143169

POPL 1992

Henceforth, we refer to this paper as "the paper".

Recovery and modularization effort due to Ralf Lämmel.

Disclaimer

The code distribution has not been approved, in any form, by the original author (P. Wadler). The author of the code distribution (R. Lämmel) takes all responsibility for any imprecision or misconception of this recovery and elaboration effort. Comments are welcome, as usual. Also, the particular way of distributing (modularizing) the code by means of heavy cpp usage is not meant to suggest any useful style of functional programming. It is merely used as a convenience for organizing the code such that code reuse is explicitly captured.

The paper's code vs. this code distribution

The branch "origin" is meant to stay close to the code in the paper. In particular, Haskell's monad (transformer) library is used only in branch "overhaul". We identify the following deviations (in branch "origin"):

• Most importantly, the original paper did not organize the code in any way that would explicitly represent code reuse. In contrast, the code distribution leverages cpp to this end. This approach may be viewed as an ad-hoc cpp-based product-line-like approach.

• We use the type class Show for "showing" values and for "getting out of the monads".

• We added a few samples; they are labeled with code comments.

• Minor forms of name mangling and refactoring are not listed here.

• We renamed a few operators to better match the current Haskell library:

unit... -> return

bind... -> (>>=)

error... -> fail

zero... -> mzero

plus... -> mplus

out... -> tell

How to understand and run the code?

One should probably have modest knowledge of monads. For instance, one may read the paper. The easiest approach towards understanding the code distribution is to study the final interpreters in subdirectory "cache". (These interpreters were assembled from pieces, but this may be less important initially.) With two exceptions, these are all complete Haskell 98 programs (modulo TypeSynonymInstances and FlexibleInstances for the sake of Show) with a main function with test cases corresponding to the samples in the paper. The interpreters correspond to scenarios in the paper, and there is a corresponding comment at the beginning of each file to identify relevant sections in the paper. A complete list of all interpreters follows below.

If you want to better understand the structure of the interpreters and their relationships, you may want to have a look at the primary sources that are preprocessed via cpp. Each interpreter is assembled through cpp #includes; see the files in subdirectory "templates". A more profound description of our ad-hoc cpp-based product-line-like approach follows below.

List of interpreters in the order of occurrence in the paper

• Baseline.hs: This is a non-monadic, CBV interpreter. This is the (non-monadic) baseline for all experiments. That is, we will turn this interpreter into monadic style, instantiate the monad parameter, perform data extensions and selective code replacements. We will also vary CBV vs. CBN, and we will use CPS eventually.

• CBV.hs: This is the scheme of a monadic-style CBV intepreter. This file is incomplete as it lacks a concrete monad. (Don't run this file.) Some of the following interpreters complete this scheme. Such completion typically involves data extension and selective code replacement.

• Identity.hs: This is CBV.hs completed by the identity monad.

• Errors.hs: This is an interpreter with error messages. To this end, we instantiate the monad parameter of our monadic-style CBV interpreter with the error monad, and we apply selective code replacement so that error messages are actually thrown by the interpreter.

• Positions.hs: This is an elaboration of Errors.hs so that position information is maintained and accordingly used in the error messages.

• State.hs: This is an interpreter with a reduction count for function applications including additions. To this end, we instantiate the monad parameter with the state monad, where the state models the reduction count. We also need to apply selective code replacement so that function applications are actually counted. We also perform a data extension to provide a language construct for reading the reduction count within the interpreted language.

• Output.hs: This is an interpreter with output. To this end, we instantiate the monad parameter with the writer monad, so that output is aggregated as a string. We also perform a data extension to provide a language construct for producing output within the interpreted language.

• Nondeterminism.hs: This is an interpreter with non-deterministic choice. To this end, we instantiate the monad parameter with the list monad, so that nondeterminism is modeled with a multiplicity of result values. We also perform a data extension to provide language constructs for the failing computation (that produces the empty list of results) and for nondeterministic choice, indeed.

• Backwards.hs: This is a variation on State.hs with backwards propagation of state.

• CBN.hs: This is the scheme of a monadic-style CBN interpreter. This file is incomplete as it lacks a concrete monad. (Don't run this file.) Some of the following interpreters complete this scheme.

• StateCBN.hs: This is a variation on State.hs with CBN.

• NondeterminismCBN.hs: This is a variation on Nondeterminism.hs with CBN.

• CPS.hs: This is a non-monadic, CBV and CPS interpreter.

• Callcc.hs: This is a monadic-style interpreter (CBV) that uses the continuation monad to provide "call with current continuation" (callcc). We perform a data extension to provide callcc as a language construct within the interpreted language.

• ErrorsCPS.hs: This is a variation on Errors.hs which leverages the continuation monad and uses the Answer type to plug errors into the interpreter.

• StateCPS.hs: This is a variation on State.hs which leverages the continuation monad and uses the Answer type to plug state into the interpreter.

Code organization of the distribution

Directories:

• cache: ready-to-run interpreters
• templates: cpp templates for interpreters
• monads: monads used in the interpreters
• types: syntactic and semantic domains
• functions: functions making up the interpreters
• terms: sample terms for the interpreters
• baselines: interpreter outputs for regression testing

Some types and functions require variation for the different monads and also in terms of the choice CBV vs. CBN. The subdirectory cba (read as call-by-"any") hosts definitions that are shared by CBV, CBN, and CPS. (Here, we should note that the CPS experiments use CBV (not CBN).) Within directories types and functions, the subdirectories cbv and cbn host definitions specific to CBV or CBN respectively. Monad-specific variations are hosted in yet deeper subdirectories with the (one-letter) name of the corresponding monad; see, for example, functions/cbv/E.

Comments and questions and contributions welcome.

Ralf