Chapter 9. Expression Blocks (*)
Prev Part I. A Tiny Imperative Language Next

Chapter 9. Expression Blocks (*)

Table of Contents

9.1. Syntax of Expression Blocks
9.2. Desugaring Expression Blocks
9.3. Example

Work in Progress

This chapter is work in progress. Not all parts have been finished yet. The latest revision of this manual may contain more material. Refer to the online version.

Sometimes it is useful to extend a language in order to ease transformations.

9.1. Syntax of Expression Blocks

Figure 9.1. file: til/til-eblock/TIL-eblocks.sdf

module TIL-eblocks
imports TIL
exports
  context-free syntax
    "begin" Stat* "return" Exp ";" Stat* "end" -> Exp {cons("EBlock")}

9.2. Desugaring Expression Blocks

Figure 9.2. file: til/til-eblock/til-eblock-desugar.str

module til-eblock-desugar
imports liblib TIL-eblocks
strategies

  io-til-eblock-desugar =
    io-wrap(til-eblock-desugar)

  til-eblock-desugar =
    bottomup(try(FunCallToEBlock))
    ; innermost(
        EBlockEBlock
	<+ NoStatements
	<+ MovePostStatementsInFront
        <+ HoistEBlockFromFunCall 
	<+ HoistEBlockFromBinOp 
	<+ HoistEBlockFromAssign 
	<+ HoistEBlockFromProcCall 
//	<+ HoistEBlockFromWrite 
	<+ HoistEBlockFromIf 
	<+ HoistEBlockFromWhile 
	<+ HoistEBlockFromFor
      )
    ; bottomup(try(flatten-block))

rules

  FunCallToEBlock :
    FunCall(f, e*) -> 
    EBlock([Declaration(x), Assign(x, FunCall(f, e*))], Var(x), [])
    where new => x

  NoStatements :
    EBlock([], e, []) -> e

  MovePostStatementsInFront :
    EBlock(st1*, e, st2*@[_|_]) -> 
    EBlock([Declaration(x), st1*, Assign(x, e), st2*], Var(x), [])
    where new => x

  EBlockEBlock :
    EBlock(st1*, EBlock(st2*, e, st3*), st4*) ->
    EBlock([st1*, st2*], e, [st3*, st4*])

  HoistEBlockFromFunCall :
    FunCall(f, e1*) -> EBlock(st1*, FunCall(f, e2*), [])
    where <collect-eblocks> e1* => (st1*, e2*)

  HoistEBlockFromBinOp :
    op#([e1, e2]) -> EBlock(st1*, op#([e1', e2']), [])
    where <is-bin-op> op
	; <collect-eblocks> [e1, e2] => (st1*, [e1', e2'])

  is-bin-op =
    ?"Or" <+ ?"And" <+ ?"Neq" <+ ?"Equ" <+ ?"Gt" <+ ?"Lt" <+ ?"Sub"
    <+ ?"Add" <+ ?"Mod" <+ ?"Div" <+ ?"Mul"

  HoistEBlockFromAssign :
    Assign(x, EBlock(st1*, e, st2*)) -> Block([st1*, st2*, Assign(x, e)])

  HoistEBlockFromProcCall :
    ProcCall(f, e1*) -> Block([st*, ProcCall(f, e2*)])
    where <collect-eblocks> e1* => (st*, e2*)

