Thu Jul 16 14:20:11 CEST 2009

Small-step vs. Big-step operational semantics

Wikipedia[1] isn't very clear here:

  In computer science, small step semantics formally describe how the
  individual steps of a computation take place in a computer-based
  system. By opposition big step semantics describe how the overall
  results of the executions are obtained.

From Pierce[2] 3.4 p.32: (reformulated)

  The small step style of operational semantics is sometimes called
  "structural operational semantics" and specifies reduction by means
  of a transition function for an abstract machine.  The meaning of a
  term is the halting state of iterative application of the transition
  function.  Big step style evaluates a term to the end result in a
  single transition.

[1] http://en.wikipedia.org/wiki/Small_step_semantics
[2] isbn://0262162091