Date Added: Jul 2009
This paper examines the role of semantic theory in determining the ontology of programming languages. It also explores how different semantic perspectives result in different ontologies. In particular, it compares the ontological implications of set-theoretic versus type-theoretic semantics. Programming Languages (PLs) combine two, not always distinct, facilities: data structures (e.g., numbers, lists, trees, finite sets, objects) and control structures (e.g., assignment, iteration, procedure calls, recursion) that operate on these data structures. Such structures (Naur 1981; McCarthy 1981; Landin 1964) are immensely varied in their style of presentation and conceptual content. Various examples in the paper express very complex ideas and construct extremely complicated and intricate algorithms. Indeed, PLs may be usefully thought of as theories of problem solving in the sense that each language proffers a means of solving problems with given methods of representation and problem solving strategies enshrined in their techniques of program construction. In DS every data item and control feature is taken to denote a mathematical object of some kind. At a deeper level, all the central notions of the underlying mathematics are sets. For example, the functions employed in the semantics are sets of ordered pairs. This is such a common characterization of the notion of function that, as an assumption, it is rarely made explicit and it even seems somewhat pedantic to spell it out. However, it will play a crucial role in the evaluation of DS as providing an acceptable ontology for PLs.