Language Semantics and Evaluation Models

Operational semantics explains program behavior by describing execution steps or state transitions.

18.1 Operational semantics

Operational semantics explains program behavior by describing execution steps or state transitions. It is useful for understanding control flow, language specifications, and interpreter/compiler behavior.

18.2 Denotational semantics

Denotational semantics maps language constructs to mathematical meanings. It can provide a compositional view of a program's meaning, although practical languages require careful modeling of state, exceptions, concurrency, and effects.

18.3 Axiomatic semantics

Axiomatic approaches use logical assertions to reason about program correctness. A Hoare triple has the form:

P is a precondition.

command is the operation.

Q is a postcondition.

It means that if P holds and the command terminates under the model's assumptions, then Q holds afterward.

{ P } command { Q }

{ x >= 0 }
x = x + 1
{ x >= 1 }

18.4 Eager and lazy evaluation

Eager/strict: evaluate an argument before calling the function, according to the language's rules.

Lazy/non-strict: delay evaluation until required.

Short-circuit evaluation: some Boolean operators skip evaluating the second operand when the first determines the result.

Evaluation strategy can affect termination, side effects, performance, and exceptions.

18.5 Value semantics and reference semantics

Value semantics emphasizes independent values; reference semantics allows multiple names or handles to refer to the same object. Actual language behavior may combine both. Copying a reference is not the same as deep-copying the referenced object.

18.6 Type erasure and runtime type information

Some languages erase generic type information at runtime; others preserve more type metadata. This affects reflection, serialization, runtime checks, and interoperability.

18.7 Interpreter, compiler, and virtual machine

Interpreter: evaluates or executes program representations.

Compiler: translates source or an intermediate representation into another representation.

Virtual machine: executes a defined instruction set or managed intermediate representation.

JIT compiler: compiles code during execution based on runtime observations or other criteria.

AOT compiler: compiles ahead of execution.

Bytecode: an intermediate instruction representation used by some runtimes.

Many implementations combine interpretation, JIT compilation, and AOT compilation. These implementation strategies do not by themselves define a source-language paradigm.

From source code to execution Text equivalent: source text becomes tokens, then an abstract syntax tree, which is checked and lowered to an intermediate representation. From there an implementation may compile ahead of time to machine code, or emit bytecode for a virtual machine that interprets it and JIT-compiles the hot parts. These are implementation strategies; none of them defines the source language's paradigm.

flowchart LR
  S[Source code] --> L[Lexer: tokens] --> PR[Parser: AST] --> SEM[Semantic analysis: types, names] --> IR[Intermediate representation]
  IR --> OPT[Optimiser]
  OPT --> AOT[AOT: machine code]
  OPT --> BC[Bytecode] --> VM[Virtual machine: interpret]
  VM --> JIT[JIT: hot code to machine code]

18.8 Abstract syntax trees and intermediate representations

An AST captures the syntactic structure of a program. Compilers may transform it into one or more intermediate representations (IRs) for analysis and optimization. Understanding ASTs helps when building linters, formatters, transpilers, and DSLs.

Exercise

Trace evaluation of a short expression in a language with short-circuit Boolean operators. Identify which subexpressions run and explain why.

Quiz

? `{ x >= 0 } x = x + 1 { x >= 1 }` is an example of which semantics?
+ Axiomatic (a Hoare triple) :: Precondition, command, postcondition.
- Operational :: Operational semantics describes execution steps.
- Denotational :: Denotational semantics maps constructs to mathematical meanings.
- Lexical :: Not a kind of semantics.

? In `user != null && user.isAdmin()`, why does the right side not run when `user` is null?
+ Short-circuit evaluation: `&&` skips its second operand when the first is false. :: The result is already known.
- Lazy evaluation of every expression. :: Only the logical operator short-circuits here.
- The compiler removes the call. :: It is a runtime rule.
- Because null equals false. :: The comparison returns false, then && stops.

? Which statements about implementation strategies are correct? (select all that apply)
+ Many runtimes combine interpretation and JIT compilation. :: The JVM and V8 do.
+ Interpretation versus compilation does not define a language's paradigm. :: They are implementation choices.
- Bytecode is always slower than machine code. :: JIT-compiled bytecode can run at native speed.
+ An AST captures a program's syntactic structure. :: Linters 
…