README

   1 Prop is a pattern matching language based on C++.
   2 It implements algebraic datatypes, pattern matching and rewriting,
   3 and generates C++ code as output.
   4 ------------------------------------------------------------------------------
   5 Release 2.3.4
   6 (i)  Fixed a few bugs in the translator that caused it not to compile
   7      on g++ 2.7.0.
   8 (ii) Added additional state compression for rewriting tree automata.
   9      We'll now use 1-byte representation for rule set and state tables
  10      whenever possible.  One-byte state representation is used whenever
  11      the number of states is <= 256.  One-byte rule representation
  12      is used whenever the number of rules is <= 127.
  13
  14 Release 2.3.3
  15 (i)  Added system V gc timer code.
  16 (ii) The old view mechanism has been reissued as a new feature, with
  17      some syntactic changes.  It should now work with rewriting.
  18 (iii) Added better debugging facilities for rewriting.
  19 (iv) The rewriting modifiers before:, topdown:, bottomup: and after: have been
  20      renamed into the following:
  21
  22           before:
  23           preorder:
  24           topdown:
  25           bottomup:
  26           postorder:
  27
  28      The meaning of preorder: is analogous to that of the old topdown:
  29      while the meaning of postorder: is analogous to the old after:
  30
  31      The topdown mode now correctly normalizes a term.
  32
  33 (v)  Missing types in traversal list are now correctly reported.
  34
  35 (vi) A state caching bug creeped into version 2.3.0:  the index
  36      is not activated if there are no explicit rewrite statements
  37      in the TRS.  This is now fixed.
  38
  39 ------------------------------------------------------------------------------
  40 Release 2.3.2
  41 (i)  The datatype mapping process has been completely redone.
  42      This affects pretty much everything that has to do with datatypes,
  43      including garbage collection, persistence, and pretty printing.
  44
  45      Previous releases' generated template code had problems.
  46
  47      Code generated by old versions of Prop will NOT work with this release.
  48
  49 (ii) Pretty printing methods generated by Prop now uses the
  50      library class PrettyPOstream defined in <AD/pretty/postream.h>.
  51      This class is still quite rudimentary.
  52
  53      I'll have to think about what to do with pretty printing.
  54
  55 (iii) Added addition code for checking for correct datatype
  56       inheritance, especially inheritance of collectable classes.
  57       Currently only one collectable class may be inherited.
  58
  59 (iv)  Adding synthesized value checking in parser generation.
  60       Missing synthesized value in production will give warnings.
  61
  62 (v)   Fixed some BigInt, AVL, SplayTree bugs.
  63
  64 (vi)  Added template instantiation stuff for g++'s -fno-implicit-templates.
  65       Please see the manual for details.
  66
  67 (vii) Improved syntax error reporting; we now prints out the set of
  68       terminals that can be part of the valid input stream.
  69
  70 Release 2.3.1
  71 (i)  Fixed various problems with collectable datatypes.
  72
  73 ------------------------------------------------------------------------------
  74 Release 2.3.0
  75
  76 (i) rewriting
  77    Added topdown:, bottomup:, before: and after: modes in rewriting.
  78
  79    Added the indexing mechanism for rewriting.  External indices are
  80    still not very well tested, especially GCRewriteCache implemented
  81    with weak pointers.
  82
  83    Added the cutrewrite construct for replacement.
  84
  85 (ii) weakpointers
  86    Changed the GC classes so that weakpointer collection
  87    is automatically performed.  Previously, weakpointer collection
  88    is tied with finalization, which makes it possible to get unsafe
  89    results if the user forgets to turn on finalization when using
  90    weakpointers.
  91
  92    Weakpointers collection can be disabled with the
  93    set_weak_pointer_collection() method.
  94    In order to reclaim entries the weak pointer table, we'll try to
  95    perform a garbage collection before the weak pointer table is expanded.
  96    [This may cause excessive garbage collection if a lot of weakpointers
  97     are manipulated.  To be fixed later.]
  98
  99 (iii)
 100    Fixed quark literal naming bug.  Generated quark literals are now prefixed
 101    with the mangled filename of the source program.
 102
 103 ------------------------------------------------------------------------------
 104 Release 2.1
 105
 106 This is *yet* another rewrite of Prop.  It has been bootscrapped from
 107 version 2.0.6 (not released), then rewritten using the new features.
 108
 109 Rarely used features and features that have been poorly implemented in
 110 releases 2.0.x have been removed.  Among these are:
 111
 112     (1) lexer and parser generation.
 113     (2) hash consing and reference counting.
 114     (3) let ... in { ... }
 115     (4) cost minimization in matching
 116     (5) rule class.
 117     (6) dataview
 118
 119 Some of these will be reintroduced later when better integration with
 120 existing features is developed.
 121
 122 CHANGES
 123 -------
 124
 125    Here are some important changes to the translator.
 126
 127 [1]  Mapping of polymorphic datatypes.
 128
 129      Mapping of polymorphic datatypes have been altered.  Previously
 130    we use a very elaborate smart pointer class to simulate pointer semantics,
 131    which failed to work consistently on buggy compilers.  Now we use macros
 132    instead.
 133
 134 [2]  Optimizations on pattern matching.
 135
 136     An adaptive traversal algorithm based on the work of Sekar, Ramesh,
 137    and Ramakrishnan (``Adaptive Pattern Matching'' TR SUNY at Stony Brook, year
 138    199?) has been implemented.  This optimization should further
 139    speed up pattern matching and reduce the size of the generated code.
 140
 141 [3]  Optimizations on inference.
 142
 143      A limited form of decomposition has been implemented on guard expressions.
 144   Specifically, guards in the form of conjuncts are decomposed and hoisted
 145   to speed up inference object matching.  This is similar to ``pushing down
 146   selects'' in database.
 147
 148      [The next step would be to implement indexing on the keys
 149    and faster joins.]
 150
 151 [4]  The following changes have been made to the syntax:
 152
 153    [a]  The pattern connectives or:, and: and not: have been
 154         eliminated in favor of ||, &&, and ! respectively.
 155    [b]  Guards can now be written using a few different syntaxes:
 156         For example,
 157
 158           foo(?x,?y) where predicate(x?,y?):
 159           foo(?x,?y) if    predicate(x?,y?);
 160           foo(?x,?y) |     predicate(x?,y?);
 161
 162         are all equivalent.
 163
 164     [c]  We can now say
 165
 166            foo(?x,?y): ?x
 167
 168          in place of    foo(?x,?y): rewrite(?x);
 169          or even        foo(?x,?y): { rewrite(?x); }
 170
 171          in a rewrite class.
 172
 173     [d]  Certain parenthesis are now optional.
 174          For example,
 175
 176              datatype Tree = empty | leaf (int) | node (Tree, int, Tree);
 177
 178          can now be written as:
 179
 180              datatype Tree = empty | leaf int | node Tree, int, Tree;
 181
 182 [5]  Semiunification of non-linear patterns has been (partially) implemented.
 183      Equality tests are automatically generated for repeated variables within
 184      a pattern.
 185
 186      This feature needs a typeclass extension to the type system
 187      to be fully functional.
 188
 189 [6]  Minor variant to 'match' called 'match while' has been added:
 190
 191      match[all] while (e1) and (e2) and ... and (en)
 192      { p1: { action1 }
 193      | p2: { action2 }
 194      | ...
 195      | ...
 196      | pn: { actionn }
 197      }
 198
 199      repeats the matching process until none of the rules matches.
 200
 201 [7]  We can now define functions using pattern matching using the
 202      'fun' declaration form.  It is an abbreviation for 'match' and
 203      function definition.  Mutually recursive functions are
 204      defined using the 'and' connective.
 205
 206      The advantage of this form is that
 207      we can omit naming the arguments and declaring the types
 208      and long as the type inferencer can deduce the types at compile time.
 209
 210      datatype Tree = empty | node Tree, int, Tree;
 211
 212      fun depth empty => int:  { return 0; }
 213        | depth node(a,_,b):   { return max(depth(a),depth(b)) + 1; }
 214      and flip  empty => Tree: { return empty; }
 215        | flip  node(a,i,b):   { return node(flip(b),i,flip(a)); }
 216      ;
 217
 218 [8]  Embedded tags optimizations on term representations.
 219
 220      It is now possible to use compact representations that embeds the
 221      variant tag of a datatype into the lower bits of its pointer.
 222
 223      For example, the datatype Tree in
 224
 225        datatype Tree = empty
 226                      | leaf int
 227                      | node Tree, int, Tree
 228                      ;
 229
 230      is mapped into the following code by default:
 231
 232      #define empty (a_Tree *)0
 233
 234      class a_Tree
 235      {
 236      public:
 237         enum Tag_Tree { tag_leaf = 0, tag_node = 1; };
 238      protected:
 239         Tag_Tree _tag_;
 240         ...
 241      };
 242
 243      class Tree_leaf : public a_Tree { ... };
 244      class Tree_node : public a_Tree { ... };
 245
 246
 247      On the other hand, with the embedded tag anotations '!':
 248
 249                    // embedded variant tag
 250        datatype Tree ! = empty
 251                        | leaf int !            // embedded argument
 252                        | node Tree, int, Tree
 253                        ;
 254
 255      the class hierarchy can be collasped into just the class
 256
 257      class a_Tree { ... };
 258
 259      The tag field in the base class a_Tree will also be eliminated.
 260      Instead the tag is embedded in the lower bits of the leaf
 261      and node pointers.  Furthermore, the integer argument in the
 262      leaf node will actually be imbedded within the pointer for the leaf,
 263      and no heap storage is consumed(the integer will loose a few bits
 264      of precision however, typically 2).
 265
 266      Using this optimization, the variant tag of a term can be accessed
 267      without a load from memory.  Furthermore, the terms can all be 1 word
 268      smaller (due to alignment this may not be always true).  Of course, bit
 269      masking must now be done to strip the tag bits before we dereference
 270      the pointers.  In most machines this requires a single instruction; but
 271      since we can eliminate one load with this optimization, I think things
 272      even out after all even if it's not improved upon.
 273
 274      These optimizations are largely transparent from the application:
 275      the correct pattern matching code will be generated.  One possible
 276      exception is that an embedded argument is not mutable.
 277
 278      As always, we generate code assuming that the C++ compiler performs
 279      agressive optimizations such as common subexpression elimination.
 280
 281 [9]  User definable lists and array-like constructors