User loginNavigation 
Tagless Staged Interpreters for Simpler Typed LanguagesFinally Tagless, Partially Evaluated, Tagless Staged Interpreters for Simpler Typed Languages.
Oleg explains: It seems like a common wisdom that an embedding of a typed object language (e.g., DSL) to a typed metalanguage so that all and only typed object terms can be represented requires dependent types, GADTs or other such advanced type systems. In fact, this problem of writing (tagless) typepreserving typed interpreters has been the motivation for most of the papers on GADTs. We show that regardless of merits and conveniences of GADTs, typepreserving typed interpretation can be achieved with no GADTs whatsoever, using very simple type systems of ML or Haskell98. We also show the same approach lets us perform statically typepreserving partial evaluation and callbyvalue or callbyname CPS tansformations. The latter transformations, too, are often claimed impossible in Haskell98 or ML  requiring instead quite advanced type systems or language features.
The complete (Meta)OCaml and Haskell code accompanying the paper is One of features of our approach is writing the DSL code in a form that can be interpreted in multiple ways. Recently we have become aware the very same approach underlies `abstract categorial grammars' (ACG) in linguistics. Chungchieh Shan has written an extensive article on this correspondence. That post itself can be interpreted in several ways: the file can be read as plain text, or it can be loaded as it is in Haskell or OCaml interpreters. It should be noted that the linguistic terms `tectogrammatics' and `phenogrammatics' were coined by none else but Haskell Curry, in his famous 1961 paper 'Some Logical Aspects of Grammatical Structure'. The summary of the ESSLLI workshop describes further connections to linear lambdacalculus. The paper has been accepted for APLAS; the authors appreciate any comments indeed. By Ehud Lamm at 20070904 09:35  Implementation  MetaProgramming  Type Theory  other blogs  19799 reads

Browse archivesActive forum topics

Recent comments
31 min 19 sec ago
38 min 13 sec ago
1 hour 18 min ago
1 hour 28 min ago
1 hour 44 min ago
2 hours 6 min ago
4 hours 38 min ago
5 hours 11 min ago
5 hours 27 min ago
5 hours 45 min ago