Algebra of Normal Function Tables

Dr. Martin von Mohrenschildt

Software Engineering Research Group
CRL, McMaster University,
Hamilton, Ontario, Canada L8S 4K1


In contrast to classical algebra and analysis the functions encountered in computer science are usually piecewise continuous functions or functions whose evaluation rules change dramatically depending on a subset of the input values. Because of the pervasiveness of the if-then-else construction in programming, we have to extend classical mathematical methods to handle this kind of object. We approach this class of functions using tabular expressions. In this paper we define a function algebra, over a many sorted algebra, which is closed under composition. Then, this function algebra is extended to tables. This enables us to define the composition of tables. We show that this algebra of tables is closed under composition. We give two algorithms to compute the composition of tables.