//  HoistEBlockFromWrite :
//    Write(EBlock(st1*, e, st2*)) -> Block([st1*, Write(e), st2*])

  HoistEBlockFromIf :
    IfElse(EBlock(st1*, e, st2*), st3*, st4*) -> 
    Block([st1*, IfElse(e, [st2*,st3*], [st2*,st4*])])

  HoistEBlockFromIf :
    IfThen(EBlock(st1*, e, st2*), st3*) -> 
    Block([st1*, IfElse(e, [st2*,st3*], st2*)])

  HoistEBlockFromWhile :
    While(EBlock(st1*, e, st2*), st3*) -> 
    Block([st1*, While(e, [st2*,st3*,st1*])])

  HoistEBlockFromFor :
    For(x, e1, e2, st1*) -> 
    Block([st2*, For(x, e1', e2', st1*)])
    where <collect-eblocks> [e1, e2] => (st2*, [e1', e2'])

  collect-eblocks = 
    fetch(?EBlock(_,_,_))
    ; map({where(new => x); !([Declaration(x), Assign(x, <id>)], Var(x))})
    ; unzip
    ; (concat, id)

  
  flatten-block =
    Block(
      foldr(![], \ (Block(st2*), st3*) -> [st2*, st3*] \ 
                     <+ \ (st, st*) -> [st | st*] \ )
      ; partition(?Declaration(_))
      ; conc
    )

9.3. Example

desugar expresion blocks, then perform simplification, copy propagation, constant propagation, and finally dead code elimination.

Figure 9.3. file: til/xmpl/eblock-desugar-test2

#! /bin/sh -v 

sglri -p ../til-eblock/TIL-eblocks.tbl -i eblock-desugar-test2.til |\
../sim/til-simplify |\
../renaming/til-rename-vars |\
../til-eblock/til-eblock-desugar -o eblock-desugar-test2.des.til

ast2text -p ../pp/TIL-pretty.pp \
	-i eblock-desugar-test2.des.til \
	-o eblock-desugar-test2.txt

../opt/til-copyprop-rev -i eblock-desugar-test2.des.til |\
../opt/til-forward-subst |\
../opt/til-copyprop |\
../opt/til-propconst |\
../opt/til-dce |\
ast2text -p ../pp/TIL-pretty.pp -o eblock-desugar-test2.cp.txt

Table 9.1. files: til/xmpl/eblock-desugar-test2.til, til/xmpl/eblock-desugar-test2.txt

beforeafter
write(
  begin
    var x;
    x := read();
    return 
      x + begin 
            x := readint(); 
            return x; 
            x := x * 2; 
          end + 1;
    x := x + 1;
    write(x);
  end
);

begin
  var k_0;
  var j_0;
  var a_0;
  var h_0;
  var f_0;
  var g_0;
  var e_0;
  var c_0;
  var d_0;
  var b_0;
  var i_0;
  var x0 : int;
  a_0 := read();
  x0 := a_0;
  f_0 := x0;
  b_0 := read();
  d_0 := b_0;
  c_0 := string2int(d_0);
  x0 := c_0;
  e_0 := x0;
  x0 := x0 * 2;
  g_0 := e_0;
  h_0 := f_0 + g_0;
  i_0 := 1;
  j_0 := h_0 + i_0;
  x0 := x0 + 1;
  write(x0);
  k_0 := j_0;
  write(k_0);
end

Table 9.2. files: til/xmpl/eblock-desugar-test2.txt, til/xmpl/eblock-desugar-test2.cp.txt

beforeafter
begin
  var k_0;
  var j_0;
  var a_0;
  var h_0;
  var f_0;
  var g_0;
  var e_0;
  var c_0;
  var d_0;
  var b_0;
  var i_0;
  var x0 : int;
  a_0 := read();
  x0 := a_0;
  f_0 := x0;
  b_0 := read();
  d_0 := b_0;
  c_0 := string2int(d_0);
  x0 := c_0;
  e_0 := x0;
  x0 := x0 * 2;
  g_0 := e_0;
  h_0 := f_0 + g_0;
  i_0 := 1;
  j_0 := h_0 + i_0;
  x0 := x0 + 1;
  write(x0);
  k_0 := j_0;
  write(k_0);
end

begin
  var a_0;
  var c_0;
  var b_0;
  a_0 := read();
  b_0 := read();
  c_0 := string2int(b_0);
  write(c_0 * 2 + 1);
  write(a_0 + c_0 + 1);
end

Prev Up Next
Chapter 8. Typestate Checking Home Part II. Example Packages (*)