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

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

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.