The Computer Science Colloquium

Steve Matthews
(University of Warwick, UK)

"Efficiency oriented programming languages and semantics"

    Following the example of Michel Schellekens, we consider how two familiar specialisms of theoretical computer science may find more common ground. Any given algorithm can be studied for properties such as its complexity, but, when coded up as a program, all that the typical programming language facilitates is retention of sufficient information to enable the computer to (automatically) execute each step in the correct order. For example, how could a coding of Bubble Sort be automatically distinguished from a coding of Quick Sort to determine which program is using the algorithm having the best average time complexity? Such questions are undoubtedly difficult to address, and will remain so as long as there remains an enormous gap between the complexity of algorithms and the denotational semantics of programming languages. The smaller the gap, the more we can contemplate programs continually analyzing themselves at run time for their own algorithmic behavior, and making improvements accordingly. In today's talk we will combine research from Mike Smyth on discrete spatial models, from Ulrich Hohle on many valued topology, with our own work on partial metric spaces to present a complementary approach to that of Schellekens to establishing connections between the discrete mathematics of present day algorithms research (i.e. graph theory) and the continuous mathematics traditionally used in denotational semantics (i.e. topology and domain theory).

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.