Collection Types in Programming Languages and Databases

结构化递归为编程语言和数据库中常见的集合类型的操作形式提供了统一的范例。作为这一权利要求的证据，为利用列表、包和集合上的结构递归的程序的语义开发了一般特征。在结构递归和一系列操作复杂对象的现有语言之间发现了密切的联系。该项目对集合类型的一般原理进行了研究，包括异质集合、存在分歧的集合的语义、集合语言的并行语义、作为发现和验证优化的基础的集合语言的等式理论以及与集合类型的扩展模式匹配。它还涉及到一种语言的设计和原型实现，该语言展示了大多数这些想法。

Structural recursion provides a unifying paradigm for the forms of manipulation of collection types that are common in programming languages and databases. As evidence for this claim a general characterization is developed for the semantics of programs that exploit structural recursion on lists, bags, and sets. An intimate connection is identified between structural recursion and a range of existing languages that manipulate complex objects. This project conducts an investigation into the general principles of collection types, including heterogeneous collections, the semantics of collections in the presence of divergence, the parallel semantics of collection languages, the equational theories of collection languages as a basis for discovering and validating optimizations, and extended pattern-matching with collection types. It also involves the design and prototype implementation of a language demonstrating most of these ideas.