This is the first of the series of videos
on programming language semantics and in
particular on the semantics of cool,
Before we dive into technical details
though I want to spend a few minutes
talking about what programming language
semantics are and why we need them. The
problem we have to address is that we need
some way to say what behavior we expect
when we run a Kuhl program. So, for every
kind of Kuhl expression, for everyone we
have to say what happens when it's
evaluated and we can regard this as the
meaning of the expression. Somehow, give
rules to specify what a particular, what
kind of computation of a particular
expression does. And I think it's useful
to look back and see how we dealt with
this with similar problems in defining
other parts of cool, okay the earlier
things that we looked at in this course.
So for example For Lexical Analysis we
defined a family of family of tokens using
regular expressions And for the, the
syntax of the language we used Context
Free Grammars to specify the, the
structure of the, how words could be
strong together to form valid sentences in
Kuhl And then for the semantic analysis we
gave formal typing rules And now we're to
the point that we have to talk about how
the programs actually running so we have
to give some evaluation rules and these
are going to guide how we do code
generation of optimization or you going to
determine what the program should do and
what kind of transformations we can do on
programs to make them run faster or use a
space or what other, what any other kind
of optimization that we would like to
perform. So far we've been specifying the
evaluation rules somewhat indirectly.
We've been doing it by giving a complete
compilation strategy down to stack machine
code and then we've been talking about the
evaluation rules for the stack machine or
actually translation the stack machine
into assembly code And that is certainly a
complete description. You can take the
generated assembly code and get it right
out of the machine, and see what the
program do es and that would be a, a
legitimate description of the behavior of
the program And the question then is, you
know, why isn't that good enough. Why
isn't just having a code generator for the
language. Why is that already a good
enough transcription of what how the code
is supposed to be executed And The answer
to that is maybe a little hard to
appreciate without having a written a few
compilers But in a nutshell, people have
learned through hard experience that
assembly language descriptions of language
implementations, language implementations,
have a lot of irrelevant detail. There's a
lot of things that you have to say when
you get such a complete executable
description that was not necessary to say
about how the program executes. So for
example the fact that we use a stack
machine, that's not intrinsic to the
implementation of any particular
programming language. There are other
co-generation strategies that we could
have used so you know you don't have to do
the stack machine to implement the
language which way the stack grows.
Whether it grows towards high addresses or
low addresses you could implement it
either way. How it, it, yeah, exact
representation of integers in a particular
instructions actually used to execute or
to implement certain language constructs.
All of these things are, are a, are one
way or, or one particular way to implement
the language but we don't want them to, to
be taken as the only way that the language
could be implemented. So, what we really
want than it has a complete description
but one that is not overly restrictive One
that will allow a variety of different
implementations. And when people have not
done this when people have not tried to
find some relatively high level way of
describing the behavior of languages,
they've been inevitably gotten into the
situation where they a, where people would
just have to go and run the program on a
reference implementation or to decide what
it does. And so this is not a very
satisfying a situation because of the
reference implementation is not completely
correct itself. It will have bugs and
there will be artifacts of the particular
way it was implemented that you didn't
mean to be part of a language but because
there was no better definition wind up
becoming fixed and have sort of accidents
of the way the language was implemented
the first time. So there are many ways to
actually specify semantics that would be
suitable for our task and it turns out
that these are all equally powerful but
some of them are more suited to various
tasks than others so the one that we're
going to be using is called operational
semantics. So operational semantics
describes program evaluation via execution
roles on an abstract machine we just gave
a bunch of rules that say you know from
particular expression how it should be
executed. You can think of this as a very,
very high level kind of co-generation And
this is most useful for specifying
implementations and it is what we're going
to use to describe the semantics of Kuhl.
I want to mention two other ways of. Of
specifying programming language semantics
because they're, they're important and you
may come across them at some point outside
of this class. One is the notational
semantics and here the programs meaning is
actually given as a mathematical function.
So the program text is mapped to a
function that goes from input and outputs
and this, this is, this function is an
actual function that exist in the
mathematical sense And this is a very
elegant approach but it uses complexities
into finding an appropriate class of
functions and we don't really need to
consider for the purposes of just
describing an implementation. And another
important approach is axiom semantics and
here program behaviors described in some
kind of logic And the basic kinds of
statements that you write in this language
or in this, in this in the axiomatic
semantics is that if execution begins in a
state satisfying x, then it ends in the
state satisfying y where x and y are
formulas in some logic And this is a very
common foundation for syst ems that
analyze programs automatically that tries
to prove facts about programs either to
prove they're correct or to discover bugs
in programs.