[TYPES] FP and the Chomsky hierarchy

[oleg at okmij.org]

Representing Chomsky hierarchy in the `natural' for functional
programmers way (as a type-restricted linear lambda-calculus) is one of
the attractions of the so-called Abstract Categorial Grammar (ACG)
formalism. It is being developed by Philippe de Groote and
collaborators. One can find many pointers on the ACG home page

http://www.loria.fr/equipes/calligramme/acg/

The specific question about Chomsky hierarchy and the orders of types
in ACG is answered on slide 44 (PDF page 44) of the following course

http://www.loria.fr/equipes/calligramme/acg/publications/esslli-09/2009-esslli-acg-week-1-day-3.pdf

(Of course one have to read previous slides to understand the L(n,m)
notation). Slide 56 talks about the hierarchy of tree
languages (rather than string languages) and the open problems.

Incidentally, ACG turns out to closely related to the Tagless-Final
approach (as Philippe de Groote himself told me).