Denotational semantics 55275 209096399 2008-04-29T21:58:35Z 85.181.41.30 corrected misspelled (intern) link {{Wikibookspar|Haskell|Denotational semantics}} In [[computer science]], '''denotational semantics''' is an approach to formalizing the meanings of [[programming language]]s by constructing mathematical objects (called ''denotations'') which describe the meanings of expressions from the languages. Other approaches to providing a [[formal semantics of programming languages]] include [[axiomatic semantics]] and [[operational semantics]]. Denotational semantics originated in the work of [[Christopher Strachey]] and [[Dana Scott]] in the 1960s. As originally developed by Strachey and Scott, denotational semantics provided the denotation (meaning) of a computer program as a [[function (mathematics)|function]] that mapped input into output.<ref>Dana Scott and Christopher Strachey. ''Toward a mathematical semantics for computer languages'' Oxford Programming Research Group Technical Monograph. PRG-6. 1971.</ref> To give denotations to [[Recursion|recursively defined]] programs, Scott proposed working with [[continuous functions]] between [[domain theory|domains]], specifically [[complete partial order]]s. Work continues in the present day in investigating appropriate denotational semantics for aspects of programming languages such as sequentiality, [[Denotational_semantics#Denotational_semantics_of_concurrency|concurrency]], non-determinism and local state. Broadly speaking, denotational semantics is concerned with finding mathematical objects that represent what programs do. Collections of such objects are called domains. For example, programs (or program phrases) might be represented by partial functions, or by [[Actor model|Actor]] [[Denotational_semantics_of_the_Actor_model|event diagram scenarios]], or by games between the environment and the system: these are all general examples of domains. An important tenet of denotational semantics is that ''semantics should be [[Principle of compositionality|compositional]]'': the denotation of a program phrase should be built out of the denotations of its subphrases. A simple example: the meaning of "3 + 4" is determined by the meanings of "3", "4", and "+". Denotational semantics was first developed as a framework for functional and sequential programs modeled as mathematical functions mapping input to output. The first section of this article describes denotational semantics developed within this framework. Later sections deal with issues of polymorphism, concurrency, etc. ==Semantics of recursive programs== In this section we review the semantics of [[functional programming|functional]] recursive programs which were the initial subject matter of denotational semantics. The problem is as follows. We need to give a semantics to programs such as the definition of the [[factorial]] function as ::<tt>function factorial(n:Nat):Nat ≡ if (n==0)then 1 else n*factorial(n-1)</tt>. The meaning of this factorial program should be a function on the natural numbers, but, because of its recursive definition, it is not clear how to understand this in a compositional way. In the semantics of recursion, a domain is typically a [[partial order]], which can be understood as an order of definedness. For instance, the set of partial functions on the natural numbers can be given an order as follows: ::given partial functions f and g, let "f≤g" mean that "f agrees with g on all values for which f is defined". The core idea behind using partial orders is that each recursive step broadens the domain on which a function is defined. Thus, for example, if ''f'' was the factorial function, recursively defined for only ''n'' iterations, then ''g'' could be the factorial function, recursively defined for ''n''+1 (or more) iterations. It is usual to assume some properties of the domain, such as the existence of limits of chains (see [[complete partial order|cpo]]) and a bottom element. The partial order of partial functions has a bottom element, the totally undefined function. It also has least upper bounds of chains. Various additional properties are often reasonable and helpful: the article on [[Domain theory|domain theory]] has more details. One particularly important property is that of [[Scott continuity]]: one is interested in the [[Continuous function (topology)|continuous]] functions between domains (in the [[Scott topology]]). These are functions that preserve the order structure, and that preserve least upper bounds. In this setting, types are denoted by domains, and the elements of the domains roughly capturing the elements of the types. A denotational semantics is given to a program phrase with free variables in terms of a continuous function from the denotation of its environment type to the denotation of its type. For example, the phrase <tt>n*g(n-1)</tt> has type <tt>Nat</tt>, and it has two free variables: <tt>n</tt>, of type <tt>Nat</tt>, and <tt>g</tt> of type <tt>Nat -> Nat</tt>. Thus its denotation will be a continuous function ::<math>\mathbb N \times (\mathbb N \rightharpoonup \mathbb N) \to \mathbb N</math>. Under this order on the partial functions, the denotation of the factorial program can be given as follows. First, we must develop denotations (as Scott-continuous functions) for the basic constructions such as <tt>if-then-else</tt>, <tt>==</tt>, and multiplication. One must also develop a denotational semantics for function abstraction and [[apply|application]]. The program phrase ::<tt>λ n:N. if (n==0)then 1 else n*g(n-1)</tt> can then be given a denotation as a continuous function between the domains of partial functions ::<math>F:(\mathbb N\rightharpoonup\mathbb N) \to (\mathbb N\rightharpoonup\mathbb N)</math>. The denotation of the factorial program is defined to be the [[least fixed point]] of this function ''F''. It is thus an element of the domain <math>(\mathbb N\rightharpoonup\mathbb N)</math>. The reason that such a fixed point exists is because ''F'' is a continuous function. A version of [[Tarski's fixed point theorem]] says that continuous functions on domains have least fixed points. One way of proving the fixed point theorem gives an intuition as to why it is appropriate to give a semantics for recursion in this way. Every continuous function ''F:D→D'' on a domain ''D'' with [[bottom element]] ⊥ has a fixed point given by ::⊔<sub>i∈N</sub>''F<sup>i</sup>''(⊥). Here, the notation ''F<sup>i</sup>'' indicates [[iterated function|''i''-many applications]] of ''F''. The symbol "⊔" means "least upper bound". It is instructive to think of the components of the chain as "iterates". In the case of the factorial program above, we had a function ''F'' on the domain of partial functions. * ''F''<sup>0</sup>(⊥) is the totally undefined partial function ''N→N''; * ''F''<sup>1</sup>(⊥) is the function that is defined at 0, to be 1, and undefined elsewhere; * ''F''<sup>5</sup>(⊥) is the factorial function defined up to 4: ''F''<sup>5</sup>(⊥)(4) = 24. It is undefined for arguments greater than 4. Thus the least upper bound of this chain, then, is the full factorial function (which happens to be a total function). ==Development of denotational semantics== Denotational semantics has developed by investigating more elaborate constructions of programming languages and different models of computation. ===Denotational semantics of state=== State (such as a heap) and [[imperative programming|imperative features]] can be straightforwardly modeled in the denotational semantics described above. All the [[Denotational semantics#Textbooks|textbooks]] below have the details. The key idea is to consider a command as a partial function on some domain of states. The denotation of "<tt>x:=3</tt>" is then the function that takes a state to the state with <tt>3</tt> assigned to <tt>x</tt>. The sequencing operator "<tt>;</tt>" is denoted by composition of functions. Fixed-point constructions are then used to give a semantics to looping constructs, such as "<tt>while</tt>". Things become more difficult in modelling programs with local variables. One approach is to no longer work with domains, but instead to interpret types as [[functors]] from some [[Category_%28mathematics%29|category]] of worlds to a [[Category_%28mathematics%29|category]] of domains. Programs are then denoted by [[natural transformation|natural]] continuous functions between these functors.<ref>Peter W. O'Hearn, John Power, Robert D. Tennent, Makoto Takeyama: Syntactic control of interference revisited. Electr. Notes Theor. Comput. Sci. 1. 1995.</ref><ref>Frank J. Oles: A Category-Theoretic Approach to the Semanics of Programming. PhD thesis, Syracuse University. 1982.</ref> ===Denotations of data types=== Many programming languages allow users to define [[recursive type|recursive data types]]. For example, the type of lists of numbers can be specified by ::<tt>datatype list = Cons of (Nat, list) | Empty.</tt> This section deals only with functional data structures that cannot change. Conventional programming languages would typically allow the elements of such a recursive list to be changed. For another example: the type of denotations of the untyped lambda-calculus is ::<tt>datatype D = (D &rarr; D)</tt> The problem of ''solving domain equations'' is concerned with finding domains that model these kinds of datatypes. One approach, roughly speaking, is to consider the collection of all domains as a domain itself, and then solve the recursive definition there. The [[Denotational semantics#Textbooks|textbooks]] below give more details. [[Polymorphism_(computer_science)|Polymorphic data types]] are data types that are defined with a parameter. For example, the type of α <tt>list</tt>s is defined by ::<tt>datatype α list = Cons of (α, list) | Empty.</tt> Lists of numbers, then, are of type <tt>Nat list</tt>, while lists of strings are of <tt>String list</tt>. Some researchers have developed domain theoretic models of polymorphism. Other researchers have also modeled parametric polymorphism within constructive set theories. Details are found in the [[Denotational semantics#Textbooks|textbooks]] listed below. A recent research area has involved denotational semantics for object and class based programming languages.<ref>Bernhard Reus, Thomas Streicher: Semantics and logic of object calculi. Theor. Comput. Sci. 316(1): 191-213 (2004)</ref> ===Denotational semantics for programs of restricted complexity=== Following the development of programming languages based on [[linear logic]], denotational semantics have been given to languages for linear usage (see e.g. [[Proof net|proof nets]], [[Coherent space|coherence spaces]]) and also polynomial time complexity<ref>P. Baillot. Stratified coherence spaces: a denotational semantics for Light Linear Logic ( ps.gz) Theoretical Computer Science , 318 (1-2), pp.29-55, 2004. </ref>. ===Denotational semantics of non-deterministic programs=== The concept of [[power domains]] has been developed to give a denotational semantics to [[nondeterministic algorithm|non-deterministic sequential programs]]. Writing ''P'' for a power domain constructor, the domain ''P''(''D'') is the domain of non-deterministic computations of type denoted by ''D''. There are difficulties with fairness and [[Unbounded nondeterminism|unboundedness]] in domain-theoretic models of non-determinism.<ref>Paul Blain Levy: Amb Breaks Well-Pointedness, Ground Amb Doesn't. Electr. Notes Theor. Comput. Sci. 173: 221-239 (2007)</ref> See [[Power_domains#Power_domains_for_nondeterminism|Power domains for nondeterminism]]. ===Denotational semantics of concurrency=== Many researchers have argued that domain theoretic models do not capture the nature of [[Concurrency_(computer_science)|concurrent computation]]. For this reason various [[Concurrency_(computer_science)#Models|new models]] have been introduced. In the early 1980s, people began using the style of denotational semantics to give semantics for concurrent languages. Examples include [[Denotational_semantics_of_the_Actor_model#Clinger.27s_Model|Will Clinger's work with the actor model]]; Glynn Winskel's work with event structures and [[petri nets]]<ref>Event Structure Semantics for CCS and Related Languages. DAIMI Research Report, University of Aarhus, 67 pp., April 1983.</ref>; and the work by Francez, Hoare, Lehmann, and de Roever (1979) on trace semantics for [[Communicating sequential processes|CSP]].<ref>Nissim Francez, [[C.A.R. Hoare]], Daniel Lehmann, and Willem-Paul de Roever. ''Semantics of nondeterminism, concurrency, and communication'' Journal of Computer and System Sciences. December 1979.</ref> All these lines of enquiry remain under investigation (see e.g. Hewitt's [[Denotational_semantics_of_the_Actor_model#The_Timed_Diagrams_Model|Timed Diagrams Model]],<ref>Carl Hewitt (2006) [http://www.pcs.usp.br/~coin-aamas06/10_commitment-43_16pages.pdf What is Commitment? Physical, Organizational, and Social] COIN@AAMAS. 2006.</ref> or the various denotational models for CSP<ref>[[Bill Roscoe|A. W. Roscoe]]: ''The Theory and Practice of Concurrency'', [[Prentice Hall]], ISBN 0-13-674409-5. Revised 2005.</ref>). Recently, Winskel and others have proposed the category of [[profunctor|profunctors]] as a domain theory for concurrency.<ref>Gian Luca Cattani, Glynn Winskel: Profunctors, open maps and bisimulation. Mathematical Structures in Computer Science 15(3): 553-614 (2005)</ref><ref>Mikkel Nygaard, Glynn Winskel: Domain theory for concurrency. Theor. Comput. Sci. 316(1): 153-190 (2004)</ref> ===Denotational semantics of sequentiality=== The problem of full abstraction (see [[denotational semantics#Full abstraction|below]]) for the sequential programming language [[Programming language for Computable Functions|PCF]] was, for a long time, a big open question in denotational semantics. The difficulty with PCF is that it is a very sequential language. For example, there is no way to define the parallel-or function in PCF. It is for this reason that the approach using domains, as introduced above, yields a denotational semantics that is not fully abstract. This open question was mostly resolved in the 1990s with the development of [[game semantics]] and also with techniques involving logical relations.<ref>P. W. O'Hearn and J. G. Riecke, Kripke Logical Relations and PCF, Information and Computation, Volume 120, Issue 1, July 1995, Pages 107-116.</ref> For more details, see the page on [[Programming language for Computable Functions|PCF]]. ===Denotational semantics as source-to-source translation=== It is often useful to translate one programming language into another. For example, a concurrent programming language might be translated into a [[process calculus]]; a high-level programming language might be translated into byte-code. (Indeed, conventional denotational semantics can be seen as the interpretation of programming languages into the internal language of the category of domains.) In this context, notions from denotational semantics, such as [[denotational semantics#full abstraction|full abstraction]], help to satisfy security concerns.<ref>Martin Abadi. Protection in programming-language translations. Proc. of ICALP'98. LNCS 1443. 1998.</ref><ref>Andrew Kennedy. Securing the .NET programming model. Theoretical Computer Science, 364(3). 2006</ref> ==Full abstraction== It is often considered important to connect the properties of a denotational semantics with those of an established [[operational semantics]]. This is especially important when the denotational semantics is rather mathematical and abstract, and the operational semantics is more concrete or closer to the computational intuitions. The following properties of a denotational semantics are often of interest. #'''Independence of denotational and operational semantics''': The denotational semantics should be formalized using mathematical structures that are independent of the operational semantics of a programming language; #'''Soundness''': All [[observational equivalence|observably distinct]] programs have distinct denotations; #'''Full abstraction''': Two programs have the same denotations precisely when they are [[observational equivalence|observationally equivalent]]. Additional desirable properties we may wish to hold between operational and denotational semantics are: #'''Constructivity''': The semantic model should be constructive in the sense that it should only include elements that can be intuitively constructed. One way of formalizing this is that every element must be the limit of a directed set of finite elements. #'''Progressivity''': For each system <tt>S</tt>, there is a <tt>'''progression'''<sub>S</sub></tt> function for the semantics such that the denotation (meaning) of a system <tt>S</tt> is <tt>⊔<sub>i∈ω</sub>'''progression'''<sub>S</sub><sup>i</sup>(⊥<sub>S</sub>)</tt> where <tt>⊥<sub>S</sub></tt> is the initial configuration of <tt>S</tt>. #'''Full completeness''' or '''definability''': Every morphism of the semantic model should be the denotation of a program.{{Fact|date=September 2007}} For semantics in the traditional style, full abstraction may be understood roughly as the requirement that "operational equivalence coincides with denotational equality". For denotational semantics in more intensional models, such as the [[Actor model]] and [[process calculi]], there are different notions of equivalence within each model, and so the concept of full abstraction is a matter of debate, and harder to pin down. Also the mathematical structure of operational semantics and denotational semantics can become very close. ==Semantics versus implementation== According to [[Dana Scott]] [1980]: :''It is not necessary for the semantics to determine an implementation, but it should provide criteria for showing that an implementation is correct.'' According to Clinger [1981]: :''Usually, however, the formal semantics of a conventional sequential programming language may itself be interpreted to provide an (inefficient) implementation of the language. A formal semantics need not always provide such an implementation, though, and to believe that semantics must provide an implementation leads to confusion about the formal semantics of concurrent languages. Such confusion is painfully evident when the presence of unbounded nondeterminism in a programming language's semantics is said to imply that the programming language cannot be implemented.'' ==Connections to other areas of computer science== Some work in denotation semantics has interpreted types as domains in the sense of [[domain theory]] which can be seen as a branch of [[model theory]], leading to connections with [[type theory]] and [[category theory]]. Within computer science, there are connections with [[abstract interpretation]], [[program verification]], and [[model checking]]. Monads were introduced to denotational semantics as a way of organising semantics, and these ideas have had a big impact in [[functional programming]] (see [[monads in functional programming]]). ==References== {{reflist}} ==Further reading== ===Textbooks=== * [[Joe Stoy|Joseph E. Stoy]], ''Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics''. [[MIT Press]], Cambridge, Massachusetts, 1977. (A classic if dated textbook.) * Carl Gunter, "Semantics of Programming Languages: Structures and Techniques". [[MIT Press]], Cambridge, Massachusetts, 1992. (ISBN 978-0262071437) * Glynn Winskel, ''Formal Semantics of Programming Languages''. [[MIT Press]], Cambridge, Massachusetts, 1993. (ISBN 978-0262731034) * R. D. Tennent, ''Denotational semantics''. Handbook of logic in computer science, vol. 3 pp 169--322. Oxford University Press, 1994. (ISBN 0-19-853762-X) ===Other references=== * S. Abramsky and A. Jung: [http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf ''Domain theory'']. In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, vol. III. Oxford University Press, 1994. (ISBN 0-19-853762-X) *Irene Greif. ''Semantics of Communicating Parallel Professes'' MIT EECS Doctoral Dissertation. August 1975. * Gordon Plotkin. ''A powerdomain construction'' SIAM Journal of Computing September 1976. * [[Edsger Dijkstra]]. ''A Discipline of Programming'' [[Prentice Hall]]. 1976. * Krzysztof R. Apt, J. W. de Bakker. ''Exercises in Denotational Semantics'' MFCS 1976: 1-11 * J. W. de Bakker. ''Least Fixed Points Revisited'' Theor. Comput. Sci. 2(2): 155-181 (1976) * Carl Hewitt and Henry Baker '''[http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-194.pdf Actors and Continuous Functionals]''' Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1-5, 1977. * [[Henry Baker (computer scientist)|Henry Baker]]. ''Actor Systems for Real-Time Computation'' MIT EECS Doctoral Dissertation. January 1978. * Michael Smyth. ''Power domains'' [[Journal of Computer and System Sciences]]. 1978. * George Milne and [[Robin Milner]]. ''Concurrent processes and their syntax'' [[JACM]]. April, 1979. * Nissim Francez, [[C.A.R. Hoare]], Daniel Lehmann, and Willem-Paul de Roever. ''Semantics of nondeterminism, concurrency, and communication'' Journal of Computer and System Sciences. December 1979. * Nancy Lynch and Michael Fischer. ''On describing the behavior of distributed systems'' in Semantics of Concurrent Computation. [[Springer Science+Business Media|Springer-Verlag]]. 1979. * Jerald Schwartz ''Denotational semantics of parallelism'' in Semantics of Concurrent Computation. Springer-Verlag. 1979. * William Wadge. ''An extensional treatment of dataflow deadlock'' Semantics of Concurrent Computation. Springer-Verlag. 1979. * Ralph-Johan Back. ''Semantics of Unbounded Nondeterminism'' [[ICALP]] 1980. * David Park. ''On the semantics of fair parallelism'' Proceedings of the Winter School on Formal Software Specification. Springer-Verlag. 1980. * Will Clinger, ''[http://hdl.handle.net/1721.1/6935''Foundations of Actor Semantics'']. MIT Mathematics Doctoral Dissertation, June 1981. * Lloyd Allison, ''A Practical Introduction to Denotational Semantics'' Cambridge University Press. 1987. * P. America, J. de Bakker, J. N. Kok and J. Rutten. ''Denotational semantics of a parallel object-oriented language'' Information and Computation, 83(2): 152 - 205 (1989) * David A. Schmidt, ''The Structure of Typed Programming Languages''. MIT Press, Cambridge, Massachusetts, 1994. ISBN 0-262-69171-X. * M. Korff ''True concurrency semantics for single pushout graph transformations with applications to actor systems'' Working papers of the Int. Workshop on Information Systems - Correctness and Reusability. World Scientific. 1995. * M. Korff and L. Ribeiro ''Concurrent derivations as single pushout graph grammar processes'' Proceedings of the Joint COMPUGRAPH/SEMAGRAPH Workshop on Graph Rewriting and Computation. ENTCS Vol 2, Elsevier. 1995. * Thati, Prasanna, Carolyn Talcott, and Gul Agha. ''Techniques for Executing and Reasoning About Specification Diagrams'' International Conference on Algebraic Methodology and Software Technology (AMAST), 2004. * J.C.M. Baeten, T. Basten, and M.A. Reniers. ''Algebra of Communicating Processes'' Cambridge University Press. 2005. * He Jifeng and C.A.R. Hoare. ''Linking Theories of Concurrency'' United Nations University International Institute for Software Technology UNU-IIST Report No. 328. July, 2005. * Luca Aceto and Andrew D. Gordon (editors). ''Algebraic Process Calculi: The First Twenty Five Years and Beyond'' Process Algebra. Bertinoro, Forl`ı, Italy, August 1–5, 2005. * [[Carl Sassenrath]] (1999) [http://www.webtechniques.com/archives/1999/09/junk/ denotational semantics] and the [[REBOL]] programming language * [[Bill Roscoe|A. W. Roscoe]]: ''The Theory and Practice of Concurrency'', [[Prentice Hall]], ISBN 0-13-674409-5. Revised 2005. == External links == * [http://www.csse.monash.edu.au/~lloyd/tilde/Semantics/ ''Denotational Semantics'']. Overview of book by Lloyd Allison * [http://www.risc.uni-linz.ac.at/people/schreine/courses/densem/densem.html ''Structure of Programming Languages I: Denotational Semantics'']. Course notes from 1995 by Wolfgang Schreiner * [http://www.cis.ksu.edu/~schmidt/text/densem.html ''Denotational Semantics: A Methodology for Language Development''] by David Schmidt [[Category:Logic in computer science]] [[Category:Computational models]] [[Category:Formal specification languages]] [[Category:Denotational semantics| ]] [[de:Denotationale Semantik]] [[es:Semántica denotacional]] [[fr:Sémantique dénotationnelle]] [[hr:Denotacijska semantika]] [[ja:表示的意味論]] [[pt:Semântica denotacional]] [[zh:指称语义]]