The Functional Machine Calculus

The Functional Machine Calculus (FMC) was recently introduced by Heijltjes [1] as a generalization of the lambda-calculus to include higher-order global state, probabilistic and non-deterministic choice, and input and output, while retaining confluence. The calculus can encode both the call-by-name and call-by-value semantics of these effects. This is enabled by two independent generalizations. The first decomposes the syntax of the lambda-calculus in a way that allows for sequencing of computations and the encoding of reduction strategies. The second parameterizes application and  abstract ion in terms of `locations’, which gives a unification of the operational semantics, syntax, and reduction of the given effects with those of the lambda-calculus. The FMC further comes equipped with a simple type system which restricts and captures the behaviour of effects and guarantees strong normalisation.  

This talk will introduce the FMC and give a summary of its categorical semantics [2]. In particular, an equational theory is introduced and shown to be validated by a notion of observational equivalence. The category of closed FMC-terms modulo this theory, with composition given by sequencing, then forms the free Cartesian closed category.  

[1] Willem Heijltjes. The Functional Machine Calculus. June 2022, MFPS 2022
[2] Chris Barrett, Willem Heijltjes, Guy McCusker. The Functional Machine Calculus II: Semantics, Feb 2023, CSL 2023