Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterTransition Semantics• Form of operational semantics• Describes how each program construct transformsmachine state by transitions• Rules look like(C, m) --> (C’, m’)• C, C’ is code remaining to be executed• m, m’ represent the state/store/memory/environment– Partial mapping from identifiers to values– Sometimes m (or C) not needed• Indicates exactly one step of computationElsa L. GunterExpressions and Values• Special class of expressions designated asvalues– Eg 2, 3 are values, but 2+3 is only an expression• Memory only holds values• Transitions or E stop when E is a value• Value is the final meaning of original expression(in the given state)• C, C’ used for commands; E, E’ for expressions;U,V for valuesElsa L. GunterSimple ImperativeProgramming Language• I ∈ Identifiers• N ∈ Numerals• B ::= true | false | B & B | B or B | not B| E < E | E = E• E::= N | I | E + E | E * E | E - E | - E• C::= skip | C;C | I ::= E| if B then C else C fi | while B do C odElsa L. GunterTransitions for Expressions• Identifiers: (I,m) --> m(I)• Numerals are values: (N,m) --> N• Notation - Function update:• m[I<--V] = λ y. if y = I then V else m(y)Elsa L. GunterBooleans:• Values = {true, false}• Operators: (short-circuit)(false & B, m) --> false (B, m) --> (B’’, m)(true & B, m) --> (B,m) (B & B’, m) --> (B’’ & B, m)(true or B, m) --> true (B, m) --> (B’’, m)(false or B, m) --> (B,m) (B or B’, m) --> (B’’ or B, m)(not true, m) --> false (B, m) --> (B’, m)(not false, m) --> true (not B, m) --> (not B’, m)Elsa L. GunterRelations(E, m) --> (E’’,m)(E ~ E’, m) --> (E’’~E’,m)(E, m) --> (E’,m) (V ~ E, m) --> (V~E’,m)(U ~ V, m) --> true or false, depending onwhether U ~ V holds or notElsa L. GunterArithmetic Expressions(E, m) --> (E’’,m)(E op E’, m) --> (E’’ op E’,m)(E, m) --> (E’,m) (V op E, m) --> (V op E’,m)(U op V, m) -->N where N is thespecified value for U op VElsa L. GunterCommands - in English• skip is done evaluating• When evaluating an assignment, evaluate theexpression first• If the expression being assigned is already avalue, update the memory with the new value forthe identifier• When evaluating a sequence, work on the firstcommand in the sequence first• If the first command evaluates to a new memory(ie completes), evaluate remainder with newmemoryElsa L. GunterCommands(skip, m) --> m(E,m) --> (E’,m)(I::=E,m) --> (I::=E’,m)(I::=V,m) --> m[I <-- V ](C,m) --> (C’’,m’) (C,m) --> m’(C;C’, m) --> (C’’;C’, m’) (C;C’, m) --> (C’, m’)Elsa L. GunterIf Then Else Command - inEnglish• If the boolean guard in anif_then_else is true, then evaluatethe first branch• If it is false, evaluate the secondbranch• If the boolean guard is not a value,then start by evaluating it first.Elsa L. GunterIf Then Else Command(if true then C else C’ fi, m) --> (C, m)(if false then C else C’ fi, m) --> (C’, m)(B,m) --> (B’,m)(if B then C else C’ fi, m)--> (if B’ then C else C’ fi, m)Elsa L. GunterWhile Command(while B do C od, m)--> (if B then C;while B do C od else skip fi, m)In English: Expand a While into a test of the booleanguard, with the true case being to do the body andthen try the while loop again, and the false casebeing to stop.Elsa L. GunterExample Evaluation• First step:(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x > 5, {x -> 7}) --> ?(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x,{x -> 7}) --> 7(x > 5, {x -> 7}) --> ?(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x,{x -> 7}) --> 7(x > 5, {x -> 7}) --> (7 > 5, {x -> 7})(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x,{x -> 7}) --> 7(x > 5, {x -> 7}) --> (7 > 5, {x -> 7})(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> (if 7 > 5 then y:=2 + 3 else y:=3 + 4 fi,{x -> 7})Elsa L. GunterExample Evaluation• Second Step:(7 > 5, {x -> 7}) --> true(if 7 > 5 then y:=2 + 3 else y:=3 + 4 fi,{x -> 7})--> (if true then y:=2 + 3 else y:=3 + 4 fi, {x -> 7})• Third Step:(if true then y:=2 + 3 else y:=3 + 4 fi, {x -> 7}) -->(y:=2+3, {x->7})Elsa L. GunterExample Evaluation• Fourth Step: (2+3, {x-> 7}) --> 5(y:=2+3, {x->7}) --> (y:=5, {x->7})• Fifth Step:(y:=5, {x->7}) --> {y -> 5, x -> 7}Elsa L. GunterExample Evaluation• Bottom Line:(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi,{x -> 7})--> (if 7 > 5 then y:=2 + 3 else y:=3 + 4 fi,{x -> 7})-->(if true then y:=2 + 3 else y:=3 + 4 fi,{x -> 7}) -->(y:=2+3, {x->7}) --> (y:=5, {x->7}) --> {y -> 5, x -> 7}Elsa L. GunterTransition SemanticsEvaluation• A sequence of steps with trees ofjustification for each step(C1,m1) --> (C2,m2) --> (C3,m3) --> … --> m• Let -->* be the transitive closure of -->• Ie, the smallest transitive relationcontaining -->Elsa L. GunterAdding Local Declarations• Add to expressions:• E ::= … | let I = E in E’ | fun I -> E | E E’• fun I -> E is a value• Could handle local binding using state,but have assumption that evaluatingexpressions doesn’t alter theenvironment• We will use substitution here instead• Recall: E [E’ / I ] means replace all freeoccurrence of I by E’ in EElsa L. GunterCall-by-value (Eager Evaluation)(let I = V in E, m) --> (E[V/ I ],m)(E, m) --> (E’’,m)(let I = E in E’, m) --> (let I = E’’ in E’)((fun I -> E) V, m) --> (E[V / I ],m)(E’, m) --> (E’’,m)((fun I -> E) E’, m) --> ((fun I -> E) E’’, m)Elsa L. GunterCall-by-name (Lazy Evaluation)• (let I = E in E’, m) --> (E’[E / I ],m)• ((fun I -> E’) E, m) --> (E’[E / I ],m)• Question: Does it make adifference?• It can depending on the languageElsa L. GunterChurch-Rosser Property• Church-Rosser Property: If E-->* E1and E-->* E2, if there exists a value Vsuch that E1 -->V, then E2 --> V• Also called confluence or diamondproperty• Example: E= 2 + 3 + 4 E1 = 5 + 4 E2= 2 + 7 V =9Elsa L. GunterDoes It always Hold?• No. Languages with side-effects
View Full Document
Unlocking...