Papers

Selected papers and their connection to the AoP theme.

Pattern:

Name of course participant

BibTeX entry

  @inproceeding{tag,
    usual bibtex tags
  }

Connection

Some text (aimed at the other participants of the course) about the paper and why it is relevant.

Jean-Philippe Bernardy

  @inproceedings{citeulike:2105258,
    abstract =	 {The Iterator pattern gives a clean interface for
		    element-by-element access to a
		    collection. Imperative iterations using the pattern
		    have two simultaneous aspects: mapping and
		    accumulating. Various functional iterations model
		    one or other of these, but not both
		    simultaneously. We argue that McBride and Paterson's
		    idioms, and in particular the corresponding traverse
		    operator, do exactly this, and therefore capture the
		    essence of the Iterator pattern. We present some
		    axioms for traversal, and illustrate with a simple
		    example, the repmin problem.},
    author =	 {Gibbons, Jeremy and Oliveira, Bruno C. },
    booktitle =	 {Mathematically-Structured Functional Programming,
		    Kuressaare, Estonia},
    citeulike-article-id =2105258,
    editor =	 {Mcbride, Conor and Uustalu, Tarmo },
    month =	 {July},
    posted-at =	 {2008-04-30 13:44:58},
    title =	 {The Essence of the Iterator Pattern},
    url =           {http://www.bcs.org/upload/pdf/ewic\_ms06\_paper7.pdf},
    year =	 2006
  }

Gibbons and Oliveira study the notion of "idiomatic traversal", a generalisation of catamorphism and functor application. Their main claim is that this notion captures the essence of the iterator pattern. They go on to define an algebra of "idiomatic traversals" and show how it can be used to produce efficient iteration out of a clear specification.

Joel Svensson

inproceedings{ paul94derivation,

    author = "Roe, Paul",
    title = "{D}erivation of {E}fficient {D}ata {P}arallel {P}rograms",
    booktitle = "Proceedings of the 17th Australasian Computer Science Conference",
    editor = "Gupta, Gopal",
    pages = "621--628",
    year = "1994",
    url = "citeseer.ist.psu.edu/roe93derivation.html" }

This paper shows how to derive SIMD as well as MIMD programs using BMF (Bird-Meertens formalism).

Raul Barbosa

  @InProceedings{Hallgren05,
    title     = "A principled approach to operating system construction in
                 {H}askell",
    author    = "Thomas Hallgren and Mark P. Jones and Rebekah Leslie and
                 Andrew P. Tolmach",
    booktitle = "Proceedings of the 10th {ACM} {SIGPLAN} International
                 Conference on Functional Programming, {ICFP} 2005, {T}allinn,
                 {E}stonia, {S}eptember 26-28, 2005",
    publisher = "ACM",
    address   = "New York, NY, USA",
    year      = "2005",
    editor    = "Olivier Danvy and Benjamin C. Pierce",
    ISBN      = "1-59593-064-7",
    pages     = "116--128",
  }

Hallgren et al. have shown that Haskell is suitable for developing operating system kernels directly on top of the hardware. To achieve this, they implemented a monadic interface to access the low-level constructs of the IA32 architecture. The authors point out that the standard I/O monad and the Foreign Function Interface already allow low-level access to the hardware, but are inherently unsafe. For this reason, they propose a restricted monad, which provides access to the hardware while enforcing type and memory safety (with the exception of I/O operations taking place using Direct Memory Access). To demonstrate the capabilities of their monadic interface, they have written two experimental kernels in Haskell, named House and Osker.

Other related papers

@InBook{gibbons-calculating-functional-programs,
  author =       {Jeremy Gibbons},
  title =        {Algebraic and Coalgebraic Methods in the Mathematics
                  of Program Construction},
  chapter =      {Calculating Functional Programs},
  publisher =    {Springer-Verlag},
  year =         {2002},
  volume =       {2297},
  series =       {{LNCS}},
  pages =        {149--201},
  note=          {Available online at
                   \url{http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/}}

Brief comments from last course instance (2004):

A nice read. Similar to chapter 2 of AoP (calculation, universal properties, category theory)
It might be a good idea to read this text before (the book) AoP.

Interesting note: Backhouse notes on page 5 in Datatype-Generic Reasoning that theorem 5.1 i the AoP book is false. http://www.cs.nott.ac.uk/~rcb/MPC/GenericReasoning.pdf