We propose an implementation model for the evaluation of the weak λ-calculus, which is invariant for both time and space complexity, in both call-by-name and call-by-value strategies. In other words, this model provides an implementation of any weak call-by-name or weak call-by-value λ-calculus reduction sequence, whose time complexity is polynomial in the number of simulated β-steps, and whose space complexity is linear in the size of the largest intermediate term. This solves in an elegant way the well-known tension between time-invariance and space-invariance in the implementation of the λ-calculus.

@article{paperbot3638,
  title = {Inlining as a Space Optimization: A Simple Time- and Space-Invariant Implementation of the Weak Lambda-Calculus},
  author = {Thibaut Balabonski},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {ICFP},
  year = {2026},
  doi = {10.1145/3828705}
}