9600604bf3134d7c60bc9a1c353292f32b274f4e
[Faustine.git] / interpretor / preprocessor / 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