Denotational semantics and Stuart Smith (actor): Difference between pages

Revision as of 18:03, 24 November 2005

Revision as of 10:24, 4 June 2007

Line 1:

'''Stuart Smith''' (a.k.a. '''Stuart Steen''' a.k.a. '''Stuart Smita''') is a [[United Kingdom|British]]-[[Australia|australian]] actor born in [[Winchester]], who grew up in [[Sidney]].

{{ActiveDiscuss}}

After studying acting and playing a few parts in [[Australia]], he moved to [[Hong Kong]] and starred in several movies in the 80's, including "[[ninja]]" flicks by [[Godfrey Ho]]. He also worked extensively as a [[voice actor]], dubbing chinese movies into english.

In [[computer science]], '''denotational semantics''' is one of the approaches to formalize the [[semantics]] of [[computer system|computer systems]] by constructing mathematical objects (called ''denotations'' or ''meanings'') which express the semantics of these systems. Originally the field was developed more narrowly to deal only with a system that is defined by a [[computer program]]. Later the field broadened to include systems not defined by a single program as found in [[networking]] and [[concurrent systems]]. The field originated in work by [[Christopher Strachey]] and [[Dana Scott]] in the [[1960s]].

Other approaches include [[axiomatic semantics]] and [[operational semantics]]. (See [[formal semantics of programming languages]].)

He is particularly popular among bad movie fans due to his overacting that makes him twist his face in [[grimace]]s.

Denotational semantics as originally developed by Strachey and Scott interpreted the denotation (meaning) of a computer program as a [[function_(mathematics)|function]] that mapped input into output. Functions later this proved to be too limiting for the denotations (meanings) of networked and concurrent systems.

He is now a financial counselor in [[Thailand]]

==Fixed point semantics==

The denotational theory of computational system semantics is concerned with finding mathematical objects that represent what systems do. The theory makes use of a computational mathematical [[Domain theory|domains]]. Examples of such computational domains are partial functions, sets of states, and [[Actor model|Actor]] event scenarios.

==External link==

The relationship <tt>x≤y</tt> means that <tt>x</tt> can computationally evolve to <tt>y</tt>. If the denotations are partial functions, for example, <tt>f≤g</tt> may mean that <tt>f</tt> agrees with <tt>g</tt> on all values for which <tt>f</tt> is defined. If the denotations are [[Actor model|Actor]] event diagram scenarios, <tt>x≤y</tt> means that a system which satisfies <tt>x</tt> can evolve into a system which satisfies <tt>y</tt>.

