"Dialgebraic techniques for object-based programming"

Abstract

Algebraic techniques have been used in functional programming for a long time. For example, the Bird-Meertens formalism provides a framework in which we can derive generic programs using algebraic laws. Similarly, coalgebraic techniques have been used for class-based languages, e.g., for proving implementations correct with respect to a coalgebraic specification.

In this talk I will discuss the use of dialgebras, which arise from mixed-variance functors, in object-based programming. Initial dialgebras are used as a model of object types. Compared to coalgebras, this model of objects treats methods as first-class and therefore makes it possible to define new classes by recursion on the methods of previously defined classes. I will show that direcursion, a universal construction on a suitable category of dialgebras, provides a computation principle that can be used when programming with structures such as linked lists, and for reasoning with design patterns arising in object-based languages. I will contrast these examples to algebraic and coalgebraic techniques and show some examples in Haskell.