CS 320: Homework 2 Operational Semantics Required problems: 3,5,6. Optional problems: 1,2,4.
Problem 1. Optional
Consider the following language L0:
constants program commands stack
const::int string
prog::com com;prog
com:: add div
S::type1v1; type2v2; ; type3vn
Due : Sunday, December 8, 23:59pm
wherev1,v2,,vn areconstantsintorstringandtypei int,string. Consider the following rules for add and div :
ADD
ADDERROR1
add ; p intv2::intv1::S p intv2 v1::S
add ; p p :error :::
ADDEMPTY
add ; p typev:: p :error :::typev::
add ; p stringv::S p :error :::stringv::S
ADDERROR2
add ; p intv2::stringv1::S p :error :::intv2::stringv1::S 1
ADDERROR3
v1 0
div; pintv2::intv1::Spintv2v1::S
DIV
DIV0
DIVERROR1
div ;
p intv2::int0::S p :error :::intv2::int0::S
div ; p p :error :::
DIVEMPTY
div ; p typev:: p :error :::typev::
DIVERROR2
DIVERROR3
div ;
where p is a program. We call a configuration p S final if no rule can be applied to it.
GiventhestackSint2; int3; int4; int0;int2; stringhello;,reduce,usingtherules above, the following configurations to final configurations.
add; add; divS
div; add; add; divS
add; add; add; add; addS
Given the stack S int0; int4; int2; int3; int4; int2, reduce, using the rules above, the following configurations to final configurations.
add; div; add; add; div; addS div; add; divS
2
div ; p stringv::S p :error :::stringv::S
p intv2::stringv1::S p :error :::intv2::stringv1::S
Problem 2. Optional
Consider the following language L1, which is an extension of L0 in Problem 1:
constants program commands stack
const::intstring
prog::com com;prog
com :: push const add div rem S::type1v1; type2v2; ; type3vn
wherev1,v2,,vn areconstantsintorstringandtypei int,string.
Design new rules for pop , push , rem , swap and neg satisfying the requirements given for the
interpreter assignment.
Given the stack S , reduce using the rules you designed the following configurations to final configurations.
push 7; push 8; neg S
push 7; neg ; swap S
push 2; push 4; rem S
push 0; push 4; rem S
push hello; push world; pop S push 2; push f oo; swap S
push2; push 3; pop; remS
Given the stack S , reduce using the rules you designed the following configurations to final configurations.
push7; push8; push 5; neg; add; add; push 8rem divS
push1; push3; div; neg; push8; push 4add; swap; pop; neg; push2;
rem ; push hello; push 8; add S
3
Problem 3. Consider, L3, a simplified version of the language for arithmetic expressions presented in class:
v1 v2 v
v1 add v2m vm
ADD
e add xm e add fetchx,mm
FETCHR
expressions operations terms memory fetch function
expr::expraddopterm term addop:: add
term::v Var
m::x1 v1;x2 v2xn vn
fetch : V ar m Z
where x1,x2,,xn are meta variables ranging over Var, and v1,v2,,vn are integers. Function fetch takes a variable v and a memory m and returning the value of the variable in the memory
Consider the following rules for add :
em e1m
FETCHL EVAL
x add vm fetchx,m add vm
em em em em
e add v2m e1 add v2m COMPOSE
em em
where e,e1,e2 are expressions. We call a configuration em final if no rule can be applied.
Given the memory m x 3,y 9,z 8, reduce using the rules the following configurations to final configurations.
4 add 9 add 8m
xadd3addyadd10addzm
4
Problem 4. Optional
Consider the following language L4 which is an extension of L3 in Problem 3:
expressions operations terms memory fetch function
expr::expropterm term op :: add minus mul term::v Var
m::x1 v1;x2 v2xn vn
fetch : V ar m Z
wherex1,x2,,xn aremetavariablesrangingoverVar,andv1,v2,,vn areintegers.
Design new rules for minus and mul by analogy to the rules for add .
Then given the memory m x 3;y 9;z 8, reduce, using the rules you designed, the following configurations to final configurations.
9 minus 8m
12 mul 2m
x add 3 minus 8 add y minus 10 minus zm xadd0minusymul3minuszmul5m
5
Problem 5. Consider the following language and the operational semantics:
M,c1 M,c1 M,c1;c2 M,c1 ;c2
M,x nMx n,skip Mx 0
M,if x then c1 else c2 M,c2 IF2
Commands Memory
c :: skip c;c x n if x then c else c M : V ar Z
x V ar
nZ
SEQ
M,skip;c M,c Mx0
SKIP
ASS
IF1
M,if x then c1 else c2M,c1 M,c M,c M,c M,c
M,c M,c
TRANS
Given the Memory: M x 5; y 7, reduce using the rules the following programs in the memory M to final configurations, and draw the trees associated to the derivations. By the notation Mx we mean the value associated with the variable x in M, while the notation Mx n represents the memory M updated with the mapping assigning n to x.
x 7;z 4;skip;w 9
ifxthenskipelsez6
ifxthenx4elsey7;z4;w9
x2;ifxthenx4elsey7;ifxthenz3elsew7;z4
6
Problem 6. Consider the following program:
void f1int z,int r
int k4r;
int uf27;
zzk;
printhello; here
int f2int x
int yx1;
return y
void f3int h
int y4h;
f1y,5;
void main
int z0;
f3z;
Draw the activation record stack with the instances active when executing the function main, which is avail able right before the print in f1. The information in the activation record consists of: return address, functional value, dynamic link, static link, parameters and local variables.
7