interpretor/faust-0.9.47mr3/compiler/tlib/tlib.hh

   1 #ifndef     __TLIB__
   2 #define     __TLIB__
   3
   4 /************************************************************************
   5  ************************************************************************
   6     FAUST compiler
   7         Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
   8     ---------------------------------------------------------------------
   9     This program is free software; you can redistribute it and/or modify
  10     it under the terms of the GNU General Public License as published by
  11     the Free Software Foundation; either version 2 of the License, or
  12     (at your option) any later version.
  13
  14     This program is distributed in the hope that it will be useful,
  15     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17     GNU General Public License for more details.
  18
  19     You should have received a copy of the GNU General Public License
  20     along with this program; if not, write to the Free Software
  21     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  ************************************************************************
  23  ************************************************************************/
  24
  25
  26
  27 /*****************************************************************************
  28 ******************************************************************************
  29                                                         TLIB : tree library
  30                                                 Y. Orlarey, (c) Grame 2002
  31 ------------------------------------------------------------------------------
  32 Tlib is a simple tree library inspired by the ATerm library. It is made of
  33 five elements : symbols, nodes, smartpointers, trees and lists :
  34
  35      +------------------------+
  36      |            shlysis                 |
  37      +------------------------+
  38      |                  rec                       |
  39      |------------------------|
  40      |              list          |
  41      |------------------------|
  42      |              tree                  |
  43      |------------------------|
  44      | nodes   |                          |
  45      |---------| smartpointer |
  46      | symbol  |                          |
  47      +---------+--------------+
  48
  49  API:
  50  ----
  51         1) Symbols :
  52         ------------
  53         Sym q = symbol("abcd");         : returns a symbol q of name "abcd"
  54         const char* s = name(q);        : returns the name of symbol q
  55
  56         2) Nodes :
  57         ----------
  58         Node(symbol("abcd"));   : node with symbol content
  59         Node(10);                               : node with int content
  60         Node(3.14159);                  : node with float content
  61
  62         n->type();                              : kIntNode or kFloatNode or kSymNode
  63
  64         n->getInt();                    : int content of n
  65         n->getFloat();                  : float content of n
  66         n->getSym();                    : symbol content of n
  67
  68         - Pattern matching :
  69
  70         if (isInt(n, &i))       ... : int i = int content of n
  71         if (isFloat(n, &f))     ... : float f = float content of n
  72         if (isSym(n, &s))       ... : Sym s = Sym content of n
  73
  74         3) Trees :
  75         ----------
  76         tree (n)                           : tree of node n with no branch
  77         tree (n, t1)               : tree of node n with a branch t
  78         tree (n, t1,...,tm)    : tree of node n with m branches t1,...,tm
  79
  80         - Pattern matching :
  81
  82         if (isTree (t, n))         ... : t has node n and no branches;
  83         if (isTree (t, n, &t1)     ... : t has node n and 1 branch, t1 is set accordingly;
  84         if (isTree (t, n, &t1...&tm)...: t has node n and m branches, ti's are set accordingly;
  85
  86         - Accessors :
  87
  88         t->node()                  : the node of t
  89         t->arity()         : the number of branches of t
  90         t->branch(i)       : the ith branch of t
  91
  92         4) List :
  93         ---------
  94
  95         nil                                     = predefined empty list
  96         cons (x,l)                      = create a new list of head x and tail l
  97         list(a,b,..)            = cons(a, list(b,...))
  98
  99         hd(cons(x,l))           = x,
 100         tl (cons(x,l))          = l
 101         nth(l,i)                        = ith element of l (or nil)
 102         len(l)                          = number of elements of l
 103
 104         isNil(nil)                      = true          (false otherwise)
 105         isList(cons(x,l))       = true          (false otherwise)
 106
 107         lmap(f, cons(x,l))      = cons(f(x), lmap(f,l))
 108         reverse([a,b,..,z])     = [z,..,b,a]
 109         reverseall([a,b,..,z])  = [ra(z),..,ra(b),ra(a)] where ra is reverseall
 110
 111         - Set :
 112         (Sets are implemented as ordered lists of elements without duplication)
 113
 114         isElement(e,s)                  = true if e is an element of set s, false otherwise
 115         addElement(e,s)                 = s U {e}
 116         singleton(e)                    = {e}
 117         list2set(l)                             = convert a list into a set
 118         setUnion(s1,s2)                 = s1 U s2
 119         setIntersection(s1,s2)  = s1 intersection s2
 120         setIntersection(s1,s2)  = s1 - s2
 121
 122         - Environment :
 123
 124         pushEnv (key, val, env) -> env' create a new environment
 125         searchEnv (key,&v,env) -> bool  search for key in env and set v accordingly
 126
 127         - Property list :
 128
 129         setProperty (t, key, val) -> t          add the association (key x val) to the pl of t
 130         getProperty (t, key, &val) -> bool      search the pp of t for the value associated to key
 131         remProperty (t, key) -> t                       remove any association (key x ?) from the pl of t
 132
 133         5) Recursive trees
 134         ------------------
 135
 136         rid()                           = a unique ID (a tree) used to identify recursive trees
 137         rec(id, t)                      = a tree containing recursive references 'ref(id)'
 138         ref(id)                         = a reference to a surrounding 'rec(id,t)'
 139         isRec(t, id, t')        = true if t = rec(id,t')
 140         isRef(t, id)            = true if t = ref(id)
 141
 142         areEquiv(t,t')          = alpha equivalence of trees
 143         shmax(t)                        = maximize the sharing of recursive subtrees
 144
 145
 146         6) Sharing Analysis :
 147         ---------------------
 148
 149         shprkey(t) -> k         = unique sharing property key of t
 150         shcount(k,t') -> n      = returns the number of occurences of t' in t (where k = shprkey(t))
 151         shlysis(t)      -> k    = annotated the subtrees of t with prop (key sharing-count)
 152                                                   (0 if t' is not a subtree of t)
 153
 154
 155  History :
 156  ---------
 157         2002-02-08 : First version
 158         2002-02-20 : New description of the API
 159         2002-04-07 : Added Sharing Analysis 'shlysis.h'
 160
 161 ******************************************************************************
 162 *****************************************************************************/
 163
 164 #include "symbol.hh"
 165 #include "node.hh"
 166 #include "tree.hh"
 167 #include "num.hh"
 168 #include "list.hh"
 169 #include "shlysis.hh"
 170 //#include "recness.hh"
 171
 172 #endif