多类型递归函数

Multi-type recursive functions

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

In this paper, we intend to establish the theory of multi-type recursive functions （MTRF）. The aim is to present a theoretical prototype of functional language to be implemented on computer. MTRF functions are computable, whose domain and range include： natural numbers, Boolean values, words on finite alphabet, context free languages, and parse trees of context free grammars. It is indicated that the natural number recursive functions and the MTRF functions are equivalent. Finally, an MTRF function eval is constructed, which is an evaluator to compute arbitrary MTRF functions, and can be implemented on the computer.