文章基本信息

标题：Syntactic Theories in Practice
本地全文：下载
作者：Olivier Danvy ; Lasse R. Nielsen
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2001
卷号：8
期号：31
出版社：Aarhus University
摘要：The evaluation function of a syntactic theory is canonically defined as the transitive closure of (1) decomposing a program into an evaluation context and a redex, (2) contracting this redex, and (3) plugging the result in the context. Directly implementing this evaluation function therefore yields an interpreter with a quadratic time factor over its input. We present sufficient conditions over a syntactic theory to circumvent this quadratic factor, and illustrate the method with two programming-language interpreters and a transformation into continuation-passing style (CPS). In particular, we mechanically change the time complexity of this CPS transformation from quadratic to linear.