Course contentsShow
← Computer Science
Lesson 2019 of 2,87245. Type Systems and SemanticsFree lesson

Semantic Rules and Judgments

How to read and write semantic rules using inference notation with premises and conclusions.

Semantic Rules and Judgments

You'll learn: How to formally describe what a program means using inference rules with premises and conclusions.

The Core Idea

When we define operational semantics (the meaning of program execution), we need a precise notation. Semantic rules use inference notation to express judgments—statements about what's true during program evaluation.

Think of it like writing legal rules: "If conditions A and B are met (premises), then conclusion C follows." In semantics, we write these as horizontal lines with premises above and the conclusion below.

Reading Inference Rules

A typical semantic rule looks like this:

premise₁    premise₂    premise₃
─────────────────────────────────
         conclusion

This reads: "If all premises hold, then the conclusion holds."

Judgments: Statements About Programs

A judgment is a statement we're trying to prove, like:

  • e ⇒ v (expression e evaluates to value v)
  • e : T (expression e has type T)

The inference rules tell us when these judgments are valid.

Simple Example

For an addition expression in big-step semantics:

e₁ ⇒ n₁    e₂ ⇒ n₂    n₃ = n₁ + n₂
────────────────────────────────────
         e₁ + e₂ ⇒ n₃

This says: "If e₁ evaluates to number n₁, AND e₂ evaluates to n₂, AND their sum equals n₃, THEN the whole expression e₁ + e₂ evaluates to n₃."

Rules with no premises (nothing above the line) are axioms—base truths that need no justification.

Key Takeaway: Semantic rules use inference notation (premises over a line, conclusion below) to precisely define when judgments about program behavior are valid—they're the formal "if-then" laws of programming language meaning.