CCF-SHF Small: Beyond Algebraic Data Types: Combinatorial Species and Mathematically-Structured Programming

CCF-SHF Small：超越代数数据类型：组合种类和数学结构规划

• 批准号: 1218002
• 负责人: Stephanie Weirich
• 金额: $ 32.58万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218002&HistoricalAwards=false
• 关键词: CCF; SHF; Small; Beyond; Algebraic

At the heart of any computer program is the data that the program is designed to manipulate. Data, in turn, is only useful when organized into some sort of structure ---be it as simple as a list or as complex as a network or hierarchical tree. The mathematical theory of "combinatorial species" studies many variations of such structure, but it has not often been applied in a computer science context. The goal of this project is a new understanding of data structure through the abstractions of combinatorial species. This understanding will lead to new classes of data structures as well as practical tools for working with existing ones. Ultimately, this work will lead to more expressive programming languages, allowing computer programs to be written at a higher level and with fewer errors.More specifically, the project seeks to extend the existing computational theory of algebraic data types with constructs derived from the theory of combinatorial species. In particular, the project will explore the specification of data types with nontrivial symmetries and sharing, such as cycles, bags, and simple graphs. The project will develop libraries and language extensions to support the use of species data types in the Haskell programming language. As a significant test case, it will explore the application of species data types to property-based testing. Although the work is to be carried out in the context of the Haskell programming language, the results will be applicable to any language, including those with direct support for algebraic datatypes (such as OCaml, F#, Racket or Scala), and those without. All libraries and tools developed under this project will be made available as open source.

任何计算机程序的核心都是程序设计用来操作的数据。 反过来，数据只有在组织成某种结构时才有用-无论是简单的列表还是复杂的网络或层次树。 “组合物种”的数学理论研究了这种结构的许多变化，但它并不经常应用于计算机科学背景。 该项目的目标是通过组合物种的抽象来对数据结构进行新的理解。这种理解将导致新的数据结构类别以及与现有数据结构一起工作的实用工具。 最终，这项工作将导致更有表现力的编程语言，使计算机程序可以在更高的水平上编写，更少的错误。更具体地说，该项目旨在扩展现有的计算理论的代数数据类型与结构来自组合物种的理论。 特别是，该项目将探索具有非平凡对称和共享的数据类型的规范，例如循环，包和简单图。该项目将开发库和语言扩展，以支持在Haskell编程语言中使用物种数据类型。作为一个重要的测试案例，它将探索物种数据类型在基于属性的测试中的应用。 虽然这项工作是在Haskell编程语言的背景下进行的，但其结果将适用于任何语言，包括那些直接支持代数数据库的语言（如OCaml，F#，Racket或Scala），以及那些不支持代数数据库的语言。在该项目下开发的所有库和工具都将作为开源提供。