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＃，球拍或Scala）以及没有的语言。该项目下开发的所有图书馆和工具将作为开源提供。