EXPRESSIVE POWER OF TYPED AND TYPE-FREE PROGRAMMING-LANGUAGES

作     者：FEHR, E 

作者机构：Lehrstuhl für Informatik II RWTH Auchen D-5100 Aachen Fed. Rep. Germany 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：1984年第33卷第2-3期

页      面：195-238页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：COMPUTER PROGRAMMING LANGUAGES 

摘      要：The classes of typed and type-free lambda-schemes are studied with respect to their use as control structures of programming languages. The semantics of both classes are analyzed in the same semantical domains. In particular, it is shown that typed λ-schemes are translatable into equivalent type-free λ-schemes but not vice versa. Furthermore, we prove that the class of type-free λ-schemes is universal in the sense that in the initial models all recursively enumerable Σ-trees (Σ is the set of operation symbols) are definable.