*[http://www.nanarland.com/interview/interview.php?id_interview=stuartsmithvo&vo=1 Interview with Stuart Smith on Nanarland.com]

*{{imdb|id=0810051|name=Stuart Smith}}

{{UK-actor-stub}}

Computational domains have the following properties:

[[Category:English film actors|Smith, Stuart]]

#''Limits exist'' As computation continues, the denotations should become better and have a limit so if we have <tt>∀i∈ω x<sub>i<sub>≤x<sub>i+1<sub> then the [[least upper bound]] <tt>∨_i∈ω x_i</tt> should exist. The property just stated is called ω-completeness.

[[Category:British B-movie actors|Smith, Stuart]]

#''Finite elements are countable'' an element <tt>x</tt> is finite (also called isolated in the ___domain literature) if and only if whenever <tt>A</tt> is directed, <tt>∨A</tt> exists and <tt>x≤∨A</tt>, there exists <tt>a∈A</tt> with <tt>x≤a</tt>. In other words, <tt>x</tt> is finite if one must go through <tt>x</tt> in order to get up to or above <tt>x</tt> via the limit process.

[[category:Hong Kong film actors|Smith, Stuart]]

#''Every element is the least upper bound of a countable increasing sequence of finite elements.''

[[Category:Living people|Smith, Stuart]]

The mathematical denotation denoted by a system <tt>S</tt> is found by solving by constructing increasingly better approximations from an initial empty denotation called <tt>⊥_S</tt> using some denotation approximating function <tt>'''progression'''_S</tt> to constuct a denotation (meaning ) for <tt>S</tt> as follows:

[[Category:british expatriates|Smith, Stuart]]

::<tt>'''Denote'''_S ≡ ∨_i∈ω '''progression'''_Sⁱ(⊥<sub>S<sub>)</tt>..

It would be expected that <tt>'''progression'''_S</tt> would be ''monotone'', ''i.e.'', if <tt>x≤y</tt> then <tt>'''progression'''_S(x)≤'''progression'''_S(y)</tt>. More generally, we would expect that

::If <tt>∀i∈ω x<sub>i<sub>≤x<sub>i+1<sub></tt>, then <tt>'''progression'''_S(∨_i∈ω x_i) = ∨_i∈ω '''progression'''_S(x_i)</tt>

This last stated property of <tt>'''progression'''_S</tt> is called ω-continuity.

A central question of denotational semantics is to characterize when it is possible to create denotations (meanings) in according to the equation for <tt>'''Denote'''_S</tt>. If the the denotations (meanings) that we are using are ω-complete and <tt>'''progression'''_S<tt> is ω-continuous then <tt>'''Denote'''_S</tt> will exist.

It follows from the ω-continuity of <tt>'''progression'''_S</tt> that

:::<tt>'''progression'''_S('''Denote'''_S) = '''Denote'''_S</tt>

The above equation motivates the terminology that <tt>'''Denote'''_S</tt> is a ''fixed point'' of <tt>'''progression'''_S</tt>.

Furthermore this fixed point is least among all fixed points of <tt>'''progression'''_S</tt>.

The denotational semantics of functional programs provides an example of fixed point semantics as shown in the next section.

===Example of factorial function===

Consider the <tt>factorial</tt> function which is defined on all non-negative numbers as follows:

:<tt>factorial ≡ λ(n)if (n==0)then 1 else n*factorial(n-1)</tt>

The '''<tt>graph</tt>''' of <tt>factorial</tt> is the set of all ordered pairs for which factorial is defined with the first element of an ordered pair being the argument and the second element being the value, ''e.g.'',

:<tt>'''graph'''(factorial) = {<0,1>,<1,1>,<2,2>,<3,6>,<4,24>…}</tt>

The denotation (meaning) <tt>'''Denote'''_factorial</tt> for the <tt>factorial</tt> progam is constructed as follows:

:<tt>'''Denote'''_factorial = '''graph'''(factorial) = ∪_i∈ω '''progression'''_factorialⁱ({})</tt>

where

:<tt>'''progression'''_factorial(g) ≡ λ(n)if (n==0)then 1 else n*g(n-1)</tt>

Note: <tt>'''progression'''_factorial</tt> is a fix point operator (see definition in section above) whose least fixed point is <tt>'''Denote'''_factorial</tt>, i.e.,

:<tt>'''Denote'''_factorial = '''progression'''_factorial('''Denote'''_factorial)</tt>

Also <tt>'''progression'''_factorial</tt> is ω-continuous (see definition in section above).

===Derivation of Scott Continuity from Actor Semantics===

The [[Actor model]] provides a foundation for deriving [[Dana Scott|Dana Scott's]] denotational semantics of functions (as illustrated in the previous section above for <tt>factorial</tt>) as demonstrated first by a theorem of [[Carl Hewitt]] and [[Henry Baker (computer scientist)|Henry Baker]] [1977]:

If an Actor <tt>f</tt> behaves like a mathematical function, then <tt>'''progression'''_f</tt> is a [[Scott continuity|Scott continuous functional]] whose least fixed point is

:<tt>'''graph'''(f) = ∪_i∈ω '''progression'''_fⁱ({})</tt></tt>

where

:<tt>'''progression'''_f(G)≡{<x,y>|<x,y>&isin;'''graph'''(f) ''and'' '''immediate-descendants'''_f(<x,y>)&sube;G}</tt>

The paper by Hewitt and Baker contained a small bug in the definition of <tt>'''immediate-descendants'''_f</tt> that was corrected in Will Clinger [1981].

==Compositionality==

An important aspect of denotational semantics is compositionality by which the denotation of a program is constructed from denotations of its parts. For example consider the expression "<tt><expression₁> + <expression₂></tt>". Compositionality in this case is to provide a meaning for "<tt><expression₁> + <expression₂></tt>" in terms of the meanings of <tt><expression₁></tt> and <tt><expression₂></tt>.

===Environments===

The [[Actor model]] provides a modern and very general way the compositionality of programs can be analyzed. In this analysis, programs are Actors that are sent <tt>Eval</tt> messages with the address of an environment Actor. The environment holds the bindings of identifiers. When an environment is sent a <tt>Lookup</tt> message with the address of an identifier '''x''', it returns the latest (lexical) binding of '''x'''.

As an example of how this works consider the lambda expression <tt><L></tt> below which implements a tree data structure when supplied with parameters for a <tt>leftSubTree</tt> and <tt>rightSubTree</tt>. When such a tree is given a parameter message <tt>"getLeft"</tt>, it returns <tt>leftSubTree</tt> and likewise when given the message <tt>"getRight"</tt> it returns <tt>rightSubTree</tt>.

λ(leftSubTree,rightSubTree)

λ(message)

''if'' (message == "getLeft") ''then'' leftSubTree

''else if'' (message == "getRight") ''then'' rightSubTree

Consider what happens when an expression of the form <tt>"(<L> 1 2)"</tt> is sent an <tt>Eval</tt> message with environment '''E'''. One semantics for application expressions such as this one is the following: <tt><L>, 1</tt> and <tt>2</tt> are all sent <tt>Eval</tt> messages with environment '''E'''. The integers <tt>1</tt> and <tt>2</tt> immediately reply to the <tt>Eval</tt> message with themselves.

However <tt><L><tt> responds to the <tt>Eval</tt> message by creating a [[Closure (computer science)|closure]] Actor '''C''' that has an address (called ''body'') for <tt><L></tt> an address (called ''environment'') for '''E'''. The Actor <tt>"(<L> 1 2)"</tt> then sends '''C''' the message '''[1 2]'''.

When '''C''' receives the message '''[1 2]''', it creates a new environment Actor '''F''' which behaves as follows:

#When it receives a <tt>Lookup</tt> message for the identifier <tt>leftSubTree</tt> it responds with <tt>1</tt>

#When it receives a <tt>Lookup</tt> message for the identifier <tt>rightSubTree</tt> it responds with <tt>2</tt>

#When it receives a <tt>Lookup</tt> message for any other identifier, it forwards the <tt>Lookup</tt> message to '''E'''.

The Actor '''C''' then sends an <tt>Eval</tt> message with enviornment '''F''' to the following actor:

λ(message)

''if'' (message == "getLeft") ''then'' leftSubTree

''else if'' (message == "getRight") ''then'' rightSubTree

===Arithmetic expressions===

For another example consider the Actor for the expression "<tt><expression₁> + <expression₂></tt>" which has addresses for two other actors <tt><expression₁></tt> and <tt><expression₂></tt>). When the composite expression actor receives an <tt>Eval</tt> message with addresses for an environment Actor '''E''' and a customer Actor '''C''', it sends <tt>Eval</tt> messages to <tt>expression₁</tt> and <tt><expression₂</tt> with environment '''E''' and customer a new Actor '''C₀'''. When '''C₀''' has received back two values '''N₁''' and '''N₂''', it sends '''C''' the value '''N₁''' <tt>+</tt> '''N₂'''. In this way, the Actor model provides a semantics for "<tt><expression₁> + <expression₂></tt>" in terms of the semantics for <tt><expression₁></tt> and <tt><expression₂></tt>.

===Delayed evaluation===

Providing a compositional semantics for delayed evaluation provides a challenge for denotational semantics. The problem with classical approaches for compositional denotatonal sementics in dealing with expressions of form <tt>"''delay'' <Expression>"</tt> has been how to formaize the semantics of the evaluation of <tt><Expression></tt>.

The Actor model provides a perfectly reasonable account:

:The ''delay'' expression responds to an <Eval> message with environment '''E''' by creating a [[Closure (computer science)|closure]] Actor '''C''' that has an address (called ''body'') for <tt><Expression></tt> an address (called ''environment'') for '''E'''.

:When '''C''' receives a message '''M''' with '''Customer₀''', it creates a new Actor '''Customer₁''' and sends <tt><Expression></tt> an </tt>Eval</tt> message with environment '''E''' and the address of '''Customer₁'''.

:When '''Customer₁''' receives a value '''V''', it sends '''V''' the message '''M''' with '''Customer₀'''.

Other programming language constructs can be provided compositional semantics in similar ways.

The Actor model compositional semantics is very general and can be used for [[Functional programming|functional]], [[Imperative programming|imperative]], [[Concurrent programming language|concurrent]], [[Logic programming|logic]], ''etc.'' programs

==Denotational semantics of concurrency==

Extending denotational semantics to concurrency proved challenging. See [[unbounded nondeterminism]].

===The ___domain of Actor computations===

Clinger [1981] explained the ___domain of Actor computations as follows:

:The augmented Actor event diagrams [see [[Actor model theory]]] form a partially ordered set < <tt>'''Diagrams'''</tt>, &nbsp;<tt>&le;</tt>&nbsp;> from which to construct the power ___domain <tt>''P''['''Diagrams''']</tt> (see the section on [[Denotational semantics#Denotations|Denotations]] below). The augmented diagrams are partial computation histories representing "snapshots" [relative to some frame of reference] of a computation on its way to being completed. For <tt>x</tt>,<tt>y</tt>&isin;<tt>'''Diagrams'''</tt>, <tt>x&le;y</tt> means <tt>x</tt> is a stage the computation could go through on its way to <tt>y</tt>. The completed elements of <tt>'''Diagrams'''</tt> represent computations that have terminated and nonterminating computations that have become infinite. The completed elements may be characterized abstractly as the maximal elements of <tt>'''Diagrams'''</tt> [see William Wadge 1979]. Concretely, the completed elements are those having non pending events. Intuitively, <tt>'''Diagrams'''</tt> is not [[Completeness (order theory)|&omega;-complete]] because there exist increasing sequences of finite partial computations

::<tt>x₀&nbsp;&le;&nbsp;x₁&nbsp;&le;&nbsp;x₂&nbsp;&le;&nbsp;x₃&nbsp;&le;&nbsp;...</tt>

:in which some pending event remains pending forever while the number of realized events grows without bound, contrary to the requirement of finite [arrival] delay. Such a sequence cannot have a limit, because any limit would represent a completed nonterminating computation in which an event is still pending.

:To repeat, the actor event diagram ___domain <tt>'''Diagrams'''</tt> is incomplete because of the requirement of finite arrival delay, which allows any finite delay between an event and an event it activates but rules out infinite delay.

===Denotations===

In his doctoral dissertation, Will Clinger explained how power domains are obtained from incomplete domains as follows:

From the article on [[Power domains]]: <tt>''P''[D]</tt> is the collection of downward-closed subsets of ___domain <tt>D</tt> that are also closed under existing least upper bounds of directed sets in <tt>D</tt>. Note that while the ordering on <tt>''P''[D]</tt> is given by the subset relation, least upper bounds do not in general coincide with unions.

:For the actor event diagram ___domain <tt>'''Diagrams'''</tt>, an element of <tt>''P''['''Diagrams''']</tt> represents a list of possible initial histories of a computation. Since for elements <tt>x</tt> and <tt>y</tt> of </tt>'''Diagrams'''</tt>, <tt>x&le;y</tt> means that <tt>x</tt> is an initial segment of the initial history </tt>y</tt>, the requirement that elements of <tt>''P''['''Diagrams''']</tt> be downward-closed has a clear basis in intuition.

:...

:Usually the partial order from which the power ___domain is constructed is required to be [[Completeness (order theory)#Completion of domains|&omega;-complete]]. There are two reasons for this. The first reason is that most power domains are simply generalizations of domains that have been used as semantic domains for conventional sequential programs, and such domains are all complete because of the need to compute fixed points in the sequential case. The second reason is that &omega;-completeness permits the solution of recursive ___domain equations involving the power ___domain such as

::<tt>R &#8776; S&nbsp;&rarr;&nbsp;''P''[S + (S <math>\times</math> R)]</tt>

:which defines a ___domain of resumptions [Gordon Plotkin 1976]. However, [[power domains]] can be defined for any ___domain whatsoever. Furthermore the power ___domain of a ___domain is essentially the power ___domain of its &omega;-completion, so recursive equations involving the power ___domain of an incomplete ___domain can still be solved, provide the domains to which the usual constructors (<tt>+</tt>, <math>\times</math>, &nbsp;&rarr;&nbsp;, and <tt>*</tt>) are applied are &omega;-complete. It happens that defining Actor semantics as in Clinger [1981] does not require solving any recursive equations involving the power ___domain.

:In short, there is no technical impediment to building power domains from incomplete domains. But why should one want to do so?

:In ''behavioral semantics'', developed by Irene Greif, the meaning of program is a specification of the computations that may be performed by the program. The computations are represented formally by Actor event diagrams. Greif specified the event diagrams by means of causal axioms governing the behaviors of individual Actors [Greif 1975].

:Henry Baker has presented a nondeterministic interpreter generating instantaneous schedules which then map onto event diagrams. He suggested that a corresponding deterministic interpreter operating on sets of instantaneous schedules could be defined using power ___domain semantics [Baker 1978].

:The semantics presented in [Clinger 1981] is a version of behavioral semantics. A program denotes a set of Actor event diagrams. The set is defined extensionally using power ___domain semantics rather than intensionally using causal axioms. The behaviors of individual Actors is defined functionally. It is shown, however, that the resulting set of Actor event diagrams consists of exactly those diagrams that satisfy causal axioms expressing the functional behaviors of Actors. Thus Greif's behavioral semantics is compatible with a denotational power ___domain semantics.

:Baker's instantaneous schedules introduced the notion of ''pending events'', which represent messages on the way to their targets. Each pending event must become an actual (realized) arrival event sooner or later, a requirement referred to as ''finite delay''. Augmenting Actor event diagrams with sets of pending events helps to express the finite delay property, which is characteristic of true concurrency [Schwartz 1979].

===Sequential computations form an &omega;-complete subdomain of the ___domain of Actor computations===

In his 1981 dissertation, Clinger showed how sequential computations form a subdomain of concurrent computations:

:Instead of beginning with a semantics for sequential programs and then trying to extend it for concurrency, Actor semantics views concurrency as primary and obtains the semantics of sequential programs as a special case.

:...

:The fact that there exist increasing sequences without least upper bounds may seem strange to those accustomed to thinking about the semantics of sequential programs. It may help to point out that the increasing sequences produced by sequential programs all have least upper bounds. Indeed, the partial computations that can be produced by sequential computation form an &omega;-complete subdomain of the ___domain of Actor computations <tt>'''Diagrams'''</tt>. An informal proof follows.

::From the Actor point of view, sequential computations are a special case of concurrent computations, distinguishable by their event diagrams. The event diagram of a sequential computation has an initial event, and no event activates more than one event. In other words, the activation ordering of an sequential computation is linear; the event diagram is essentially a conventional execution sequence. This means that the finite elements of <tt>'''Diagrams'''</tt>

:::<tt>x₀&nbsp;&le;&nbsp;x₁&nbsp;&le;&nbsp;x₂&nbsp;&le;&nbsp;x₃&nbsp;&le;&nbsp;...</tt>

::corresponding to the finite initial segments of a sequential execution sequence all have exactly one pending event, excepting the largest, completed element if the computation terminates. One property of the augmented event diagrams ___domain < <tt>'''Diagrams'''</tt>, &nbsp;<tt>&le;</tt>&nbsp;> is that if <tt>x&le;y</tt> and <tt>x&ne;y</tt>, then some pending event of <tt>x</tt> is realized in <tt>y</tt>. Since in this case each <tt>x_i</tt> has at most one pending event, every pending event in the sequence becomes realized. Hence the sequence

:::<tt>x₀&nbsp;&le;&nbsp;x₁&nbsp;&le;&nbsp;x₂&nbsp;&le;&nbsp;x₃&nbsp;&le;&nbsp;...</tt>

::has a least upper bound in <tt>'''Diagrams'''</tt> in accord with intuition.

:The above proof applies to all sequential programs, even those with choice points such as [[guarded commands]]. Thus Actor semantics includes sequential programs as a special case, and agrees with conventional semantics of such programs.

==Early history of denotational semantics==

As mentioned earlier, the field was initially developed by [[Christopher Strachey]] and [[Dana Scott]] in the [[1960s]] and then [[Joe Stoy]] in the [[1970s]] at the [[Programming Research Group]], part of the [[Oxford University Computing Laboratory]].

[[Montague grammar]] is a form of denotational semantics for idealized fragments of [[English language|English]].

According to Clinger [1981],

:[[Gordon Plotkin|Plotkin]]'s original power ___domain construction was simplified in [Smyth 1978] which remains the standard introduction to the subject. A number of nondeterministic programming languages have now been given power ___domain semantics. Of these the semantics of [Francez, [[Hoare]], Lehmann, and de Roever 1979] had the most influence over the development of the denotational model in Clinger's dissertation.

:The denotational semantics in Clinger's dissertation is probably the first power ___domain semantics for languages with true concurrency, but it is not the first power ___domain semantics for a language with unbounded nondeterminism. [Back 1980] has given a power ___domain semantics for a language with unboundedly nondeterministic assignment as a primitive operation. Three differences between Back's work and the Actor denotation semantics in Clinger's dissertation stand out:

:#The source of nondeterminism in Back's paper is basic assignment statements whereas in the Actor model it is message latency.

:#Back's paper treats nondeterministic sequential programming languages whereas the Actor model is concerned with concurrent programming languages.

:#The power ___domain in Back's paper apparently is constructed from a complete underlying ___domain. This third difference is not entirely clear because Back's power ___domain construction appears to be nonstandard.

:A similarity between Back's work the Actor denotational semantics in Clinger's dissertation is that Back found it necessary to build the power ___domain out of execution sequences instead of single states: the Actor power ___domain is built out of Actor event diagrams, which are generalizations of execution sequences.

==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 a branch of [[model theory]]. and has many connections with [[type theory]] and [[category theory]]. Within computer science, there are connections with [[abstract interpretation]], [[program verification]] and [[functional programming]], see for instance [[monads in functional programming]]. In particular, denotational semantics has used the concept of [[continuation]]s to express control flow in sequential programming in terms of [[functional programming]] semantics.

==References==

*Irene Greif. ''Semantics of Communicating Parallel Professes'' MIT EECS Doctoral Dissertation. August 1975.

* [[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.)

* 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 (computer scientist)|Henry Baker]] ''Actors and Continuous Functionals'' Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1&ndash;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.

* [[C.A.R. Hoare]]. ''[[Communicating Sequential Processes]]'' [[CACM]]. August, 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-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, ''Foundations of Actor Semantics''. MIT Mathematics Doctoral Dissertation, June 1981. (Quoted by permission of author.)

* 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 026269171X.

*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.

==External links==

* [http://www.csse.monash.edu.au/~lloyd/tilde/Semantics/ ''Denotation Semantics''] by Lloyd Allison

* [http://www.risc.uni-linz.ac.at/people/schreine/courses/densem/densem.html ''Structure of Programming Languages I: Denotational Semantics''] by Wolfgang Schreiner

* [http://www.cis.ksu.edu/~schmidt/text/densem.html ''Denotational Semantics: A Methodology for Language Development''] by David Schmidt

* [http://www.honors.montana.edu/~jjc/presentation/contents.xhtml Presentation] by Josh Cogliati

* [http://www.hhm.com.ar/hql.htm HQL] by H. Hernan Moraldo &ndash; complete denotational semantics of a small language

[[Category:Formal methods]]

[[Category:Logic in computer science]]

[[Category:Actor model]]

[[Category:Concurrent computing]]

[[Category:Specification languages]]

{{Compu-stub}}

[[fr:Sémantique dénotationnelle]]

[[pt:Semântica denotacional]]