1
00:00:03,660 --> 00:00:08,399
This is the first of the series of videos
on programming language semantics and in

2
00:00:08,399 --> 00:00:12,624
particular on the semantics of cool,
Before we dive into technical details

3
00:00:12,624 --> 00:00:17,021
though I want to spend a few minutes
talking about what programming language

4
00:00:17,021 --> 00:00:24,571
semantics are and why we need them. The
problem we have to address is that we need

5
00:00:24,571 --> 00:00:29,798
some way to say what behavior we expect
when we run a Kuhl program. So, for every

6
00:00:29,798 --> 00:00:34,895
kind of Kuhl expression, for everyone we
have to say what happens when it's

7
00:00:34,895 --> 00:00:40,058
evaluated and we can regard this as the
meaning of the expression. Somehow, give

8
00:00:40,058 --> 00:00:45,024
rules to specify what a particular, what
kind of computation of a particular

9
00:00:45,024 --> 00:00:51,465
expression does. And I think it's useful
to look back and see how we dealt with

10
00:00:51,465 --> 00:00:58,232
this with similar problems in defining
other parts of cool, okay the earlier

11
00:00:58,232 --> 00:01:05,178
things that we looked at in this course.
So for example For Lexical Analysis we

12
00:01:05,178 --> 00:01:10,968
defined a family of family of tokens using
regular expressions And for the, the

13
00:01:10,968 --> 00:01:16,684
syntax of the language we used Context
Free Grammars to specify the, the

14
00:01:16,684 --> 00:01:22,913
structure of the, how words could be
strong together to form valid sentences in

15
00:01:22,913 --> 00:01:30,773
Kuhl And then for the semantic analysis we
gave formal typing rules And now we're to

16
00:01:30,773 --> 00:01:35,502
the point that we have to talk about how
the programs actually running so we have

17
00:01:35,502 --> 00:01:39,943
to give some evaluation rules and these
are going to guide how we do code

18
00:01:39,943 --> 00:01:44,615
generation of optimization or you going to
determine what the program should do and

19
00:01:44,615 --> 00:01:49,460
what kind of transformations we can do on
programs to make them run faster or use a

20
00:01:49,460 --> 00:01:53,958
space or what other, what any other kind
of optimization that we would like to

21
00:01:53,958 --> 00:01:59,103
perform. So far we've been specifying the
evaluation rules somewhat indirectly.

22
00:01:59,103 --> 00:02:04,316
We've been doing it by giving a complete
compilation strategy down to stack machine

23
00:02:04,316 --> 00:02:09,590
code and then we've been talking about the
evaluation rules for the stack machine or

24
00:02:09,590 --> 00:02:14,775
actually translation the stack machine
into assembly code And that is certainly a

25
00:02:14,775 --> 00:02:19,995
complete description. You can take the
generated assembly code and get it right

26
00:02:19,995 --> 00:02:24,885
out of the machine, and see what the
program do es and that would be a, a

27
00:02:24,885 --> 00:02:30,505
legitimate description of the behavior of
the program And the question then is, you

28
00:02:30,505 --> 00:02:35,014
know, why isn't that good enough. Why
isn't just having a code generator for the

29
00:02:35,014 --> 00:02:39,808
language. Why is that already a good
enough transcription of what how the code

30
00:02:39,808 --> 00:02:45,977
is supposed to be executed And The answer
to that is maybe a little hard to

31
00:02:45,977 --> 00:02:51,564
appreciate without having a written a few
compilers But in a nutshell, people have

32
00:02:51,564 --> 00:02:56,822
learned through hard experience that
assembly language descriptions of language

33
00:02:56,822 --> 00:03:02,225
implementations, language implementations,
have a lot of irrelevant detail. There's a

34
00:03:02,225 --> 00:03:06,762
lot of things that you have to say when
you get such a complete executable

35
00:03:06,762 --> 00:03:11,784
description that was not necessary to say
about how the program executes. So for

36
00:03:11,784 --> 00:03:16,201
example the fact that we use a stack
machine, that's not intrinsic to the

37
00:03:16,201 --> 00:03:20,437
implementation of any particular
programming language. There are other

38
00:03:20,437 --> 00:03:25,398
co-generation strategies that we could
have used so you know you don't have to do

39
00:03:25,398 --> 00:03:29,634
the stack machine to implement the
language which way the stack grows.

