Programming Languages ECS 240
Popular in Course
Popular in Engineering Computer Science
This 121 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 240 at University of California - Davis taught by Zhendong Su in Fall. Since its upload, it has received 46 views. For similar materials see /class/187740/ecs-240-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Programming Languages
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/08/15
Dam Flow Analysis Lecture 13 ECS 240 E05240 DauFlnwAmJysls The Plan 39 Infroduce a few example analyses 39 Generalize To see The underlying Theory 39 Discuss some more advanced issues 555 240 Data FlnwAmJyms Confrol Flow Graphs xab ab whileygtab aquota1 am rar Hawymphs are 5mm Vansmm sysfems ms 240 Data FlnwAmJyms Nomfion s is a statement succs successar sfafemenfs 0f 5 preds predecessor sfafemenfs 0f 5 wri ies variables wriffen by s reads variables read by s Kis fac is killed by sfcriemen i s Gens fads genera ied by sTaTemen i 5 ms 240 Data FinwAmJyms A Liveness Analysis For each program point 39 h some execution path Optimization If a variable is not live no need To keep it in a register ms 240 Data FinwAmJyms 5 Example ms 240 Data FinwAmJyms 5 Dafaflow Equafions Lquot s Ln s wrires u read s Q if succs Q ALquot 5 U LM 539 ofher wise s39E uccG Available Expressions modified on all paths Ta Optimization Where available expressions need not be recampufed ms 240 Data FlnwAmJyms 2 Example ms 240 Data FlnwAmJyms 9 Dafaflow Equafions Q if preds Q Am5 Ams o rherwise gt S Epred 5 Aaurs Ams a 65 erres la g gt Us I if wrlfes rems Q 555 240 Data FlnwAmJyms m Available Expressions Schem afic W Transfer fme mm s 755 C1 U 6392 Must analysts properUhods on all paths Forwards analysis from Inputs fa outputs ms 240 Data FlnwAmJyms n Live Variables Again Lquot s 4quot s wrires u read s Q if succs Q 145 U LM 5 ofher wise s 39Ewcc s ms 240 Data FlnwAmJyms 12 Live Variables Schem afic Transfer fme flan 655 5 C1 U 6392 M May analysts property holds on some path Backwards analysis from outputs fa mpurs ms 240 Data FinwAmJyms 13 Very Busy Expressions 39 An expression 6 is very busy at program point p if every path from p must evaluate e before any variable in e is redefined 39 Opfimiza iion hois iing expressions 39 A must analysis 39 A backwards analysis 555 240 Data FinwAmJyms 14 Reaching Definifions 39 For a program point p which assignmen is made on paths reaching p have not been overwrif ien 39 Connec is definifions wifh uses use def chains 39 A may anlaysis 39 A forwards analysis 555 240 Data FinwAmJyms 15 One Cuf of ue Dafaflow Design Space May Must Forwards Reaching vailable definitions expressions Backwards Live variables Very busy expressions 05 240 mymmm m The Liferafure 39 Vas39i literature of da iaflow analyses 39 90 can be described by Forwards or backwards May or must 39 Some oddballs but not many Bidirectional analyses ms 240 Data FlnwAmJyms l7 Ano ier Cuf of Dafaflow Design 39 Wha i Theory are we dealing with RCVlCW GUIquot SCl39iClTlClS Am5 nAvursl Ln5Luur5 61UC2 y Epred y AmsAms C1UC2 laurs U MS39 S39Esucc5 ms 240 Data FlnwAmJyms 12 Essential Features 39 Set variables Lquots LouS 39 Set operations union intersection Restricted complement constant 39 Domain of atoms E 9 variable names 39 Equations with single variable on lhs ms 240 Data FlnwAmJyms w Dataflow Problems 39 Many datatlow equations are described by the grammar EQ5 gtVEEQ5 EeE EIEUEllIa 39 v is a variable 39 a is an atom 39 Note More general than most problems mm mymmws 2n Solving Dataflow Equations 39 Simple worklist algorithm Initially let Sv 0 for all v Repeat until Sv SE for all equations P c unyv E such that 500 55 Set 5 sv5E ms 240 Data FlnwAmJyms 21 Term inafion 39 How do we know The algoriThm TerminaTes 39 Because operaTions are monotonic The domain is finiTe ms 240 Dam FlnwAmJyms Monofonicify OperaTion fis monoTonic if XS Ygt fXlt y 39 We require ThaT all operaTions be monoTonic Easy To check for The seT operaTions Easy To check for a Transfer funcTions recall ms Lamcl we ms 240 Dam FlnwAmJyms Term inafion again 39 To see The algoriThm TerminaTes All variables sTarT empTy Variables and rhs39s only increase wiTh each updaTe By induction on t of updates using monotonicity SeTs can only grow To a max finiTe size 39 TogeTher These imply TerminaTion ms 240 Dam FlnwAmJyms The Res of ue Lecfur e 39 Dis iribu iive Problems 39 Flow Sensi iivi iy 39 Confex i Sensi iivi iy Or inferprocedural analysis 39 What are The limi is of da iaflow analysis 555 240 Data FlnwAmJyms 25 Distribufive Dafaflow Problems 39 Mono ionici iy implies for a Transfer function 1 fx U y 2 fx U fy 39 Dis iribu iive da iaflow problems satisfy a stronger proper iy fx U y fx U fy ms 240 Data FlnwAmJyms 25 Distribufivify Example khf0 Ug0 The analysis of The lgraph is e LIiva em To corn inin ka w U haw Theinalysis of each pathsl k7f0 U kh90 ms 240 Data FlnwAmJyms 27 Meef Over All Pafhs 39 If a daTaflow problem is disTribuTive Then The leasT soluTion of The daTaflow equaTions is equivalenT To The analyzing every paTh including infiniTe ones and combining The 39 Says Joins cause no loss of informaTion ms 240 Data FlnwAmJyms 22 Distribufivify Again 39 ObTaining The meeT over all paThs soluTion is a very powerful guaranTee 39 Says ThaT daTaflow analysis is really as good as you can do for a disTribuTive problem 39 AlTernaTively can be viewed as saying disTribuTive problems are very easy indeed ms 240 Data FlnwAmJyms 29 Whaf Problems are Disfribufive 39 Many analyses of program sTrucTure are disTribuTive Eg live variables available expressions reaching definiTians very busy express39ans PraperTies of how The program campuTes ms 240 Data FlnwAmJyms 3n Liveness Example Revisited ab 39 X Xab quot X yab gt yab quot Xyab o mb x I a b ECS 240 Data Flow Analysis 31 Constant Folding Ordering i ltT for any integer i le k T if 2 k Example Transfer function CV 2 e1 X620 0V e Cela CeZ0 a x b if a b constants where 0 69 b u otherwnse Consider 02 1 y yy 1 U062 1 y yy 1 Cz 1 y yy 1 U y 1 ECS 240 Data Flow Analysis 32 What Problems are Not Distributive 39 Analyses of What the program computes The output is a constant positive ECS 240 Data Flow Analysis 33 Flow Sensitivity 39 Flow sensitive analyses The order of statements matters Need a control flow grap Or transition system 39 Flow insensitive analyses The order of statements doesn39t matter Analysis is the same regardless of statement order 555 240 Data FlnwAmJyms 34 Example Flow Insensitive Analysis 39 What variables does a program fragment modify 6x e X 65132 651 U 652 Note 65132 65231 ms 240 Data FlnwAmJyms 35 The Advantage 39 Flow sensitive analyses require a model of program state at each program point Eg liveness analysis reaching definitions 39 Flow insensitive analyses require only a single global state E g for G the set of all variables modified ms 240 Data FlnwAmJyms 35 Notes on Flow Sensitivity 39 Flow insensitive analyses seem weak but 39 Flow sensitive analyses are hard to scale to very large programs Additional cast state size X of program points 39 Beyond 100039s of lines of code only flow insensitive analyses have been shown to scale ms 240 Data FlnwAmJyms 37 Context Sensitive Analysis 39 What about analyzing across procedure boundaries Def fgtlt Def gyfa Def hzfb 39 Goal Specialize analysis of f to take advantage 0 39 f is called with a by g 39 f is called with b by h 555 240 Data FlnwAmJyms 32 Control Flow Graphs Again 39 How do we extend control flow graphs to procedures 39 Idea Model procedure call fa by Edge from point before call to entry of f Edge from exits of f to point after call 555 240 Data FlnwAmJyms 39 Example Edges from before fu to entry of f Exit of f to after fb ms 240 Duh FlnwAmJyms Example Edges from before fu to entry of f Exit of f to after fu Before fb to entry of f Exit of f to after fb Has The correct flows ms 240 Duh FlnwAmJyms Example Edges 1 am before fu to entry of f Exit of f to after fu Before fb to entry of f Exit of f to after fb Has The correct flows for h ms 240 Duh FlnwAmJyms Example But also has flows we don39t want One path captures u call to 9 return rig at h Socolled infeasible pathsquot ms 240 Data FinwAmJyms What to do 39 Must distinguish calls to f in different contexts 39 Three Techniques Assumptions 39 later Contextfree reochobility 39 Later Cull strings Today ms 240 Data FinwAmJyms Call Strings 39 Observation At run time different calls to f are distinguished by the call stack 39 Problem The stock is unbounded 39 Idea Use the last k calls on the stack to distinguish contex epresent a call by the name of the calling procedure 555 240 Data FinwAmJyms Example Revisifed Use call sTrings of length 1 Context is name of calling procedure Nofe labels on edge are parf of fhesfafe my a call Wm quoton call ram 9 porfion of the state with callsfriny quotg on refurn from go to 0 ms 240 Data FlnwAmJyms Experience wifh Call Sfrings 39 Very expensive Multiplies of abstract values by of procedures quot length of call string Hard To contemplate call strings gt1 39 Fragile Very sensiTive To organization of procedures 39 Well sfudied bu i not much used in practice ms 240 Data FlnwAmJyms 47 Review of Terminology Mus l vs May Forwards vs Backwards Flow sensi live vs Flow insensi live ConTex i sensi live vs Con lexT insensi live Dis iribu live vs non Dis iribu live ms 240 Data FlnwAmJyms Where is Dataflow Analysis Useful Best for flow sensitive context insensitive distributive problems on small pieces of code E g the examples we39ve seen and many others 39 Extremely efficient algorithms are known Use different representation than controlflow graph but not fundamentally different More on this in a minute ms 240 Data FlnwAmJyms 49 Where is Dataflow Analysis Weak 39 Lots of places ms 240 Data FlnwAmJyms 5n Data Structures 39 Not good at analyzing data structures 39 Works well for atomic values Labels constants variable names 39 Not easily extended to arrays lists trees etc Work on shape analysis 555 240 Data FlnwAmJyms 51 The Heap 39 Good aT analyzing flow of values in local variables 39 No noTion of The heap in TradiTional daTaflow applications 39 In general very hard To model anonymous values accura ely Aliasin The strong updatequot roblem mm inFlnwAmJyms 52 Confexf Sensifivify 39 STandard da raflow Techniques for handling con rex r sensiTiviTy don39T scale well 39 BriT He under common program ediTs 39 Eg call sTrings ms 240 Data FlnwAmJyms 53 Flow Sensifivify Beyond Procedures 39 Flow sensiTive analyses are standard for analyzing single procedures 39 NoT used or noT aware of uses for whole programs Too expensive 555 240 Data FlnwAmJyms 54 Introduction to Model Checking Lecture 14 ms 240 thzlchzckmg Model Checking Does model M satisfy property up What is M What is quot What is sofisz39 ms 240 Mndzlchzckmg Temporal Logic Model Checking Does model M satisfy temporal property q What is M hat is What is sofisz39 ms 240 Mndzlchzckmg What is Status valuations to all variables Initial states subset of states Arcs transitions between states Atomic Pnopositions e x5 btrue Observation color Valuation to all atomic propositions ms 240 Mndzichzcktng What is MWIRL1 W set of states I Q W set of initial states R Q WXW setofarcs L set of atomic propositions I W a 2L mapping from states to colors ms 240 Mndzichzcktng What is 2 Different kinds of temporal logics S ntax What are the formulas in the logic Semantics What does it mean for model M to satisfy formula w in the logic ms 240 Mndzichzcktng Invariant Alswlwmplwvw A atomic propositions x5 btrue satisfaction M satisfies p if all the reachable states satisfy p ms 240 Mndclchcckmg Invariant checking algorithm Does M satisfy p Start at the initial states and explore the states of M us rig DFS or BFS At any state if a is violated then print an error tracequot If all reachable states have been visited then say quotyesquot 555 24a Mndclchcckmg CTL a branching time logic AI wlwvwlixwliwuwliew A atomic propositions e g x 5 btrue What is satisfy39 ms 240 Mndclchcckmg CTL semantics CTL is a state logic E ch formula is true or false in a state State s satisfie p atomic propositions if 1s satisfies o w 39 d esNo satis o o v w 5 satisfies a or s satisfiestp ms 240 Mndchhcckmg CTL semantics s satisfies ax o if there exists t such that kst and t satisfies w as U w if there exists a sequence of states st v such that v satisf es to st all satisfy W i there exists an inf hite sequence of states starting from s where w is alway true Let us come up with a model checking algorithm for CTL ms 240 Mndchhcckmg LTL a linear time logic AI wlwnwlwvwlowlwuw A atomic propositions What is quotsatisfyquot ms 240 Mndchhcckmg LTL semantics LTL talks about traces Eacii formula is true or false at astate by checking it on the infinite traces starting from that state An infinite trace t LO til LZ ms 240 Mndzlchzckmg 13 LTL semantics Language of deadlockfree statetransition graph K at state q LK q set of infinite traces of K starting at q Kq vn iff for all tELKq tip K q 3tp iff exists tELK q t cp 55 240 Mnthth 14 LTL semantics t I a iff aEtO tcpnw iff tcpandtw t I ip iff not t cp t Ocp iff tltz cp tchw iff exists 205T foral05iltn t tM cp and What I 1i 555 24a Mndzlchzckmg is The modal MC lCuluS p atomic propositions w P quot w egion P V w variables x y 2 3X p I X p VX P v x p What is satisfy39 55 240 Mnazicmm m Refinement Implementation s Specification Every behavior of the implementation should be an allowable behavior of the specification ms 240 Mndzlchzckmg 17 ms 240 Mndzlchzckmg 12 M s S Linear Time Every trace of M is a trace of 5 Language Containmentquot Every formula in linear logic LTL satisfied by S is also satisfied by M Complexity M lel In practice can be done using reachability ms 240 Mndzichzckmg w Story so far ms 240 Mndzichzckmg 2n Problem State explosion M is exponential in the description of M ms 240 Mndzichzckmg 21 Fighting state emlosion Algorithms Symbolic techniques BDDs SAW v15 Partialorder reduction SPIN Symmetry reduction Mmphi Methodolog Y Divide and Conquer MOCHA new smv Abstraction STeP ms 240 Wencch 22 Binary Decision Diagrams Bryant Ordered decision Tree for f 069 b 9 c 9 d 0110100110010110 ms 240 Wencch 23 OBDD reduction fzaebeced ms 240 Wencch 24 OBDD properties Variable order stroneg affects size Canonical representation for a given order Efficient apply algorithm 7 boolean operations on BD s is Easy 7 Can build BDD S for large c rcuits 0f 9 ms 240 Mndzlchzckmg Boolean quantification hen IV at flu Example 3070 11b zb39zl n2 If vis aboolean variable t a Complexity on BDD representation t case exponential heuristcally effce t ms 240 Mndzlchzckmg Characterizing sets Let M be a model with Boolean variables v1 v2 vquot Represent P Q 0 1quot by its characteristic function xp P v1 v2 vquot XP Example Variable xyz P00lOlOl00 110 XV gtlt oz 555 24a Mndzlchzckmg Characterizing sets Represent characteristic function as B Set operations can be now done as BDD operations 7 XI false X5 true quqPQ XrnqPQ 3m ms 240 Mndzlchzckmg Transition Relations Transition relation P is a set of state pairs for all the arcs in the state machine 39 R V1V2wvn VIIVZIwv39n 1 En W X V39u VuAV1 VDEBW ms 240 Mndzlchzckmg Forward Image ImagePR ImagePRv39 forsomevvEP and Mug 3 Kim4 V39 3V XpV A XRV7V39 05 240 Mnmcmm Reverse Image ImogequotPR P R LnagequotPR v for somev39 VEP and VV39ER Xmas V 3V39 XsV39 A XRVV39 05 40 dzlchzckmg Symbolic invariant checking S BDD for initial states V BDD for negation of invarth R BDD for transition relation Loop If 5 V then print failed and exit I Image 5 R S39 5 UI If S S39 then print quotpassedquot and exit 5 539 End 555 24a Mndzlchzckmg 32 BDDs Big breakthrough in hardware 39 McMillan39s thesis won the ACM thesis award Intel IBM Motorola all have BDD based model checkers and large formal verificationquot teams based on them BDDs compactly represent transition relations Can prove that if the c rcuit has bounded communicationthen transition relation is small Images and keachable sets tend to blowup ms 240 Mndzlchzckmg z BDDs Images and reachable sets blow up often Subject of intense investigation PhD theses on how to compute images without BDDs blow ng up Alphabetical soup of variations ADDs to ZDDs Work upto 100 variables don39t really scale to thousands of variables Provide good bootstrap for compositional methods ms 240 Mndzlchzckmg 34 Partial Order Methods Protocols are usually modeled as an asynchronous composition of processes interleaving model Partial order reduction explores only a portion of the s te space You can still prove properties about the entire state space 555 24a Mndzlchzckmg 35 Process Object Model Processes P1P2 Pquot Objects 0102 Om Some objects are local to a process some are shared Each process runs a program has a program counter An action of the system Is ss e u changes PC for the process and possibly some of the objects 555 24a Mndzlchzckmg 35 39 a proce xec ting a statement Example Two integer objects x and y both initialized to 0 P1 L1 if xlt 10 then x x1 goto L1 P2 L2 if ylt 10 then y y1 goto L2 555 24a Mndzlchzckmg Guarded Commands integer x y Init true ex 0y0 Update xlt 10 a x x1 ylt10 yy1 ms 240 Mndzlchzckmg State machine model tern is still a labeled 39 The global sys state mac me The processobject model is a succinct description 555 24a Mndzlchzckmg Actions integer x y Init true ex0y0 Update x xlt10 gt Xx1 l3 ylt 10 a yy1 ms 240 Mndzlchzckmg AU Actions An action is a guarded command Nondeterminism arises because of the enabled actions could be scheduled next Can label state machine Transitions with action names 555 24a Mndzlchzckmg 41 Independent Actions Actions x and 3 are independent if a 1 Neither action enables or disables the other 2 If both x and 3 are enabled then they commute ms 240 mmcmm Example integer x y boolean bomb Init true a x 0 y 0 bomb false Update x xlt10 Slt bombe xx1 3 ylt10 Slt bombe yy1 y x 3 Slt y3amp bomb bomb true 555 24a mmcmm Partial Order Methods Key idea If actions 04 are independent then 5 006339 Bux Bxcwxab Hx a Need to explore only one But there are some caveats ms 240 Mndzlchzckmg 47 Partial Order Equivalence Two action se LIences A and B are partialorder equivalent ig A can be transformed to B by swapping adjacent independent actions Need to explore only one representative in each equivalence class 555 24a Mndzlchzckmg 42 Partial Order Reduction Take 1 Suppose 1 I is the set of all actions enabled in s 2 A Q P 3 every action in I A is independent of every action in A Then explore only A from s Justification Can delay39 actions in I A Ecs 24a Mndzichzckmg 49 Partial Order Reduction Take 2 Sup ose 1 I is the set of all actions enabled in s 3 every action that is reachable from s by LIting actions in I A is independent of every action in A Then explore only A from s l A is called a Persistent setquot Ecs 24a Mndzichzckmg 52 Partial Order Reduction Take 3 Sup ose 1 I is the set of all actions enabled in s 2 A Q P 3 every action that is reachable from s by e ing actions in I A is independent of every action n A If A yields new statesquot explore only A from s else explore all actions I from Ecs 24a Mndzichzckmg Partial Order Methods Difficulty Computing independence relations and persistent sets is hard Solution Come up with syntactic sufficient conditions Ecs 24a Mndzichzckmg Infroducfion to Domain Theory Lecfure 5 ECS 240 ac 2m Lecture 5 i A Simplified Setup Consider programs in an eager deferminisi ic language wifll one variable called x All these restrictions arejust to simplify the examples A sl39ai39e a is jusf The value of x Thus we can useZ instead of 2 The semanfics of a command give The value of final x as a funci ion of inpui x c c 2 a2 ac 2m Lecture 5 2 Examples Revisifed Take C while True do skip Unwind ng equation reduces to w x w x Any function satisfies the unw nding equation Desired solution is Wx L Unwind ng equation Wx if x e 0 then Wx 2 else x Solutions for allvalues n m e 21 Wx ifx 2 0 then if x even then 0 else n Take Cwllile X 0 do x x 2 else m Desired solution Wx if x 2 o n x even then 0 else u c c M Lecture 5 An Ordering of Solutions The desired solution is the one in which all the arbitrariness is replaced with nontermination The arbitrary values n a solution are not uniquely deterrn ned by the semantics of the code We introduce an ordering of semantic functions Let f g e Z A Zi Define f E g as Vx e Z fx L or fx gx A quotsmallerquot function term notes at most as often and tilnan it terminates it produces the same result cc 2m Lecture 5 a Altemative Views of Function Ordering A semantic function f e Z A Zi can be written as Sf g Z X Z as follows 5tgtlt YlgtltEZ 1 gtltY L A list of the term notingquot values for the function If f E g then sf g 59 and vice versa We say thatgrefinesf We say that f ap rmimates g We say that 9 provides more nfor39rnation than f cc 2m Lecture 5 s The quotBestquot Solution Consider again Cwhile x 0 do x x 2 Unwind ng equation Wx if x s 0 then Wgtlt 2 elsex Not all solutions are comparable Wxfx2 xeventhenOelselelseZ Wx fx 2 0 then ifx even then 0 else u else 3 Wx if x 2 0 then ifx even then 0 else u else u least best Is there always a least solution How do we find it 9 General framework for answering these questions cc 2m Lecture 5 5 Fixed Point Equations Consider the general unwinding equation for while while b do 1 E if b then c vlfnile b doc else skp We define a context C command with a hole C if b then 390 else skip whilebdoc whilebdo c C does not contain quotwhile b do cquot We can find such a context for any looping construct Consider fact n if n 0 then 1 else n quot fact CAnifn0then1elsenquot n1 factCfact ac 2m Lecture 5 Fixed Point Equations The meaning of a context is a semantic functional F z 4 zi 4 z 4t 21 such that lclwlll F inl For quotwhilequot C if b then c 0 else skip F w x if b x then w c x else x F depends only on c and M We can rewrite the unwinding equation for while Wx if b x then Wc x else x or x for all x or w s F w function equality ac eu Lecture 5 Fixed Point Equations The meaning of while is a solution for W F W Such a W is called a fixed point of F We want the least fixed o39nt We need a general way to find least fixed po nts Whether such a least fixed point exists depends on the properties of function F Counterexample F wx if wx L then 0 else L Assume Wis a fixed po nt FWx WxifoJthen0elseJ PickunxthenifoJ thean0 elseWxJ Contradiction This F hm no fixed po nt ac 2m Lecture 5 Monofon icity Good news the functions F that correspond to contexts in our language have least fixed points I The only way F f x uses f is by invoking it If any such invocation diverges then F f x diverges ac 2m Leanne s in Monotonicity Cont Consider f0 E fl What can we say about the relationship between F f0 x and F fl x for any x Assume F f0 x n s L Showthat Ff1x n In computin F fu x fu is invoked a f nite number of times All those nvocations term note with some values The value of fu at other points does not matter But f terminates with same results everywhere fu terminates Thus F f x n determinism of F In general if f0 E f1 then P f0 E F f We say that F must be monotonic ac 2m Leanne s it Monotonicity Cont If we replace the subcommand with one that terminates more often the host command will terminate more often The following F is not monotonic F 39wxJthen0elseJ This function does not correspond to a computable context The semantics of computable contexts are monotonic Can be proved byinduction on the structure of context ac 2m Leanne 5 i2 Chains of Approximations Consider the command while x s 0 then x x 1 39 Semantics W x ifO g xthen 0 else L Try the following approximations for arbitrary k i 7 else L w is the semant cs if we allow less than k iterations Show that wk E W All wk approximate W Also wk 7 wkl We get more information if we allow more iteration wk form a chain of aggrox mations of the true semant cs We say that Wis an upper bound for the chain wk ac 2m Leanne s Least Upper Bounds Recall W x ifO g xthen 0 else L w x ifO g xltkthen0elseL Pick any other upper bound for chain wk eg Uif0 gxthenOelsen We see that W E U W is the lemt upger39 bound of the chai wK Compute the least upper bound for a chain in Z 4t Zi e struct thesequencefx fzx Thus UV fk x if 3m x n e L then n else L We can verify that w or wk ac 2m Leanne s Solving Fixed Point Equations Thus W U wk Note that w0 Ax L Note also that wk P w where F is the meaning of context if x s 0 then x x 1 0 else skip Thus W LFPF le Fk Ax L quot Is this true for all functions F ac 2m Leanne s Continuity Consider F corresponding to a context in our language Consider a chain g0 E 7 with le 6 k Note that F a form achain also because F is monoton c We39ll show that for any x F 6 x le F gk x We say that such functions F are co t uous If F 6 x n s L t en 6 was invoked a finite number of times and terminated each time For each such invocation there is uj such that 9 term nates with the same result Let max be the maximum such i for all nvocations Thus F 9W x n and Hi F a x n Similar reasoning for F 6 x L Ecsm Leonie The Fixed Point Theorem If F is a semantic functional corresponding to a context in our language F is monoton c and continuous For any fixedpoint e of F and k e N g The least of all fixed points is llllt F ltAxL Proof 1 by mathematical induction on k cue F uXL ML e Inductive F lt AxL FF ltuxL F6 e 2 Suffices to show that u FkCAxL is a fixedpoint Fuk Fk xL uk Fk AxL uk FkaxL Ecsm Leann Denofa onal Semantics For WHILE We can use the fixedpoint th denotational semantics o 39 whie to do c u F lt ML wherefo if loll xthenf c x elsex Example while true do skipl AxL Example while x 0 then x x 1 F AxL ifx 0 then x else L eorem to write the F2 AxLxifx0thenxelseifx10thenx1else L ileXZOthenOelse L Fa AxLxif2 2x 20then02lse L LFPF ifx 2 0 then 0 else L In general it is not easy to find the closed form for LFP l ac 2m Lecture s 15 Discussion We can wriTe The denoTaTional semanTics buT we cannoT always compuTe i Otherwise we could decide the haITing problem H holts on input I iff H I e L We have derived This for programs wiTh one variable We can generalize To mulTiple variables even To variables ranging over richer daTa Types even higher order funcTions Domain Theory ac 2m Leanne s 19 Domain Theory A seT D is a domain if It hes a partial order x Re exive lranslllve and anihsymmelric There is a least element L called bottom Any chun x E E xquot E hcs u leusTupper bound u xi For oiii x g u x is on upper bound For ohw such that Vi x g y we have u x y leasl upper bound Usual seTs of semanTic values are domains ac 2m Leanne 5 2n Example of Domains ExampleDZ 4Z1 ng lffforullnEZfnLorfngn LD7unJ Foruchunf TheLUB7unif3kkamsi thehhieiseu Example Take a seT A and a special elemenT L Then A1AUJisaflaTdomai ubiffuioru For uchun a LUB if akak e i Then uk elsel Exercise If Di and D2 are domains Then D1 4 D2 is a domain and so is D1 gtlt ac 2m Leanne 5 2i Monotonicify and Confinuify A funcfion 1Dl 7 D2 is mono i onic iff forallx yeDx y fngy A funcfion FD14 D2 is confinuous iff for all chains x in D1 F Li x Li F x We can Show Thai funcfions corresponding To usual language consfr39ucfs are monofonic and confinuous ac 2m Leanne s 22 Leas Fixed Point Theorem If D is a domain and F D A D is a confinuous funci ion Then L F L F F form uchuin in D Li F L is the lam fixed point of F ac 2m Leanne s 2 Equivalence of Denofa onal and Operafional Semanfics ac 2m Lama s m Equivalence with Operational Semanfics STaTernenT iff Aeon iff ltb39 51 t Ema t lt I 39 Each of These proofs has Two direcTions The case of ariThrneTic and boolean expressions are easy by sTrucTural inducTion The case for commands is more inTeresTing ac 2m Lecture 5 Equivalence Proof I t If we have a derivaTion D 2 ml 039 Then Cca 039 The proof is by inducTion on The sTrucTure of D NoTaTion whilebdoc w Cw w To prove ThaT Wa a39 We consider only The cases when aT The rooT of D we have eiTher whileTrue or whilefalse The oTher cmes are easi ac 2m Lecture 5 Equivalence Proof II From D and Case The rule aT rooT is whilefalse D ltb m i false Dquot Luihiiebdocmio a musT be a Bbo fals using the equivalence for booleans we have that e From the unw nd ng equaTion we geT that me 0 ac 2m Lecture 5 Equivalence Proof III Case The rule aT The rooT of D is whileTrue ltwhile b do c 0 l 039 ltw lebdocogtii 039 From D1 we geT ThaT Bba True By IH on D2 we geT ThaT Cca 01 By IH on D3 we geT ThaT Wal a39 From The unwinding equaTion we geT WU WCCU WUt 039 NoTe ThaT any soluTion To The unwinding eguaTio has The same properTy Why ac 2m Lecture 5 22 Equivalence Proof IV e If Cca 039 and 039 s L Then There exisTs D 2 mil 039 Proof by inducTion on The sTrucTure of The command 2 We do only The case for WHILE We know ThaT ll Fkotx La a39 s L From The definiTion of Li on The flaT domain 21 k a 039 s L SufficienT To prove k N Fkotx Laa LtDltc mild This can be proved by maThemaTical inducTion on k NaTe ThaT This is nesTed inducTion ac 2m Lecture 5 Equivalence Proof V Base k 0 Vacuously True InducTive sTep k 21 If Bbo false Check ThaT Fknx he s c Thu We know ThaT D ltb m l false exisTs We consTrucT D as follows D ltb m l false Dquot 39sullllebdocmlo ac 2m Lecture 5 Introduction to Denofafional Semantics Lecture 4 EC 555 24a LecmreA I Review The operational semantics is simple not compositional of many flavors natural smallstep more or less abstract Denotational semantics is mathematical the mean ng of asyntactic expression is a t emat ca o 39 t anonical compositional Denotational semantics is also called fixed oint semantics mathematical semantics Scott trachey semantics E05 240 Lecture 4 2 Plan Define the denotational semantics of IMP F rst attempt Domains and their properties Monotonicity Continulty Finish the denotational semantics of IMP E05 240 Lecture 4 z Rough Idea of Denotational Semantics The meaning of an arithmetic expression e in state 0 Is a num er n So we try to define Ae as a function that maps the current state to an integer A Aexp a E a Z The meaning of boolean expressions is defined in a similar way B Bexp a E a true false All of these denotational function are total Def ned for all syntact c elements For other Ian uuges it mi ht be convenient to def ne the semantics on y for welltyped elements E05 240 Leetme A A Denotational Semantics for Commands Running a command c starting from a state 0 yields another state 039 So we try to define Cc as a function that maps 0 to o39 CComa2a2 E05 240 Leetme A 5 Denotational Semantics of Arithmetic Emressions We define inductively a function A Aexpa Ea Z An o the integer denoted by literal n Ax o ox Alle ezll U Allelllo Allezllo A elez o Ae1o A ez o Ae1e2o Ae1o x Ae2o This is a total function defined for all expressions E05 240 Leetme A 5 Denotational Semantics of Boolean Expressions We define inductively a function B Bexp a E a true false Btrueo true Bfalseo false Bb1 bZHUZ Bb1o B bz o Be1 6202 Ae1o Ae2 0 E05 240 Lecture 4 7 Denotational Semantics of Commands We try to define a function Coma2a2 Problem running a command might not yield anything if the command does not terminate We introduce the special element L to denote a special state that stands for nontermination For anysetX let Xi Xu Convention whenever f E X H Xi extend f to Xi H Xi so that fL L This is called sfricfness E05 240 Lecture 4 2 Denotational Semantics of Commands Wetry C Coma2ia2i Cskip 2 AU 0 Cc1 c2 Cc2 o Cc1 Cif b then c1 else c2 A0 if Bbo then Cc1o else Cc2o Cwhile b do c E05 240 Lecture 4 9 Examples CX 2 2 X 1 2 k0 OX 1 Cif True Then x 22 x 1 else A0 ox 2 1 The semanTics does noT care of The inTermediaTe sTaTes We didn39T need L yeT ECS 240 Lecture 4 10 DenoTaTional SemanTics of WHILE NoTaTion WbC Cwhile b do c Idea rely on The equivalence while b do c if b Then c while b do c else skip Try Wo if Bbo Then WCco else 0 This is The unwinding equaTion BuT iT is noT an accepTable definiTion of W because IT defines W in Terms of iTself IT is noT evidenT ThaT such a W exisTs IT does noT describe W un quer IT is noT composiTional ECS 240 Lecture 4 11 More on WHILE The unwinding equaTion does noT specify W uniquely Take Cwhile True do skiPl The unwinding equaTion reduces To Wo Wo which is saTisfied by every funcTion Take Cwhile x 0 do x x 2 The following soluTion works for any 039 01 2 0 if 033 2 2k 0513 2 0 W07 0 otherwise ECS 240 Lecture 4 12 Denofafional Semantics of WHILE Let39s start with something similar Define Wk 2 a El for k E N such that 39 iIe ocquot in stuteoterminutes n WAG less than kiterutionsin Sta 039 L otherwise We can define the Wk functions as follows Wu0 L w 7 Cc0 if Bbo Wko l O otherwise E05 240 Lecture 4 Denofafional Semantics of WHILE How do we get W from Wk M0 0 if 3kWko a e L L otherWise This is a valid compositional definition of W Depends only on cm and c Try the examples aga39 For Cwhilex e0 dox M0 0x 0 if 0x e 21m 0x 20 L otherWise More on WHILE The solution is not quite satisfactory because It has an operational flavor It does not generalize easily to more complicated semantics H wever precisely due to the operational flavor this solution is easy to prove sound w r t operational semantics E05 240 Lecture 4 Abstracf Inferprefafion Non 5fandard Semanfics LecTure 1112 S 240 ms 241 Lecture 1m 1 The Problem IT is useful To predicT program behavior a caIy wiThouT running The program For optimizing compilers For sofTware engineer ng Tools The semanTics we sTudied so far give us The precise semanTics However precise sTaTic predicTions are impossible he exacT semantics is noT compuTable We musT seTTle for approximaTe buT correcT sTaTic analysis e g VC vs 55240 Leanne 1142 2 The Plan We will inTroduce absTracT inTerpreTaTion by example STarTing wiTh a miniscule language we will build up To a fairly realisTic applicaTion Alon The way we will see mosT of The ideas and difficulTies ThaT arise in a big class of applicaTions 55240 Leanne 1142 3 A Tiny Language Consider The following language of ariThrneTic x 52 The denoTaTional sernanTics of This language n lei x 52 lle X llzzll For This language The precise sernanTics is compuTable Ecsm Lecture im 4 An Abstraction Assume ThaT we are inTeresTed noT in The value of The expression buT only in iTs sign posiTive negaTive or zero 0 e can define an absTracT sernanTics ThaT compuTes only The sign of The resulT 39 390T 0a signn 02i quot 22 0a 022 Ecsm Lecture im 5 Correctness of Sign Abstraction We can show ThaT The absTracTion is correcT in The sense ThaT iT correchy predicTs The sign e gt0 e 0a e 0 e oe 0 e lt 0 e 0a Our sernanTics is absTracT buT precise Proof is by sTrucTural inducTion on expression e Each case repeaTs s milar reasoning Ecsm Lecture im 5 Another View of Soundness We associaTe wiTh each concreTe value an absTracT a e vlu 3 Z A This is called The absTracTion funcTion Conversely we can also define The concreTizaTion funchon v o 04132 vnEZngt0 700 vHEZIHlt0 55240 Lecmre llelz Another View of Soundness Cont Soundness can be sTaTed succincTIy Ve 6 Exp e e yoe the true value of the expression is among the represented by the absTracT value of the expr39 e C be The concreTe domain e 9 Z and A be The absTracT domain e g 0 concr39eTe values 39on Exp 0 A 11 v e 790 555240 Lecmre llelz Another View of Soundness Cont Consider The generic absTracTion of an operaTor 021 up 22 021 22 a 22 This is sound iff ValV lz 701 02 2 m 0P quot2 quotl 6 701 quot2 E 7012 E9 701 09 02 2nl quot2 quot1 6701 quot2 67012 This reduces The proof of correcTness To one proof for each operaTor 55240 Lecmre llelz Abstract Interpretation This is our first example of an abstract interpretation We carry out computation in an abstract domain The abstract semantics is a sound approximation of the standard seman ics The concretization and abstraction functions establish the connection between the two domains 55240 Lecture 1142 m Adding Unary Minus and Addition We extend the language to e n el quot e2 e We define a e e 0e Now we add addition e n 21 22 e 21 22 We define oel e2 0e1 a 0e2 55240 Lecture 11712 n Adding Addition The sign values are not closed under addition What should be the value of a quot Start from the soundness condition v2n1quot2 I we n2lt0z We don39t have an abstract value whose concretization includes Z so we add one T a 0 T T T 0 0 T T T T T T T T 55240 Lecture 11712 12 Examples AbsTracT compuTaTion mighT loose informaTion 1230 012 3 01 89 02 a a3 a a T We loose some precision BuT This will simplify The compuTaTion of The absTracT answer in es when The precise answer is noT compuTabIe 55240 Leanne 11712 13 Adding Division Fairly sTraighTforward excepT for division by 0 We sayThaT There is no answer in T at case Votnnnnongto 0 We inTroduce L To be The absTracTion of The V We also use The same ubsTr39ucTion for nonTerminaTion 0 T L 0 T L 0 L L L L L 0 T L T T T T T L L L L L L L some Leanne in IA The Abstracf Domain Our absTracT domain forms a aTTice A partial order is induced byy 61 u2 ifftui Q t 2 We say that a is more precise that a2 i Every finite subseT has a leusTupper39 bound Iub and a greaTesTIower bound glb T L 55240 Leanne 11712 is Lattice Facts A lattice is complete when all subsets have Iub and 9 Even infinite ones Every finite lattice is complete Every complete lattice is a CPO Since a chu n is a subset Not every CPO is a complete lattice Might not even be a lattice Ecsm Lecture 11712 16 More Lattice Facts Early work in denotational semantics used lattices But it was latter seen that only chains need to have Iub And there was no need for T and glb In abstract interpretation we39ll use T to denote I don39t knowquot Corresponds to all values in the concrete domain Ecsm Lecture 11712 17 More Defin ans We can start with the abstraction function 3 a A maps a concrete value to the best abstract value A must be a Iatt ce From here we can derive the concretization function y A a7c Vugtlt C i x Sn And the abstraction for sets aE77C4gtA aSub xxeS Ecsm Lecture 1142 la Example Consider our sign laH39ice n0 ifn0 ifnlt0 15 lub 3x x e S Example 1 1 2 lub a10ub0T a0ubl 7an 3n 0 ExamplevnIllnn Fquot nlngt0 TquotlFquotltTZ Vinl3n LlJ 55240 Lecmre 11712 Galois Connections We can show Hlaf y and a are monolon c will the g ordering an 720 a V a a for all y 015 2 s for all s e 72c Such a pair of funcl ions is called a Galois connecl ion Between lullices A and 77 C S C you 55240 Lecmre 11712 Correctness Condifion In general absl39racf inl39erprefal39ion safisfies The following diagram Exp 4 A ill 7 I S c 6 736 55240 Lecmre 11712 Correctness Conditions Conditions for correct abstract interpretations 1 a and y are monotonic 2 a and y form a Galois connection 3 Abstraction of operations is correct 01 Quiz 0tvai 0P 7012 555240 Lecture 1142 22 So far Introduced abstract interpretation Two mappings form a Galois connection An abstraction mapp ng from concrete to abstract values A concretization mapping from abstract to concrete values Next look a bit more at Galois connections Then extend these ideas from expressions to ms pro r 55240 Lecture m2 2 Why Galois Connections We have an abstract domain A We argued that for correctness Vul BE 2 2 Vul 0P Vu2 We wish for the set on the left to be as small as possible To reduce the loss of information through abstraction For each set S Q C define 15 as follows Pick 539 the smallest that includes 5 and is in the image of y Define 15 syrx s Then we define a1 9152 owl op ya2 Then a and y form a Galois connection 55240 Lecture 1142 24 Abstract Interpretation for Imperative Programs So far we absTracTed The value of expressions We wanT now To absTracT The sTaTe aT each poinT in The program FirsT we define The concreTe semanTics ThaT we are absTracTing We use a collecTing semanT cs 55240 Lecture llelz 25 The Collecting Semantics AsTaTeoEEVar HZ STaTes vary from program poinT To program po nT We inTroduce a seT of program poinTs Labels We wanT To answer quesTions like Is x always positive at Iabe ya Is x always greater or equal to y at label j 7 To answer These quesTions iT helps To consTrucT C e ConTesz Labels A 132 For each label all The sTaTes aT ThaT label This is called the collect ng semantics of the program How can we define The collecTing semanTics 55240 Lecture llelz 25 Defining the Collecting Semantics We firsT define relaTions beTween The collecTing semanTics aT differenT labels do it for a flowchart program It can be done for IMP with careful definition of program p0 nTs Define a label on each edge in The flowcharT For assignmenT CJaxnaeC ean 55240 Lecture llelz 27 Defining the Collecting Semantics For cond if ionals CJaaeC bafalse CkaaeC ba139rue 55240 Lecture llelz 22 Defining the Collecting Semantics For ajoin QQUQ Verify Thai These relafions are monofonic If we quotcrease aC all other cJ can only increase 55240 Lecture llelz 29 Collecting Semantics Example Consider The following program assume x 2 0 inil ially 1 Cl UI 0x Z 0 c a HIUECQ u axax1 l a 6 c4 ngnwlqnem C5C2 aax 0 C4 Uly0YquotUgtlt a 6 Ca 55240 Lecture llelz The Collecting Semantics We have an equation with The unknown C The equation is defined by a monotonic and continuous function on the domain Labels a 722 We can use The least fixedpoint Theorem We slurl Willi C 39 AL ll We apply the relations between cl and c1 to construct c from Cu i We slopvlfnenck0ltquot The problem is that we39ll go on forever for most programs But we know the fixed p0 nt exists 55240 Lecture im 31 Collecting Semantics Example Consider The following program assume x 2 0 initially 1 0 C1ialax220 2 0 lllaeCi u axax1 l o e c C3C2 aax0 c c2nfolox 0 54 Uly0YquotUgtlt a 6 Ca Collecting Semantics Example Consider The following program assume x 2 0 initially Cia 0x 20 c o 1oec u axax1 o 6 CA C3C2 alax0 c Cz aax 0 alyayax a 6 Ca 0 cm 55240 Lecture iieiz Collecting Semantics Example Consider The following program assume x 2 0 iniTially 6 a am 20 Cz Uly a I U axax1 a 6 C4 Ca 52 0 000 Ca 52 M a 0x 0 C4 ayoyogtlt a 6 Ca 55240 Lecture 1112 Collecting Semantics Example Consider The following program assume x 2 0 iniTially clltaIaltxgt2o 5 W 52 ay11 I use x U 0 0001 a 6 C4 C3C2 ala 0 C5 62 N a 0x 0 C4 0YUYquotUgtlt U 6 Ca 55240 Lecture 1112 Collecting Semantics Example Consider The following program assume x 2 0 iniTially x20y1 5 c al 0020 W2 6 2 swim I a e so u axax1 a 6 c4 gt0yzx CaCz 0Ux0 C5C2 aax o 64 ayayax a e 6 55240 Lecture 1112 Collecting Semantics Example Consider the following program assume x 2 0 initially x2 0 yx1 x 2 0 y 1 M3y1ie 5 x0y1 32 0X 2 E C 5 Old X7 CC x 55240 Lecture iieiz 51 u axax1 a 6 Q s o a 0x 0 C4 0YUYquotUgtlt U 6 Ca Collecting Semantics Example Consider the following program assume x 2 0 initially c al 0020 W 6 2 ay1 I a e cl 0 xax1 a 6 c4 C3C2 alax0 Ca 2 m l a 0x 0 C4 0YUYquotUgtlt U 6 Ca 55240 Lecture iieiz Abstract Interpretation We pick a complete lattice A abstractions for PE Along with amonotonic abstraction o 7 2 a A Alternatively it ckp 2 gt This uniquely defines its Galois connection y We take the relations between C and move them to the abstract domain a 6 Labels A A Assignment Concrete CJ ax n a e C ea n Abstract aJ on ax n a 6 10 eo n 55240 Lecture 1112 39 Abstract Interpretation Conditional Concrete CJ 0 0 e C bo false and C aIaEC A b 02true Abstract ai 10 a e 1a A bo false and ak 10 a e 1a bo true oin Concrete Ck C U CJ Abstract ak a 7a U yaJ ub a a 55240 Lecture iieiz AU Least Fixed Points in the Abstract Domain Now we have a recursive equation with unknown a Defined by a monoton c and continuous function on the domain bels 4 A We can use the least fixedpoint theorem Start with a ALL Apply the monotonic function to compute dlt from uk Stop when uk 1 dlt Exactly the same computation as for the collecting semantics What is new 55240 Lecture iieiz Al Least Fixed Point in Abstract Domain We have a hope of termination The classic setup is when A has only uninteresting chains finite number of elements in each chain We say that A has f nite height say h In this case the computation takes at most Oh quot Labelslz steps At each step quotaquot makes progress on at least one label We can only make progress h t mes And each t me we must compute ILabelsI elements This is a quadratic analysis good news 05240 ii Abstracf Interpretation Example Consider The following program 1 We wanT To do sign analysis on iT 55240 Leanne 11712 43 The Abstracf Domain for Sign Analysis Consider The compleTe laTTice S L 0 T From iT consTrucT The compleTe laTTice A x y A S With p0 ntwise ordering as usual The abstth state consists of the sign for x and y We sTarT wiTh a0 KL de y L 55240 Leanne 11712 44 Example 55240 Leanne 11712 45 Notes We abstracted The state of each variable independently A y4t T We lost relationships between variables Eg that at a point x and y are always of the same sign In the previous abstraction we get x T y T at 2 We can also abstract The state as a whole 7 TgtltJ0T For the previous example we now get the abstraction 0 1 4 at 2 55240 Lecture ttetz Other Abstract Domains Range analysis Lattice of ranges R L nm 00 m h 00 T It is a complete Iatt ce h m u h39 m mmn ha magtltm m 332 a k such that Mn nn a 722 a k such that a5 Iub pm h e s m nSmux 5 yka7JZsuchthatyrnIner This laH ice has infiniteheight chain 50 the abstract nterpretation might not terminate 55240 Lecture ttetz Example of Non Termination Consider This common program fragment 1 We want To do range analysis for if 55240 Lecture ttetz Introduction to Axiomafic Semantics Lecture 89 E65 240 E05240 Lecture 23 i Review Operational semantics reiativeiysimpie many flavors adequate guide for an implementation of the language not compositional Denotational semantics mat emat ca canonicu compositional Operational 4 denotational e would also like a semantics that is appropriate for arguing program correctness E05240 Lecture 23 2 Axiomafic Semantics An axiomatic semantics consists of A language for stat ng assertions about programs kules for establishing the truth of assertions Some typical kinds of assertions This program termina e If this program terminates thevariables x and y have the samevalue throughout the execution of the program The array accesses are within the array bounds Some typical languages of assertions Frstorder lo ic Other iog cs temporai iinear E05240 Lecture 23 z History Program verification is almost as old as programming e g Checking a Large Routinequot Turing 1949 In the late 3960s Floyd had rules for flowcharts and Hoare for structured languages Since then there have been axiomatic semantics for substantial languages and many applications E05240 LecimXJ A Hoare Said Thus the practice of proving programs would seem to lead to solution of three of the most pressing problems in software and programming namely reliability documentation and compatibility However program proving certainly at present will be difficult even for programmers of high caliber an may e applicable only to quite simple program designs quot R Hoare An Axiomatic Basis for Computer Programmingquot 1969 E05240 LecimXJ 5 Dijkstra Said Program testing can be used to show the presence of bugs but never to show their absencequot E05240 LecimXJ 5 Hoare Also Said It has been found a serious problem to define these languages ALGOL FORTRAN COBOL with sufficient rigor ensure compatibility amon all implementations one way to achieve this would be to insist that all implementations of the language shall satisfy the axioms and rules of inference which underlie proofs of properties of programs expressed in the language In effect this is equivalent to accepting the axioms and rules of inference as the ultimately definitive specification of the meaning of the languagequot E05240 LecimXJ 7 Other Applications of Axiomatic Semantics The project of defining and proving everything formally has not succeeded at least not yet Proving has not replaced testing and debugging and r in Applications of axiomatic semantics Proving the correctness of algorithms or find ng bugs Proving the correctness of hardware descr ptions or finding bu s extended static check ngquot eg checking array bounds Documentation of programs and interfaces E05240 LecimXJ Assertions for IMP The assertions we make about IMP programs are of the form A C B with the meaning that If A holds in state 0 and ltc 11 o39 then B holds in o39 A is called precondition and B is called postcondition For example xzxzz1yltz is a valid assertion These are called Hoare triple or Hoare assertions E05240 LecimXJ 9 Assertions for IMP II A c B is apartial correctness assertion It does not imply termination A c B is a total correctness assertion meaning that If A holds in state a then there exists 039 such that ltc a ll 039 and B holds in state 039 Now let39s be more formal Formalize the language of assertions A and B Say when an assertion holds in as a e Give rules for deriving Hoare triples E05240 LecimXJ in The Assertion Language We use firstorder predicate logic on top of IMP expressions Atruefalse e1e2 e12e2 IAIAAZIAgvAZIAiA2 IVxAIExA Note that we are somewhat sloppy and mix the logical variables and the program variab es Implicitly for us all IMP variables range over integers All IMP boolean expressions are also assertions E05240 LecimXJ ii Semantics of Assenions We introduced a language of assertions we need to assign meanings to assertions Notation o l A to say that an assertion holds in a given sta e This is welldefined when 0 is defined on all variables occurr rig n A The t judgment is defined inductively on the structure of assertions It relies on the denotational semantics of arithmetic expressions from IMP 05240 Leanne l2 Semantics of Assertions Formal definition cl true always 0 l e1 e2 iff e1 0 ez o o l e12 e2 iff e1 0 2 ez o olEAlAA2 iffolEAlandolEA2 olEAlvAZ iffolEAlorolEAZ olEAlA2 iffolEAlimpliesolEAZ olEVxA iff VHEZ oxnl A o l 3x A iff EnEZ oxn l A 05240 Leanne 13 Semantics of Assertions Now we can define formally the meaning of a partial correctness assert39on r A c B VoEEVo39EE cl A ltc cpl 039 o39 l B and the meaning of a total correctness assertion r A c B iff VoEEVdEEolAAltcogtllo39gto39lEB VUEEUl A 3062 ltcogtll o39 E05240 Lemmas IA Deriving Assertions Now we have the formal mechanism to decide when A C B But it is not sutisfuctor Because r A c B is defined in terms of the operational mantics we pract cully have to run the program to verify an assertion And also it is impossible to effectivelyverify the truth of a w A assertion by using the definition of validity So we define a symbolic technique for deriving valid assertions from other valid assertions E05240 Lemmas is Derivation Rules for Hoare Triples We wriTe F A c B when we can derive The Triple using derivaTion rues One derivaTion rule for each command in The language Plus The rule of consequence A392A FAcB H221 FCMCCB E05240 Lemmas Derivation Rules for Hoare Logic One rule for each synTacTic consTrucT r A skip A r eXA x eA F A C B F B Ce C F0051 Ce C FAAbcB A Asbc2s r A if b Then c else c2 B r A A b c A l Avnileb docA A sb E05240 Lemmas Hoare Rules For some consTrucTs muTipe rules are possible r Ax e ixuxuXA A x XEX12 This was The forward axiom for assignmenT FAAb26 FCcA AAsb23 r A ulnile b do c B Exercise These rules can be derived from The previous ones using The consequence rules E05240 Lemmas Example Assignment Assume that x does not appear in e Prove true x e x e First the assignment rule l eexexe because exgtlt e E e exe E e e Then with the consequence rule hirueee l e ex ex e l truexexe E05240 LecimXJ w The Assignment Axiom Cont re said Assignment is undoubtedly the most characteristic feature of programming a digital computer and one that most clearly distinguishes it from other branches of mathematics It is surprising therefore that the axiom governing our reasoning out assignment is quite as simple as any to be found in elementary logIc How about aliasing Ifx and y are aliased then mien 5xy1o is true E05240 LecimXJ 2n Example Conditional D mm Ayg 0x 1xgt0 D2 l true ygt0x yxgt0 r true if y g 0 then x 1elsex D1 is obtained by consequence and assignment mm y g 0x 1x gt0 D2 is also obtained by consequence and assignment r ygt0x y gt0 HrueAygt02ygto r true ygt0x E05240 LecimXJ 21 Example Loop We want to derive that hx0whilex5doxx1x6 Use the rule for while with invariantx 6 hxg Axg52x1g rx1gex x1xg hxgX 5xx1xg ng6whiexngoxx1xgeAxgt5 Then finishoff with consequence rx go 2 x g 6 hxg Axgt52x6 rxgeullllexgeAxgt5 rx g0whilex6 E05240 Lecture 23 Another Example Verify that hA while true do c B holds for any A B and c We must construct a derivation tree r true A true c true r true A false 2 B true ulnile true do c true A false r A ulnile true do c B We need an additional lemma AVc hActrue How do you prove this one E05240 Lecture 23 Using Hoare Rules Notes Hoare rules are mostly syntax directed There are three wrinkle When to apply the rule of consequence 7 What invariant to use for while How do you prove the rnpllcetlons involved n consequence 7 The last one can rely on theorem proving This turns out to be doable Loop invariants turn out to be the hardest problem E05240 Lecture 23 Where Do We Stand We have a language for asserting properties of ograms We know when such an assertion is true We also have a symbolic method for deriving assertions meaning A o r A A CB soundness A C B symbolic derivation PI theorem rovin com a eness P 9 k A h A c B BcszAa Lecture 23 25 Soundness of Axiomafic Semantics Formal statement IfhAcBthenlAcB or equivalently Forallo ifolEAandDmc wild andH hAcBtheno39l B How can we prove this By induction on the structure of of No problems With while and rule of consequence By induction on the structure of D No problems With rule of consequence By induction on the structure of H o problems With while By simultaneous induction on the structure of D and H 05240 Lemme Simultaneous Induction Consider two structures D and H Assumethatxltyiffxisasubstructure ofy Define the orderin d hltd39 h39iff dltd39 or dd39andhlth39 Just like the ordering in ct dictionur This is a well founded order and leads to simultaneous induction If d lt d39 then h can actually be larger than h39l It can even be unrelated to h39l E05240 Lecture 23 27 Soundness of the Consequence Rule Case last rue used in H F A c B is the consequence rule FAaA39 A39 c 339 e B39 2 B HA C B From soundness of the firstorder logic derivations we have 0 i A A39 hence o i A39 From IH with H1 and D we get that o39 i B39 From soundness of the firstorder o ic derivations we have that o39 i B39 B hence o39 i q e d E05240 LeclmXJ 22 Soundness of the Assignment Axiom Case the last rue used in H F A c B is the assignment rue The last rue used in D ltx e o J 039 must be D lte 0 gt1 n We must prove the substitution lemma If 0 i exB and lt0 egtJ n then ox n i B E05240 LeclmXJ Soundness of the While Rule Case last rue used in H F A c B was the while rule Higt AAbcA Awhile b docA e b There are two possible rules at the root of D We do only the complicated eese D ltb out true D2 ltc0gtli 039 D3 ltwhile b doc 039 gt3 0quot ltwhiebdocogtiioquot E05240 LeclmXJ Soundness of the While Rule Cont Assume that o l A To show that oquot l A s b By property of booleans and D1 we get 0 l b Hence 0 l A b ByIH on H1 and D2 we get 039 l A ByIHonHand D3 weget 0quotAA b qed Note that in the last use of IH the derivation H did not decrease See Winskel Chapter 6 5 for a soundness proof with denotational semantics E05240 Lemmas Complncnss of Axiomutic Samantics Weeks Praconditions E05240 Lemmas Completeness of Axiomatic Semantics Is it true that whenever l A c B we can also derive k A c B If it isn39t then it means that there are vali properties of programs that we cannot verify with Hoare rules Good news for our language the Hoare triples are com ete Bad news only if the underlying logic is complete whenever e A we also have P A this is called relative completeness E05240 Lemmas Proof Idea Dijkstra39s idea To verify that A c B a Find out all predicates A39 such that H A39 c B inis set Pr2c B b Verify for one A39 e Prec B that A 2 A39 Assertions can be ordere false true weak 5 mg l weakest A precondition Wm B Thus compute WPc B and prove A 2 WPc B E05240 Lemmas 34 Proof Idea Cont Completeness of axiomatic semantics IflAcBthenrAcB Assuming that we can compute wpc B with the following properties 1 wp is a precondition according to the Hoare rules WWW BHCC 2 wp is the weakest precondition f Hmong then EA2wpoB l A 2 wpc B l wpc 3 c B We also need that whenever i A then r A l E05240 Lemmas 35 Weakest Preconditions Define wpc B inductively on c following Hoare rules 0 Ci C C C2 B C A Ci C2 B WPCi2 Ce B WPCi WPC2 B exB x eB wpx e B exB A Ci B Mel C2 B E 2 A 2 E 2 A2if E then o else 93 wpif E then o else c2 3 E 2 wpo B 2 E 2 wpcz B E05240 Lemmas 35 Weakest Preconditions for Loops We start from the equivalence if b then c while b do c else skip Let w while b do c and W wpw B Wehavethat Wbwpc W bB But this is a recursive equation I We know how to solve these us rig doma n theory We need a domain for assertions E05240 Lemmas A Partial Order for Assenions What is the assertion that contains least information true does not say anything about the stat What is an appropriate information ordering A E A39 iff i A39 2 A Is this partial order complete T g A2 g Let My be the infinite conjunction of A 0 e A iff for all i we have that 0 e A Verify that A is the least upper bound Can A be expressed in our language of assertions In many cases yes we39ll assume yes for now E05240 Lemmas Weakest Precondition for WHILE Use the fixedpoint theorem FAbwpc A b Verify that F is both monotonic and continuous The leastfixed point i e the weakest fixed point is wpw B F true Notice that unlike for denotational semantics of IMP we are not working on a flat domain I E05240 Lemmas Weakest Preconditions Cont Define a family of w 39s wpkwliile e do c B weakest precondition on wii cii tiie ioop i it terminates in k or fewer iterations it term nates in B wpu e E 2 wpE2 wpcwpuA2E2B wpwhile e do c B Akzo wpk lle wpk k 2 0 Weakest preconditions r Imposs ble to compute in genera I Can we find sometii rig easier to compute yet suffic ent 7 E05240 Lemmas Verification Conditions E05240 Lemmas Not Quite Weakest Preconditions Recall what we are trying to do false true stron T weak 9 l weakest precondition WPc B verif cation condition vcc B We shall construct a verification condition VCc B The loops are annotated with ioop invariants i vc is guaranteed stronger than WP But hopefully stiii weaker than A A 2 VCc B 2 WPc a E05240 Lemmas 42 Verification Conditions Factor out the hard work Loop invariants Function specifications Assume programs are annotated with such specs eood software engineering practice anyway We will assume that the new form of the while construct includes an invariant while 0 c The invariant formula must hold every time before b is evaluated E05240 LecthJ 43 Verification Condition Generation 1 Mostly follows the definition of the wp function VCslltip B B c c2 B VCc VCc2 B if b than c else c2 B b 2 vcc B n 2b 2 VCc2 B x e B exB while b do c B 7 VC VC VC VC E05240 LecthJ 44 Verification Condition Generation for WHILE vcwniieI e do c a In xxIeoVCcI n2e2a V I holds I is preserved n B holds wnen tne on entry mm iteration loop terminates m an arbitrary iteration I is the loop invariant provided externally x1 xquot are all the variables modified in c The V is similar to the V in mathematical induction P0 n Vn e N Pn 2 Pn1 E05240 LecthJ 45 VC and Invariants Consider The Houre Triple XS0whileIXS5 dox x1x e The V6 for This is no Ix A VXIXltquotXgt5gtX6A x g 5 gt Ix1 RequiremenTs on The invarianT Holds on enTry w x e o e Ix Preserved by The body vX Ix A x e 5 e Ix1 Useful vX XAxgt5gtx6 Check ThaT Ix x s 6 saTisfies all consTruinTs E05240 Lemrem 46 Memory Aliasing E05240 Lemrem 47 Hoare Rules Assigmuem When is The following Houre Triple valid Ax5xy10 A oughT To be quoty 5 or x yquot The Hoare rule for ussignmenT would give us 5xx y 10 5 y 10 y 5 we losT one case How come The rule does noT work E05240 Lemrem 42 Handling Program State We cannot have sideeffects in assertions While creating the VC we must remove sideeffects But how to do that when lacking precise aliasing information 7 Important Technique Postpone alias analysis Model the state of memory as a symbolic mapping from addresses to values If E denotes an address and M a memory state then seIME denotes thecontents of the memor c updMEV denotes a newmemory state obtained from M by writ ng v at address E E05240 Lemmas 49 Hoare Rules Side Effects To model writes correctly we use memory expressions A memory write changes the value of memory BUPdP iEztlquotEi 23 Important technique treat memory as a whole And reason later about memory expressions with inference rules such as McCart y if EE3 52 selupdMEiE2Ea KM E ifE sE a i a E05240 Lemmas 5n Memory Aliasing Consider again A x 5 x y 10 We obtain A updm x We x y 10 updm x syn semi xsein y 10 S lLIPdH x 5 xselupdp x 5 y 10 5 S lLIPdH x 5 y 10 ifxythen55 10else5selii y 10 x y or y 5 To is theorem generation From to is theorem proving E05240 Lemmas 5i Proof Techniques for Language Analysis Lecture 3 E65 555 24a lecng Plan We39ll study various flavors of induction hemut cal induction wellfounded nduction structurulinduction E05 240 Lecluie z Induction Probably the single most important technique for the study of formal semantics of programming languages Of several kinds incitlieincit cal induction the simplest wellfounded nduction the most general structural induction the most widely used in PL E05 240 Lecluie z Mathematical Induction Goal prove that Vn E N Pn Strategy 2 steps 1 se case prove that P0 2 Inductive case 7 ich an arbitrary n e N assume that Pn holds 7 prove that M 1 7 or formally prove that Vn e N Pn m4 E05 240 Lecture 3 A Mathematical Induction Notes The inductive case looks similar to the overall goal Vn E N Pn a Pn1 vs Vn E N P n but it is s mpler because of the assumption that Pn hoids Why does mathematical induction work The key property of N is that there are no infinite descending chains of naturals It has to stop somewhere For each n Pn can be obtained from the base case and n uses of the inductive case E05 240 Lecture 3 5 Example of Mathematical Induction Recall the evaluation rules for IMP commands Prove that if 0x s 6 then ltwhilex e 5 dox i x10gtll 0X i e Reformulate the claim LetWwhileX55 doxx1 ox i Clam1IENltW pilot Now the claim looks provable by mathematical induction on i E05 240 Lecture 3 o Example of Mathematical Induction Base Case Bose casei0orltW 0 gt 00 To prove an evuluuTion judgment construct a derivation Tree 0000 6 ltx 00gt 6 lt6 5 5 00gt false ltx s 5 00gt J false ltWhll Xs5d0XlX1UOgtllUO This compleTes The base case E05 240 Lecture 3 7 Example of Mathematical Induction Inductive Case MusT prove Vi 6V ltW up 00 ltW 0M J 00 The beginning of The proof is sTruighTforword Pick an urbiTrury i e N i I 0n MUST construct a derivuTion Tree 1o gtJ6i ltxqgtl5i 545 ltXx10 gtlo ltW0 gtl0u ltx g 5 0 gt J True ltXx1 w 0 gt J on ltwhilexs5doxx1o gtlou E05 240 Lecture 3 2 Discussion A proof is more powerful Than running The code and observing The resLIlT Why The proof relied on a loop invoriunT g 6 n all iTer39uTions and a loop vorionT 6 x is posiTive and decreus quotg Picking The loop invoriunT and vorionT is Typically The hordesT porT of a proo E05 240 Lecture 3 9 Discussion We proved termination and correctness This is called total correctness Mathematical induction is good when we prove properties of natural numbers In PL analysis we most often prove propert es of expressions commands programs nput data etc We need amore powerful induction principle E05240 Lecture in Well Founded Induction A relation 4 Q A x A is wellfounded if there are no infinite descending chains in A Example lt xx 1 Ix e N the predecessor relation Examplelt gtlty lXyEN andxlty Wellfounded induction To prove Vx E A Px it is enough to prove in e A Vy 4 x e Py e Px If 4 is ltl then we obtain a special case of mathematical induction Why does it work see Winskel Ch 3 for a proof E05240 Lecture ii Well Founded Induction Examples Consider4 QNX Nwith x4y iffx 2 y w e N Vy 4 x e Py e Px is equivalent to P0 n P1 n 1n e N Pn e Pn 2 Consider 4 El x Z with x 4 y iff ylt0andyx1orygt0andyx1 P0t VX50PXvPx1 n VX20PXgtPX1 Consider 4 Q N x N x N x N and x1 y14gtlt2 y2 iff x2x1v X IXZAYZY 1 This leads to the nduction pr nciple P00 A 1 xyV Pxy gt Px 1 V A Px y 1 This is sometimes called lexicographic induction 05240 Lennie t2 Structural Induction Recall Aexp e e2e1 e2 x Define 4 Q Aexp x Aexp such that 4 e quot e and no other elements of Aexp gtlt Aexp are related by lt To prove Ve E Aexp Pe 1 Prove Vn E z Pn 2 Prove VX E Lee P X 3 Prove 1ee2 e Aexp Pe n Pe2 Pe e2 4 Prove 1ee2 e Aexp Pe n Pe2 gt Pe 22 E05240 Lecture 13 Structural Induction Notes Called structural induction because the proof is guided by the structure of the expression As many cases as there are expression forms Atomic expressions with no subexpressions are all base cases Composite expressions are the nductive cases This is the most useful form of induction in PL study E05240 Lecture 14 Example of Induction on Structure of Emressions Define Le the number of iiterais and variable occurrences n e 0a the number of operators n e Prove that Ve E Aexp Le Oe 1 By induction on the structure of e en Le1and0e0 Casee x Le 1 and 02 0 Casee ee2 Le Le Lez and Oe Oe 022 1 By nduction hypothesis Lz Oe land Lez 022 1 Thus Le Oe i1 Case e e 22 Same as the case for E05240 Lecture is Other Proofs by Structural Induction on Emressions Most proofs for Aexp sublanguage of IMP Smallstep and natural semantics Ve E Ex 39 Natural semantics and denotational semantics n Smallstep and denotational semantics Ve e39 e Exp egt e39 39 e a VeEExpVnENegt39 ngten Structural induction on expressions works here because all of the semantics are syntax directed E05240 Lecture 16 Another Proof Prove that IMP is deterministic EAexp10E21nn39E N lteogtll n A lteogtJl n39 a n n39 we Bexp10E21tt39E 13 ltbogtJl t A ltbogtJl t39 gt t t39 VCEComV00390 E2 lt90 039 A ltcogtll 0quot t 039 0quot No immediate way to use mathematical induction For commands we cannot use induction on the structure of the comm d Consider the rule for while Its evaluation does not depend i s on y on the evaluation of its strict subexpress on do 11 true ltc 11 039 while b do c 051 0quot while b do c 11 o E05240 Lecture 17 Induction on the Structure of Derivations Key idea The hypothesis does not assume just a c E but the existence of a derivation of ltc 11 o39 Derivation trees are also defined inductively just like expression trees A derivation is built of subderivations ltx1qgtlli clawi 5is5 ltxx10 gtllo ltWqgtllou ltx g 5 0 gt LL true ltxx1 w 0 gt LL on ltwhilexg5 dox x1q M on Adapt the structural induction principle to work on 39 i s the structure of derIvat on 505240 Lem 12 Induction on Derivations To prove that for all derivations D of ajudgment property P holds 1 For each derivation rule of the form H 2 Assume that P holds for derivations of H i 1 n 3 Prove that the property holds for the derivation o tained rom the derivations of H using the given rule E05240 Lecture 19 Example of Induction on Derivations I Prove that evaluation of commands is deterministic ltcogtii 039gtV0 E2ltcogtlloquotgto39 Pick arbitraryc o o39 and D 39 c evil 039 To prove V0quot E E ltc ogtll oquot t o39 oquot Proof by induction on the structure of the derivation D Case last rule used in D was the one for skip ltskip 0 ii 0 This means that c skp and 039 0 By inversion ltc 0 ii 0quot uses the rule for 5k p Thus 0quot 0 This is a base case n the induction E05 240 Lecture 3 2n Example of Induction on Derivations II Case the last rule used in D was the one for sequencing D D1ltc1 when D2ltc2 opilo39 ltc1 c2 0 ll 039 Pick arbitrary 0quot such that D 61262 by nversion D uses the rule for sequencing and has subderivations D 2 0 ii aquot and by By induction hypothesis on D1with Dquot1 01 o 1 Now Dquot2 ltc20gt 0quot By induction hypothesis on D2 with Dquot2 oquot o39 This is a simple inductive case 0quotigtll 0quot E05240 Lecture 21 Example of Induction on Derivations III Case The lasT rule used in D was The one for while True D ltb 0gtll true D2 ltc 0gtll o l3a ltwhile b do c opll 039 ltwhile b do c 0 ll 039 Pick arbiTrary 0quot such ThaT D39 ltwhile b do c owl oquot by nversion and determinism of boolean expressions D also e D uses The rule for while Tru and lies subderivaTions by 2 D it aquot and l3quota wit 0quot ll 0quot By inducTion hypoThesis on D2 wiTh Dquot2 N nilquot3 ltw ile b doc opll 0quot By inducTion hypoThesis on D3 wiTh Dquot E05 240 Lecture 3 22 Induction on Derivation Notes If we have To prove Vx E A Px Qx wiTh X nducTively defined and Px ruledefined we p ck arbiTr39aryx E A and D Px we could do inducTion on boTh facTs X E A leads l0 YldLlCllOYl on the SlV LlClLlV Z of X D 39Pgtlt leads to lnducllon on the structure of D eenerclly The induction on 39 more powerful and a safer beT In many siTuaTions There are several choices for inducTion choosing The righT one is aTrialanderror process a biT of pram ce can help at 0T E05 240 Lecture 3 23 Equivalence Two expressions commands are equivalenT if They yield The same resulT from all sTa es el mez iff V062 VnEN ltel ogtll n i1 1 lte2 ogtll n and for commands clue2 iffVod EX ltcl ogtll o39 iffltc2 ogt ll 039 E05 240 Lecture 3 24 Notes on Equivalence Equivalence is like validity m s 211IS Itke 211isvalidquot o 2 is not equlvalznl to 1 gtlt Equivalence for IMP is undecidable If it were we could solve the halting problem How Equivalence justifies code Transformations compiler optimizations de instrumentation abstract modeling Semantics is the basis for proving equivalence E05 240 Lecture 3 Equivalence Examples skip cmc x e1 x e2 a x e2 When is this true while b do cu if b then c while b do c else skip Ifelmezthenxeluxe2 while true do skip a while true do x x 1 Ifc is whilexsydo ifxzythenxzx yelseyyx then x 221 y 527 c a x 17 y 17 E05 240 Lecture 3 Proving An Equivalence Prove that skip c a cquot for all c Assume that D ltskip c 11 o39 By inversion twice we have that D ltskip 11 o D1ltc o J o39 ltskip c 11 o39 Thus we have D1ltc 71 o39 The other direction is similar E05 240 Lecture 3 Introduction to Lambda Calculus Lecture 1819 EC E05 240 Lecture my Plan Introduce lambda calculus 5V and operational semantics Propert es Relationship to programming languages later Study of types and type systems even later ms 240 team my Background Developed in 193039s by Alonzo Church Subsequently studied by man quotTestbedquot for procedural and functional languages Simple Powerful Easy to extend with features of inter est Plays similar role for PL research as Turing machines for Computability Whatever the next 700 languages turn out to be they will surely be variants of lambda calculus quot Landin 3966 05 240 mm my 3 Syntax The A calculus has three kinds of expressions terms e x Varia es Ax e Functions abstraction e1 e2 Application Ax e is a neargument function with body e e1 e2 is a function application Application associates to the left x y s x Abstr Ax action extends to the right as far as possible xkyx y 1 means Axgtlt Ay x y ms 240 Lscfius i249 4 Examples of Lambda Emressions The identity function I f A function that given an argument y discards it and yields the identity function39 A function that given a function f invokes it on the identity function Af f Ax x ms 240 Lscfius i249 Scope of Variables As in all languages with variables it is important to discuss the notion of sco kec II the scope of an identifier is theportion of aprogram where the identif er is accessible An abstraction Ax E binds variable x in E x is the newly introduced variable Just like formal function arguments are bound in the function body 555 24a Lscfius i249 Free and Bound Variables A variable is said to be m in E if it has occurrences that are not oun 39 We can define the free variables of an expression E recursively as follows Freex x FreeE E2 FreeE u FreeE2 Freenx E FreeE x Example Freeotx x Ay x y 1 2 Free variables are implicitly or explicitly declared outside the term ms 240 Lecture i249 7 Free and Bound Variables Cont Like in any language with statically nested scoping we need to worry about variable shadowing or capturing An occurrence of a variable might refer to different things in different contexts Eg inIMP with locals letxEinxletxE39inxx ll ll In A calculus Ax x Ax x x l l ms 240 Lecture i249 2 Renaming Bound Variables A terms that can be obtained from one another by renamin of the bound variables are considered identical This is called cxeguivalence Example xx x is identical to Ay y and to AZ 2 Intuition By changing the name of a formal argument and of all its occurrences n the function body the behavior of the function does not c an e In Acalculus such functions are considered identical ms 240 Lecture i249 9 Renaming Bound Variables Cont Convention we will always try to rename bound variables so that they are all unique eg unitan x Ayy x instead of Ax x Axx x This makes it easy to see the scope of bindings And also prevents confusion ms 240 Lecture i249 Substitution The substitution of E39 for x in E written EXE 5 ep 1 kename bound variables n E so they are un que Step 2 Perform the textual substitution of E39 for Example y xx x x ivy xx x y x After renaming y Av vx Az Au u z x After substitution Az Au u z y Av v If we are not careful with scopes might get M39 OXXvv AXgt0 ms 240 Lecture i249 Informal Semantics We consider only closed terms The evaluation of Ax e e39 1 Bi 2 2 Evaluates a with the new b ndi g 3 Yields the result of this evaluation Like a function call or like let x e39 in equot am le At f f e g avaluates to g g a ms 240 Lecture i249 Operational Semantics There exist many operational semantics for the A calculus All are based on the equation x e e39 p e39xe usually oriented from left to right This is called the rule and the evaluation step a reduction The subterm Ax e e39 is a redex e Hp e39 e reduces to e39 in one step HF e39 e reduces to e39 in 0 or more steps ms 240 Lecture i249 Examples of Evaluation The identity function xgtlt Egt ExxE Another example with the identity Af f Ax x Ax x a Axx f f Axx Ax x f f Ayy M X Avy a AvvXgtltAvv A nonterminating evaluation M XX7 Y W Ay yy xxx Ay WAy W a ms 240 Lecture i249 If we forget to rename the bound y Evaluation and the Static Scope The definition of substitution guarantees that evaluation respects static scopin A X W Y gt0 v M x as M 1 v M v H U y remains free ie defined externally A gtlt M39 v gt0 v AX x 5 Ay y y Av v tl Ll E U y was free before but is bound now 555 240 Lecture i249 Another View of Reduction The application APP Ax X X X Terms can grow39 becomes substantially through a re uctionl mm mm my 6 Normal Forms A term without redexes is in normal form A reduction sequence stops at a normal form If e is in normal form then e a e39 implies e e39 Examples Axky x normal form Ax Ay x xx x not normal form 555 24a innquot127w 17 Nondefer39minisfic Evaluation Define a smallstep reduction relation Ax e e39 gt e39xe e a equot 22 a 2239 2 22 H Equot 22 2 22 H 2 2239 E H 239 Ax e gt Ax e39 ote This is anondeterministic semantics We evaluate under A 555 24a innquot127w 12 The Order of Evaluation A A term can have more than one instances of Ax E E39 W Ax xy E A choice reduce the inner or the outer A Which one should we pick 1y Ax x y E Ay yx x E Ay y E outer Ey xx x y Ax x E E 555 24a teem my The Diamond Property A relation R has the diamond property if e R e and e k e2 implies there exists e39 with e k e39 and e2 k e39 Hp does not have the diamond property Hr has the diamond property The simplest known proof is quite technical ms 240 teem my The Diamond Property Languages defined by nondeterministic sets of rules are common Log c programming languages Expert systems Constraint satisfaction systems It is useful to know whether such systems have the diamond property 555 24a teem my Equa fy LeT p be The reflexive TransiTive and symmeTric closure o p is Hp u EB In anoTher words e B e2 if el converTs To e2 via a sequence of forward and backward a ms 240 Lecmre law 22 The Church Rasser Theorem If e1p e2 Then There exisTs e39 such ThaT e1 Hp e39 and e2 ag e39 V e Proof informal apply The diamond properTy as many Times as necessar ms 240 Lecmre law 23 Carol laries f e1 p e2 and e1 and e2 are normal forms Then ei is idenTicaI To e2 From Ck we have 3239 2 45 e39 and e2 a e39 Since e and e2 are normal forms They are idenTicul To 239 If e a39x e and e a e2 and ei and e2 are normal forms Then e1 is idenTicaI To e2 All Terms have a un qua normal form 555 240 Lecmre law 24 Evaluation Strategies ChurchRosser Theorem says ThaT independent of The redLIcTion sTraTegy we will noT find more Than o normal form BLIT some redLIcTion sTraTegies mighT fail To find a normal form Ax y mu 1 an m gt Ax y my 351011 m gt x y 111 1 My 34 gt y We will consider Three sTraTegies callbyvalue mm minim Normal Order Reduction A redex is oLITermosT if iT is noT conTained inside anoTher redex Use KAxkyx S M Agkxfxgx ExampleSny KLIv Kx KLIand Sny are allredexes BoTh KLIandSny are oLITe Normal order always reduces The le 39 sT T ffmosf outermost redex fir Theorem If e has a norm al form e39 Then normal order redLIcTion will reduce e To e39 555 24a innquot127w Why Not Normal Order In mosT all programming languages funcTions are considered values fully evaluaTed Example Ax D D L wiTh normal order where D xx x x Thus no redLIcTion is done under lambda No popular programming language uses normal order 555 24a innquot127w Call by Name Don39t reduce under A Don39t evaluate the argument to a function call A value is an abstraction e a Ax equot ezxe39 a e Ax ea Ax e 39 Callbyname is demanddriven an expression is not evaluated unless neede It is normalizing converges whenever normal order converges Callbyname does not necessarily evaluate to a normal form Example D D xx x x xx x x 555 240 mm my Call by Name Example KY AX X Y MI L000 v myquot xx x Au u Av v arm Au u Av v arm Avv ms 240 mm my Call by Value Evaluation Don39t reduce under lambda Do evaluate the arguments to a function call A value is an abstraction e aux equot 22 a 2239 e39Zxe39gtv39 e Ax ea Ax e e 22 gt 39 Most languages are primarily callbyvalue But CBV is not normalizing Ax I D D CBV diverges more often than normal order and CBN ms 240 mm my Call by Value Example KY AX X Y MI L000 0 ain 1y Ax xy Av v m xx x Av v AFN Avv ms 240 Leanne my Considerations Callbyvalue eas to implement wellbehaved predictable with respect to sideeffects Callbyname More difficult to implement must pass unevaluated expressions he order of evaluation is harder to predict eg diff culty with sideeffects Has a s mpler theory than callbyvalu e Allows thenatural expression of nfinite data structures eg streams Terminates more often than callbyvalue Various other not as common evaluation strategies ms 240 Leanne my 32 Functional Programming The A calculus is a prototypical functional language with 0 side effects several evaluation strategies lots of functions noth rig but functions pure Acalculus does not have any other data type How can we program with functions How can we program with only functions ms 240 Leanne my Programming With Functions Functional programming style is a programming style that relies on lots of functions A typical functional paradigm is using functions as arguments or results of other functions Higherorder programming Some quotimpurequot functional languages permit side 39 L effects e g Llsp references pointers inplace update arrays exceptions ms 240 Lecture my 34 Variables in Functional Languages We can introduce new variables I e1 in e2 x is bound b let x is statically scoped in e2 This is pretty much like Ax e2 e1 In a functional language variables are never updated they arejust names for expressions or values 59 x is aname for thevalue denoted by e in e2 This models the meaning of quotletquot in math ms 240 Lecture my 35 Referential Transparency In pure functional programs we can reason equationally by substitution x eine2 E exe2 n an imperative language a sideeffectquot in el might invalidate the above equation The behavior of a function in a pure functional language depends only on the actual arguments Just like a function in math This makes it eas er to understand and to reason about functional programs ms 240 Lecture my 35 Emressiveness of A Calculus The A calculus is a minimal system but can express data types integers booleans lists trees etc branch ng recursion This is enough to encode Turing machines Corollary e p e39 is LIndecidable Still how do we encode all these constructs using only functions Idea encode the quotbehaviorquot of values and not their structure Ecs 24a Lemquot1249 37 Encoding Booleans in Lambda Calculus What can we do with a boolean we can make abinary choice A boolean is a function that given two choices selects one of them true def Ax Ay x false de ex Ay y if E then E2 eIse E3 sagf E1E2 E3 Example if true then Ll else vquot is mm x uvgt5ky uvgt5u Ecs 24a Lemquot1249 32 Encoding Pairs in Lambda Calculus What can we do with a pair we can select one of its elements A air is a function that given a boolean returns the left or the right element mkpair x y sagf Ab b x y xample fst mkpar x y a mkpa r x y truegt truex ygt x Ecs 24a Lemquot1249 39 Encoding Natural Nunbers in Lambda Calculus What can we do with a natural number we can iterate a number of times over some function A natural number is a function that given an operation f and a starting value s applies f a number of times to S 0 sagf Af As s 1M At As f s 2 M At As f f s These are numerals in unary representation Also called Church numerals ms 240 mm my 40 Computing with Natural Numbers The successor function ucc n def if is f n f s or succ n M if is n f f s Addition add n1 n2 def n1 succ n2 Multiplication mult n1 n2 def n1 add n2 0 Testing equality with 0 iszero n def n Ab false true 555 240 mm my 41 Computing with Natural Numbers Example succnAfAsfnfs mult 2 2 a add n1 n2 n1 succ n2 mult nan n1 add n2 0 add 2 add 2 o a 2 succ add 2 o a 2 succ 2 succ o a succ succ succ succ o a succ succ succ Af As f o f s a succ succ succ Af As f s a succ succ Ag Ay 9 At As f s g y succ Succ 19M 9 9 Y 39 A9 Av 9 9 9 9 v 4 ms 240 mm my 42 Computing with Natural Numbers Example What is the result of the application add 0 Amme succn20 as Anz o succ n m M As 5 succ n2 as Anz n2 Ax x By computing with functions we can express some optimizations ut we need to reduce under the lambda ms 240 mm my 43 Encoding Recursion Given a predicate P encode the function quotfindquot such that quotfind P nquot is t e smallest natural number which is larger than n and satisfies P with find we can encode all recursion quotfindquot satisfies the equation n if p n then n else find p succ n Define F Mxpxnp n n fp succ n We need a fixed point of F f or findpnandpn ms 240 mm my 44 The Fixed Point Combinator Let Y AF Ay Fy y Ax Fgtlt x This is called the fixedp0 nt combinator Verify that v F is a fixed point of F V F H5 AvF YY M F X gt0 H5 F V F ThusYFBFF Given any function in A calculus we can compute its fixedpoint Thus we can define quotfindquot as the fixedpoint of the function from the previous slide The essence of recursion is the selfapplication y 555 240 mm my 45 Emressiveness of Lambda Calculus Encodings are fun BLIT programming in pure Aculculus is painful We will add constants 0 1 2 True false ifThen else etc And we will add Txges next Time ms 240 innquot127w 46 IMP and Operational Semantics Lecture 2 E65 555 24a LecmreZ Plan We39ll study a simple imperative language IMP Abstract syntax Operationalsemant cs Denotational semantics Axiomat c semantics and relationships between various semant cs with proofs Today operational semantics Ch 2 of Winskel E05240 Lesimez Syntax of IMP Concrete syntax The rules by which programs can be expressed as strings of characters Deals with issues like keywords identifiers statement separators terminators comments indentation etc Concrete syntax is important in practice For readability familiarity parsing speed effectiveness of erro I r recovery clarity of error messages Well understood principles f nite automate and contextfree grammars Automat c parser generators E05240 Lesimez Abstract Syntax We ignore parsing issues and study programs given as abstract syntax trees AST Abstract syntax tree is the parse tree of the pro ram Ignores issues like comment conventions More convenient for formal and algorithmic manipulation Fa rly independent of the concrete syntax E05240 Lsamnz A IMP Syntactic Entities Int integer literals n E Z Baal Boolean values true false Loc locations updateable variables xy Aexp arithmetic expressions e Bexp Boolean expressions b Com commands 5 E05 240 Lecth 5 Abstract Syntax Aetqa Arithmetic expressions Aexp e n x for x E Loc e1 e2 for e1 e2 E Aexp e1 e2 for e1 e2 E Aexp e1 e2 for e1 e2 E Aexp otes Variables are not declared All variables have integer type No sideeffects in expressions E05240 Lsamnz o Abstract Syntax Benn Boolean expressions Bexp true I false I e1 e2 for e1 e2 E Aexp e1 e2 for e1 e2 EAexp b for b E Bexp b1 A b2 for b1 b2 E Bexp b1 v b2 for b1 b2 E Bexp E05240 Lsaiuisz 7 Abstract Syntax Com Commands Com s lp xe foerLocondeEAexp 61262 for 1 2 E Com I if b then cl else 2 for 6162 E Corn and b EBexp Iwhilebdoc forcECom ondbEBexp Notes The typ rig rules have been embedded in the syntax definition Other parts are not contextfree and need to be chec ed separately eg all variables are declared Commands contain all the sideeffects in the language Missing pointers function calls E05240 Lsaiuisz 2 Analysis of IMP Questions to answer what is the meaningquot of a given IMP expression or command How would we go about evaluating IMP expressions and commands How are the evaluator and the meaning related E05240 Lsaiuisz 9 An Operational Semantics Specifies the evaluation of expressions and commands Abstracts the execution of a concrete interpreter Depending on the form of the expression o 1 2 don39t evaluate any further Tnev are normal forms or M e e2 is evaluated by first evaluating e to n tlien evaluating 22 to n We result of tne evaluation is tne literal representing n n2 Similar for e e2 E05240 LecimZ in Semantics of IMP The meaning of IMP expressions depends on the values of variables The value of variables at a given moment is obstructed as a function from Loc to Z a state The set of all states is E Loc a Z We use a to range over 2 E05240 LecimZ ii Judgment Use lte 0 l n to mean e evaluates to n in state a This is a judgment a statement to relate e 0 and n it view it as a function with two arguments e and 0 This formulation is called natural operational semantics Or bigstep operational semantics The judgment relates the expression and its quotmeaningquot Next we need to specify how l is defined E05240 LecimZ i2 Rules of Inference We express the evaluation as rules ofmference for our judgment called the derivation rules for the judgment also called the evaluation rul25for operational semantics In general we have one rule for each language anstruct Example e1 e2 lte1 0 n1 lte2 0 n2 lte1e2 ogtJt39I1t39I2 E05240 Lecth 13 Evaluation Rules for Aem ltn ogtJn lte1 o J nl lte2 0 n2 ltx o J ox lte1 0 nl lte2 0 n2 lte1e2 ogtJt39I1t39I2 lte1 o J n1 lte1e2 ogtJt39I1YI2 lte2 o J n2 lte1e2 ogtJn1n2 This is called structural operational semantics rules defined based on the structure of th e expression These rules do not impose an order of evaluation E05240 Lecth 14 Evaluation Rules for Benn lttrue o J true lte1 o J nl lte2 0 n2 ltfalse o J false lte1 0 nl lte2 0 n2 lte1e2 ogtJt39I1t12 ltll o J false do A b 0 false 1 2 ltll 0 true 61562 ogtJt39llst12 ltl2 o J false ltb1A l2 0 false ltl2 0 true ltb1A l2 o J true E05240 Lecth ts How to Read the Rules Forward as inference rules if we know that the hypothesisjudgments hold then we can infer that the conclusionjudgment also holds 29 if we know that e l 5 and e2 l 7 then we can infer that e e2 ll 12 E05240 Lestmz lo How to Read the Rules Backward as evaluation rules Suppose we want to evaluate e e2 ie find n st e e2 ll n is derivable using the previous rules By nspection of the rules we notice that the last step in the derivation of e e2 l n must be the addition rule the other rules have concluslons that would not match e v e2 it n Thus we must find n and n2 such that 21 n and e2 l n2 are derivable This is done recurslvely Since there is exactly one rule for each kind of expression we say that the rules are syntaxdirected At each step at most one rule up lies This allows a simple evaluation procedure as above EcszAa Lecth Evaluation of Comands Evaluation of AexpBexp produces direct results a number or a Boolean value but has no sideeffects Evaluation of Com has sideeffects but no direct result The quotresultquot of aCom is a new state c a l a The evaluation of Com may not terminate E05240 Lestmz i2 Evaluation Rules for Com lte ogtJl39l e ogtJox n lt610gtJo39 ltc2 ogtJo ltskip ogtJ o 6162 0 U 0 ltb 0 true ltc1 o J o39 ltb o J false ltc2 o J o39 ltif b then c1 else c2 0 J o39 ltif b then c1 else c2 0 J o39 ltb 0 true ltc while b do c o J o39 ltb 0 false ltwhilebdoc ogtJ o39 ltwhile b do c o J 0 1505240 Lecth Notes an Evaluation of Commands The order of evaluation is important a is evaluated before c n o c2 is not evaluated in if true t c is not evaluated in while fa se b is evaluated first n if b then a else c2quot this is explicit n the evaluation rules The evaluation rules are not smtaxdirected See the rule for wh39 The evaluation might not terminate The evaluation rules suggest an interprete c hen o else o2 cquot t only one can be applied at one time E05240 Leetiuez Conditional constructs have multiple evaluation rules Disa Sem dvantages of Natural Style Operational antics Naturalstyle semantics has two disadvantages I t There is no 0 s away two commands is lnterlea Execution is modeled as a possible infinite seque s s E05240 Leetiuez t is hard to talk about commands whose evaluation does not erminate But that is true also of lllrfor ed or err neous commands to talk about intermediate states It does not giv Thus we cannot say that on aparallel mach ne the execution of ed Smallstep semantics overcomes these problems nce of Contextual Semantics Contextual semantics is a smallstep semantics where the atomic execution step is a rewrite f the program We will define areation ltc o gt ltc39 039 c39 is obtained from c through an atomic rewrite step Evaluation terminates when the program has been rewritten to a fErmin lprDyr One from wh ch we cannot mahe further progress For IMP the terminal command is quotskipquot As long as the command is not skip we can make further progress Some commands never reduce to ship e g while true do shp E05240 Lestiire2 22 What is an Atomic Reduction We need to define What constitutes an atomic reduction step Granuiarlty is acho ce of the semantics designer e g choice between an addition of arbitrary ntegers or an addition of 32bit ntegers How to select the next reduction step when several are possible This is the order of evaiuatlon issue E05240 Lestiire2 23 Redexes A redex is a syntactic expression or command that can be reduced transformed in one atomic step Defined as a grammar r x n n2 x n sk p c i if true then c else c2 i if false then c else c2 I while b do c For brevity we mix expression and command redexes Note that 1 3 2 is not a redex but 1 3 is E05240 Lestiire2 24 Local Reduction Rules for IMP One for each redex ltr o gt lte 039 m ans ThaT n sTaTe 0 The redex r can be replaced in one sTep wiTh The expression e ltx ogt a ltox ogt ltn1 n2 0 ltn o where n n1 n2 ltn1 n2 0 a ltTrLle o if n1 n2 ltx n o gt ltskip ox ngt ltskip c o gt lt1 0 ltif True Then cl else 2 o gt 1 o ltif false Then cl else c2 0 gt lt1 0 while b do 6 o a ltif b Then 6 while b do c else skip o E05240 LechlreZ 25 The Global Reduction Rule General idea of The conTexTLlal semanTics Decompose The currenT expression quotTo The redex To reduce nexT and The rema n rig progra The remaining program is called a coniexi The resulTing expression consisTs of quotequot wiTh The original Conlexl We use H To range over conTesz We wriTe Hr for The expression obTained by placing redex r in conTexT H Now we can define a small sTep If ltr o a lte 039 Then ltHr o a ltHe 039 E05240 LechlreZ 25 Contexts A conTexT is like an expression or command wiTh a marker I in The place where The redex goes ConTexT are also called expressions wiTh ahole The marker is someTimes called a hole Hr is The expression obTained from H by replac rig wiTh The redex r like The subsTiTuTion rH ConTesz are defined by a grammar nHHexHifHThenc1elsec2 H c E05240 LechlreZ 27 Contexts Notes I A context has exactly one I marker A redex is never a value Contexts specify precisely how to find the next redex Consi er e e2 and its decomposition as H r IfeismandezisnzthenHandrnn2 In the last two cases the decomposition is done recursively Check that in each case the solution is unique E05240 Lssiunz 22 Contextual Semantics Notes II g c c1 c2 either a skpand then c Hskp cg with H or a a skip and then a Hr so c H39r with H39 H c2 E9 cifbthenc1 else c2 either b true or b false and then c Hr with H or b is not avalue and b Hr so c H39r with H39 if H then a eiseo2 Decomposition theorem ski quot then there exist LInigLIe H and r c is r H a 3 o Exist means progress Unique means determinism E05240 Lssiunz 29 Contextual Semantics Example Consider the smallstep evaluation of x s 1 x x 1 in the nitiaI state x o State Context kedex ltx x x1x gt 39xx1 x 1 ltskipxx1 x 1 skipxx1 ltxx1x1gt x 1 x ltx11x1gt x 11 ltxx1gt x2 ltskip x 2 505240 Lawn 3n Contextual Semantics Notes What if we want to express shortcircuit evaluation of A 9 D rul ef he the following contexts redexes and local reduction es H H A b2 true A b Ifalse A b ltfals e ogt the local reduction kicks in before b2 is evaluated E05240 LectureZ Contextual Semantics Notes One can think of the I as representing the program oLIn er The advancement rules for o are non trivial At each step the ent re command is decomposed This makes contextual semantics ineff cent to mplement d rectly it allows a mix of local and global reduction rLIles For red d The major advantage of contextual semantics is that IMP we have only local reduction rules only the redex is uce Sometimes it is useful to work on the context too E05240 LectureZ