smallstep

Smallstep, in the context of computer science, refers mainly to small-step semantics, a formal approach for describing program execution. In contrast to big-step (or natural) semantics, which relate a term directly to its final result, small-step semantics describes computation as a sequence of elementary transitions between configurations. Each transition, or step, represents a single computational action, such as reducing an expression, updating a store, or changing control state. By chaining these steps, the complete execution of a program is modeled in fine-grained detail.

A configuration in small-step semantics typically captures the current program state, including the expression being evaluated, the environment, memory store, and control information. The step relation defines when one configuration can move to another in one minimal action. This granularity makes it easier to analyze intermediate states, reason about nonterminating or non-deterministic computations, and model features like memory management, control flow constructs, exceptions, and concurrent interleaving.

Formal properties associated with small-step systems include progress and preservation (type safety). Progress asserts that well-typed configurations are either values or can take a step, while preservation ensures that types are maintained across steps. These properties support rigorous proofs of program correctness and guide the design of programming languages and compilers.

Beyond theory, the term smallstep has also appeared in software practice as a project or tool name in areas related to formal methods, verification, and security infrastructure. The core idea remains the same: representing computation through explicit, incremental transitions to illuminate how programs execute.