Lune

OOPSLA2024Top-tier venue

Intensional Functions

Zachary Palmer, Nathaniel Wesley Filardo, Ke Wu

Abstract

Functions in functional languages have a single elimination form — application — and cannot be compared, hashed, or subjected to other non-application operations. These operations can be approximated via defunctionalization: functions are replaced with first-order data and calls are replaced with invocations of a dispatch function. Operations such as comparison may then be implemented for these first-order data to approximate e.g. deduplication of continuations in algorithms such as unbounded searches. Unfortunately, this encoding is tedious, imposes a maintenance burden, and obfuscates the affected code. We introduce an alternative in intensional functions , a language feature which supports the definition of non-application operations in terms of a function’s definition site and closure-captured values. First-order data operations may be defined on intensional functions without burdensome code transformation. We give an operational semantics and type system and prove their formal properties. We further define intensional monads , whose Kleisli arrows are intensional functions, enabling monadic values to be similarly subjected to additional operations.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. Mœbius: metaprogramming using contextual types: the stage where system f can pattern match on itselfJunyoung Jang, Samuel Gélineau, Stefan Monnier, Brigitte PientkaPOPL 2022 · 28 citations

Related papers

  1. Defunctionalization with Dependent TypesYulong Huang, Jeremy YallopPLDI 2023 · 4 citations
  2. A Pure Demand Operational Semantics with Applications to Program AnalysisScott F. Smith, Robert ZhangOOPSLA 2024 · 1 citation
  3. Better Defunctionalization through Lambda Set SpecializationWilliam Brandon, Benjamin Driscoll, Frank Dai, Wilson Berkow et al.PLDI 2023 · 7 citations
  4. Handling Higher-Order Effectful Operations with Judgemental Monadic LawsZhixuan Yang, Nicolas WuPOPL 2026
  5. Hyperfunctions: Communicating ContinuationsDonnacha Oisín Kidney, Nicolas WuPOPL 2026
Dusk over the sea between two cliffs drawn in fine vertical lines