[TYPES] FP and the Chomsky hierarchy

Benjamin C. Pierce bcpierce at cis.upenn.edu
Thu Dec 18 11:22:54 EST 2014

A colleague asked me an interesting question recently:

Can the Chomsky hierarchy (regular grammars, context-free, context-sensitive, Turing-complete) be phrased in terms that functional programmers would find natural, e.g. in terms of typed or syntactically restricted lambda-calculi?

Pointers appreciated...

     - Benjamin

More information about the Types-list mailing list