The Expressive Power of Programming Languages

点击翻译按钮获取中文摘要

The literature on programming languages contains an abundance of informal claims on the relative expressive power of programming languages and on the expressibility or non-expressibility of programming constructs with respect to programming languages. Despite tremendous progress in various subdisciplines, programming language theory has not developed a formal framework for specifying and verifying such statements. Consequently, it is also impossible to draw any solid conclusions from such claims or to use them for an objective comparison of programming languages. An investigation of the expressiveness of programming languages has recently been initiated. Based on a first formalization of expressibility, universal programming languages in a restricted setting can now formally be distinguished and some of the informal claims in the literature can be confirmed. More examples within the current framework will be explored in order to broaden our perspective. From these examples, more meta-properties about the formal framework will be deduced.