From Foundations of Computing. The Formal Semantics of Programming Languages provides the basic mathematical techniques necessary for those who are beginning a study of the semantics and logics of programming languages. These techniques will allow students to invent, formalize, and justify rules with which to reason about a variety of programming languages. Although the treatment is elementary, several of the topics covered are drawn from recent research, including the vital area of concurency. The book contains many exercises ranging from simple to miniprojects.
|Published (Last):||11 July 2013|
|PDF File Size:||11.67 Mb|
|ePub File Size:||20.10 Mb|
|Price:||Free* [*Free Regsitration Required]|
In computer science , denotational semantics initially known as mathematical semantics or Scott—Strachey semantics is an approach of formalizing the meanings of programming languages by constructing mathematical objects called denotations that describe the meanings of expressions from the languages. Other approaches provide formal semantics of programming languages including axiomatic semantics and operational semantics.
Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do. For example, programs or program phrases might be represented by partial functions or by games between the environment and the system. An important tenet of denotational semantics is that semantics should be compositional : the denotation of a program phrase should be built out of the denotations of its subphrases.
Denotational semantics originated in the work of Christopher Strachey and Dana Scott published in the early s. As described below, work has continued in investigating appropriate denotational semantics for aspects of programming languages such as sequentiality, concurrency , non-determinism and local state.
Denotational semantics have been developed for modern programming languages that use capabilities like concurrency and exceptions , e. For example, the meaning of the applicative expression f E1,E2 is defined in terms of semantics of its subphrases f, E1 and E2. In a modern programming language, E1 and E2 can be evaluated concurrently and the execution of one of them might affect the other by interacting through shared objects causing their meanings to be defined in terms of each other.
Also, E1 or E2 might throw an exception which could terminate the execution of the other one. The sections below describe special cases of the semantics of these modern programming languages.
Denotational semantics are given to a program phrase as a function from an environment holding the current values of its free variables to its denotation. If in the environment n has the value 3 and m has the value 5, then the denotation is A function can be modeled as a set of ordered pairs of argument and corresponding result values. The problem to be solved is to provide meanings for recursive programs that are defined in terms of themselves such as the definition of the factorial function as.
A solution is to build up the meanings by approximation. At the beginning, we start with the empty function an empty set.
Next, we add the ordered pair 0,1 to the function to result in another partial function that better approximates the factorial function. Afterwards, we add yet another ordered pair 1,1 to create an even better approximation.
It is instructive to think of this chain of iteration as F 0 , F 1 , F 2 , So by a fixed-point theorem specifically Bourbaki—Witt theorem , there exists a fixed point for this iterative process. In this case, the fixed point is the least upper bound of this chain, which is the full factorial function, which can be expressed as the direct limit. The directed join is essentially the join of directed sets.
The concept of power domains has been developed to give a denotational semantics to 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 unboundedness in domain-theoretic models of non-determinism.
Many researchers have argued that the domain-theoretic models given above do not suffice for the more general case of concurrent computation. For this reason various new models have been introduced. In the early s, people began using the style of denotational semantics to give semantics for concurrent languages. Examples include Will Clinger's work with the actor model ; Glynn Winskel's work with event structures and petri nets ;  and the work by Francez, Hoare, Lehmann, and de Roever on trace semantics for CSP.
Recently, Winskel and others have proposed the category of profunctors as a domain theory for concurrency. State such as a heap and simple imperative features can be straightforwardly modeled in the denotational semantics described above. All the textbooks below have the details. The key idea is to consider a command as a partial function on some domain of states. The sequencing operator " ; " is denoted by composition of functions.
Fixed-point constructions are then used to give a semantics to looping constructs, such as " while ". 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 of worlds to a category of domains. Programs are then denoted by natural continuous functions between these functors.
Many programming languages allow users to define recursive data types. For example, the type of lists of numbers can be specified by. This section deals only with functional data structures that cannot change. Conventional imperative 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. 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 textbooks below give more details. Polymorphic data types are data types that are defined with a parameter. Lists of natural numbers, then, are of type nat list , while lists of strings are of string list. 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 textbooks listed below. A recent research area has involved denotational semantics for object and class based programming languages. Following the development of programming languages based on linear logic , denotational semantics have been given to languages for linear usage see e. The problem of full abstraction for the sequential programming language 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 s with the development of game semantics and also with techniques involving logical relations. 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 full abstraction, help to satisfy security concerns. It is often considered important to connect denotational semantics with 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.
For semantics in the traditional style, adequacy and 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 concepts of adequacy and of full abstraction are a matter of debate, and harder to pin down.
Also the mathematical structure of operational semantics and denotational semantics can become very close. Additional desirable properties we may wish to hold between operational and denotational semantics are:. An important aspect of denotational semantics of programming languages is compositionality, by which the denotation of a program is constructed from denotations of its parts.
A basic denotational semantics in domain theory is compositional because it is given as follows. We start by considering program fragments, i. A typing context assigns a type to each free variable. We now give a denotational semantics to program fragments, using the following scheme. In fact, this is a general scheme for compositional denotational semantics.
There is nothing specific about domains and continuous functions here. One can work with a different category instead. For example, in game semantics, the category of games has games as objects and strategies as morphisms: we can interpret types as games, and programs as strategies. For a simple language without general recursion, we can make do with the category of sets and functions. For a language with side-effects, we can work in the Kleisli category for a monad.
For a language with state, we can work in a functor category. Milner has advocated modelling location and interaction by working in a category with interfaces as objects and bigraphs as morphisms. According to Dana Scott : . According to Clinger :  : Some work in denotational 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.
From Wikipedia, the free encyclopedia. Semantics Linguistic Logical. Lexical lexis lexicology. Statistical Structural. Prototype theory Force dynamics. Latent Machine-learning. Semantic Web Semantic wiki. Outline of a mathematical theory of computation. Revised Notes Theor. December
The formal semantics of programming languages - an introduction
In programming language theory , semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages. It does so by evaluating the meaning of syntactically valid strings defined by a specific programming language, showing the computation involved. In such a case that the evaluation would be of syntactically invalid strings, the result would be non-computation. Semantics describes the processes a computer follows when executing a program in that specific language. This can be shown by describing the relationship between the input and output of a program, or an explanation of how the program will be executed on a certain platform , hence creating a model of computation. Formal semantics, for instance, helps to write compilers, better understand what a program is doing, and to prove , e.