paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The essence of ornaments

Ornaments 的本质
JFP vol.272017匹配度 2/10 · 该论文属于纯类型论/语言设计范畴,研究 ornaments 与索引数据类型的去语法化抽象模型(多类签名、GADTs/refinement types),与用户关注的 PL↔AI 交叉、静态分析与 LLM/Agent 结合、浮点或贝叶斯程序分析均无直接关联;仅在“形式化建模”这一宽泛的方法论偏好上略有共鸣。引用 15 inbox
PIERRE-EVARISTE DAGAND
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:用多类签名抽象索引数据类型,为 ornaments 建立去语法化模型,使其可推广到 GADTs/refinement types。

函数式程序员常用精细索引的数据类型来刻画程序不变式,并由此发展出 ornaments 理论;但 ornaments 原生于依赖类型,对非依赖类型的程序员而言较为艰深。本文旨在从第一性原理介绍 ornaments,并剥离其语法细节。作者用 many-sorted signatures(多类签名)为索引数据类型建立足够抽象的模型,将索引数据类型形式化为数据结构与数据逻辑的组合。在此抽象之上重新表述 ornaments 的定义,从而给出 ornaments 的模型。该模型兼具操作性与抽象性,使 ornaments 有望超越类型论圈子,适用于支持 GADTs 或 refinement types 的语言。

问题
如何为依赖类型中的 ornaments 及索引数据类型提供去语法化的抽象理解,使其能被更广的函数式程序员掌握并推广到其他语言特性。
方法
以多类签名建模索引数据类型,将其视为数据结构与数据逻辑的组合,并在此抽象上重述 ornaments 的定义,给出其模型。
评估
论文未报告实现或实验评估,主要通过抽象模型论证 ornaments 的适用性,并指出其可推广到 GADTs 或 refinement types。
原文摘要(Abstract)

Abstract Functional programmers from all horizons strive to use, and sometimes abuse, their favorite type system in order to capture the invariants of their programs. A widely used tool in that trade consists in defining finely indexed datatypes. Operationally, these types classify the programmer's data, following the ML tradition. Logically, these types enforce the program invariants in a novel manner. This new programming pattern, by which one programs over inductive definitions to account for some invariants, lead to the development of a theory of ornaments (McBride, 2011 Ornamental Algebras, Algebraic Ornaments . Unpublished). However, ornaments originate as a dependently-typed object and may thus appear rather daunting to a functional programmer of the non-dependent kind. This article aims at presenting ornaments from first-principles and, in particular, to declutter their presentation from syntactic considerations. To do so, we shall give a sufficiently abstract model of indexed datatypes by means of many-sorted signatures. In this process, we formalize our intuition that an indexed datatype is the combination of a data- structure and a data- logic . Over this abstraction of datatypes, we shall recast the definition of ornaments, effectively giving a model of ornaments. Benefiting both from the operational and abstract nature of many-sorted signatures, ornaments should appear applicable and, one hopes, of interest beyond the type-theoretic circles, case in point being languages with generalized abstract datatypes or refinement types.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@article{Dagand17,
  title = {The essence of ornaments},
  author = {PIERRE-EVARISTE DAGAND},
  journal = {Journal of Functional Programming},
  volume = {27},
  year = {2017},
  doi = {10.1017/s0956796816000356}
}