Polytypic Compact Printing and Parsing

[Paper as .ps.gz (72 Kb), implementation as .tar (30 Kb) ]

Abstract

A generic compact printer and a corresponding parser are constructed. These programs transform values of any regular datatype to and from a bit stream. The algorithms are constructed along with a proof that printing followed by parsing is the identity. Since the binary representation is very compact, the printer can be used for compressing data - possibly supplemented with some standard algorithm for compressing bit streams. The compact printer and the parser are described in the polytypic Haskell extension PolyP.

Implementation

The polytypic core of the implementation is in the file PrintParseArrows.phs and the complete program (including a makefile) is in dc.tar.

The paper appeared in the proceedings of ESOP'99, in Lecture Notes in Computer Science 1576, 1999.

Last modified: Tue Aug 17 15:20:53 MET DST 1999 by

Patrik Jansson / NOpatrikjSP@AMchalmers.se