[Icfp04-discuss] Ant optimizers?

[Luca Saiu]

Michael Levin wrote:
> A state optimizer is also important for compiling and's and or's
> of conditional expressions efficiently. 

   I wouldn't say that. Apart from the compactness issue you can compile 
boolean connectives in a traditional short-circuit style, and the 
resulting code *is* efficient. From my submission (the TRUE and FALSE 
cases would benefit from DFA minimization):

--------------------------------------------------------------------
/* Here the generated code is represented as a list of pairs: each pair 
contains
    the instruction address and the instruction. Since instructions are 
generated
    in (reverse) order the first component wouldn't be needed, but it 
has been
    useful for debugging. */

/* This function takes:
    - the predicate to compile
    - the code generated so far
    - the next free label
    - the label where to jump if the result is true
    - the label where to jump if the result is false
    (note that predicate evaluation can *not* fail)
    And returns a pair:
    - generated code (prepended to the given one),
    - next free label */
define compile_predicate =
   fix \ f . \ p : predicate . \ code . \ next_label . \ on_true . \ 
on_false .
   match p with
     TRUE ->
       ((next_label, Flip(2, on_true, on_true)) :: code),
       (next_label + 1)
   | FALSE ->
       ((next_label, Flip(2, on_false, on_false)) :: code),
       (next_label + 1)
   | ROCK(sd) ->
       ((next_label, Sense(sd, on_true, on_false, Rock)) :: code),
       (next_label + 1)
   | FRIEND(sd) ->
       ((next_label, Sense(sd, on_true, on_false, Friend)) :: code),
       (next_label + 1)
   | FOE(sd) ->
       ((next_label, Sense(sd, on_true, on_false, Foe)) :: code),
       (next_label + 1)
   | FRIENDWITHFOOD(sd) ->
       ((next_label, Sense(sd, on_true, on_false, FriendWithFood)) :: code),
       (next_label + 1)
   | FOEWITHFOOD(sd) ->
       ((next_label, Sense(sd, on_true, on_false, FoeWithFood)) :: code),
       (next_label + 1)
   | FOOD(sd) ->
       ((next_label, Sense(sd, on_true, on_false, Food)) :: code),
       (next_label + 1)
   | HOME(sd) ->
       ((next_label, Sense(sd, on_true, on_false, Home)) :: code),
       (next_label + 1)
   | FOEHOME(sd) ->
       ((next_label, Sense(sd, on_true, on_false, FoeHome)) :: code),
       (next_label + 1)
   | MARKERBIT(b_sd) ->
       ((next_label, Sense((b_sd ^ 2), on_true, on_false, Marker(b_sd ^ 
1))) :: code),
       (next_label + 1)
   | FOEMARKER(sd) ->
       ((next_label, Sense(sd, on_true, on_false, FoeMarker)) :: code),
       (next_label + 1)
   | RANDOM(k) -> // k is a percentage
       ((next_label, Flip((100 / k), on_true, on_false)) :: code),
       (next_label + 1)
   | VARIABLEPREDICATE(v) ->
       impossible // this has been already expanded
   | AND(p1_p2) ->
       let length_of_p1 be
         length_of_compiled_predicate (p1_p2 ^ 1)
       in let newcode_newnextlabel be // generate code for p1
         f (p1_p2 ^ 1) code next_label (next_label + length_of_p1) on_false
       in // generate code for p2
assert next_label + length_of_p1 = (newcode_newnextlabel ^ 2) in
         f (p1_p2 ^ 2)
           (newcode_newnextlabel ^ 1)
           (newcode_newnextlabel ^ 2)
           on_true
           on_false
   | OR(p1_p2) ->
       let length_of_p1 be
         length_of_compiled_predicate (p1_p2 ^ 1)
       in let newcode_newnextlabel be // generate code for p1
         f (p1_p2 ^ 1) code next_label on_true (next_label + length_of_p1)
       in // generate code for p2
assert next_label + length_of_p1 = (newcode_newnextlabel ^ 2) in
         f (p1_p2 ^ 2)
           (newcode_newnextlabel ^ 1)
           (newcode_newnextlabel ^ 2)
           on_true
           on_false
   | NOT(p1) ->
       f p1 code next_label on_false on_true;
--------------------------------------------------------------------
   ...just as an excuse to show my code :-).

   Regards,

-- 
Luca Saiu, maintainer of GNU epsilon
http://www.gnu.org/software/epsilon
http://www.cli.di.unipi.it/~saiu/icfp2004.html