PROPERTIES OF A FIRST-ORDER FUNCTIONAL LANGUAGE WITH SHARING

被引：16

作者：

ARIOLA, ZM ^{[1
]}

ARVIND ^{[1
]}

机构：

[1] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

THEORETICAL COMPUTER SCIENCE | 1995年 / 146卷 / 1-2期

关键词：

D O I：

10.1016/0304-3975(94)00185-L

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A calculus and a model for a first-order functional language with sharing is presented. In most implementations of functional languages, argument subexpressions in a function application are shared to avoid their repeated evaluation. Recursive functions are typically implemented using graphs with cycles. Compilers for these languages sometimes employ non-left-linear and left-cyclic rules for optimizations. A graph rewriting system (GRS) to address these concerns is developed. It is shown that a GRS without interfering rules is confluent. Along the lines of Levy's term model for the lambda-calculus, a semantics of such a GRS is also presented. An application of the term model to compiler optimizations is discussed.

引用

页码：69 / 108

页数：40