the
future” and prevent us from trying to execute any program that has the potential to blow
up or get stuck. This chapter isabout
dynamic semantics
—what a program does when it’s
executed—but that’s not the only kind of meaning that a program can have; in Chapter 9 , we’ll investigate
static semantics
to see how we can decide whether a syntactically
valid program has a useful meaning according to the language’s dynamic semantics.
Applications
The programminglanguagewe’ve specified is very basic, but in writing down all the reduction rules,
we’ve still had to make some design decisions and express them unambiguously. For example,
unlike Ruby, Simple is a language that makes a
distinction between expressions, which return a value, and statements, which don’t; like
Ruby, Simple evaluates expressions in a left-to-right
order; and like Ruby, Simple ’s environments associate
variables only with fully reducedvalues, not with larger expressions that still have some unfinished
computation to perform. [ 12 ] We could change any of these decisions by giving a different small-step
semantics which would describe a new language with the same syntax but different runtime
behavior. If we added more elaborate features to the language—data structures, procedure
calls, exceptions, an object system—we’d need to make many more design decisions and
express them unambiguously in the semantic definition.
The detailed, execution-oriented style of small-step semantics lends itself well to
the task of unambiguously specifying real-world programming languages. For example, the
latest R6RS standard for theScheme programming language uses small-step semantics to describe its execution, and provides a reference implementation of those semantics writtenin PLT Redex , “a
domain-specific language designed for specifying and debugging operational semantics.” The
OCaml programming language, whichis built as a series of layers on top of a simpler language called Core ML,
also has a small-step semantic definition of the base language’s runtime behavior.
See Semantics for another example of using
small-step operational semantics to specify the meaning of expressions in an even simpler
programming language called the lambdacalculus.
Big-Step Semantics
We’ve now seenwhat small-step operational semantics looks like: we design an abstract machine
that maintains some execution state, then define reduction rules that specify how each kind
of program construct can make incremental progress toward being fully evaluated. In
particular, small-step semantics has a mostly iterative flavor,
requiring the abstract machine to repeatedly perform reduction steps (the Ruby
while
loop in
Machine#run
)
that are themselves constructed to produce as output the same kind of information that they
require as input, making them suitable for this kind of repeated application. [ 13 ]
The small-step approach has the advantage of slicing up the complex business of
executing an entire program into smaller pieces that are easier to explain and analyze, but
it does feel a bit indirect: instead of explaining how a whole program construct works, we
just show how it can be reduced slightly. Why can’t we explain a statement more directly, by
telling a complete story about how its execution works? Well, we can, and that’s the basis
of
big-step semantics
.
The idea of big-step semantics is to specify how to get from an
expression or statement straight to its result. This necessarily
involves thinking about program execution as a recursive rather than an iterative process:
big-step semantics says that, to evaluate a large expression, we
evaluate all of its smaller subexpressions and then combine their
results to get our final answer.
In many ways, this feels more natural than the small-step approach, but it does lack
some of its fine-grained attention to detail. For example,
future” and prevent us from trying to execute any program that has the potential to blow
up or get stuck. This chapter isabout
dynamic semantics
—what a program does when it’s
executed—but that’s not the only kind of meaning that a program can have; in Chapter 9 , we’ll investigate
static semantics
to see how we can decide whether a syntactically
valid program has a useful meaning according to the language’s dynamic semantics.
Applications
The programminglanguagewe’ve specified is very basic, but in writing down all the reduction rules,
we’ve still had to make some design decisions and express them unambiguously. For example,
unlike Ruby, Simple is a language that makes a
distinction between expressions, which return a value, and statements, which don’t; like
Ruby, Simple evaluates expressions in a left-to-right
order; and like Ruby, Simple ’s environments associate
variables only with fully reducedvalues, not with larger expressions that still have some unfinished
computation to perform. [ 12 ] We could change any of these decisions by giving a different small-step
semantics which would describe a new language with the same syntax but different runtime
behavior. If we added more elaborate features to the language—data structures, procedure
calls, exceptions, an object system—we’d need to make many more design decisions and
express them unambiguously in the semantic definition.
The detailed, execution-oriented style of small-step semantics lends itself well to
the task of unambiguously specifying real-world programming languages. For example, the
latest R6RS standard for theScheme programming language uses small-step semantics to describe its execution, and provides a reference implementation of those semantics writtenin PLT Redex , “a
domain-specific language designed for specifying and debugging operational semantics.” The
OCaml programming language, whichis built as a series of layers on top of a simpler language called Core ML,
also has a small-step semantic definition of the base language’s runtime behavior.
See Semantics for another example of using
small-step operational semantics to specify the meaning of expressions in an even simpler
programming language called the lambdacalculus.
Big-Step Semantics
We’ve now seenwhat small-step operational semantics looks like: we design an abstract machine
that maintains some execution state, then define reduction rules that specify how each kind
of program construct can make incremental progress toward being fully evaluated. In
particular, small-step semantics has a mostly iterative flavor,
requiring the abstract machine to repeatedly perform reduction steps (the Ruby
while
loop in
Machine#run
)
that are themselves constructed to produce as output the same kind of information that they
require as input, making them suitable for this kind of repeated application. [ 13 ]
The small-step approach has the advantage of slicing up the complex business of
executing an entire program into smaller pieces that are easier to explain and analyze, but
it does feel a bit indirect: instead of explaining how a whole program construct works, we
just show how it can be reduced slightly. Why can’t we explain a statement more directly, by
telling a complete story about how its execution works? Well, we can, and that’s the basis
of
big-step semantics
.
The idea of big-step semantics is to specify how to get from an
expression or statement straight to its result. This necessarily
involves thinking about program execution as a recursive rather than an iterative process:
big-step semantics says that, to evaluate a large expression, we
evaluate all of its smaller subexpressions and then combine their
results to get our final answer.
In many ways, this feels more natural than the small-step approach, but it does lack
some of its fine-grained attention to detail. For example,
Similar Books
