Previous talks

In reverse chronological order. (Unfortunately the details of some previous talks are lost in the mists of time).

  • Tracing the STG machine. Bernie Pope. 1-2pm Friday 21 August 2009. Room, 4.04 ICT Building. In a previous FPU talk (7 August this year) I discussed the (small step) operational semantics of the STG machine, and showed an implementation in Haskell. Despite being quite high-level, it is still very hard to understand the dynamic behaviour of the STG machine by looking at the static rules alone. Therefore I decided to add a new feature to my interpreter which can trace the steps of the machine and render them in HTML.  An example rendering is here: (Follow the next and previous links to go backwards and forwards one step at a time). The example illustrates the space-leaky version of list summation, based on foldl (with lazy accumulation). If you go to step11.html you will see a chain of thunks on the heap identified by variables $0-$2. These correspond to the suspended additions on the accumulator parameter. I've also added a garbage collector to the interpreter which keeps the heap tidy in each step.  The tracer has already proven itself useful by helping me to quickly identify a couple of subtle bugs in the interpreter. However my main goal is to use the interpreter to explore various extensions to the STG machine, in particular debugging facilities, such as call-stack tracing. If time permits I will also talk about this work. I also expect that the interpreter will be a useful tool for teaching programming language implementation.
  • Procedural aspects of declarative programs. Lee Naish. 1-2pm Friday 14 August 2009. Room, 4.04 ICT Building. This talk will be a wander through some of my previous work on such things as verification of logic programs and imperative programs, a declarative view of modes and a three-valued semantics for logic programmers, with a few new insights.
  • The operational semantics of the STG machine. Bernie Pope. 1-2pm Friday 7 August 2009. Room, 4.04 ICT Building.The Spineless Tagless G-Machine (STG) is the abstract machine employed by GHC. A high-level operational semantics for the machine is given by Peyton Jones and Marlow in this paper: How to make a fast curry: push/enter vs eval/apply I will present that semantics in the talk, and hopefully show animplementation of it in Haskell.  My purpose for doing this is to explore the semantics of stack tracing in Haskell (or rather, GHC).
  • Relating Models of Backtracking. No presenter (internet video instead). 1-2pm Friday 31 July 2009. Room, 4.04 ICT Building. We watched a video presentation by Mitch Wand: There are two common semantic models for backtracking computations: 1) streams of answers; 2) functions which operate on success and failure continuations. In this talk (presented by Mitchell Wand for Dan Friedman's 60th birthday), the relationship between these two models is considered. Some interesting elements of the talk are the use of monadic meta languages (which originated with Moggi) and the so-called logical relations of Plotkin to connect the two models.  The talk begins with a short discussion about the desire for modular denotational semantics and briefly explains the contributions of monads from Moggi's work. So it may be additionally interesting to people who are trying to understand what monads are (or at least what they were originally intended for).
  • Writing Business Rules Engines in Mercury. Ian MacLarty. 1-2pm Friday 24 July 2009. Room, 4.04 ICT Building. At Mission Critical we use the declarative language Mercury extensively. I will talk about how we use Mercury in our business rules engines (of which we have several). I will also give some examples of the kinds of business rules we model and talk about some of the problems we face when interpreting these rules.
  • Object-oriented graph reduction - an alternative to lambda lifting. Nick Downing. 1-2pm Friday 10 July 2009. Room, 4.04 ICT Building. Nick explained a slow (but powerful) approach to reducing lambda calculus expressions expressed as sharing graphs, and in the process he briefly explained how lambda lifting speeds things up. He then presented an original idea in which nodes are represented by java objects and lambda lifting is avoided, leading to fewer reductions. A nice feature of this proposed scheme is that types would be assigned to expressions in a Haskell-like way and then the resulting types mapped onto Java types.
  • Applicative Functors and Friends. Bernie Pope. 1-2pm Friday 3 July 2009. Room 4.04 ICT Building. Applicative functors provide a programming abstraction which sits between functors and monads. They capture a common pattern of programming with "effects", which do not require the full expressiveness of monads. 

    One of the benefits of applicative functors over monads is that they allow "effectful" code to be written in direct style. For example, when using monadic parser combinators such as Parsec, one often writes code like this: 

       do { x <- e1; y <- e2; z <- e3; return (f x y z) } 

    where e1,e2,e3 are themselves parsers and f is some "pure" function which builds the result of the overall parser. 

    With applicative functors the same parser can be written like so: 

       f <$> e1 <*> e2 <*> e3 

    which resembles ordinary function application (hence the name "applicative"). 

    In cases like this, the monadic style obscures the important structure of the code, and requires redundant naming of the results of sub- computations (the x,y,z variables). Furthermore, in such cases the full expressiveness of monads is not warranted, and it is arguably better to use less expressive constructs where possible. 

    Applicative functors were introduced in the paper "Applicative Programming with Effects" (2008) by McBride and Paterson: 

    In this talk Bernie discussed the implementation and use of applicative functors, and introduced some related abstractions. He also showed how these ideas have been adopted in the parser combinator library in Scala.

  • The Lambda Cube. Ben Horsfall. 1-2pm Friday 26 June 2009. Room 4.04 ICT Building. Henk Barendregt's lambda-cube is a taxonomy of eight Church-style type systems, classified by sort constraints on the formation of product (that is, function) types. The simplest system is the simply-typed lambda-calculus, with the three dimensions of the cube corresponding to the addition of polymorphism, dependency and type functions. Taken all together these yield the calculus of constructions, a system similar to those of Coq and Agda. A recent textbook account is section 13E of Hindley & Seldin, LambdaCalculus and Combinators, an Introduction, CUP, 2008. 
  • Data Parallel Haskell. Paul Bone. 1-2pm Friday 19 June 2009. Room 4.04 ICT Building. As a precursor to Roman Leshchinskiy's visit in July, Paul Bone lead a discussion of the paper "Harnessing the Multicores: Nested Data Parallelism in Haskell":

  • Simple graph reduction with visualisation. Bernie Pope. 1-2pm Friday 12 June 2009. Room 4.04 ICT Building. Last year, whilst teaching the fourth year functional programming subject, I wrote a little functional language called miniFP for demonstration purposes. Near the end of the course we covered graph reduction. I extended miniFP to compile to a simple graph reduction system, implemented in C. One of the more interesting and useful aspects of the system is that it can produce pictures of the graph at each step of reduction. This allows the user to visualise the graph reduction process. It is especially helpful for understanding how cyclic data structures can be produced by 'tying the knot', which is a difficult topic to explain on paper. In this talk I will outline some of the interesting aspects of the implementation, and show how it can be used. Slides for the talk: graphreduction.pdf
  • How pure is Haskell? Bernie Pope. 1-2pm Friday 15 May 2009. Room 4.04 ICT Building. Bernie wanted to draw attention to two interesting topics that have been percolating on the Haskell mailing lists: 

        Definitions of purity and Lazy IO: 

        Notions of purity in Haskell: 

    There is an obvious connection to the previous FPU talk by Harald about Amr Sabry's paper: What is a Purely Functional Language? 

  • Paper Discussion: The power of Pi (Oury & Swierstra, ICFP 08). Ben Horsfall. 1-2pm Friday 1 May 2009. Room 4.04 ICT Building. Ben will lead a discussion about the paper "The power of Pi" by Oury & Swierstra, from ICFP 08.  

    It's an introduction to dependently-typed programming, with some concrete examples. 

  • Type Families and Type Functions in Haskell. Ben Horsfall. 1-2pm Friday 27 March 2009. Room 4.04 ICT Building. Ben will introduce type families for Haskell, and present an example of their application from his research. Type families are a development of indexed or assocatiated types, and they are implemented in the current release of GHC. Amongst other things, they provide an elegant replacement for multi-parameter type classes with functional dependencies. 

    For an introduction see: 

    The latest paper is: 
    Tom Schrijvers, Simon Peyton Jones, Manual Chakravarty 
    & Martin Sulzmann, Type Checking with Open Type Functions, ICFP'08 

  • Introduction to Scala. Matt Giuca. 1-2pm Friday 13 March 2009. Room 4.04 ICT Building. Matt demonstrated some features of the Scala programming language, which is based on Java, but with a bunch of functional features added. Scala supports higher-order functions, currying, etc, as well as algebraic data types and pattern matching, and is also fully object- oriented. The Scala website is here:
  • Playing with the Haskell bindings to LLVM. Bernie Pope. 1-2pm Friday 6 March 2009. Room 4.04 ICT Building. Bernie provided an overview of LLVM and demonstrated the Haskell bindings with a compiler for a small imperative language (terpie).
  • OCaml as a second (functional) language. Ben Horsfall. 1-2pm Friday 18 February 2009. Room 4.04 ICT Building. Ben presented a short and partial introduction to OCaml from the point of view of a beginner, but one not new to functional programming. He gave some attention to the blending of applicative and imperative features and to the module system, and made some comparisons with Haskell.
  • Automatic Parallelism in Mercury. Paul Bone. 1-2pm Friday 10 February 2009. Room 4.04 ICT Building. Paul presented his work so-far on a profiler feedback directed automatic parallelisation feature for Mercury. He discussed the profiler feedback framework and changes to Mercury's deep profiler that have been necessary. He described how he intends to use this information to parallelise a program, including potential extensions to create more-optimal programs. Slides for Paul's talk are available.
  • Mars: An Imperative Functional Programming Language. Matt Giuca. 1-2pm Friday 4 February 2009. Room 4.04 ICT Building. Matt talked about his research-oriented programming language, with discussion of language design and implementation of an interpreter in Mercury.
  • A parser for Python written in Haskell using Alex and Happy. Bernie Pope. 1-2pm Friday 14 January 2009. Room 4.04 ICT Building. Over the end-of-year break Bernie wrote a parser for Python 3.0 in Haskell using Happy and Alex (the Haskell equivalents of yacc and lex). In this talk he demonstrated the use of these tools, and the design of his parser.
  • Extended pattern-matching and higher-order abstract syntax. Ben Horsfall. 1-2pm Friday 5 December 2008. Room 4.04 ICT Building. Ben demonstrated his latest work on first-class pattern matching in a small programming language.
  • Continuations: an overview. Bernie Pope. 1-2pm Friday 3 October 2008. Room 4.04 ICT Building. Bernie presented an overview of the fascinating and broad topic of continuations. Continuations are a method of reifying the evaluation context of a term within some computation. Intuitively, the continuation describes what may become of the value of the term in the overall computation. In this sense, a continuation provides a concrete representation of program control, and allows it to be manipulated. This "purely functional" account of program control has many useful results, such as:
    • The extension of denotational semantics from the lambda calculus to (constructs from) conventional imperative languages, such as jumps.
    • Techniques for compiling high-level languages to machine code.
    • First class control operators, such as exception handlers.
    In recent times, more refined versions of continuations have emerged, such as the delimited continuations (or subcontinuations), which reify only a part of the evaluation context of a term. Bernie's talk covered these aspects of continuations:
    • The continuation passing style (CPS).
    • The history of continuations.
    • Some interesting applications of continuations.
    • The use of continuations in the "direct style" of programming,via primitives such as call/cc of Scheme.
    Slides for Bernie's talk are available.
  • Purity and parameter passing. Harald Søndergaard. 1-2pm Friday 15 August 2008. Room 4.04 ICT Building. Harald discussed the paper "What is a purely functional language" (Journal of Functional Programming, 1998) by Amr Sabry. which suggested a definition of "purity" of functional programming languages as essentially parameter-passing independence. Sabry considers other possible definitions, rejecting them for various reasons, and he arrives at one based on parameter passing via this process of elimination. Harald repeated and discussed Sabry's arguments.
  • Splint. Ben Horsfall. 1-2pm Friday 25 July 2008. Room 4.04 ICT Building. Melbourne University. Ben presented his recent work on Splint: λ-calculus with pattern functions and primitive case. He demonstrated his interpreter for a simple lazy functional programming language named Splint. Its distinctive features are a primitive case construction and a binding annotation on pattern variables which allows patterns to be computed (since they are terms) and for this computation to depend upon and be interleaved with pattern matching. It also allows patterns to contain variables over constructors.
  • Disciplined Disciple Compiler. Ben Lippmeier. 1-2pm Friday 30 May. Room 4.04 ICT Building, Melbourne University. Ben was our special guest from ANU. He talked about his recent work on the DDC compiler, and also gave us a demo of the graphics library used in teaching at ANU. This is the abstract from his departmental seminar on DDC: In the land of functional programming a bitter war rages between the ideals of purity and the temptation of side effects. On one hand, the banishment of effects from a pure language makes programs easier to reason about, permits safe lazy evaluation and accommodates a host of clever compiler optimisations. On the other hand, side effects and destructive update are useful, if not mandatory, for writing efficient programs and for interaction with the outside world. The Disciplined Disciple Compiler, now in alpha release, seeks to unify these two camps. 'Disciple', being an explicitly lazy dialect of Haskell which supports allied functional goodness as well as arbitrary destructive update, computational effects and type-directed field projections. 'Disciplined' referring to the way the core language is annotated with mutability, effect and data sharing information via a type-based analysis. This information leaves the door wide open for the same code-transformation style optimisations previously restricted to pure applicative languages, without resorting to state monads, linear typing or other coarse restrictions on the way programs are constructed.
  • Resources: A Mercury alternative to monads and 'do' notation. Peter Schachte. 1-2pm Friday 9 May. Room 4.04 ICT Building, Melbourne University. Peter proposed a syntactic extension to Mercury to allow values to be passed through a computation implicitly, much like (state) monads, and do notation, do for Haskell. Like monads, resources allow values to be passed into and out of code without having to explicitly appear in argument lists; their presence is indicated in declarations. The compiler ensures that the value is threaded correctly through the code, passed everywhere it should be. Resources do not provide the generality of monads, but Mercury natively provides the functionality of many of the commonly-used Haskell monads; resources provide a few more.
    Slides for Peter's talk are available.
  • Uniqueness typing simplified. Matt Giuca. 1-2pm Friday 2 May. Room 4.04 ICT Building, Melbourne University. Matt discussed the paper Uniqueness typing simplified, by Plasmeijer et al on an improved implementation of uniqueness typing. Slides for Matt's talk are available.
  • Data types à la carte. Ben Horsfall. 1-2pm Friday 18 April. Room 4.04 ICT Building, Melbourne University. Ben discussed the recent paper by Wouter Swierstra, which demonstrates a solution to the "expression problem" in Haskell.
  • The History of Functional Programming. Les Kitchen. 1-2pm Friday 11 April. Room 4.04 ICT Building, Melbourne University. Les led a lively discussion about some of the historical aspects of functional programming. One of the major topics of interest was Lisp macros. We also talked about laziness as a default evaluation strategy, and considered its pros and cons.
  • Haskell in a commercial setting. Tom Conway. 1-2pm Friday 28 March. Room 4.04 ICT Building, Melbourne University. Tom talked about his experiences using Haskell in a commercial application.
  • Hyacinth, a sound synthesiser written in Haskell. Jeremy Wazny. 1-2pm Friday 14 March 2008. Room 4.04 ICT Building, Melbourne University. Jeremy demonstrated Hyacinth, a sound synthesiser which is based heavily on the composition of "functional" sound waves. The key idea of Hyacinth is that sound waves are implemented as functions which are mappings from time to output magnitude, similar to the scheme used for graphics in Conal Elliot's Pan 2D graphics system.
  • XMonad. Ben Horsfall. 1-2pm Friday 29 February 2008. Room 4.04 ICT Building, Melbourne University. Ben presented XMonad, a tiling window manager for the X Windows System (X11), written in Haskell. As part of the talk, Ben demonstrated some of his own extensions that he has made to XMonad.
  • Terpie, a small imperative language with Logo-like graphics. Bernie Pope. 1-2pm Friday 22 February 2008. Room 1.09 ICT Building, Melbourne University. Bernie discussed a little programming language he has been developing in his spare time which is something like a cross between Logo, Python and C. Terpie is noteworthy because:
    • It was implemented in a weekend so it is short.
    • It features turtle graphics modelled of Logo.
    • It has a basic interactive command line which is implemented in Terpie.
    • It was the basis of the programming project in 433-431 Functional Programming (a fourth year subject taught by Bernie in Semester 1 2008).
    Of course Terpie is written in Haskell, and in this talk Bernie shared some of the nice things that he used such as:
    • the Parsec library for parsing.
    • the state monad transformer library for the evaluation environment.
    • cairo and gtk for graphics.
  • Deriving monads from vague ideas in several easy steps. Andrew Bromage. 1-2pm Friday 15 February 2008. Room 4.04 ICT Building, Melbourne University. Andrew showed us how to develop a monad incrementally, taking good advantage of the monad laws. He also discussed how this might also be mapped to arrows. A somewhat related discussion is available in the Unimo paper by Chuan-kai Lin.
  • A demonstration of the Coq proof tool. Ben Horsfall. 1-2pm Friday 8 February 2008. Room 4.04 ICT Building, Melbourne University. Ben demonstrated the use of Coq on some examples in classical logic.
  • A curious space leak in merge sort in Haskell. Bernie Pope. 1-2pm Friday 1 February 2008. Room 4.04 ICT Building, Melbourne University. Bernie discussed a curious stack overflow which was discovered (by others) in the context of merge sorting large lists in Haskell, and discussed on the Haskell cafe mailing list.
  • Arrows in parser combinators. Ben Horsfall. 1-2pm Friday 25 January 2008. Room 4.04 ICT Building, Melbourne University. Ben presented some of the ideas in the paper from John Hughes' paper Generalising Monads to Arrows. Some background reading on Arrows is available on the Haskell wiki.
  • The GHCi debugger. Bernie Pope. 1-2pm Friday 18 January 2008. Room 4.04 ICT Building, Melbourne University. The FPU (Functional Programming Union) arose after several years of slumber. Bernie presented some of the recent work that had been done on the GHCi breakpoint debugger.
  • The anatomy of a Haskell type-checker Bernie Pope. 19 March 2001. Bernie presented a basic outline of a Haskell type-checker and discussed some of the thornier aspects of type-checking Haskell. He illustrated kind inference, binding groups, polymorphic recursion, ambiguities and the defaulting mechanism, and finally the monomorphism restriction. It was noted that the choice of algorithm for inferring the types of the implicitly typed bindings within a mutually recursive group can make a difference in the result. Much of the material described comes from the Typing Haskell in Haskell paper by Mark Jones.
  • A General Type Inference Framework for Hindley/Milner systems. Martin Sulzmann. 5 March 2001. Martin presented his work on a general type inference framework for Hindley/Milner systems. This will also be presented at FLOPS 2001 (the Fifth International Symposium on Functional and Logic Programming). In the framework he uses constraint based typing inference in place of the more traditional substitution model. Effectively the constraint system subsumes substitutions (by means of equality constraints). The framework makes a clear distinction between the various phases of inference, these are: generation, propagation, solving, and simplification of constraints, and term reconstruction. The framework also allows for partial solutions to typing problems which permits a more flexible constraint propagation during type inference. This is beneficial for both early and accurate detection of type errors, and type-based program analysis. The framework also provides a means for very concise soundness and completeness results for derived type inference algorithms. As a demonstration of his framework, Martin showed how unit types could be handled, and how Kennedy's problem can be solved in the framework, a problem for which substitution based inference fails. Slides for Martin's talk are available.
  • Maude. Chris Wright. 13 Nov 2000. Chris described Maude, a language which supports both equational and rewriting logic specification and programming. It is influenced greatly by OBJ3 (but OBJ3 supports only equational logic). It has a powerful reflective system and very flexible syntax (including mix-fix). Together with an efficient implementation this has made it popular for meta-language systems. Other features include sub-sorting, when importing a module a distinction between keeping and modifying its semantics, attributes rewrite rules (assoc, commutative, specifying identities, idempotemce). This flexibility can be a headache when using the system as an (executable) specification language. But it allows powerful tools to be written in Maude that can check that properties such as confluence, church-rosser, termination etc. are satisfied. An extension to Maude (Full Maude, which will at some stage become Maude) allows operations to be polymorphic. Chris is interested in Maude because he is looking for systems for specifying agent systems, and Maude supports a concurrent rewriting semantics.
  • Clean Game Library. Bernie Pope. 6 Nov 2000. Martin Weiring developed a library for programming two-dimensional graphical computer games in the Clean language. The library allows a programmer to specify the behaviour of the game in a declarative fashion, defering the task of handling input and output and resource management to a game engine (written in C). He also developed a program called Tile Studio that assists in the creation and manipulation of graphical elements in the game (sprites, and layers). The program allows one to draw a graphical element and then encode certain characteristics for the element such as animation or placement. The program can then be used to output Clean code that can be imported into the game definition. The game is run via an event loop and information is passed between elements in the game via events. Some events are external, such as keyboard presses, some are generated by the game engine, such as timer alarms, and some are generated by objects within the game. Large numbers of event creations can greatly reduce the performance of the game engine, to the point where the game is no longer playable. Unique types and strictness annotations within the Clean language and strictness analysis within the compiler help to improve the runtime performance of the game. It was noted by Lee Naish that it would be interesting to see what effect these features have on the memory usage of the game (especially with respect to garbage collection).
  • Type Safe Cast. Details currently unavailable. 16 Oct 2000.
  • Meta-Haskell on the Cheap. Kevin Glynn. 4 Sep 2000. Kevin described GHC's implementation of rewrite rules. These provide relatively cheap support of list deforestation and type driven function specialization. (c.f. deforestation analyses proposed previously). The price paid is that fusion rules have to be explicitly provided for the types of interest. GHC provides fusion rules for lists. Rules can be tricky to get right, and if not used carefully may reduce performance, or lead to incorrect programs.
  • Normalization by Evaluation. Torben Ægidius Mogensen. 17 Aug 2000. Torben described a method he has devised for converting arbitrary expressions into a text representation. The expression is transformed to a new expression with reflect/reify calls. Evaluating the new expression gives a textual representation of the original expression. Interestingly, it is a normalized representation which is printed. Torben showed how to achieve this for both typed and untyped lambda calculus. Unfortunately, there are restrictions on the expressions that can be normalized. However, techniques similar to these have been successfuly applied to type based partial evaluators. See Olivier Danvy's home page for examples. Torben has written a paper on this topic.
  • Hood: Haskell Object Observation Debugger. Bernie Pope. 7 Aug 2000. Bernie has been looking at Andy Gill's Hood. This is a much improved version of debugging by trace. You insert observe calls into your code. When they are executed they generate trace events to a XML log file. These can then be browsed through a java browser. Bernie has been looking to see if any of the Hood work can help his declarative debugging project.
  • Functional Programming in Mercury. 29 March 2001. Details currently unavailable.
  • Laziness is a virtue. Kevin Glynn. 1 March 2001. Details currently unavailable.
  • HM(X) for Binding Time Analysis. Martin Sulzmann. 23 Feb 2000. Martin discussed the application of HM(X) to binding time analysis.
  • Hindley Milner Style Type Systems. Martin Sulzmann. 16 Feb 2000. Martin presented his work on Hindley Milner style type systems, and his framework for them. This is based on work from his (then forthcoming) thesis.
  • Stepwise Enhancement and Higher Order Programming in Prolog. Lee Naish. 15 Dec 1999. Lee presented his work with Leon Sterling on Stepwise Enhancement and Higher Order Programming in Prolog, which is realted to poly-typic programming whereby higher-order functions such as folds and maps can be derived for given data structures. Lee and Leon Sterling wrote a paper about this topic.
  • HEP: Haskell Execution Platform. Bernie Pope. 17 Nov 1999. Bernie presented the details of the Haskell Execution Platform, which is a design for a common compilation and execution environment for Haskell implementations. It is intended to unite the Hugs and GHC Haskell implementations. There is a design document for the platform.
  • Dependent Type Systems. 3 Nov 1999. Details not currently available.
  • ICFP99 and PPDP99 Conference Summary. Harald Søndergaard. 20 Oct 1999. Harald gave us the gossip from ICFP99 and PPDP99 which were held together in Paris. Tyson Dowd was also there or thereabouts, and so he also gave us some interesting feedback. The keynote speaker at ICFP99 was Chris Okasaki, he gave a FP data structures and algorithms tutorial based on material from his book. Harald thought that Mercury's red-black tree implementation may benefit from similar techniques. Chris also gave another talk, which looked at representing square matrices. These are usually represented as a list of lists. But it isn't possible to constrain such a type to be square. He solved this problem with a type similar to the following:
    data SqM a = Zero a 
    | Succ (SqM (a, a, a, a))
    Note that, in the Succ alternative the parameterised Type Constructor SqM is applied to a tuple of four as. Such a type is called a `nested datatype' or a `non-regular datatype'. Other papers discussed included:
    • Using value slices to detect non-termination in logic programs.
    • Deforestation (via Attribute Grammars).
    • `Short cut deforestation' via type inference.
    • Affordable declarative debugging of functional programs.
  • Efficient Parser Combinators. Bernie Pope. 29 Sep 1999. Bernie presented some recent work on making Parser Combinators efficient Pieter Koopman and Rinus Plasmeijer: Efficient Combinator Parsers. The authors take a standard set of parser combinators (such as those in J. Fokker: Functional Parsers.) and show that on one example they run about 5000 times slower and use 10 times more memory than a direct implementation of the same parser. They then show how various transformations of the combinators can improve the speed and memory consumption to be only 4 times slower and use 50% more memory. The important transformations which we looked at in the meeting were:
    • Using continuations to remove explicit intermediate results.
    • Limiting back tracking by introducing an XOR combinator.
    • Introducing a `cut' operator to remove uninteresting alternatives.
    • The authors of the paper use clean to demonstrate their new combinators. We felt that the presentation would be clearer using Haskell's monads and do notation.
    However, these results do show that parser combinators can be tractable for non-trivial parsing.
  • Mycroft Types. Harald Søndergaard. 15 Sep 1999. Harald continued his dicussion from the last meeting about variations of polymorphic type systems. The major implementations of Haskell available today use a combination of classic Hindley-Milner and Mycroft type inference [1] (well, at least Hugs appears to, but I assume the others do too). This enables a larger class of sensible programs to be type-checked, without adding significantly to the cost of inference. Harald explained that the difference between Hindley-Milner's system and Mycroft's is in their treatment of the fix operator (think letrec and mutually recursive top level function definitions). HM restricts the types of the fixed variable so that inference is still decidable, but that means that all uses of the variable must be used at the same type. Mycroft arranges all types in a lattice, and uses a fixpoint mechanism to arrive at the smallest (possibly generic) type that can be used at all required instances. Unfortunately, the fixpointing is not guaranteed to terminate, so some mechanism is required to ensure it does (e.g. by setting an arbitrary limit on the number of iterations). As an example consider the following function:
    k = \x y.x
    i = \x.x
    g = \v.k (g i) (g k)
    HM can't type this because g is applied to functions with different types (a -> a) and (a -> b -> a). Mycroft first typechecks g's body assuming g has type Forall a.a. We find the rhs of g's definition has type Forall a.b. a -> b. Since this doesn't equal the type we had originally assigned g we repeat the process with g assumed to be Forall a.b. a -> b. This time the inferred type for the body is Forall a.b. a -> b and we are done. Try this in hugs .... Also Mycroft can deduce a more general type than HM. (So what does it mean that HM deduces `principal' types ??). For the following function:
    r1 x y = r1 (r1 y const) x
    HM deduces the type Forall a.b (a -> b -> a) -> (a -> b -> a) -> a -> b -> a, while Mycroft can confirm the type: Forall a.b.c. a -> b -> c As an example of a function definition which would make Mycroft's algorithm diverge:
    f x = f
    Haskell implementations use Mycroft's mechanism if a type is provided by the user. They add the provided type to the assumptions and after checking the body expression they check to see if the inferred type equals the provided one, if it does then they will accept the type. It was requested at the meeting that GHC (the popular Glasgow Haskell Compiler) be made available on the departmental machines. Version 4.04 of GHC is now available on the student (solaris) machines. At the next meeting Bernie has asked if we can discuss Parser Combinators, in particular there have been some proposals recently for parser combinators that are much more efficient than the traditional presentations. Reference: Alan Mycroft: Polymorphic Type Schemes and Recursive Definitions.
  • Hindley Milner Types and Extensions. Harald Søndergaard. 1 Sep 1999. The FPU has restarted its bi-weekly meetings (after a very long Summer break!). We are holding them at 3:15 on Wednesday afternoons. Kevin asked for suggestions (or meant to ...) for making the FPU home page more useful and said that he would try to move it to We will add an 'interesting snippets' section which will be a repository of interesting FP related mail messages and links that we come across. People are encouraged to forward such info to Bernie. At the meeting proper Harald discussed 'Variants of Polymorphic Type Inference'. We reviewed Hindley-Milner type systems and inference, seeing that Hindley-Milner is a compromise that allows us to type most 'reasonable' programs and has an efficient inference algorithm. Kevin confused the presentation by mentioning that as well as principal types there are principal typings (Trevor Jim: What Are Principal Typings and What Are They Good For?). We spent some time looking for a good example to motivate the Hindley Milner treatment of polymorphism (allowing different monomorphic instances for let bound identifiers and disallowing it for function parameters). Harald presented algorithm M (Oukseh Lee and Kwangkeun Yi: Proofs about a Folklore Let-Polymorphic Type Inference Algorithm). A variant of the famous algorithm W by Damas and Milner, which performs unification more frequently during type inference and thus can give better error messages. Harald also briefly discussed Mycroft's method for inferring/checking types, this will be continued in the next meeting. It takes programmer-supplied types into consideration and can allow programs to be typed that Damas Milner can't. Haskell implementations support this. At the next meeting Harald will continue to discuss Hindley-Milner based systems, a later meeting will be about Cayenne, which supports Dependent Types.
  • Raytracer in Haskell. Bernie Pope. 1 Oct 1998. This meeting was dedicated to a brief discussion of the ray tracer that Bernie and Kevin are developing in Haskell. The discussion was led by Bernie, who presented the code that has been developed thus far, and the approach used in developing the ray tracer. The current version of the ray tracer is a prototype, which has proven that Haskell is a suitable language for developing such an application. In fact the time required to develop a functioning ray tracer was minimal, and very little debugging was required on the end product. The ray tracer currently supports the requirements of a project in the computer graphics subject (433-380). Bernie and Kevin have plans to extend it much further than this. The two major extensions that are scheduled for the ray tracer are: 1) to use the Haskell type class system to allow the addition of different objects to be placed within a rendered scene; 2) write the rendered image to a "better" image format than pgm/ppm. Bernie will be working on the first extension and Kevin will be working on the second extension. Mark Brown suggested that objects within the scene could be represented as functions that given the representation of a line will map to a point in space. Mark also suggested that the raytracer might be optimised by computing the intersection of planes with objects, rather than lines and objects. David said that he had implemented a rendering program in Mercury which was similar in design to our current program, although his program rendered polygonal objects. It was decided that there would be no fpu meeting in two weeks time due to the fact that Neil Jones would be visiting the department in that week.
  • Fran. David Overton. 17 Sep 1998. David Overton presented Fran, a system for reactive animations in the functional language Haskell. References to this system can be found at the FPU links page. David's slides for this talk can be found at the following link. The significance of laziness in the implementation of Fran "behaviours" was noted at the meeting. The possibility of implementing such as system in a strict language was also considered. Kevin illustrated the flexibility and composability of animations with a few examples. The declarative composition of animations exhibited by Fran was considered one of its key features. Some of the negative aspects of Fran (in its current implementation) are that it is rather slow, and requires the Microsoft Direct-X graphics library/interface, which is currently only available for the Windows operating system. Some consideration was made in the meeting to what would be required to port Fran to another graphics library, such as Open GL. Kevin made the point that the principle behind Fran could be extented to other fields other than animation. Possible connections to the music system of Haskore were also considered. No topic was set for the next meeting, which will most likely be in four weeks time.
  • Exceptions. 2 Sep 1998. At the beginning of the meeting Harald introduced to the new members the concept of the FPU that was devised at the previous meeting. Bernie then proceeded to give a brief overview of the issues surrounding exceptions in functional programming languages. He noted the different views that people have of exceptions, which are typically divided into those that are requested by the program itself (e.g. explicit function failure), and those that are external in some way to the program (e.g. heap exhaustion and numerical overflow). The approach to handling an exception may depend on its origin, and program initiated exceptions are probably easier to deal with than external exceptions. The "Maybe" type approach to exception flagging was discussed, and its link to Wadler's "list of successes" approach was made. This approach was considered generally inflexible, and only suitable to a small class of program initiated exceptions. The "catch" primitive used in Augustsson's interactive lazy ML system was also discussed. This was considered slightly more flexible than the "Maybe" approach, but it was still subject to problems due to lazy evaluation, and hence is not considered a complete solution. There are also problems due to referential transparency with this technique as well. Fergus Henderson discussed an approach to handling exceptions in a referentially transparent manner using non-deterministic sets to flag the occurrence of exceptions. This technique is based on his experience of implementing committed-choice non-determinism in Mercury. The proposed advantage of this technique over the IO monad approach in Haskell is that the non-deterministic sets do not impose an order in the evaluation of the program whereas the monads do. Discussions were then held about various general topics in functional languages. The topic for the next meeting was not decided. It was suggested that an alternative time for the meeting be voted upon to allow more members to attend. The vote may be delayed until the mailing list is established.
  • Inaugural meeting. 25 Aug 1998. Attendees: Harald Søndergaard, Kevin Glynn, and Bernie Pope. This was the inaugural meeting of the FPU. The main agenda of this meeting was to discuss how the FPU would be run. The general concensus was that it should be an informal forum for interested members of the department to enter into discussions about issues related to functional programming languages. It was agreed that the meetings should (in general) have a theme, and that any interested parties could lead the discussion, perhaps by presenting research that they have read or done themselves. It was also agreed that there should be no obligation for any member of the FPU to present material, however, everyone should feel comfortable to contribute to the discussion. A list of topics was developed, which now resides on the FPU homepage. Kevin undertook the responsibility to invite other members of the Computer Science Department to join the group. It was also decided that a web-page would be useful, and also a mailing list to distribute relevant information to members of the FPU. Bernie undertook the responsibility for creating the web-page and the mailing list, however, Kevin would maintain his own list until the mailing list was in operation. A small discussion was held regarding exceptions in functional programming languages. Kevin made a copy of the Haskell mailing list available (now residing here), and Harald offered to follow some references he had seen on the topic. It was decided that exceptions would be a good topic to continue with in the next meeting.