HOME

TheInfoList




In
programming language theory Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages and of their individual Programming ...
, semantics is the field concerned with the rigorous mathematical study of the meaning of
programming language A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
s. It does so by evaluating the meaning of
syntactically In linguistics Linguistics is the science, scientific study of language. It encompasses the analysis of every aspect of language, as well as the methods for studying and modeling them. The traditional areas of linguistic analysis includ ...
valid
strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * Strings (1991 film), ''Strings'' (1991 fil ...
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 Platform may refer to: Technology * Computing platform, a framework on which applications may be run * Platform game, a genre of video games * Car platform, a set of components shared by several vehicle models * Weapons platform, a system or s ...
, hence creating a
model of computation A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a meas ...
.


Overview

The field of formal semantics encompasses all of the following: *The definition of semantic models *The relations between different semantic models *The relations between different approaches to meaning *The relation between computation and the underlying mathematical structures from fields such as
logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and ar ...
,
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, i ...
,
model theory In mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical ...
,
category theory Category theory formalizes mathematical structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ...
, etc. It has close links with other areas of
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
such as
programming language design A programming language is a formal language In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calcu ...
,
type theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
,
compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...

compiler
s and
interpreters Interpreting is a Translation studies, translational activity in which one produces a first and final translation on the basis of a one-time exposure to an expression in a Source language (translation), source language. The most common two modes ...
,
program verification In the context of hardware and software system A software system is a system of intercommunicating software component, components based on software forming part of a computer system (a combination of Computer hardware, hardware and software). It ...
and
model checking In computer science, model checking or property checking is a method for checking whether a finite-state machine, finite-state model of a system meets a given formal specification, specification (also known as correctness (computer science), corr ...
.


Approaches

There are many approaches to formal semantics; these belong to three major classes: *
Denotational semantics In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of compu ...
, whereby each phrase in the language is interpreted as a ''
denotation The denotation of a word is its central sense A sense is a biological system A biological system is a complex biological network, network which connects several biologically relevant entities. Biological organization spans several scales and ar ...
'', i.e. a conceptual meaning that can be thought of abstractly. Such denotations are often mathematical objects inhabiting a mathematical space, but it is not a requirement that they should be so. As a practical necessity, denotations are described using some form of mathematical notation, which can in turn be formalized as a denotational metalanguage. For example, denotational semantics of
functional languages In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Alg ...
often translate the language into
domain theory Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer s ...
. Denotational semantic descriptions can also serve as compositional translations from a programming language into the denotational metalanguage and used as a basis for designing
compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...

compiler
s. *
Operational semantics Operational semantics is a category of formal programming language semantics Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference Reference is a relationship between objects in which one ...
, whereby the execution of the language is described directly (rather than by translation). Operational semantics loosely corresponds to
interpretation Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event i ...
, although again the "implementation language" of the interpreter is generally a mathematical formalism. Operational semantics may define an
abstract machine An abstract machine, also called an abstract computer, is a theoretical computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations automatically. Modern compute ...
(such as the
SECD machineThe SECD machine is a highly influential (''see: '') virtual machine and abstract machine intended as a target for functional programming, functional programming language compilers. The letters stand for Stack, Environment, Control, Dump—the intern ...
), and give meaning to phrases by describing the transitions they induce on states of the machine. Alternatively, as with the pure
lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system A formal system is an used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, ar ...
, operational semantics can be defined via syntactic transformations on phrases of the language itself; *
Axiomatic semantics Axiomatic semantics is an approach based on mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory ...
, whereby one gives meaning to phrases by describing the ''
axiom An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' o ...

axiom
s'' that apply to them. Axiomatic semantics makes no distinction between a phrase's meaning and the logical formulas that describe it; its meaning ''is'' exactly what can be proven about it in some logic. The canonical example of axiomatic semantics is
Hoare logic Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and mat ...
. Apart from the choice between denotational, operational, or axiomatic approaches, most variations in formal semantic systems arise from the choice of supporting mathematical formalism.


Variations

Some variations of formal semantics include the following: *
Action semantics Action semantics is a framework for the formal specification of formal semantics of programming languages, semantics of programming languages invented by David Watt (computer scientist), David Watt and Peter D. Mosses in the 1990s. It is a mixture o ...
is an approach that tries to modularize denotational semantics, splitting the formalization process in two layers (macro and microsemantics) and predefining three semantic entities (actions, data and yielders) to simplify the specification; * Algebraic semantics is a form of
axiomatic semantics Axiomatic semantics is an approach based on mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory ...
based on
algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In its most ge ...

algebra
ic laws for describing and reasoning about
program semantics In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming language A programming language is a formal language comprising a Instruction set architecture, set of instruc ...
in a
formal Formal, formality, informal or informality imply the complying with, or not complying with, some set theory, set of requirements (substantial form, forms, in Ancient Greek). They may refer to: Dress code and events * Formal wear, attire for forma ...
manner. It also supports
denotational semantics In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of compu ...
and
operational semantics Operational semantics is a category of formal programming language semantics Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference Reference is a relationship between objects in which one ...
; *
Attribute grammarAn attribute grammar is a formal way to define attributes for the productions of a formal grammar In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a l ...
s define systems that systematically compute "
metadata Metadata is "data Data (; ) are individual facts, statistics, or items of information, often numeric. In a more technical sense, data are a set of values of qualitative property, qualitative or quantity, quantitative variable (research), v ...

metadata
" (called ''attributes'') for the various cases of the language's syntax. Attribute grammars can be understood as a denotational semantics where the target language is simply the original language enriched with attribute annotations. Aside from formal semantics, attribute grammars have also been used for code generation in
compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...

compiler
s, and to augment
regular The term regular can mean normal or in accordance with rules. It may refer to: People * Moses Regular (born 1971), America football player Arts, entertainment, and media Music * Regular (Badfinger song), "Regular" (Badfinger song) * Regular tunin ...
or
context-free grammars In formal language theory, a context-free grammar (CFG) is a formal grammar whose Production (computer science), production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of Terminal and nontermi ...
with context-sensitive conditions; * Categorical (or "functorial") semantics uses
category theory Category theory formalizes mathematical structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ...
as the core mathematical formalism. A categorical semantics is usually proven to correspond to some axiomatic semantics that gives a syntactic presentation of the categorical structures. Also, denotational semantics are often instances of a general categorical semantics, * Concurrency semantics is a catch-all term for any formal semantics that describes concurrent computations. Historically important concurrent formalisms have included the
actor model The actor model in computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the ...
and
process calculi In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorit ...
; *
Game semantics with separate sliding drawer, from 1390–1353 BC, made of glazed faience, dimensions: 5.5 × 7.7 × 21 cm, in the Brooklyn Museum The Brooklyn Museum is an art museum An art museum is a building or space for the disp ...
uses a metaphor inspired by
game theory Game theory is the study of mathematical model A mathematical model is a description of a system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. ...
. *
Predicate transformer semanticsPredicate transformer semantics were introduced by Edsger Dijkstra in his seminal paper " Guarded commands, nondeterminacy and formal derivation of programs". They define the semantics of an imperative programming In computer science, imperative pro ...
, developed by
Edsger W. Dijkstra Edsger Wybe Dijkstra ( ; ; 11 May 1930 – 6 August 2002) was a Dutch computer scientist A computer scientist is a person A person (plural people or persons) is a being that has certain capacities or attributes such as reason, morality, cons ...
, describes the meaning of a program fragment as the function transforming a
postconditionIn computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a specific task. Programming involves tasks such as: analysis, generatin ...
to the
precondition In computer programming, a precondition is a condition or Predicate (mathematics), predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification. If a precondition is violat ...
needed to establish it.


Describing relationships

For a variety of reasons, one might wish to describe the relationships between different formal semantics. For example: *To prove that a particular operational semantics for a language satisfies the logical formulas of an axiomatic semantics for that language. Such a proof demonstrates that it is "sound" to reason about a particular (operational) ''interpretation strategy'' using a particular (axiomatic) ''proof system''. *To prove that operational semantics over a high-level machine is related by a
simulation A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of models; the model represents the key characteristics or behaviors of the selected system or process, whereas the simulat ...

simulation
with the semantics over a low-level machine, whereby the low-level abstract machine contains more primitive operations than the high-level abstract machine definition of a given language. Such a proof demonstrates that the low-level machine "faithfully implements" the high-level machine. It is also possible to relate multiple semantics through
abstractions Abstraction in its main sense is a conceptual process where general rules Rule or ruling may refer to: Human activity * The exercise of political Politics (from , ) is the set of activities that are associated with Decision-making, ma ...
via the theory of
abstract interpretationIn computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorith ...
.


History

Robert W. Floyd is credited with founding the field of programming language semantics in .


See also

* Computational semantics *
Formal semantics (logic) In logic, the semantics of logic or formal semantics is the study of the semantics, or interpretation (logic), interpretations, of formal language, formal and (idealizations of) natural languages usually trying to capture the pre-theoretic notion ...
*
Formal semantics (linguistics) Formal semantics is the study of grammatical meaning in natural language In neuropsychology Neuropsychology is a branch of psychology. It is concerned with how a person's cognition and behavior are related to the brain and the rest of the ...
*
Ontology Ontology is the branch of philosophy that studies concepts such as existence, being, Becoming (philosophy), becoming, and reality. It includes the questions of how entities are grouped into Category of being, basic categories and which of these ...

Ontology
*
Ontology (information science) In computer science and information science, an ontology encompasses a representation, formal naming and definition of the categories, properties and relations between the concepts, data and entities that substantiate one, many, or all Domain of d ...
*
Semantic equivalence{{about, semantic equivalence of metadata, the concept in mathematical logic, Logical equivalence In computer metadata, semantic equivalence is a declaration that two data elements from different vocabularies contain data that has similar meaning. T ...
*
Semantic technology The ultimate goal of semantic technology is to help machines understand data. To enable the encoding of semantics with the data, well-known technologies are RDF (Resource Description Framework) and OWL (Web Ontology Language). These technologies f ...


References


Further reading

; Textbooks * * * * * * * * * * (Working draft) * * * ; Lecture notes *


External links

* Semantics. {{DEFAULTSORT:Semantics Of Programming Languages Formal methods Logic in computer science