ࡱ> 'G( I/ 00DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 00DWingdings MSn0:A 0 C.  @n?" dd@  @@`` `k)2 .V.j(jD>#$!  %$#"557&()  5< 5 -5  +*43' 6C X0e0e    A A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|ES"@8\ʚ;ʚ; g4hdhd :A 0ppp@ <4!d!dL$ 0l%<4ddddL$ 0l%g4CdCd :A 0p@ pp<4BdBdL$ 0l%j0___PPT10 *___PPT9 z? %O 5;3)Statement ComponentiIF next-is-empty THEN move turnright ELSE IF next-is-enemy THEN infect END IF END IFjZj AK?Statement Component L@Statement Component UF BL StatementsVGBL Statements: IFWHBL Statements: IF_ELSEXIBL Statements: WHILEYJBL Statements: CALLZK An ExampleWHILE true DO IF next-is-enemy THEN infect ELSE IF next-is-empty THEN move ELSE turnleft END IF END IF END WHILEZ4*(Statement Continued& ]Type Statement_Kernel is modeled by STATEMENT Initial Value IS_INITIAL_STATEMENT (self) r. I5+(Statement Continued& math subtype STATEMENT_LABEL is ( kind: Statement_Kind test: Condition instruction: IDENTIFIER ) constraint & math subtype STATEMENT is tree of STATEMENT_LABEL exemplar s constraint IS_LEGAL_STATEMENT (s)  Z b    6,(Statement Continued& *Statement_Kind BLOCK IF IF_ELSE WHILE CALL& Condition NEXT_IS_EMPTY NEXT_IS_NOT_EMPTY NEXT_IS_WALL NEXT_IS_NOT_WALL NEXT_IS_FRIEND NEXT_IS_NOT_FRIEND NEXT_IS_ENEMY NEXT_IS_NOT_ENEMY RANDOM TRUE, ZZ 7-(Statement Continued& IS_LEGAL_STATEMENT?,!Statement OperationssOperations s.Add_To_Block (pos, statement) s.Remove_From_Block (pos, statement) s.Length_Of_Block () s.Compose_If (cond, block) s.Decompose_If (cond, block) s.Compose_If_Else (cond, if_block, else_block) s.Decompose_If_Else (cond, if_block, else_block) s.Compose_While (cond, block) s.Decompose_While (cond, block) s.Compose_Call (inst) s.Decompose_Call (inst) s.Kind () > h h-"Statement Block OperationsZs.Add_To_Block (pos, statement) s.Remove_From_Block (pos, statement) s.Length_Of_Block ()  Z[.#Statement If Operations7s.Compose_If (cond, block) s.Decompose_If (cond, block)88/(Statement If_Else Operationss.Compose_If_Else ( cond, if_block, else_block) s.Decompose_If_Else ( cond, if_block, else_block),$>0'Statement While Operations=s.Compose_While (cond, block) s.Decompose_While (cond, block)>>1&Statement Call Operations-s.Compose_Call (inst) s.Decompose_Call (inst)..2%Statement Other Operations s.Kind ()   OAUsing Statement Operations:What operations are needed to produce Statement if_stmt =$;11PBUsing Statement Operations RCUsing Statement OperationsCShow the operations to produce If_Else_stmt on the previous slide: &D  SDPractice Operation_Most operations on Statement have to be recursive Use 5 step process to recursion: 0. State the problem 1. Visualize recursive structure 2. Verify that visualized recursive structure can be leveraged into an implementation 3. Visualize a recursive implementation 4. Write a skeleton for the operation body 5. Refine the skeleton into an operation body0SZ ZS 8.%Step 0: State the ProblemProcedure Demobilize replaces every occurrence of the  move instruction in statement s with a  skip instruction. global_procedure Demobilize ( alters Statement& s ); /*! ensures s = DEMOBILIZE (#s) !*/s{s tj9/Demobilize this Statement:0LStep 0: State the Problem Continued& Rmath definition DEMOBILIZE ( s: STATEMENT ): STATEMENT satisfies if root (s).kind = CALL then if root (s).instruction =  move then DEMOBILIZE (s) = compose ((CALL, TRUE,  skip ), empty_string) else DEMOBILIZE (s) = s else there exists label: STATEMENT_LABEL, nested_stmts: string of STATEMENT (s = compose (label, nested_stmts) and DEMOBILIZE (s) = compose (label, STRING_DEMOBILIZE (nested_stmts))X*Z4 !'   D 5*tZ"] u 7 ] ;1LStep 0: State the Problem Continued& math definition STRING_DEMOBILIZE ( str: string of STATEMENT ): string of STATEMENT satisfies if str = empty_string then STRING_DEMOBILIZE (str) = empty_string else there exists s: STATEMENT, rest: string of STATEMENT (str = * rest and STRING_DEMOBILIZE (str) = DEMOBILIZE (s) * STRING_DEMOBILIZE (rest))"     , 6 +h,B  o4B<2(Step 1: Visualize Recursive Structure=3&Step 2: Verify That Leveraging Works Ask yourself: If Demobilize could get a helper to demobilize the nested statements in each of the five (four?) cases, could it take advantage of this generous offer? Yes! Once you know how to demobilize the nested statements, you can demobilize the entire statement.>4RStep 2: Let s Jump Ahead*procedure_body Demobilize ( alters Statement& s ) { case_select (s.Kind ()) { case BLOCK: {Demobilize_Block (s);} break; case IF: {Demobilize_If (s);} break; case IF_ELSE: {Demobilize_If_Else (s);} break; case WHILE: {Demobilize_While (s);} break; case CALL: { object Text inst, skipinst =  skip ; s.Decompose_Call (inst); if ( inst ==  move ) { inst &= skipinst; } s.Compose_Call (inst); } break; } }<Z0" dZZ    $   Re @ ( %#@B#?5~Step 2 (or back to Step 0 L): State the Problem$@#global_procedure Demobilize_Block ( alters Statement& s ); /*! requires root (s).kind = BLOCK ensures s = DEMOBILIZE (#s) !*/Z   @6Steps 1-5 Condensed (BLOCK) object Statement nested; object Integer pos; while (pos < s.Length_Of_Block ()) { s.Remove_From_Block (pos, nested); Demobilize (nested); s.Add_To_Block (pos, nested); pos ++; }X>= 0$A7xStep ? (or back to Step 2 ): State the Problem Continued& $=!global_procedure Demobilize_If ( alters Statement& s ); /*! requires root (s).kind = IF ensures s = DEMOBILIZE (#s) !*/    " B8Steps 1-5 Condensed (IF) object Statement if_blk; object Integer cond; s.Decompose_If (cond, if_blk); Demobilize (if_blk); s.Compose_If (cond, if_blk);Bc TESteps 1-5 Condensed (IF_ELSE)  cprocedure_body Demobilize_If_Else ( alters Statement& s ) { // You try it! }PdZ 2CC9Statement: RepresentationThe representation for Statement_Kernel_1 has one field: tree_rep: a Tree_Of_Tree_Node where a Tree_Node is a Record with three fields: kind: Integer test: Integer instruction: Text 9O.     D:Statement: CorrespondenceNself, the Statement, is equal to self.tree_rep, the Tree used to represent it.8O !E;Statement: ConventionAll the labels in the tree, tree_rep, are legal statement labels (i.e., they satisfy the constraint for the definition of STATEMENT_LABEL); The tree itself is a legal statement (i.e., it satisfies the constraint for the definition of STATEMENT).$F<Statement: CCDG=Statement: Compose_IfH>Statement: Decompose_If/pJMNQZ ` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@(?n<d@ `7 `2@`7``2 n?" ddH@ f @`PR    @ ` ` p>>-K0  z   (     <+%" .  T/%d" .  <2%"U_ .  Tp6%d">& .  Nt4%"P .  <9%"{ .  C xL%?d?"mU .  6% "` % T Click to edit Master title style! !$  0d% " " % RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6% "@ % B*  6f% "@`  % D*  6 T% "` % D*B  s *޽h ? 13 321=  -K0   k (  T +  "+bb P@ # "Dwoh  s *"PP  Bd" P@bb P 0  # "Nyh  s *"P    Bd"P 0 z   <" a*h   s *"    f?d?"+)   < ?"pP  T Click to edit Master title style! !   0 " `    W#Click to edit Master subtitle style$ $  64 "`p   F*  6H "`p   H*  6 "`  H*B  s *޽h ? 13* 0 P:(    0, P    \*   01     ^* d  c $ ?    04  @  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6; `P   \*   6D `   ^* H  0޽h ? ̙3380___PPT10.glC( DH(  D D 0 P    B*  D 0H;     D*  D 68; `P  ; B*  D 6h ; `  ; D* H D 0޽h ? ̙3380___PPT10.g DW -K0 % 0c(  x  c $@ `   x  c $| 0@  +  N 8c?" @0@ -How can we use tree to model a BL statement ?V.  H  0޽h ? 13A  -K0 %    L- (  Lx L c $. `  .  L Np8c?"P  \"What s wrong with 8 V&  LX(  L  `X 8c?" Z KIF_ELSE NEXT_IS_EMPTY L  `h 8c?"V _Z  ? CALL move   L  `芻 8c?" &Z  FIF NEXT_IS_ENEMY L TD 8c?" 0 K  A CALL infect    L N8c?" b   L  `tE 8c?" Z  fCALL turnright B L ZD8c?"Z B L ZD8c?"Z B L ZD8c?" Z + H L 0޽h ? L L 13 -K0 % =5T (  Tx T c $' `    T N/8c?")] QAn Abstract Syntax Tree \ 8 @0j Tj T # lR 8c?"  KIF_ELSE NEXT_IS_EMPTY  T  ``D 8c?"f 0  fCALL turnright  T # lt 8c?" f 00  FIF NEXT_IS_ENEMY T Tp 8c?" M j A CALL infect   T  `(Q 8c?" g  ;BLOCK  T  `Y 8c?"`V`  ;BLOCK  T  `$ 8c?" Vi `  ;BLOCK  TB T8c?" N  T  `8c?" ( N  TB  `8c?"h ^  TB  `8c?"' h ( ^  TB T8c?"& 8 '  T  `8c?"& (  T  f<$ 8c?"@P I  ? CALL move  B TB  `D8c?"`` P H T 0޽h ?oT T TT T T TT T TTTTTTTTT 13     _ (  x  c $ `      fp$8c?">}  KIF test THEN END IF  Z8c?" X   `1?"    f\$8c?" @}  OWHILE test DO END WHILE  Z8c?"= X   `1?",     fTE$8c?"B T  T IF test THEN ELSE END IF!!   Z8c?"$ k   Z8c?" $ *    Z1?" l     f,O$8c?"/ x)  ? instruction     `1?" P@l H  0޽h ? 13  8 0 @ (  x  c $D$ `      f+$8c?"R =  KIF test THEN END IF  Z8c?"p    `1?"p P z j  j,$D 0   fp$ 8c?" j =IF testB   `D8c?" `hz r%    r% ,$D 0   ZL$ 8c?" pz  ;BLOCK   Z8c?"rh   Z8c?" H   B N8c?"O V   N8c?" aV    f  8c?"@    f$ 8c?" %  ;. . . 2   ` 8c?"P,$D 0H  0޽h ?O        13  ___PPT10 +RID ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +!  ZR@(  x  c $i$ `  $ bz r%   r% ,$D 0  Z~$ 8c?"6pz  ;BLOCK B Z8c?"xrh  Z8c?"x xH  B N8c?" xV   N8c?"x V     `|  8c?"     fJ$ 8c?" e%  ;. . .     f`L$8c?"R  T IF test THEN ELSE END IF!!   Z8c?"p1    Z8c?" p   Z1?"v 2z P   P ,$D 02   ` 8c?"P2   ` 8c?"0  z     ,$D 0   fD$ 8c?"aj B IF_ELSE test  B   `D8c?"`B   `D8c?" Vz r   r ,$D 0  Z#$ 8c?"?pz  ;BLOCK  N8c?"rh  Z8c?" H  B N8c?" V   N8c?" V    f0$ 8c?" n%  ;. . .    ` 8c?"P  H  0޽h ? 13  ___PPT10 +eD ' = @B Dm ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+  3 + 0; (  x  c $<% `   z @j  @j,$D 0   f$ 8c?" j @ WHILE test  B   `D8c?"@ `bz r%   r% ,$D 0  Z$ 8c?"pz  ;BLOCK  Z8c?"TrTh   Z8c?"T TH   B N8c?" TV    N8c?"T V     `  8c?"~ :     f\$ 8c?"s A%  ;. . . 2  Z 8c?"k,$D 0   f$8c?"l =  OWHILE test DO END WHILE  Z8c?"p    `1?"p P H  0޽h ?O    13  ___PPT10 +7шD ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+}   p (  x  c $% `   "z S.  S.,$D 0   fx" 8c?"~ S. FCALL instructionB   `D8c?"  2  Z 8c?"` ,$D 0F  `   x   fD"8c?"(#   ? instruction      `1?" ` H  0޽h ? 13 ___PPT10+AD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+h)  D<`(  x  c $" `  " x  c $L!"  @  " z " ?a    " ?Q ,$D 0   f"" 8c?"" ?a  A CALL infect    Z8c?"1 1  z ';   +' ,$D 0  Z'" 8c?"'  ? CALL move     Z8c?";  z  3     #,$D 0    fX," 8c?" ia  KIF_ELSE NEXT_IS_EMPTY   Z|0" 8c?"< @3  ;BLOCK   Z8c?"   B Z8c?"i 4   NH " 8c?".- $  ;BLOCK  N8c?"i p% z ,   q,$D 0  Nؼ" 8c?"  C CALL turnleft  N8c?"p, p z 0  p0,$D 0   f" 8c?"0$ @ WHILE TRUE    Z" 8c?"L ;BLOCK  Z8c?"q,tz       ,$D 0   f" 8c?" 3P KIF_ELSE NEXT_IS_ENEMY  Z0 " 8c?" Y  ;BLOCK  Z" 8c?"   ;BLOCK B N8c?"1Xr  Z8c?"rX B N8c?"rtH  0޽h ?@          13___PPT10+=D' = @B DC' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+ -K0 P<(  ~  s *" `  " ~  s * "  " " H  0޽h ? ̙33 -K0 @0(  x  c $h" `   x  c $"  " " H  0޽h ? 13 -K0 nf0(  x  c $" `   ~  s *" I " " x  c $"  " " @  ZD"8c?"  rThese are all integer values, but we use the names because they are more meaningful than arbitrary integer values.ssH  0޽h ? 13C -K0   (  x  c $% `     c $p% "<$ 0 % o8 0`Y  ` @ 0Y  0`Y:   # lLc" 8c?"0Y B IF condition     ``d" 8c?"  ;BLOCK B T8c?" G p  0`Y: ,$D 0    f`" 8c?"G p  EWHILE condition   Z" 8c?"  ;BLOCK   N8c?"  &    fp" 8c?" j ,$D 0 FCALL instructiong  `:     `n : ,$D 0   fܸ" 8c?"L `{* GIF_ELSE condition  Z" 8c?" 0 <:  ;BLOCK B N8c?" 2(   Z;" 8c?"0 :  ;BLOCK  B8c?"2(    `l=" 8c?" #  ;BLOCKB B  `D8c?"`     `z 8c?"   8& B B  `D8c?"@  B   `D8c?"  H  0޽h ?O  13Z -K0 P(  x  c $" `  " ~  s *y"   "    `8c?"',$D 0   `8c?" ,$D 0   `8c?" k ,$D 0   `8c?"W 7 ,$D 0   `8c?"A ,$D 0H  0޽h ? 3333*"___PPT10+DrD' = @B D' = @BA?%,( < +O%,( < +DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<* D' =1:Bvisible*o3>+B#style.visibility<* %(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(+ -K0  6(  x  c $w `   ~  s *4w  0  w H  0޽h ? 3333 -K0 6(  x  c $ w `   ~  s *4w   w H  0޽h ? 3333 -K0 6(  x  c $w `  w ~  s *0 w   w H  0޽h ? 3333 -K0 6(  x  c $)w `  w ~  s **w   w H  0޽h ? 3333 -K0 6(  x  c $`7w `  w ~  s *,9w   w H  0޽h ? 3333 -K0 6(  x  c $Cw `  w ~  s *Dw   w H  0޽h ? 3333+ -K0   \ (  \r \ S dQw `  w r \ S 8Rw P " w b \  fSw 8c?"5 / ,$D  0 &object Statement call, block, if_stmt;&'!F  \ Z4Yw 8c?"%  ,$D  0 z8object Text inst =  infect ;&  \ # l<^w 8c?"J  FIF NEXT_IS_ENEMY  \ T_w 8c?"   A CALL infect    \  `fw 8c?" *  ;BLOCK  \ T8c?"R   \  `8c?"  ? \  f`kw 8c?"@ v: ,$D  0 gcall.Compose_Call (inst); 7 \ Zow 8c?"0 P* ,$D  0 kblock.Add_To_Block (0, call); ` \  f1 8c?"  ,$D  0 $object Integer cond = NEXT_IS_ENEMY;&%Y \  fsw 8c?" {,$D  0 !if_stmt.Compose_If (cond, block);""$ H \ 0޽h ?/@ \ \ \ \ \\ 3333___PPT10+HD' = @B D' = @BA?%,( < +O%,( < +D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*\D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*\D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* \%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* \D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* \D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*\D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*\D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*\D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*\D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*\D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*\D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*\D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*\+P+0+\w ++0+ \w ++0+\w ++0+\w ++0+\w ++0+\w + -K0 % }u` U(  `x ` c $w `  w E `  fw 8c?"h3  7Consider Statement object If_Else_stmt with this value:,8  P 8 j `j ` N8c?"gd h  `  `w 8c?" m. KIF_ELSE NEXT_IS_EMPTY  `  `,w 8c?"* B  fCALL turnright  ` # lw 8c?":   FIF NEXT_IS_ENEMY ` T|w 8c?"X j A CALL infect   `  `̖w 8c?"Xx u\  ;BLOCK `  `ܙw 8c?" P 4 ;BLOCK  `  `+B#style.visibility<*h%(D' =-o6Bdissolve*<3<*hD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =-o6Bdissolve*<3<*hD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*h%(D' =-o6Bdissolve*<3<*h+B -K0 plj(  lx l c $+B#style.visibility<*/%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*1%(+p+0+1 ++0+/ +4 -K0 P\(  x  c $  `     c $d  P<$ 0  H  0޽h ? 33334 -K0 0\(  x  c $ `     c $x  0<$ 0  H  0޽h ? 33333 -K0 ## 56I"(  x  c $ܭ `      f 8c?"0A 9s =   Z 8c?"@P z  P   P,$D 0T 0 P  #  PN G     ;!v     f 8c?"   ;BLOCK   T 8c?"G )    T 8c?"     B T8c?"     T8c?"     T 8c?"N     B T8c?"      `v 8c?" J  9...   Z 8c?"0 P B   fD8c?"`    f 8c?"P  Yroot (s).kind = BLOCK(z PP  PP,$D 0yN P   P@{N )3   q%    f 8c?")Y =IF test   T 8c?"0 3  B T8c?"fag)   Z 8c?"P B   fD8c?"Pp   f 8c?"   Vroot (s).kind = IF(/l b  6b ,$D 0 gU  # W b ,$D 0N .0.   %/%    f 8c?".0^ B IF_ELSE test     T 8c?"+ .  !B T8c?"[f$  " T 8c?"^+ *.  # T8c?"f$  $ Z 8c?"gU B % # lD8c?"   & # l0 8c?" B   [root (s).kind = IF_ELSE(z  @ '  @,$D 0T  B  (#  ` @~N P ^  ) I W  *  f 8c?"P   @ WHILE test    + T 8c?"[ V^  ,B T8c?" T  - Z 8c?" B B .  fD8c?" P 0  /  f 8c?" z  Yroot (s).kind = WHILE(8z    0   ,$D 0T  p 1# 0   2  f 8c?"( `X  FCALL instruction  3 Z 8c?" pB 4  fD8c?" P  5  fl 8c?"   Xroot (s).kind = CALL(H  0޽h ?   *+, !"# 3333___PPT10+D' = @B DX' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D' =-o6Bdissolve*<3<*6D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*'%(D' =-o6Bdissolve*<3<*'D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-o6Bdissolve*<3<*0+  -K0 \(  x  c $ `     c $$  "<$ 0  H  0޽h ? 3333~v___PPT10V.+NwnD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =-o6Bdissolve*<3<* +8+0+ + -K0  0(  x  c $ `   x  c $h p  H  0޽h ? 33334 -K0 `\(  x  c $L `     c $. Pp"<$ 0  H  0޽h ? 33336 -K0 F >  n (   x   c $H `      c $I [p<$D 0  il  #  N ,$D  0    fJ 8c?" Q  9s =  0 P   # @#,$D  0N G      ;!v      f(Q 8c?"   ;BLOCK    T 8c?"G )     T 8c?"     B T8c?"     T8c?"      T 8c?"N      B T8c?"       `V 8c?" J  9...    Z 8c?"0 P    ZxT8c?"l Qprocedure_body Demobilize_Block ( alters Statement& s ) { }hR0n<Z "$3H   0޽h ??`          3333)*!*___PPT10*.+G39D)' = @B D\)' = @BA?%,( < +O%,( < +D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* /%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* /D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* /D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* /S%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* /SD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* /SD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* SV%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* SVD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* SVD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* V}%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* V}D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* V}D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* }%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* }D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* }D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<* D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<* +8+0+  +4 -K0 \(  x  c $ `     c $ 2P0<$ 0  H  0޽h ? 3333+B#style.visibility<*%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*0D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*0D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0P%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*0PD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*0PD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Pf%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*PfD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*PfD{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*f%(D' =+4 8?dCB0-#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*fD' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*f+8+0+ + -K0 OG p(  px p c $B `    p c $` <$D 0  '8 :^`  p:^`   p # l" 8c?":,$D 0 9s = T gU   p# ^` N .0.   p %/%  p  f9 8c?".0^ B IF_ELSE test    p T 8c?"+ .  pB T8c?"[f$  p T 8c?"^+ *.  p T8c?"f$  p Z 8c?"gU H p 0޽h ?/@pppppp 3333 -K0 (0(  (x ( c $" `   x ( c $&  "  H ( 0޽h ? 13 -K0 ,0(  ,x , c $( `   x , c $  "  H , 0޽h ? 13 -K0 00(  0x 0 c $|5 `   x 0 c $x7  "  H 0 0޽h ? 13& -K0 }&u&;;4 &(  4x 4 c $> `   F P@ 4   " 4  f 8c??P@ 4  fB 8c?? <S_Type 4  `XG ??p% j 7extF  4 " 4  f 8c??  4  fX: 8c??" DS_Pretty_PrintB  4 # lDjJ??0 0 B  4 3 rZDjJ??   4  `  ??  7extB  4 # lDjJ??pp  4  `TR ??Q  5iF  4 \ 4  ` p?? 4  fM p?? FS_Pretty_Print_1B 4 # lDjJ?? 4  `dY ??p[j 5i 4  `] ??` UZ 7extB 4 3 rZDjJ??P PB 4 3 rZDjJ??P PF P@ 4   " 4  f p??P@ 4  f0 p?? >S_Kernel  F P@ 4    4  ` p??P@ 4  fc p??_1 @ S_Kernel_1   4 NjJ?"  4  `L ?? a  5iF PB 4 p"  4  f p??P@ !4  fk p??PB DRepresentationF P@ "4 p! " #4  f p??P@ $4  ff p?? <RecordF P@ %4 p P" &4  f p??P@ '4  f p?? A Tree_Kernel   (4 NjJ?"   )4 NjJ?"   *4 NjJ?" ` P B +4@ # lDjJ??P @pB ,4@ # lDjJ??P 0 0 pB -4 # lDjJ??P p .4 NjJ?"0 B /4 # lDjJ?? ` B 04 # lDjJ??  14  `h ??  5uB 24@ # lDjJ?? @ B 34@ # lDjJ?? 0 0 B 44 # lDjJ?? `  54  `, ?? 0  5u 64  `_ ?? i 0  5u 74  `5 ?? p  7enc 84  ` ?? pz 5i 94  ` G ?? A z 5i :4  `G ?? a z 5i ;4  `ءG ??` A Z 5iH 4 0޽h ? 13K -K0 p8s(  8x 8 c $ߧ `    8 Z| jJ?"W* #object Tree_Of_Tree_Node new_tree_rep, t; // make t a valid representation for an initial value of Statement t[current][kind] = BLOCK; t[current][test] = TRUE; // extract representation tree from block and consume block block[tree_rep] &= t; // construct new representation tree new_tree_rep[current][kind] = IF; new_tree_rep[current][test] &= cond; // consume cond new_tree_rep.Add (0, t); // produce self self[tree_rep] &= new_tree_rep; ,[ LH 8 0޽h ? 13, -K0 `<T(  <x < c $ `    < Z jJ?"W!* object Tree_Of_Tree_Node new_tree_rep, t; // make new_tree_rep a valid representation for // an initial value of Statement new_tree_rep[current][kind] = BLOCK; new_tree_rep[current][test] = TRUE; // consume self self[tree_rep] &= new_tree_rep; // extract condition and body from representation of if new_tree_rep[current][test] &= cond; new_tree_rep.Remove (0, t); // swap body representation into block block[tree_rep] &= t; N]H < 0޽h ? 13) 0 @@(  @X @ C    $ @ S $ @  $  H @ 0޽h ? ̙33? 0 P((  P^ P S     P c $ @    H P 0޽h ? ̙33@ 0 X((  X^ X S     X c $t @    H X 0޽h ? ̙33B 0  d((  d^ d S     d c $ @    H d 0޽h ? ̙33r0/GU_,2eJLNPRT8jN)/ =$N`Pczs|~ӫfmw۱Vȴqȑk>1m{Z/G( I/ 00DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 00DWingdings MSn0:Oh+'04 hp  $ 0 <HPBinary_Tree ComponentP Paolo Bucci8C:\WINDOWS\Application Data\Microsoft\Templates\321.pot Paolo Bucci86lMicrosoft PowerPointn D@@s@gVG3g    -- @ !--'-- @ !40M---'--- @ !4MW---- @ !4MX---- @ !4MZ---- @ !4M[---- @ !4M\---- @ !4M]---- @ !4M^---- @ !4M_---- @ !4M`---- @ !4Ma---- @ !4Mb---- @ !4Mc---- @ !4Md--~-- @ !4Me--{-- @ !4Mf--w-- @ !4Mg--r-- @ !4Mh--m-- @ !4Mi--i-- @ !4Mj--d-- @ !4Mk--^-- @ !4Ml--Y-- @ !4Mm--S-- @ !4Mn--M-- @ !4Mo--G-- @ !4Mp--B-- @ !4Mq--<-- @ !4Mr--6-- @ !4Ms--0-- @ !4Mt--*-- @ !4Mu--%-- @ !4Mv---- @ !4Mw---- @ !4Mx---- @ !4My---'-- @ !4.{;--'--- @ !4{c---- @ !4{d---- @ !4{e--&-- @ !4{f----- @ !4{g--4-- @ !4{h--;-- @ !4{i--B-- @ !4{j--H-- @ !4{k--O-- @ !4{l--V-- @ !4{m--]-- @ !4{n--c-- @ !4{o--j-- @ !4{p--ݱq-- @ !4{q--حx-- @ !4{r--Ҩ~-- @ !4{s--ͣ-- @ !4{t--ƞ-- @ !4{u---- @ !4{v---- @ !4{w---- @ !4{x---- @ !4{y---- @ !4{z--{-- @ !4{{--u-- @ !4{|--n-- @ !4{}--g-- @ !4{~--ya-- @ !4{--qZ-- @ !4{--hS-- @ !4{--`L-- @ !4{--WF-- @ !4{--O?-- @ !4{--G8-- @ !4{-->1-- @ !4{--6*-- @ !4{---#-- @ !4{-- -- @ !4{-- -- @ !4{---'A .=s ( %')*,--./012222#$&(*,,-./01222 "$&(*+,-./01 "#%')+,--.01!#-u!gs~Ydp{KVamx' =HS_j! / : EQ\ , 8 CNcdefgKLMNO-./01]^_`aFGHIb !"#$VWXYZAB[D\PQRST;<=>?UKLMNO-./0123456FGHIJ !"#$%&'()ABCDE;<=>?@ -./0123456789:, !"#$%&'()*+, '-- @ !sAS--'--- @ !E/---- @ !5t---- @ !'---- @ !#---- @ ! ---- @ !---- @ !+---- @ !D---- @ !Y---- @ !q---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !%---- @ !6---- @ !O---- @ !d---- @ !}---- @ !---- @ !#---- @ !'---- @ !8---- @ !U:---- @ !#---'@BComic Sans MS-. $2 Statement Component'+",."System-@BComic Sans MS-. 2 5IF next .-@BComic Sans MS-.  2 5- .-@BComic Sans MS-.  2 5is .-@BComic Sans MS-.  2 5- .-@BComic Sans MS-. 2 5 empty THEN .-@BComic Sans MS-.  2 a=move.-@BComic Sans MS-. 2 ; turnrightN .-@BComic Sans MS-.  2 ELSE.-@BComic Sans MS-. 2 =IF next .-@BComic Sans MS-.  2 - .-@BComic Sans MS-.  2 is .-@BComic Sans MS-.  2 - .-@BComic Sans MS-. 2  enemy THEN .-@BComic Sans MS-. 2 einfect .-@BComic Sans MS-. 2 ==END IF .-@BComic Sans MS-. 2 hEND IF .-@BComic Sans MS-. 2 nHow can we use     .-@BComic Sans MS-.  2 gtree.-@BComic Sans MS-. 2  to model a u   .-@BComic Sans MS-. 2 _ BL statement e  .-@BComic Sans MS-.  2 ;?.-  @@`` `k$2 .V.j(jD>#$!  %$#"557&()  5p 5 -5  +*43' 6C X0e0e    A A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|ES"@8\ʚ;ʚ; g4hdhd :A 0ppp@ <4!d!dL$ 0l%<4ddddL$ 0l%g4CdCd :A 0p@ pp<4BdBdL$ 0l%j0___PPT10 *___PPT9 z? %O 5;3)Statement ComponentiIF next-is-empty THEN move turnright ELSE IF next-is-enemy THEN infect END IF END IFjZj AK?Statement Component L@Statement Component UF BL StatementsVGBL Statements: IFWHBL Statements: IF_ELSEXIBL Statements: WHILEYJBL Statements: CALLZK An ExampleWHILE true DO IF next-is-enemy THEN infect ELSE IF next-is-empty THEN move ELSE turnleft END IF END IF END WHILEZ4*(Statement Continued& ]Type Statement_Kernel is modeled by STATEMENT Initial Value IS_INITIAL_STATEMENT (self) r. I5+(Statement Continued& math subtype STATEMENT_LABEL is ( kind: Statement_Kind test: Condition instruction: IDENTIFIER ) constraint & math subtype STATEMENT is tree of STATEMENT_LABEL exemplar s constraint IS_LEGAL_STATEMENT (s)  Z b    6,(Statement Continued& *Statement_Kind BLOCK IF IF_ELSE WHILE CALL& Condition NEXT_IS_EMPTY NEXT_IS_NOT_EMPTY NEXT_IS_WALL NEXT_IS_NOT_WALL NEXT_IS_FRIEND NEXT_IS_NOT_FRIEND NEXT_IS_ENEMY NEXT_IS_NOT_ENEMY RANDOM TRUE, ZZ 7-(Statement Continued& IS_LEGAL_STATEMENT?,!Statement OperationssOperations s.Add_To_Block (pos, statement) s.Remove_From_Block (pos, statement) s.Length_Of_Block () s.Compose_If (cond, block) s.Decompose_If (cond, block) s.Compose_If_Else (cond, if_block, else_block) s.Decompose_If_Else (cond, if_block, else_block) s.Compose_While (cond, block) s.Decompose_While (cond, block) s.Compose_Call (inst) s.Decompose_Call (inst) s.Kind () > h h-"Statement Block OperationsZs.Add_To_Block (pos, statement) s.Remove_From_Block (pos, statement) s.Length_Of_Block ()  Z[.#Statement If Operations7s.Compose_If (cond, block) s.Decompose_If (cond, block)88/(Statement If_Else Operationss.Compose_If_Else ( cond, if_block, else_block) s.Decompose_If_Else ( cond, if_block, else_block),$>0'Statement While Operations=s.Compose_While (cond, block) s.Decompose_While (cond, block)>>1&Statement Call Operations-s.Compose_Call (inst) s.Decompose_Call (inst)..2%Statement Other Operations s.Kind ()   OAUsing Statement Operations:What operations are needed to produce Statement if_stmt =$;11PBUsing Statement Operations RCUsing Statement OperationsCShow the operations to produce If_Else_stmt on the previous slide: &D  SDPractice Operation_Most operations on Statement have to be recursive Use 5 step process to recursion: 0. State the problem 1. Visualize recursive structure 2. Verify that visualized recursive structure can be leveraged into an implementation 3. Visualize a recursive implementation 4. Write a skeleton for the operation body 5. Refine the skeleton into an operation body0SZ ZS 8.%Step 0: State the ProblemProcedure Demobilize replaces every occurrence of the  move instruct  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\^_`abcdefghijklmnopqrstuvwyz{|}~Root EntrydO)09~7-Current User/SummaryInformation(]5PowerPoint Document(uxDocumentSummaryInformation84A 0 C.  @n?" dd@  @@`` `k)2 .V.j(jD>#$!  %$#"557&()  5< 5 -5  +*43' 6C X0e0e    A A8c 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|ES"@8\ʚ;ʚ; g4hdhd :A 0ppp@ <4!d!dL$ 0l%<4ddddL$ 0l%g4CdCd :A 0p@ pp<4BdBdL$ 0l%j0___PPT10 *___PPT9 z? %O 5;3)Statement ComponentiIF next-is-empty THEN move turnright ELSE IF next-is-enemy THEN infect END IF END IFjZj AK?Statement Component L@Statement Component UF BL StatementsVGBL Statements: IFWHBL Statements: IF_ELSEXIBL Statements: WHILEYJBL Statements: CALLZK An ExampleWHILE true DO IF next-is-enemy THEN infect ELSE IF next-is-empty THEN move ELSE turnleft END IF END IF END WHILEZ4*(Statement Continued& ]Type Statement_Kernel is modeled by STATEMENT Initial Value IS_INITIAL_STATEMENT (self) r. I5+(Statement Continued& math subtype STATEMENT_LABEL is ( kind: Statement_Kind test: Condition instruction: IDENTIFIER ) constraint & math subtype STATEMENT is tree of STATEMENT_LABEL exemplar s constraint IS_LEGAL_STATEMENT (s)  Z b    6,(Statement Continued& *Statement_Kind BLOCK IF IF_ELSE WHILE CALL& Condition NEXT_IS_EMPTY NEXT_IS_NOT_EMPTY NEXT_IS_WALL NEXT_IS_NOT_WALL NEXT_IS_FRIEND NEXT_IS_NOT_FRIEND NEXT_IS_ENEMY NEXT_IS_NOT_ENEMY RANDOM TRUE, ZZ 7-(Statement Continued& IS_LEGAL_STATEMENT?,!Statement OperationssOperations s.Add_To_Block (pos, statement) s.Remove_From_Block (pos, statement) s.Length_Of_Block () s.Compose_If (cond, block) s.Decompose_If (cond, block) s.Compose_If_Else (cond, if_block, else_block) s.Decompose_If_Else (cond, if_block, else_block) s.Compose_While (cond, block) s.Decompose_While (cond, block) s.Compose_Call (inst) s.Decompose_Call (inst) s.Kind () > h h-"Statement Block OperationsZs.Add_To_Block (pos, statement) s.Remove_From_Block (pos, statement) s.Length_Of_Block ()  Z[.#Statement If Operations7s.Compose_If (cond, block) s.Decompose_If (cond, block)88/(Statement If_Else Operationss.Compose_If_Else ( cond, if_block, else_block) s.Decompose_If_Else ( cond, if_block, else_block),$>0'Statement While Operations=s.Compose_While (cond, block) s.Decompose_While (cond, block)>>1&Statement Call Operations-s.Compose_Call (inst) s.Decompose_Call (inst)..2%Statement Other Operations s.Kind ()   OAUsing Statement Operations:What operations are needed to produce Statement if_stmt =$;11PBUsing Statement Operations RCUsing Statement OperationsCShow the operations to produce If_Else_stmt on the previous slide: &D  SDPractice Operation_Most operations on Statement have to be recursive Use 5 step process to recursion: 0. State the problem 1. Visualize recursive structure 2. Verify that visualized recursive structure can be leveraged into an implementation 3. Visualize a recursive implementation 4. Write a skeleton for the operation body 5. Refine the skeleton into an operation body0SZ ZS 8.%Step 0: State the ProblemProcedure Demobilize replaces every occurrence of the  move instruction in statement s with a  skip instruction. global_procedure Demobilize ( alters Statement& s ); /*! ensures s = DEMOBILIZE (#s) !*/s{s tj9/Demobilize this Statement:0LStep 0: State the Problem Continued& Rmath definition DEMOBILIZE ( s: STATEMENT ): STATEMENT satisfies if root (s).kind = CALL then if root (s).instruction =  move then DEMOBILIZE (s) = compose ((CALL, TRUE,  skip ), empty_string) else DEMOBILIZE (s) = s else there exists label: STATEMENT_LABEL, nested_stmts: string of STATEMENT (s = compose (label, nested_stmts) and DEMOBILIZE (s) = compose (label, STRING_DEMOBILIZE (nested_stmts))X*Z4 !'   D 5*tZ"] u 7 ] ;1LStep 0: State the Problem Continued& math definition STRING_DEMOBILIZE ( str: string of STATEMENT ): string of STATEMENT satisfies if str = empty_string then STRING_DEMOBILIZE (str) = empty_string else there exists s: STATEMENT, rest: string of STATEMENT (str = * rest and STRING_DEMOBILIZE (str) = DEMOBILIZE (s) * STRING_DEMOBILIZE (rest))"     , 6 +h,B  o4B<2(Step 1: Visualize Recursive Structure=3&Step 2: Verify That Leveraging Works Ask yourself: If Demobilize could get a helper to demobilize the nested statements in each of the five (four?) cases, could it take advantage of this generous offer? Yes! Once you know how to demobilize the nested statements, you can demobilize the entire statement.>4RStep 2: Let s Jump Ahead2procedure_body Demobilize ( alters Statement& s ) { case_select (s.Kind ()) { case BLOCK: {Demobilize_Block (s);} break; case IF: {Demobilize_If (s);} break; case IF_ELSE: {Demobilize_If_Else (s);} break; case WHILE: {Demobilize_While (s);} break; case CALL: { object Text inst, skipinst =  skip ; s.Decompose_Call (inst); if ( inst ==  move ) { inst &= skipinst; } s.Compose_Call (inst); } break; } }@Z0" dZZ    $   Re D ( %#@B#?5~Step 2 (or back to Step 0 L): State the Problem$@#global_procedure Demobilize_Block ( alters Statement& s ); /*! requires root (s).kind = BLOCK ensures s = DEMOBILIZE (#s) !*/Z   @6Steps 1-5 Condensed (BLOCK) object Statement nested; object Integer pos; while (pos < s.Length_Of_Block ()) { s.Remove_From_Block (pos, nested); Demobilize (nested); s.Add_To_Block (pos, nested); pos ++; }X>= 0$A7xStep ? (or back to Step 2 ): State the Problem Continued& $=!global_procedure Demobilize_If ( alters Statement& s ); /*! requires root (s).kind = IF ensures s = DEMOBILIZE (#s) !*/    " B8Steps 1-5 Condensed (IF) object Statement if_blk; object Integer cond; s.Decompose_If (cond, if_blk); Demobilize (if_blk); s.Compose_If (cond, if_blk);Bc TESteps 1-5 Condensed (IF_ELSE)  cprocedure_body Demobilize_If_Else ( alters Statement& s ) { // You try it! }PdZ 2CC9Statement: RepresentationThe representation for Statement_Kernel_1 has one field: tree_rep: a Tree_Of_Tree_Node where a Tree_Node is a Record with three fields: kind: Integer test: Integer instruction: Text 9O.     D:Statement: CorrespondenceNself, the Statement, is equal to self.tree_rep, the Tree used to represent it.8O !E;Statement: ConventionAll the labels in the tree, tree_rep, are legal statement labels (i.e., they satisfy the constraint for the definition of STATEMENT_LABEL); The tree itself is a legal statement (i.e., it satisfies the constraint for the definition of STATEMENT).$F<Statement: CCDG=Statement: Compose_IfH>Statement: Decompose_If/pJMNQ -K0  0(  x  c $ `   x  c $h p  H  0޽h ? 3333r>4m[Z/G( I/ 00DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 00DWingdings MSn0:A 0 C.  @n?" dd@ ՜.+,0    $ On-screen ShowThe Ohio State Universitytu*{ /Times New RomanComic Sans MSTahoma Wingdings321Statement ComponentStatement ComponentStatement ComponentBL StatementsBL Statements: IFBL Statements: IF_ELSEBL Statements: WHILEBL Statements: CALL An ExampleStatement Continued…Statement Continued…Statement Continued…Statement Continued…Statement OperationsStatement Block OperationsStatement If OperationsStatement If_Else OperationsStatement While OperationsStatement Call OperationsStatement Other OperationsUsing Statement OperationsUsing Statement OperationsUsing Statement OperationsPractice Operation&Step 0: State the ProblemDemobilize this Statement)Step 0: State the Problem Continued…)Step 0: State the Problem Continued…)Step 1: Visualize Recursive Structure'Step 2: Verify That Leveraging Works-Step 2½: Let’s Jump AheadCStep 2¾ (or back to Step 0 ): State the ProblemSteps 1-5 Condensed (BLOCK)@Step ? (or back to Step 2¾ ): State the Problem Continued…Steps 1-5 Condensed (IF)Steps 1-5 Condensed (IF_ELSE)Statement: RepresentationStatement: CorrespondenceStatement: ConventionStatement: CCDStatement: Compose_IfStatement: Decompose_If  Fonts UsedDesign Template Slide Titles*_ubuccibucciolo Buccig Servicesion in statement s with a  skip instruction. global_procedure Demobilize ( alters Statement& s ); /*! ensures s = DEMOBILIZE (#s) !*/s{s tj9/Demobilize this Statement:0LStep 0: State the Problem Continued& Rmath definition DEMOBILIZE ( s: STATEMENT ): STATEMENT satisfies if root (s).kind = CALL then if root (s).instruction =  move then DEMOBILIZE (s) = compose ((CALL, TRUE,  skip ), empty_string) else DEMOBILIZE (s) = s else there exists label: STATEMENT_LABEL, nested_stmts: string of STATEMENT (s = compose (label, nested_stmts) and DEMOBILIZE (s) = compose (label, STRING_DEMOBILIZE (nested_stmts))X*Z4 !'   D 5*tZ"] u 7 ] ;1LStep 0: State the Problem Continued& math definition STRING_DEMOBILIZE ( str: string of STATEMENT ): string of STATEMENT satisfies if str = empty_string then STRING_DEMOBILIZE (str) = empty_string else there exists s: STATEMENT, rest: string of STATEMENT (str = * rest and STRING_DEMOBILIZE (str) = DEMOBILIZE (s) * STRING_DEMOBILIZE (rest))"     , 6 +h,B  o4B<2(Step 1: Visualize Recursive Structure=3&Step 2: Verify That Leveraging Works Ask yourself: If Demobilize could get a helper to demobilize the nested statements in each of the five (four?) cases, could it take advantage of this generous offer? Yes! Once you know how to demobilize the nested statements, you can demobilize the entire statement.>4RStep 2: Let s Jump Ahead2procedure_body Demobilize ( alters Statement& s ) { case_select (s.Kind ()) { case BLOCK: {Demobilize_Block (s);} break; case IF: {Demobilize_If (s);} break; case IF_ELSE: {Demobilize_If_Else (s);} break; case WHILE: {Demobilize_While (s);} break; case CALL: { object Text inst, skipinst =  skip ; s.Decompose_Call (inst); if ( inst ==  move ) { inst &= skipinst; } s.Compose_Call (inst); } break; } }@Z0" dZZ    $   Re D ( %#@B#?5~Step 2 (or back to Step 0 L): State the Problem$@#global_procedure Demobilize_Block ( alters Statement& s ); /*! requires root (s).kind = BLOCK ensures s = DEMOBILIZE (#s) !*/Z   @6Steps 1-5 Condensed (BLOCK) object Statement nested; object Integer pos; while (pos < s.Length_Of_Block ()) { s.Remove_From_Block (pos, nested); Demobilize (nested); s.Add_To_Block (pos, nested); pos ++; }X>= 0$A7xStep ? (or back to Step 2 ): State the Problem Continued& $=!global_procedure Demobilize_If ( alters Statement& s ); /*! requires root (s).kind = IF ensures s = DEMOBILIZE (#s) !*/    " B8Steps 1-5 Condensed (IF) object Statement if_blk; object Integer cond; s.Decompose_If (cond, if_blk); Demobilize (if_blk); s.Compose_If (cond, if_blk);Bc TESteps 1-5 Condensed (IF_ELSE)  cprocedure_body Demobilize_If_Else ( alters Statement& s ) { // You try it! }PdZ 2CC9Statement: RepresentationThe representation for Statement_Kernel_1 has one field: tree_rep: a Tree_Of_Tree_Node where a Tree_Node is a Record with three fields: kind: Integer test: Integer instruction: Text 9O.     D:Statement: CorrespondenceNself, the Statement, is equal to self.tree_rep, the Tree used to represent it.8O !E;Statement: ConventionAll the labels in the tree, tree_rep, are legal statement labels (i.e., they satisfy the constraint for the definition of STATEMENT_LABEL); The tree itself is a legal statement (i.e., it satisfies the constraint for the definition of STATEMENT).$F<Statement: CCDG=Statement: Compose_IfH>Statement: Decompose_If/pJMNQ# -K0 X#P#6o4"(  4x 4 c $> `   F  <4 >5" =4  f p??"` >4  fG2 p??"`" DS_Pretty_PrintB ?4 3 rZDjJ??q  @4  `2 ??  7extB A4 # lDjJ??H B4  `a2 ??.( 5iF  C4 `  D4  ` p?? E4  f,j2 p?? FS_Pretty_Print_1B F4 # lDjJ??0{{ G4  `t2 ??\ 5i H4  `}2 ??G 7extB I4 3 rZDjJ??Ha  .B J4 3 rZDjJ??pF P@ K4 p H" L4  f p??P@ M4  fS_Kernel  F P@ N4 p 8  O4  ` p??P@ P4  fHu2 p??_1 @ S_Kernel_1   Q4 NjJ?"  R4  `P/2 ??H B 5iF PB S4  (" T4  f p??P@ U4  f; p??PB DRepresentationF P@ V4  q (" W4  f p??P@ X4  fo; p?? <RecordF P@ Y4  (" Z4  f p??P@ [4  f,2 p?? A Tree_Kernel   \4 NjJ?"( @0  ]4 NjJ?"(  ^4 NjJ?"( B _4@ # lDjJ??  B `4@ # lDjJ?? B a4 # lDjJ?? P p  b4 NjJ?"8 B c4 # lDjJ??H  B d4 # lDjJ??   e4  `82 ??  5uB f4@ # lDjJ??8 0 B g4@ # lDjJ??8 ( B h4 # lDjJ??8  i4  `82 ??8 W 2  5u j4  `<2 ??8 2  5u k4  `2 ??8 B2  7enc l4  `42 ?? /  5i m4  `2 ?? B  5i n4  `2 ??  5i o4  `  ??  5iH 4 0޽h ? 13s -K0  p8(  8x 8 c $ߧ `    8 Z| jJ?"W* Kobject Tree_Of_Tree_Node new_tree_rep, t; // make t a valid representation for an initial value of Statement t[current][kind] = BLOCK; t[current][test] = TRUE; // extract representation tree from block and consume block block[tree_rep] &= t; // construct new representation tree new_tree_rep[current][kind] = IF; new_tree_rep[current][test] &= cond; // consume cond new_tree_rep.Add (0, t); // produce self self[tree_rep] &= new_tree_rep; @,[ LH 8 0޽h ? 135 -K0 `<](  <x < c $ `    < Z jJ?"W!  }object Tree_Of_Tree_Node new_tree_rep, t; // make new_tree_rep a valid representation for // an initial value of Statement new_tree_rep[current][kind] = BLOCK; new_tree_rep[current][test] = TRUE; // consume self self[tree_rep] &= new_tree_rep; // extract condition and body from representation of if new_tree_rep[current][test] &= cond; new_tree_rep.Remove (0, block[tree_rep]);@~,NH < 0޽h ? 13rF09Im|q>muZRoot EntrydO)0 Q[KCurrent UserASummaryInformation(]5PowerPoint Document(ux -5 Condensed (IF)Steps 1-5 Condensed (IF_ELSE)Statement: RepresentationStatement: CorrespondenceStatement: ConventionStatement: CCDStatement: Compose_IfStatement: Decompose_If  Fonts UsedDesign Template Slide Titles*#_u %Paolo BucciPaolo Buccig Services