Papers of Summer 2003
From Lambda Group
Monads and Monad-based Programming
Moggi introduced the concept of a monad to represent computations. Commonly used in pure-functional langauges to represent various styles of computation with and without side effects, monads form the basis of modeling and evaluating Rosetta facets.
- Wadler - Image:Wadler - How to Declare an Imperative.pdf examines the motivation behind using monads to model side effects in a pure functional programming language.
- Wadler - Image:Wadler - Monads for functional programming (1995).pdf provides more background on Monads.
- Wadler - Image:Wadler - The essence of functional programming (1992).pdf includes several examples of using using monads.
- Liang, Hudak, and Jones - Image:Modular-interpreters.pdf introduces monad transformers for combining monads which support the creation of modular interpreters.
- Mark Jones - Image:Jones - Composing Monads.pdf describes some rules and theory behind the composition of different monad transformers.
- Ralf Hinze - Image:Hinze - Deriving Backtracking Monad Transformers.pdf demonstrates how to derive programs from their specifications. The paper derives a monad for supporting backtracking as seen in logic programming languages.
- Hughes - Image:Hughes Generalizing Monads to Arrows.pdf describes a more abstract version of a monad called an arrow. The use of an arrows allows for more aggressive static analysis of monadic computations.
Many algebraic types are similar in the having a common shape, dictated by the type's recursive definition. These papers try to generalize functions over types with a common shape.
- Meijer, et al - Image:Meijer Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire.pdf introduces common recursion schemes in functional programming and provides methods for using and reasoning about these recursion schemes.
- Meijer and Hutton - Image:MEIJE 44.pdf generalizes the above paper, which is concerned primarily with list types, to general algebraic types.
- Duponcheel - Image:Duponcheel Writing Interpreters using Catamorphisms, Subtypes, and Monad Transformers.pdf combines the use of monad transformers with generic programming techniques to build interpreters.
- Gayo - Image:Gayo Reusable Monadic Semantics of Logic Programs with Arithmetic Predicates.pdf provides an example of using the methods from the above paper to extend a simple prolog-like logic programming language with arithmetic operations.
- Jansson and Jeuring - Image:Jansson Jeuring-Polytypic Unification.pdf gives a generic unification algorithm, such as that used by Prolog. It then uses generic programming techniques to make the algorithm work for any term type, automatically.
Domain Specific Extension Languages
DSELs are attempts to extend langauges to provide capabilities specific to a particular domain. Rosetta domains are in effect semantic DSELs. Understanding DSELs and their implementation will help in understanding the implementation of evaluators for individual Rosetta domains.
- Hudak - Image:Hudak-Modular Domain Specific Languages and Tools.pdf is an overview of and argument for DSELs.
- Hudak, et al - Image:Hudak-Arrows Robots and Functional Reactive Programming.pdf describes techniques for eventbased (reactive) DSELs. This paper expands on previous work on DSELs for programming robots (FROB) and animated graphics (FRAN).
- Hudak - The Haskell School of Expression (Haskore Chapter) describes the development of a DSEL which can be used to compose music in Haskell.
- Matthews, Launchbury, and Cook - Image:Matthews-Microprocessor Specification in HAWK.pdf describes the HAWK DSEL, which is used for the specification and simulation of computer hardware.
- Bjesse, Claussen and Sheeran - Image:Bjesse98lava.pdf. Lava is currently used by Xilinx as a specification language for FPGA synthesis.
- Claussen, et. al. - Image:Claessen00tutorial.pdf. A longer tutorial on the Lava hardware description language.