9/12/2010

The essence of "The essence of functional programming"


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
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

4 comments:

  1. Ralf, thank you very much for the making these lectures available, I have to say I enjoy them quite a lot.

    I especially appreciate that you reference papers as further reading material -- I've already printed few and put in the to-read queue.

    It's fantastic to look at a a language with lambda calculus but I think it would also be interesting to see a small imperative language interpreter as well -- expression and maybe few statements, especially w.r.t. open data types.

    I look forward to watching the lectures to come!

    Best regards,
    Árni Hermann

    ReplyDelete
  2. Árni, thanks!

    Your proposal for a small imperative language made me thinking.
    In the not too far future, I would talk about an imperative OO language embedding in Haskell. An interpreter instead of an embedding should also be feasible and interesting, perhaps, if I combined it with some other stuff such as parsing and partial evaluation or deeper discussion of laziness.

    Next lecture will be about bananas though :-)

    ReplyDelete
  3. This is my Good luck that I found your post which is according to my search and topic, I think you are a great blogger, thanks for helping me outta my problem..
    Dissertation Abstract Help

    ReplyDelete
  4. I must show some thanks to this writer just for bailing me out of this particular issue. As a result of browsing through the net and seeing views which are not productive, I assumed my life was well over. Being alive devoid of the solutions to the issues you have fixed as a result of your entire post is a serious case, and ones that could have negatively damaged my entire career if I had not come across your web site. That expertise and kindness in dealing with a lot of stuff was crucial. I am not sure what I would’ve done if I had not encountered such a subject like this. I’m able at this time to look forward to my future. Thanks so much for your skilled and sensible guide. I will not hesitate to suggest your blog to anybody who needs and wants support about this topic. Cell Phone Lookup | Outdoor Lighting | Pellet Stoves | Outdoor Flood Lights | Used Pellet Stoves | Outdoor Security Lights | Landscape Lighting Ideas

    ReplyDelete