Semantics Flashcards
What is the difference between operational and denotational semantics:
Denotational:
ascribes to programs functions taking input data to output data
Operational:
describes the execution of programs on an abstract machine
operational semantics has two sub-classes:
Structural operational semantics: Small-step semantics describes the operation of a machine on a program and input step by step
Natural semantics: Big-step semantics. Gives the description in one big step and is close to denotational semantics
You can choose the granularity
What is a state?
Finitely supported partial functions from variables to natural numbers, which we can represent by sets of pairs of the form (X, n)
The value of X in a state ó will be written ó(X)
ó[X – n] refers to the state ó modified at variable X to value n.
What are configurations (for commands)?
Pairs [(c, ó)] where c is a command (the residual command or what is left to do) and ó is a state
Describe steps
Intermediate steps: [(c, ó)] -> [(c’, ó’)]
Final step: [(c, ó)] -> ó’
Valid steps are determined by inference rules.
What is a computation in the context of semantics
A maximal finite or infinite sequence of steps.
Computations can terminate
- normally (with a final state)
- abruptly (with a stuck configuration where no further step is possible)
Infinite sequences correspond to nonterminating computations.
What do the rules do?
They tell you what can be done and how to do it
What is nondeterministic semantics?
Semantics that has several computations from the same initial configuration
