The While Programming Language
he Three Cs of
-
Computer Science What is a computer ?
1. Does
program Pr and Pa that
a both compute a
function ,
f
Complexity A thing that compute...
which one is better ?
.
2 Does Correctness
a
program p correctly compute a
function fu
.
3 What functions can we compute ? i e
.
. are there functions that Computability
cannot be computed by any program ?
Do we need a
computer for Computation ?
No !
The While
Programming Language
Semantics What a
Meaning of a
program what function it
computes
:
program means
Define what it means to interpret execute programs Operational
Syntax : The
form that programs are allowed to take We
focus on these
Define a
program by what it provably does Axiomatic
All languages have will defined
a
syntax
Transform other metalanguage Denotational
Very few have a
formal semantics programs
into some
Syntax given as a
grammar Semantics of the Language
.
5 v := alskip)Seise if then Sy else Se while b do s We need : Weintroduce a relation - on
programs and states :
b : true false an = as an Ea2 it b, "be
·
Represent current values of variables (State
a : In a, +as a, -de a, a2
·
Evaluate arithmetic and logical expressions Si G
A
↓ Sid
·
program state
·
Show how program statements transform state
S =
Statements (Stm) S , 019, 01 ...
15
b =
Boolean Expression (BExp) State = Var 1 > I
a =
Arithmetic Expressions (AExp) D 5
X =
Variables Y 7 [ -1) 5 4117 2110] , ,
I
maps to ...
n =
Numerals Z O
Use () to remove ambiguities Examples
[x + <
3 , y1 ,
2](x) = 3 ([x . < 3) [x ·,
2] (x) =
3 [24y](x) =
?
o(x) · (x) = 2 Y + T
= 3
[2H 3)
[NYIST
· 1 , y H 2 ,
2 -
I
not state (0 ( y +
47)(y) =
3 (0[2 +])(2) + =
4
Y = 4 x = 1
(0[X ++
2))(v) =
3
v = 0 not defined variables default to 0
o this
The Transition System is in the !
given exam
[ass] [Skip]
!
[2 : = 1
,
[]) <2 : = x +y, [X +
1]) < Skip ,
[x ++ 3, y >
2]
IJAIS
↓ [x
↓ +
1][z1)1] ↓ [2 3, y + .
2
S - [x + 1
,
24 1]
- [] [11 <
I
-[2 H
1]
, [iffetiff] b is true
,
then use iffet b is false , then use iffff [while]
if two then [J] *
else [J) While (y < 1) do (y : y + 2) [y Y
1 else
~
,
z := v : = 2
,
if xx then X := 1 v : = 2 = + 2]
10
,
I
So
,
9b Si Sa 9b Si
WE While (y < 1) do (y : =
y + 2)
S2
-
↓ (v : = 1
, []Y (iftt) ↓ [v : = 2, [JY lifff) ↓ (if (y <1) than (4 :=
y +2
; W) also ship [y
,
+
2]) [while]
[ifff]
Si
↓ [2H 1] (ass) ↓ [2 + 2] (ass) ↓ (skip [y ,
+ 2])
↓ [y +
2] [Skip]
[comp]
!!!
(2 := 10 = x +1
, []
Rewrite ! Alternative !
[x : = 1
,
[3)][X +
1] X(x := x +1
,
[x +
1]) [ass]
[comp2]
[ : = 1 ; k : = x +1
, [])X(k := x + 1 ,
[x +
1]) ↓ [x +
2] [ass]
he Three Cs of
-
Computer Science What is a computer ?
1. Does
program Pr and Pa that
a both compute a
function ,
f
Complexity A thing that compute...
which one is better ?
.
2 Does Correctness
a
program p correctly compute a
function fu
.
3 What functions can we compute ? i e
.
. are there functions that Computability
cannot be computed by any program ?
Do we need a
computer for Computation ?
No !
The While
Programming Language
Semantics What a
Meaning of a
program what function it
computes
:
program means
Define what it means to interpret execute programs Operational
Syntax : The
form that programs are allowed to take We
focus on these
Define a
program by what it provably does Axiomatic
All languages have will defined
a
syntax
Transform other metalanguage Denotational
Very few have a
formal semantics programs
into some
Syntax given as a
grammar Semantics of the Language
.
5 v := alskip)Seise if then Sy else Se while b do s We need : Weintroduce a relation - on
programs and states :
b : true false an = as an Ea2 it b, "be
·
Represent current values of variables (State
a : In a, +as a, -de a, a2
·
Evaluate arithmetic and logical expressions Si G
A
↓ Sid
·
program state
·
Show how program statements transform state
S =
Statements (Stm) S , 019, 01 ...
15
b =
Boolean Expression (BExp) State = Var 1 > I
a =
Arithmetic Expressions (AExp) D 5
X =
Variables Y 7 [ -1) 5 4117 2110] , ,
I
maps to ...
n =
Numerals Z O
Use () to remove ambiguities Examples
[x + <
3 , y1 ,
2](x) = 3 ([x . < 3) [x ·,
2] (x) =
3 [24y](x) =
?
o(x) · (x) = 2 Y + T
= 3
[2H 3)
[NYIST
· 1 , y H 2 ,
2 -
I
not state (0 ( y +
47)(y) =
3 (0[2 +])(2) + =
4
Y = 4 x = 1
(0[X ++
2))(v) =
3
v = 0 not defined variables default to 0
o this
The Transition System is in the !
given exam
[ass] [Skip]
!
[2 : = 1
,
[]) <2 : = x +y, [X +
1]) < Skip ,
[x ++ 3, y >
2]
IJAIS
↓ [x
↓ +
1][z1)1] ↓ [2 3, y + .
2
S - [x + 1
,
24 1]
- [] [11 <
I
-[2 H
1]
, [iffetiff] b is true
,
then use iffet b is false , then use iffff [while]
if two then [J] *
else [J) While (y < 1) do (y : y + 2) [y Y
1 else
~
,
z := v : = 2
,
if xx then X := 1 v : = 2 = + 2]
10
,
I
So
,
9b Si Sa 9b Si
WE While (y < 1) do (y : =
y + 2)
S2
-
↓ (v : = 1
, []Y (iftt) ↓ [v : = 2, [JY lifff) ↓ (if (y <1) than (4 :=
y +2
; W) also ship [y
,
+
2]) [while]
[ifff]
Si
↓ [2H 1] (ass) ↓ [2 + 2] (ass) ↓ (skip [y ,
+ 2])
↓ [y +
2] [Skip]
[comp]
!!!
(2 := 10 = x +1
, []
Rewrite ! Alternative !
[x : = 1
,
[3)][X +
1] X(x := x +1
,
[x +
1]) [ass]
[comp2]
[ : = 1 ; k : = x +1
, [])X(k := x + 1 ,
[x +
1]) ↓ [x +
2] [ass]
