Iteration Theories and Data Type Specifications

在与Elgot和Wright的合作中，PI使用了迭代理论的概念来公理化流程图算法的控制结构。迭代理论似乎也为循环抽象数据类型的功能描述提供了一种公理化，正如最近由Smyth、Lehmann、Plotkin、Arbib &； mane等人所描述的那样。PI现在正在研究迭代理论对抽象数据类型描述的适用性。正在确定是否可以使用相同的等式公理来描述程序的控制结构和程序所操作的数据类型、操作和域的结构。解决数据类型描述等价问题的算法也在发展中：给定两种描述（作为某些内函子的不动点），它们描述的是“同一件事”吗？这个问题类似于以下问题：给定两个流程图方案，它们是否具有保存行为？验证迭代理论和数据类型之间的联系正如PI所期望的那样，将表明这两个问题是相同的。拟议的研究预计将导致对数据类型的更好理解。PI在相关研究成果方面有着良好的记录。

In joint work with Elgot and Wright, the PI used the notion of iteration theories in axiomatizing the control structure of flowchart algorithms. Iteration theories also appear to provide an axiomatization for the functorial description of circular abstract data types as described most recently by Smyth, Lehmann, Plotkin, Arbib & Manes, and others. The PI is now investigating the suitability of iteration theories for the description of abstract data types. It is being determined whether the same equational axioms can be used to describe both the control structure of programs and the structure of the data types, operations and domains on which the programs operate. Also in progress is the development of algorithms for the solution of problems concerning the equivalence of data type descriptions: Given two descriptions (as fixed points of certain endofunctors), do they describe the "same thing"? The question is analogous to the question: Given two flowchart schemes, do they have the save behavior? Verification that the connection between iteration theories and data types is as the PI expects will show that these two questions are identical. The proposed research is expected to lead to an improved understanding of data types. The PI has a fine record of related research accomplishments.