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