Magmadic metalanguages (project proposal)

Magmadic metalanguages (project proposal)

The following is a proposal for an undergraduate student.

Moggi’s simple programming language (sometimes called “monadic metalanguage”), or Haskell’s do-notation both assume associativity of the underlying monad. In particular, the following two pieces of code are equal.

do a <- f x          do a <- f
   b <- g a             c <- do b <- g a
   c <- h b     ===             c <- h b
   return c                     return c
                       return c

However, some notions of computation do not satisfy associativity. Márk Széles, Elena Di Lavore and I found recently that normalized stochastic kernels are one notable example, accounting for some of the weirdness in categorical probability with updating.

It seems that many other interesting simple programming languages can be obtained by only assuming limited forms of associativity.

Research proposal. To develop the theory of non-associative “magmadic” metalanguages. To provide categorical semantics to these languages. To extend these languages to programming structure (e.g., via traced coproducts). To find examples and programming paradigms that benefit from this perspective.

References.

• Notions of Computation and Monads (Moggi)
• Comonadic Notions of Computation (Uustalu, Vene)
• A Simple Formal Language for Probabilistic Decision Problems (Di Lavore, Jacobs, Román, 2024)
• The Magmoid of Normalized Stochastic Kernels (Di Lavore, Román, Széles, 2026)