Minutes of the FPU, Wednesday 29 September, 1999

Attendees

David Jeffery, Kevin Glynn, Bernie Pope.

Minutes

Bernie presented some recent work on making Parser Combinators efficient [1]. The authors take a standard set of parser combinators (such as those in [2]) 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.

References

[1] Pieter Koopman and Rinus Plasmeijer: Efficient Combinator Parsers. LNCS 1595: 120-136, IFL '98

[2] J. Fokker: Functional Parsers. LNCS 925: 1-23, 1st Advanced Functional Programming Workshop 1995

Minutes by Kevin Glynn.

Previous meeting

Return to the minutes index page

Next meeting

Return to the FPU homepage

Kevin GLYNN

Last Modified: Fri Sep 1 12:15:46 EST 2000