40
00:03:29,634 --> 00:03:34,474
Whether it grows towards high addresses or
low addresses you could implement it

41
00:03:34,474 --> 00:03:39,688
either way. How it, it, yeah, exact
representation of integers in a particular

42
00:03:39,688 --> 00:03:45,255
instructions actually used to execute or
to implement certain language constructs.

43
00:03:45,255 --> 00:03:50,705
All of these things are, are a, are one
way or, or one particular way to implement

44
00:03:50,705 --> 00:03:56,251
the language but we don't want them to, to
be taken as the only way that the language

45
00:03:56,251 --> 00:04:01,293
could be implemented. So, what we really
want than it has a complete description

46
00:04:01,293 --> 00:04:06,461
but one that is not overly restrictive One
that will allow a variety of different

47
00:04:06,461 --> 00:04:12,395
implementations. And when people have not
done this when people have not tried to

48
00:04:12,395 --> 00:04:17,667
find some relatively high level way of
describing the behavior of languages,

49
00:04:17,667 --> 00:04:23,355
they've been inevitably gotten into the
situation where they a, where people would

50
00:04:23,355 --> 00:04:29,390
just have to go and run the program on a
reference implementation or to decide what

51
00:04:29,390 --> 00:04:34,443
it does. And so this is not a very
satisfying a situation because of the

52
00:04:34,443 --> 00:04:39,211
reference implementation is not completely
correct itself. It will have bugs and

53
00:04:39,211 --> 00:04:44,037
there will be artifacts of the particular
way it was implemented that you didn't

54
00:04:44,037 --> 00:04:48,690
mean to be part of a language but because
there was no better definition wind up

55
00:04:48,690 --> 00:04:53,918
becoming fixed and have sort of accidents
of the way the language was implemented

56
00:04:53,918 --> 00:04:59,684
the first time. So there are many ways to
actually specify semantics that would be

57
00:04:59,684 --> 00:05:04,781
suitable for our task and it turns out
that these are all equally powerful but

58
00:05:04,781 --> 00:05:09,754
some of them are more suited to various
tasks than others so the one that we're

59
00:05:09,754 --> 00:05:14,415
going to be using is called operational
semantics. So operational semantics

60
00:05:14,415 --> 00:05:19,699
describes program evaluation via execution
roles on an abstract machine we just gave

61
00:05:19,699 --> 00:05:24,609
a bunch of rules that say you know from
particular expression how it should be

62
00:05:24,609 --> 00:05:29,760
executed. You can think of this as a very,
very high level kind of co-generation And

63
00:05:29,760 --> 00:05:34,459
this is most useful for specifying
implementations and it is what we're going

64
00:05:34,459 --> 00:05:41,676
to use to describe the semantics of Kuhl.
I want to mention two other ways of. Of

65
00:05:41,676 --> 00:05:47,425
specifying programming language semantics
because they're, they're important and you

66
00:05:47,425 --> 00:05:52,843
may come across them at some point outside
of this class. One is the notational

67
00:05:52,843 --> 00:05:58,460
semantics and here the programs meaning is
actually given as a mathematical function.

68
00:05:58,460 --> 00:06:03,944
So the program text is mapped to a
function that goes from input and outputs

69
00:06:03,944 --> 00:06:08,834
and this, this is, this function is an
actual function that exist in the

70
00:06:08,834 --> 00:06:14,864
mathematical sense And this is a very
elegant approach but it uses complexities

71
00:06:14,864 --> 00:06:20,459
into finding an appropriate class of
functions and we don't really need to

72
00:06:20,459 --> 00:06:26,123
consider for the purposes of just
describing an implementation. And another

73
00:06:26,123 --> 00:06:32,786
important approach is axiom semantics and
here program behaviors described in some

74
00:06:32,786 --> 00:06:38,521
kind of logic And the basic kinds of
statements that you write in this language

75
00:06:38,521 --> 00:06:44,002
or in this, in this in the axiomatic
semantics is that if execution begins in a

76
00:06:44,002 --> 00:06:49,282
state satisfying x, then it ends in the
state satisfying y where x and y are

77
00:06:49,282 --> 00:06:54,629
formulas in some logic And this is a very
common foundation for syst ems that

78
00:06:54,629 --> 00:07:00,110
analyze programs automatically that tries
to prove facts about programs either to

79
00:07:00,110 --> 00:07:03,920
prove they're correct or to discover bugs
in programs.