Title: Finally tagless observable recursion for an abstract grammar model
Authors: Devriese, Dominique ×
Piessens, Frank #
Issue Date: Nov-2012
Publisher: Cambridge University Press
Series Title: Journal of Functional Programming vol:22 issue:6 pages:757-796
Abstract: We define a finally tagless, shallow embedding of a typed grammar
language. In order to avoid the limitations of traditional parser
combinator libraries (no bottom-up parsing, no full grammar analysis
or transformation), we require object-language recursion to be
observable in the meta-language. Since existing proposals for
recursive constructs are not fully satisfactory, we propose new
finally tagless primitive recursive constructs to solve the problem.
To do this in a well-typed way, we require considerable
infrastructure, for which we reuse techniques from the multirec
generic programming library. Our infrastructure allows a precise model
of the complex interaction between a grammar, a parsing algorithm and
a set of semantic actions. On the flip side, our approach requires the
grammar author to provide a type- and value-level encoding of the
grammar's domain and we can provide only a limited form of constructs
like many. We demonstrate five meta-language grammar algorithms
exploiting our model, including a grammar pretty-printer, a
reachability analysis, a translation of quantified recursive
constructs to the standard one and an implementation of the
left-corner grammar transform. The work we present forms the basis of
the grammar-combinators parsing library, which is the first to work
with a precise, shallow model of abstract context-free grammars in a
classical (not dependently typed) functional language and which
supports a wide range of grammar manipulation primitives. From a more
general point of view, our work shows a solution to the well-studied
problem of observable sharing in shallowly embedded domain-specific
languages and specifically in finally tagless domain-specific
ISSN: 0956-7968
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
gc-jfp.pdfOA article Published 807KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science