Towards Algebra-Oriented Programming

April 2, 2013
Bruno Oliveira | National University of Singapore

Programs can be modularly decomposed in several dimensions. However, it has long been noted that existing programming languages typically suffer from “the tyranny of the dominant decomposition”, only supporting decomposition of programs well in one dimension. Bad support for other dimensions leads to crosscutting concerns: code that logically represents some separate, modular functionality of the program, but which is not easily modularized. The main problem lies in existing programming language structuring abstractions, such as algebraic/inductive datatypes in functional languages or object interfaces in object-oriented languages, which dictate the particular flavor of modularity supported by the language.

This talk suggests a form of algebraic signatures, which we generally refer to as algebras, as an alternative programming language structuring abstraction. Algebras do not dictate a particular modularity dimension on the programmer. Instead they support various composition operators which allow them to cater for several dimensions of modularity at once. Algebras have desirable properties of a programming abstraction: they support modular type-checking, separate-compilation and modular reasoning/proofs. I will show how algebras can already be encoded in existing programming languages and theorem provers, and how they can help dealing with several practical problems: from modularizing DSL components, to modularizing inductive proofs and meta-theory of programming languages. I’ll finish the talk by discussing some of the remaining challenges on creating truly algebra-oriented programming languages.

Speaker Details

Dr. Bruno Oliveira received his M. Sc. In Computer Science from the Universidade do Minho (Portugal) in 2002, and his PhD in Computer Science from the University of Oxford in 2007. In 2009 he joined Seoul National University as a Research Professor and he is currently a Senior Research Fellow in the National University of Singapore. His work covers various aspects of Modularity in Functional Programming and Object-Oriented Programming languages. He has been a program committee member in several conferences and workshops in these areas, and he has won the ECOOP 2012 best paper award.