Paolo Pistone

What functions do functional programs compute?


One of the fundamental goals of program semantics is to model programming languages by means of purely mathematical structures. Indeed, we all have the intuition that algorithms implement some kind of functions, but what functions then? As Turing and Van Neumann had already understood in the 30s, a fundamental feature of algorithms is that they can themselves be fed as input to other algorithms. In mathematical terms, this means that, if we model data by some class of structures C and programs by maps between such structures, these maps must form themselves some structure in C. In other words, the class C and its maps must form a so-called (cartesian) closed category. In this talk we discuss some results and perspectives on the mathematical modeling of functional algorithms, focusing in particular on how to obtain cartesian closed categories using standard structures such as topological, metric or measure spaces.