EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Multicategorical Semantics for Untyped Effects

Ariel Grunfeld, Liron Cohen

Electronic Notes in Theoretical Informatics and Computer Science · 04.11.2026 · Volume 6: Proceedings of MFPS...

DOI: 10.46298/entics.19631 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Electronic Notes in Theoretical Informatics and Computer Science, online erschienen am 04.11.2026. Verfasst von Ariel Grunfeld und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Completeness proofs in categorical semantics usually proceed by building a syntactic category whose composition is given by substitution. For untyped effectful Call-by-Value languages, this runs into a basic obstacle: there is no canonical notion of simultaneous substitution of computations, since evaluation order is semantically meaningful. We address this by taking single computation substitutions, that is, binding steps, as primitive, and representing computation substitution by finite sequential lists composed by concatenation. We formalize this idea in a one-object Freyd-multicategorical setting. We introduce Freyd operads, separating a cartesian operad of values from a symmetric Ren-cartesian preoperad of computations, connected by a Freyd functor, and from any Freyd operad we construct a corresponding Freyd PROP of substitutions. We prove that this construction is representable and, in the strict one-object setting, left adjoint to restriction to codomain 1. Using the induced term model, we interpret untyped computational lambda-calculus with procedures and higher-order functions in weakly closed Freyd operads, and prove soundness, initiality, and completeness. This yields a categorical semantics tailored to untyped effectful computation and broad enough to encompass realizability-oriented models such as monadic combinatory algebras.

Zitieren

APA

Grunfeld, A., & Cohen, L. (2026). Multicategorical Semantics for Untyped Effects. Electronic Notes in Theoretical Informatics and Computer Science, Volume 6: Proceedings of MFPS.... https://doi.org/10.46298/entics.19631

Vancouver

Grunfeld A, Cohen L. Multicategorical Semantics for Untyped Effects. Electronic Notes in Theoretical Informatics and Computer Science. 2026;Volume 6: Proceedings of MFPS.... doi:10.46298/entics.19631

BibTeX
@article{Grunfeld2026,
  author = {Grunfeld, Ariel and Cohen, Liron},
  title = {Multicategorical Semantics for Untyped Effects},
  journal = {Electronic Notes in Theoretical Informatics and Computer Science},
  year = {2026},
  volume = {Volume 6: Proceedings of MFPS...},
  doi = {10.46298/entics.19631}
}
Kostenlos starten →