typename fix
[prop.git] / README
blob5e906fdcbf45b062e43aa54bef1e58562caf3acf
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.
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:
22           before:         
23           preorder:   
24           topdown:
25           bottomup:
26           postorder:
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:
31      The topdown mode now correctly normalizes a term.
33 (v)  Missing types in traversal list are now correctly reported.
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.
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.
45      Previous releases' generated template code had problems.
47      Code generated by old versions of Prop will NOT work with this release.
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.  
53      I'll have to think about what to do with pretty printing.
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.  
59 (iv)  Adding synthesized value checking in parser generation.
60       Missing synthesized value in production will give warnings.
62 (v)   Fixed some BigInt, AVL, SplayTree bugs.
64 (vi)  Added template instantiation stuff for g++'s -fno-implicit-templates.
65       Please see the manual for details.
67 (vii) Improved syntax error reporting; we now prints out the set of
68       terminals that can be part of the valid input stream.
70 Release 2.3.1
71 (i)  Fixed various problems with collectable datatypes.
73 ------------------------------------------------------------------------------
74 Release 2.3.0
76 (i) rewriting
77    Added topdown:, bottomup:, before: and after: modes in rewriting.
79    Added the indexing mechanism for rewriting.  External indices are
80    still not very well tested, especially GCRewriteCache implemented
81    with weak pointers.
83    Added the cutrewrite construct for replacement.
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.
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.]  
99 (iii) 
100    Fixed quark literal naming bug.  Generated quark literals are now prefixed
101    with the mangled filename of the source program.
103 ------------------------------------------------------------------------------
104 Release 2.1
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.
109 Rarely used features and features that have been poorly implemented in
110 releases 2.0.x have been removed.  Among these are:
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
119 Some of these will be reintroduced later when better integration with
120 existing features is developed. 
122 CHANGES
123 -------
125    Here are some important changes to the translator.  
127 [1]  Mapping of polymorphic datatypes.
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.
134 [2]  Optimizations on pattern matching.
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.
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.
148      [The next step would be to implement indexing on the keys
149    and faster joins.]
151 [4]  The following changes have been made to the syntax:
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,
158           foo(?x,?y) where predicate(x?,y?): 
159           foo(?x,?y) if    predicate(x?,y?);
160           foo(?x,?y) |     predicate(x?,y?);
162         are all equivalent.
164     [c]  We can now say
166            foo(?x,?y): ?x
168          in place of    foo(?x,?y): rewrite(?x);
169          or even        foo(?x,?y): { rewrite(?x); }
171          in a rewrite class.
173     [d]  Certain parenthesis are now optional.
174          For example,
176              datatype Tree = empty | leaf (int) | node (Tree, int, Tree);
177     
178          can now be written as:
180              datatype Tree = empty | leaf int | node Tree, int, Tree;
182 [5]  Semiunification of non-linear patterns has been (partially) implemented.
183      Equality tests are automatically generated for repeated variables within
184      a pattern.  
186      This feature needs a typeclass extension to the type system 
187      to be fully functional.
189 [6]  Minor variant to 'match' called 'match while' has been added:
191      match[all] while (e1) and (e2) and ... and (en)
192      { p1: { action1 } 
193      | p2: { action2 } 
194      | ...
195      | ...
196      | pn: { actionn } 
197      }
199      repeats the matching process until none of the rules matches.
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.
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.  
210      datatype Tree = empty | node Tree, int, Tree;
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      ;
218 [8]  Embedded tags optimizations on term representations.
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.
223      For example, the datatype Tree in 
225        datatype Tree = empty 
226                      | leaf int 
227                      | node Tree, int, Tree
228                      ;
230      is mapped into the following code by default:
232      #define empty (a_Tree *)0 
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      };
243      class Tree_leaf : public a_Tree { ... };
244      class Tree_node : public a_Tree { ... };
247      On the other hand, with the embedded tag anotations '!':
249                    // embedded variant tag
250        datatype Tree ! = empty 
251                        | leaf int !            // embedded argument
252                        | node Tree, int, Tree
253                        ;
255      the class hierarchy can be collasped into just the class
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).  
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.
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. 
278      As always, we generate code assuming that the C++ compiler performs 
279      agressive optimizations such as common subexpression elimination.  
281 [9]  User definable lists and array-like constructors