More Web Proxy on the site http://driver.im/

Article

Polytypic Compact Printing and Parsing

Authors:

Patrik Jansson,

Johan JeuringAuthors Info & Claims

ESOP '99: Proceedings of the 8th European Symposium on Programming Languages and Systems

Pages 273 - 287

Published: 22 March 1999 Publication History

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.

References

[1]

R. Backhouse, P. Jansson, J. Jeuring, and L. Meertens. Generic programming -- an introduction. To appear in AFP'98, LNCS, Springer-Verlag, 1998.

[2]

R.C. Backhouse, P.J. de Bruin, P. Hoogendijk, G. Malcolm, T.S. Voermans, and J.C.S.P. van der Woude. Relational catamorphisms. In B. Möller, editor, Constructing Programs from Specifications, pages 287-318. North-Holland, 1991.

[3]

Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text Compression. Prentice Hall, 1990.

[4]

R.S. Bird and O. de Moor. Algebra of Programming. Prentice-Hall International, 1996.

[5]

Algorithmic Research B.V. SDR compression products. See http:// www.algoresearch.com/, 1998.

[6]

Robert D. Cameron. Source encoding using syntactic information source models. IEEE Transactions on Information Theory, 34(4):843-850, 1988.

[7]

J. Halenbeek. Comparing approaches to generic programming. Master's thesis, Department of Computer Science, Utrecht University, 1998. To appear.

[8]

John Hughes. Generalising monads. Invited talk at MPC'98, 1998. Slides available from http://www.md.chalmers.se/Conf/MPC98/talks/JohnHughes/.

[9]

P. Jansson and J. Jeuring. PolyP - a polytypic programming language extension. In POPL'97, pages 470-482. ACM Press, 1997.

[10]

J. Jeuring and P. Jansson. Polytypic programming. In AFP'96, volume 1129 of LNCS, pages 68-114. Springer-Verlag, 1996.

[11]

L. Meertens. Calculate polytypically! In PLILP'96, volume 1140 of LNCS, pages 1-16. Springer Verlag, 1996.

[12]

Erik Meijer. Calculating compilers. PhD thesis, Nijmegen University, 1992.

[13]

Mathematics of Program Construction Group (Eindhoven Technical University). Fixed-point calculus. Information Processing Letters, 53(3):131-136, 1995.

[14]

Swierstra S.D. and L. Duponcheel. Deterministic, error-correcting combinator parsers. In John Launchbury, Erik Meijer, and Tim Sheard, editors, Advanced Functional Programming, LNCS 1129, pages 184-207. Springer-Verlag, 1996.

[15]

R.G. Stone. On the choice of grammar and parser for the compact analytical encoding of programs. The Computer Journal, 29(4):307-314, 1986.

[16]

M. Wallace and C. Runciman. Heap compression and binary I/O in haskell. In 2nd ACM Haskell Workshop, 1997.

[17]

J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337-343, 1977.

Cited By

Tan GMorrisett G(2018)Bidirectional Grammars for Machine-Code Decoding and EncodingJournal of Automated Reasoning10.1007/s10817-017-9429-160:3(257-277)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s10817-017-9429-1
Nielsen LHenglein F(2011)Bit-coded regular expression parsingProceedings of the 5th international conference on Language and automata theory and applications10.5555/2022896.2022930(402-413)Online publication date: 26-May-2011
https://dl.acm.org/doi/10.5555/2022896.2022930
Rendel TOstermann K(2010)Invertible syntax descriptionsACM SIGPLAN Notices10.1145/2088456.186352545:11(1-12)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/2088456.1863525
Show More Cited By

Recommendations

Fast patterning microstructures using inkjet printing conformal masks

The presented paper describes a novel process using inkjet printing to pattern a conformal (built-on) mask onto photoresist for further microstructure formation. The advantages of using the inkjet printing conformal mask include no Cr photomask required,...
Fabrication of stamps for microcontact printing by injection molding

Microcontact printing has been shown to be a viable lithographic technique for the fabrication of a variety of microelectronic components, including source/drain and gate electrodes for organic field effect transistors. Future manufacturing efforts may ...
LLLR parsing
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

The idea of an LLLR parsing is presented. An LLLR(k) parser can be constructed for any LR(k) grammar but it produces the left parse of the input string in linear time (in respect to the length of the derivation) without backtracking. If used as a basis ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ESOP '99: Proceedings of the 8th European Symposium on Programming Languages and Systems

March 1999

304 pages

ISBN:3540656995

Editor:
S. Doaitse Swierstra

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 22 March 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tan GMorrisett G(2018)Bidirectional Grammars for Machine-Code Decoding and EncodingJournal of Automated Reasoning10.1007/s10817-017-9429-160:3(257-277)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s10817-017-9429-1
Nielsen LHenglein F(2011)Bit-coded regular expression parsingProceedings of the 5th international conference on Language and automata theory and applications10.5555/2022896.2022930(402-413)Online publication date: 26-May-2011
https://dl.acm.org/doi/10.5555/2022896.2022930
Rendel TOstermann K(2010)Invertible syntax descriptionsACM SIGPLAN Notices10.1145/2088456.186352545:11(1-12)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/2088456.1863525
Rendel TOstermann KGibbons J(2010)Invertible syntax descriptionsProceedings of the third ACM Haskell symposium on Haskell10.1145/1863523.1863525(1-12)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/1863523.1863525
Fisher KMandelbaum YWalker D(2010)The next 700 data description languagesJournal of the ACM10.1145/1667053.166705957:2(1-51)Online publication date: 8-Feb-2010
https://dl.acm.org/doi/10.1145/1667053.1667059
Liu HCheng EHudak P(2009)Causal commutative arrows and their optimizationACM SIGPLAN Notices10.1145/1631687.159655944:9(35-46)Online publication date: 31-Aug-2009
https://dl.acm.org/doi/10.1145/1631687.1596559
Liu HCheng EHudak PHutton GTolmach A(2009)Causal commutative arrows and their optimizationProceedings of the 14th ACM SIGPLAN international conference on Functional programming10.1145/1596550.1596559(35-46)Online publication date: 31-Aug-2009
https://dl.acm.org/doi/10.1145/1596550.1596559
Hudak PHughes JPeyton Jones SWadler PRyder BHailpern B(2007)A history of HaskellProceedings of the third ACM SIGPLAN conference on History of programming languages10.1145/1238844.1238856(12-1-12-55)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1238844.1238856
Alimarine ASmetsers Svan Weelden Avan Eekelen MPlasmeijer RLeijen D(2005)There and back againProceedings of the 2005 ACM SIGPLAN workshop on Haskell10.1145/1088348.1088357(86-97)Online publication date: 30-Sep-2005
https://dl.acm.org/doi/10.1145/1088348.1088357
van Weelden ASmetsers SPlasmeijer R(2005)Polytypic syntax tree operationsProceedings of the 17th international conference on Implementation and Application of Functional Languages10.1007/11964681_9(142-159)Online publication date: 19-Sep-2005
https://dl.acm.org/doi/10.1007/11964681_9
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents