Ken,

Thanks for the references! Have two-level types been applied to parser generation?

Best wishes,

--greg

Greg Meredith <lgreg.meredith@biosimilarity.com> wrote in article < 5de3f5ca0712111100l79ec280fl1d828b12125abbdc@mail.gmail.com > in gmane.comp.lang.haskell.cafe:
> Here is an idea so obvious that someone else must have already thought of it
> and worked it all out. Consider the following grammar.

Hello!

If I understand your basic idea correctly, it is to split a recursive
data type into two parts, a non-recursive type constructor and a
knot-tying recursive type. This idea has been christened "two-level
types" by

Tim Sheard and Emir Pasalic. 2004. Two-level types and
parameterized modules. Journal of Functional Programming
14(5):547-587.

The idea dates earlier, to initial-algebra semantics and "functional
programming with bananas and lenses":

Mark P. Jones. 1995. Functional programming with overloading and
higher-order polymorphism. In Advanced functional programming:
1st international spring school on advanced functional programming
techniques, ed. Johan Jeuring and Erik Meijer, 97-136. Lecture
Notes in Computer Science 925.
http://web.cecs.pdx.edu/~mpj/pubs/springschool.html

Erik Meijer, Maarten Fokkinga, and Ross Paterson. 1991. Functional
programming with bananas, lenses, envelopes and barbed wire. In
Functional programming languages and computer architecture: 5th
conference, ed. John Hughes, 124-144. Lecture Notes in Computer
Science 523.
http://research.microsoft.com/~emeijer/Papers/fpca91.pdf

Cheers,
Ken

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