Understanding Computation Read Online Free Page B

parser should read a
     string like
y = x + 1
and turn it intoan
abstract syntax tree
(AST), a representation of the
     source code that discards incidental detail like whitespace and focuses on the hierarchical
     structure of the program.
    In the end, syntax is only concerned with the surface appearance ofprograms, not with their meanings. It’s possible for a program to be syntactically
     valid but not mean anything useful; for example, it might be that the program
y = x + 1
doesn‘t make sense on its own because it doesn’t say
     what
x
is beforehand, and the program
z = true + 1
might turn out to be broken when we run it because
     it’s trying to add a number to a Boolean value. (This depends, of course, on other properties
     of whichever programming language we’re talking about.)
    As we might expect, there is no “one true way” of explaining how the syntax of a
     programming language corresponds to an underlying meaning. In fact there are several different
     ways of talking concretely about what programs mean, all with different trade-offs between
     formality, abstraction, expressiveness, and practical efficiency. In the next few sections,
     we’ll look at the main formal approaches and see how they relate to each other.
    Operational Semantics
    The mostpractical way to think about the meaning of a program is what it does —when we run the program, what do we
    expect to happen? How do different constructs in the programming language
    behave at run time, and what effect do they have when they’re plugged
    together to make larger programs?
    This is the basis of
operational semantics
, a way of capturing the
     meaning of a programming language by defining rules for how its programs execute on some kind
     of device. This device is often an
abstract machine
: an imaginary, idealized computer that is designed for
     the specific purpose of explaining how the language’sprograms will execute. Different kinds ofprogramming language will usually require different designs of abstract machine in
     order to neatly capture their runtime behavior.
    By giving an operational semantics, we can be quite rigorous and precise about the purpose
     of particular constructs in the language. Unlike a language specification written in English,
     which might contain hidden ambiguities and leave important edge cases uncovered, a formal
     operational specification will need to be explicit and unambiguous in order to convincingly
     communicate the language’s behavior.
    Small-Step Semantics
    So, how can wedesign an abstract machine and use it to specify the
     operational semantics of a programming language? One way is to imagine a
     machine that evaluates a program by operating on its syntax directly,
     repeatedly
reducing
it in small steps, with each
     step bringing the program closer to its final result, whatever that
     turns out to mean.
    These small-stepreductions are similar to the way we are taught in school to evaluate algebraic
     expressions. For example, to evaluate (1 × 2) + (3 × 4), we know we should:
    Perform the left-hand multiplication (1 × 2 becomes 2) and reduce the expression to
     2 + (3 × 4)
Perform the right-hand multiplication (3 × 4 becomes 12) and reduce the expression
     to 2 + 12
Perform the addition (2 + 12 becomes 14) and end up with 14
    We can think of 14 as the result because it can’t be reduced any further by this
     process—we recognize 14 as a special kind of algebraic expression, a
value
, which has its own meaning and doesn’t require
     any more work on our part.
    This informal process can be turned into an operational semantics
     by writing down formal rules about how to proceed with each small
     reduction step. These rules themselves need to be written in somelanguage (the
metalanguage
), which
     is usually mathematical notation.
    In this chapter, we’re going to explore the semantics of a toy programming
     language—let’s call it Simple . [ 4 ] The mathematical description of Simple ’s