grammars and generics

11 Dec 2007

      Haskellians,

Here is an idea so obvious that someone else must have already thought of it
and worked it all out. Consider the following grammar.

N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0
N1 ::= T3 N0

where Ti (0 <= i < 4) are understood to be terminals.

Using generics we can translate each production independently of the others.
Like so:

[| N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0  |]
=
data N0 n1 = T0 n1 | T1 n1 (N0 n1) | T2 (N0 n1) (N0 n1) deriving (Eq, Show)

[| N1 ::= T3 N0 |]
=
data N1 n0 = T3 n0 deriving (Eq, Show)

Then, we can compose the types to get the recursive grammar.

data G = N0 (N1 G) deriving (Eq, Show)

This approach has the apparent advantage of treating each production
independently and yet being compositional.

Now, let me de-obfuscate the grammar above. The first production should be
very familiar.

Term ::= Var Name | Abstraction Name Term | Application Term Term

The generics-based translation of this grammar yields something we already
know: we can use lots of different types to work as identifiers. This is
something that the nominal of Gabbay, Pitts, et al, have factored out
nicely.

The second production can be treated independently, but composes well with
the first.

Name ::= Quote Term

This illustrates that a particularly interesting class of names is one that
requires we look no further than our original (parametric) data type.

So, my question is this. Does anyone have a reference for this approach to
translation of grammars?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com

Greg Meredith

Chung-chieh Shan

tags

participants (2)