使递归算法泛型化

Making Recursive Algorithms Generic

对于泛型程序设计来说,类型理论中的参数化多态是其理论框架,因为参数化多态引入了类型变量,使得类型参数化,从而完全支持类型上的抽象。然而对于现行的泛型算法,无论是C++标准模版库中的泛型算法还是基于函数式程序设计语言的算法,函数功能的定义比较具体化、单一化,因而缺乏可扩展性和高度的复用性。将对递归算法进行抽象,构造原始递归构造子,使得一般的泛型算法都可以通过该算子来构造,从而加强泛型算法的可复用型与可扩展性。除此之外,分析了递归算法构造子与泛型程序设计中的iterator概念和用于描叙泛型概念的形式化语言Tecton中所提倡的reuse概念的一致性。也给出算法复杂度的定量分析,并用函数式语言ML来实现。

Parametric polymorphism is crucial to generic programming in that it adopts parameterized types and therefore fully supports the abstraction on types. However, current generic algorithms, both developed in C＋ ＋ standard template library and in functional programming, have sole and concrete functional definitions, which lack scalability and reusability. Presents the abstraction on algorithms and primitive recursion eonstructor, aiming to reinforce the high reusability and extensibility of generic algorithms. In addition, analyzes the consistency of this algorithmic abstraction with generic iterator concepts and Tecton concepts, presents quantitative time- complexity analysis, and gives the practical implementation in ML.