Formalizing ϕ-Calculus: A Purely Object-Oriented Calculus of Decorated Objects
Nikolai Kudasov, Violetta Sim · 2022
Many calculi exist for modeling various features of object-oriented languages. Many of them are based on λ -calculus and focus either on statically typed class-based languages or dynamic prototype-based languages. We formalize the untyped calculus of decorated objects, informally presented by Bugayenko, which is defined in terms of objects and relies on decoration as a primary mechanism of object extension. It is not based on λ -calculus, yet with only four basic syntactic constructions is just as complete (in particular, it is Turing complete and possesses the Church-Rosser property). We also provide a sound translation to Wand’s λ -calculus with records and concatenation, and discuss the key differences of these calculi.