Ｃｏｍｂｉｎａｔｏｒ演算族的π演算语义

张　红　刘　磊

摘要：以SKI演算作为Combinator演算族的代表，通过形式化的手段给出了SKI演算的π演算语义；通过一个实例验证了所论方法的正确性．所给出的转换方法证明了π演算的表达能力：π演算为图灵完备的．由于高阶函数式语言与Combinator演算族之间存在着自然的转换，所给的转换思想不仅为在π演算的理论框架下研究Combinator演算族提供了基础，也为探讨高阶函数式语言的表示和实现问题提供了新途径．

关键词：π演算；Combinator演算族；SKI演算；语义

中图分类号：TP311

文献标识码：A

文章编号：1671-5489(2006)03-0391-06