多类型递归函数

作者：董韫美

来源：中国科学:数学 , 2015, 45(09): 1549-1562.

• 多类型递归函数(MTRF)
• 多类型原始递归函数(MTPRF)
• 通用求值函数

本文旨在建立多类型递归函数(MTRF),目的是,为在计算机上实现的函数式语言提供理论原型.MTRF函数是可计算函数,其定义域和值域的数据类型包括:自然数、逻辑值、有穷字母表上的字、上下文无关语言(CFL)句子、CFL句子的分析树.本文指出MTRF函数与自然数递归函数是等价的,构造了可在计算机上实现的MTRF函数eval,可用来对任意MTRF函数求值.

• 单位
  计算机科学国家重点实验室; 中国科学院软件研究所