Elpi is a higher-order logic programming language derived from \(\lambda \) Prolog and widely used to extend the Rocq interactive theorem prover. Typical users are familiar with types and functional programming but often lack experience with backtracking. We introduce a language of signatures to declare that a predicate is operationally deterministic, meaning that calling the predicate does not leave any choice points. The signature language handles higher-order programs and dynamic programs. We present a static analyzer that verifies these signatures and report its application to the majority of public Elpi code in the Rocq ecosystem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Determinacy Checking for Elpi: an Higher-Order Logic Programming Language with Cut

  • Davide Fissore,
  • Enrico Tassi

摘要

Elpi is a higher-order logic programming language derived from \(\lambda \) Prolog and widely used to extend the Rocq interactive theorem prover. Typical users are familiar with types and functional programming but often lack experience with backtracking. We introduce a language of signatures to declare that a predicate is operationally deterministic, meaning that calling the predicate does not leave any choice points. The signature language handles higher-order programs and dynamic programs. We present a static analyzer that verifies these signatures and report its application to the majority of public Elpi code in the Rocq ecosystem.