Operational semantics

operationalnatural semanticsOperationallyStructural operational semanticsstructured operational semanticssemanticsSmall step semantics
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics).wikipedia
84 Related Articles

Denotational semantics

denotationalfully abstractHistory of denotational semantics
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics). Other approaches to providing a formal semantics of programming languages include axiomatic semantics and denotational semantics.
Other approaches provide formal semantics of programming languages including axiomatic semantics and operational semantics.

Formal verification

program verificationverificationautomated verification
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics).
Examples of mathematical objects often used to model systems are: finite state machines, labelled transition systems, Petri nets, vector addition systems, timed automata, hybrid automata, process algebra, formal semantics of programming languages such as operational semantics, denotational semantics, axiomatic semantics and Hoare logic.

Semantics (computer science)

semanticsformal semantics of programming languagesformal semantics
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics). Other approaches to providing a formal semantics of programming languages include axiomatic semantics and denotational semantics.

Gordon Plotkin

Gordon D. PlotkinGordon David PlotkinPlotkin
Gordon Plotkin introduced the structural operational semantics, Robert Hieb and Matthias Felleisen the reduction contexts, and Gilles Kahn the natural semantics.
Plotkin is probably best known for his introduction of structural operational semantics (SOS) and his work on denotational semantics.

Axiomatic semantics

axioms
Other approaches to providing a formal semantics of programming languages include axiomatic semantics and denotational semantics.

SECD machine

SECD
Abstract machines in the tradition of the SECD machine are also closely related.
The description published by Landin was fairly abstract, and left many implementation choices open (like an operational semantics).

Functional programming

functionalfunctional programming languagefunctional language
In the context of functional programs, the final step in a terminating
Launchbury 1993 describes some difficulties that lazy evaluation introduces, particularly in analyzing a program's storage requirements, and proposes an operational semantics to aid in such analysis.

Abstract machine

abstract computerabstract computer modelcomputational models
Abstract machines in the tradition of the SECD machine are also closely related.
Abstract data types can be specified in terms of their operational semantics on an abstract machine.

Gilles Kahn

Gordon Plotkin introduced the structural operational semantics, Robert Hieb and Matthias Felleisen the reduction contexts, and Gilles Kahn the natural semantics.
He notably introduced Kahn process networks as a model for parallel processing and natural semantics for describing the operational semantics of programming languages.

Bisimulation

bisimilarity(weak)bisimilar
Important relations include simulation preorders and bisimulation.
Typically, if the state transition system gives the operational semantics of a programming language, then the precise definition of bisimulation will be specific to the restrictions of the programming language.

Type safety

type-safetype safesafe
These properties make small-step semantics more convenient when proving type soundness of a type system against an operational semantics.
In 1994, Andrew Wright and Matthias Felleisen formulated what is now the standard definition and proof technique for type safety in languages defined by operational semantics.

Transition system

state transition systemlabelled transition systemtransition function
An SOS specification defines the behavior of a program in terms of a (set of) transition relation(s).

Simulation preorder

simulation
Important relations include simulation preorders and bisimulation.

Computation

computationalcomputationscomputing
Operational semantics are classified in two categories: structural operational semantics (or small-step semantics) formally describe how the individual steps of a computation take place in a computer-based system; by opposition natural semantics (or big-step semantics) describe how the overall results of the executions are obtained.

Nondeterministic algorithm

non-deterministicnondeterministicnon-deterministic algorithm
because the program could be nondeterministic, and even for a deterministic program there can be many computation sequences since the semantics may not specify exactly what sequence of operations arrives at that value.)

Lambda calculus

beta reductionλ-calculusuntyped lambda calculus
Perhaps the first formal incarnation of operational semantics was the use of the lambda calculus to define the semantics of LISP.

Lisp (programming language)

LispLisp programming languageLisp 1.5
Perhaps the first formal incarnation of operational semantics was the use of the lambda calculus to define the semantics of LISP.

Dana Scott

Dana S. ScottScottD. S. Scott
Dana Scott (Plotkin04).

Matthias Felleisen

Felleisen
Gordon Plotkin introduced the structural operational semantics, Robert Hieb and Matthias Felleisen the reduction contexts, and Gilles Kahn the natural semantics. The method was introduced by Robert Hieb and Matthias Felleisen in 1992 as a technique for formalizing an equational theory for control and state.

Recursive definition

inductive definitionrecursively definedinductively defined
The basic idea behind SOS is to define the behavior of a program in terms of the behavior of its parts, thus providing a structural, i.e., syntax-oriented and inductive, view on operational semantics.

Rule of inference

inference rulerules of inferenceinference rules
SOS specifications take the form of a set of inference rules that define the valid transitions of a composite piece of syntax in terms of the transitions of its components.

Binary relation

relationrelationsidentity relation
Such a definition allows formal analysis of the behavior of programs, permitting the study of relations between programs.

Concurrency (computer science)

concurrencyconcurrentconcurrently
These are especially useful in the context of concurrency theory.

Universal algebra

algebraequational theoryequational reasoning
The method was introduced by Robert Hieb and Matthias Felleisen in 1992 as a technique for formalizing an equational theory for control and state.

Control flow

looploopscontrol structure
The method was introduced by Robert Hieb and Matthias Felleisen in 1992 as a technique for formalizing an equational theory for control and state.