依赖项重写系统及其在程序设计语言中的应用

摘要

项重写系统是一种简洁通用的计算模型,在许多领域中有着重要的应用.但是,在一些应用中,它不能很好地解决问题,为此,文中提出了一种新的项重写计算模型--依赖项重写系统,并给出了它在程序设计语言中的应用.直观上说,依赖项重写系统是重写规则之间存在着关于函数符号的依赖关系的项重写系统.这一模型具有较好的性质(例如,合流性、终止性等)和很强的表达能力.应用它,能够解决某些计算不终止问题,并有利于并行性的开发.