File | share.str |
Author | unknown |
Since | unknown |
The ATerm library preserves maximal sharing of subtermsthrough hash-consing. This sharing is not directly availableto the user of an ATerm. For some applications it is necessaryto make the implicit sharing in terms explicit in the form ofa let construct in which all occurences of a shared subtermare replaced by a symbolic pointer (variable).
General | |
Lines of code | 86 |
Stratego | |
Module number | 1 (100% documented) |
Constructor number | 1 (0% documented) |
Overlay number | 0 |
Strategy number | 5 (40% documented) |
Rule number | 3 (0% documented) |
DynamicRule number | 0 |
Constructor summary |
||
GraphLet(ATerm , ATerm ) | n/a | share.str |
Strategy summary |
||
edge(Strategy mkvar) | n/a | share.str |
graph(Strategy mkvar) | The graph of a term is obtained by turning each node \verb|F(t1, | share.str |
inline-graph(Strategy always, Strategy mklet) | n/a | share.str |
list-edge(Strategy mkvar) | n/a | share.str |
share(Strategy mkvar, Strategy always, Strategy mklet) | The strategy share defined in this module achieves such an explicit sharing for arbitrary terms | share.str |
Rule summary |
||
term-share-dead | n/a | share.str |
term-share-dont-inline(Strategy mklet) | n/a | share.str |
term-share-inline | n/a | share.str |
Strategy details |
|||||||||
ATerm | graph(Strategy mkvar) | ||||||||
The graph of a term is obtained by turning each node\verb|F(t1,...,tn)| into an edge \verb|(a, F(a1,...,an))|,where \verb|a| is the address of the node and the \verb|ai|are the addresses of its direct subterms. The \verb|mkvar|parameter is used to embed the address in some constructor.(If \verb|mkvar| is \verb|id|, nothing is done.) The first edge in the graph is the root of the tree. Bydefinition it is never shared. The graph can be turned intoone big let-expression with the root as its body. That is whatthe first line of the definition of \verb|inline-graph|accomplishes. Subsequently, nodes that are not shared, i.e., a pointer towhich only occurs once, can be inlined. Some nodes may alwayshave to be inlined (for application specific reasons). Theshape of such nodes is specified by the parameter\verb|always|. Edges that cannot be inlined are turned into alet-binding the form of which is determined by the parameter\verb|mklet|. After all graph edges have either been inlined or turned intolet-bindings the, now empty, \verb|GraphLet| is discarded andreplaced by its body. |
|||||||||
ATerm | share(Strategy mkvar, Strategy always, Strategy mklet) | ||||||||
The strategy share defined in this module achieves suchan explicit sharing for arbitrary terms. The approach used bythe strategy is to first turn the term into its underlyinggraph and then inlining those subterms that are not shared(only occur once) or that cannot be shared in this way (uptothe needs of an application). |
|||||||||