Reproduce “HITrees: Higher-Order Interaction Trees” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Amir Mohammad Fadaei Ayyam, Michael Sammler

Higher-Order Interaction Trees (HITrees) introduce a framework for defining compositional denotational semantics that supports higher-order effects within a standard, non-guarded type theory like Lean. This approach allows for modular formalization of complex language features such as concurrency and continuations, alongside providing both executable and reasoning-oriented interpretations.

Key insights

  • Higher-order effects can be modeled compositionally within a non-guarded type theory by carefully managing recursive occurrences through input/output type separation and dynamic validation.
  • Defunctionalization, which represents higher-order computations with abstract identifiers and separate invocation, provides an effective means to handle negative occurrences of recursive types in inductive definitions.
  • Sophisticated meta-programming greatly streamlines the practical definition and composition of both simple and recursive effects, reducing manual boilerplate in proof assistants.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.