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