[TYPES] FP and the Chomsky hierarchy
"Benjamin C. Pierce" <[email protected]>
| Newsgroups | gmane.comp.science.types |
|---|---|
| Message-ID | <[email protected]> |
[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
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