00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include <assert.h>
00025 #include <stdio.h>
00026 #include <stdlib.h>
00027 #include <limits.h>
00028 #include "tlib.hh"
00029
00030
00031 static Tree calcDeBruijn2Sym (Tree t);
00032 static Tree substitute(Tree t, int n, Tree id);
00033 static Tree calcsubstitute(Tree t, int level, Tree id);
00034 static Tree liftn(Tree t, int threshold);
00035 static Tree calcliftn(Tree t, int threshold);
00036
00037
00038
00039 Sym DEBRUIJN = symbol ("DEBRUIJN");
00040 Sym DEBRUIJNREF = symbol ("DEBRUIJNREF");
00041 Sym SUBSTITUTE = symbol ("SUBSTITUTE");
00042
00043 Sym SYMREC = symbol ("SYMREC");
00044 Sym SYMRECREF = symbol ("SYMRECREF");
00045 Sym SYMLIFTN = symbol ("LIFTN");
00046
00047
00048
00049
00050
00051
00052
00053
00054 Tree rec(Tree body)
00055 {
00056 return tree(DEBRUIJN, body);
00057 }
00058
00059 bool isRec(Tree t, Tree& body)
00060 {
00061 return isTree(t, DEBRUIJN, body);
00062 }
00063
00064 Tree ref(int level)
00065 {
00066 assert(level > 0);
00067 return tree(DEBRUIJNREF, tree(level));
00068 }
00069
00070 bool isRef(Tree t, int& level)
00071 {
00072 Tree u;
00073
00074 if (isTree(t, DEBRUIJNREF, u)) {
00075 return isInt(u->node(), &level);
00076 } else {
00077 return false;
00078 }
00079 }
00080
00081
00082
00083
00084
00085 Tree RECDEF = tree(symbol("RECDEF"));
00086
00087
00088 Tree rec(Tree var, Tree body)
00089 {
00090 Tree t = tree(SYMREC, var);
00091 t->setProperty(RECDEF, body);
00092 return t;
00093 }
00094
00095 bool isRec(Tree t, Tree& var, Tree& body)
00096 {
00097 if (isTree(t, SYMREC, var)) {
00098 body = t->getProperty(RECDEF);
00099 return true;
00100 } else {
00101 return false;
00102 }
00103 }
00104
00105
00106 Tree ref(Tree id)
00107 {
00108 return tree(SYMREC, id);
00109 }
00110
00111 bool isRef(Tree t, Tree& v)
00112 {
00113 return isTree(t, SYMREC, v);
00114 }
00115
00116
00117
00118
00119
00120
00121 int CTree::calcTreeAperture( const Node& n, const tvec& br )
00122 {
00123 int x;
00124 if (n == DEBRUIJNREF) {
00125
00126 if (isInt(br[0]->node(), &x)) {
00127 return x;
00128 } else {
00129 return 0;
00130 }
00131
00132 } else if (n == DEBRUIJN) {
00133
00134 return br[0]->fAperture - 1;
00135
00136 } else {
00137
00138 int rc = 0;
00139 tvec::const_iterator b = br.begin();
00140 tvec::const_iterator z = br.end();
00141 while (b != z) {
00142 if ((*b)->aperture() > rc) rc = (*b)->aperture();
00143 ++b;
00144 }
00145 return rc;
00146 }
00147 }
00148
00149 Tree lift(Tree t) { return liftn(t, 1); }
00150
00151 void printSignal(Tree sig, FILE* out, int prec=0);
00152
00153
00154
00155 #if 0
00156 static Tree _liftn(Tree t, int threshold);
00157
00158 static Tree liftn(Tree t, int threshold)
00159 {
00160 fprintf(stderr, "call of liftn("); printSignal(t, stderr); fprintf(stderr, ", %d)\n", threshold);
00161 Tree r = _liftn(t, threshold);
00162 fprintf(stderr, "return of liftn("); printSignal(t, stderr); fprintf(stderr, ", %d) -> ", threshold);
00163 printSignal(r, stderr); fprintf(stderr, "\n");
00164 return r;
00165 }
00166 #endif
00167
00168
00169 static Tree liftn(Tree t, int threshold)
00170 {
00171 Tree L = tree( Node(SYMLIFTN), tree(Node(threshold)) );
00172 Tree t2 = t->getProperty(L);
00173
00174 if (!t2) {
00175 t2 = calcliftn(t, threshold);
00176 t->setProperty(L, t2);
00177 }
00178 return t2;
00179
00180 }
00181
00182 static Tree calcliftn(Tree t, int threshold)
00183 {
00184 int n;
00185 Tree u;
00186
00187 if (isClosed(t)) {
00188
00189 return t;
00190
00191 } else if (isRef(t,n)) {
00192
00193 if (n < threshold) {
00194
00195 return t;
00196 } else {
00197
00198 return ref(n+1);
00199 }
00200
00201 } else if (isRec(t,u)) {
00202
00203 return rec(liftn(u, threshold+1));
00204
00205 } else {
00206 int n = t->arity();
00207
00208 tvec br(n);
00209 for (int i = 0; i < n; i++) {
00210 br[i] = liftn(t->branch(i), threshold);
00211 }
00212
00213 return CTree::make(t->node(), br);
00214 }
00215
00216 }
00217
00218
00219
00220
00221 Tree DEBRUIJN2SYM = tree(symbol("deBruijn2Sym"));
00222
00223 Tree deBruijn2Sym (Tree t)
00224 {
00225 assert(isClosed(t));
00226 Tree t2 = t->getProperty(DEBRUIJN2SYM);
00227
00228 if (!t2) {
00229 t2 = calcDeBruijn2Sym(t);
00230 t->setProperty(DEBRUIJN2SYM, t2);
00231 }
00232 return t2;
00233 }
00234
00235 static Tree calcDeBruijn2Sym (Tree t)
00236 {
00237 Tree body, var;
00238 int i;
00239
00240 if (isRec(t,body)) {
00241
00242 var = tree(unique("W"));
00243 return rec(var, deBruijn2Sym(substitute(body,1,ref(var))));
00244
00245 } else if (isRef(t,var)) {
00246
00247 return t;
00248
00249 } else if (isRef(t,i)) {
00250
00251 fprintf(stderr, "ERREUR, une reference de Bruijn touvee ! : ");
00252 printSignal(t, stderr);
00253 fprintf(stderr, ")\n");
00254 exit(1);
00255 return t;
00256
00257 } else {
00258
00259
00260 int a = t->arity();
00261 tvec br(a);
00262
00263 for (int i = 0; i < a; i++) {
00264 br[i] = deBruijn2Sym(t->branch(i));
00265 }
00266
00267 return CTree::make(t->node(), br);
00268 }
00269 }
00270
00271 static Tree substitute(Tree t, int level, Tree id)
00272 {
00273 Tree S = tree( Node(SUBSTITUTE), tree(Node(level)), id );
00274 Tree t2 = t->getProperty(S);
00275
00276 if (!t2) {
00277 t2 = calcsubstitute(t, level, id);
00278 t->setProperty(S, t2);
00279 }
00280 return t2;
00281
00282 }
00283
00284 static Tree calcsubstitute(Tree t, int level, Tree id)
00285 {
00286 int l;
00287 Tree body;
00288
00289 if (t->aperture()<level) {
00290
00291 return t;
00292 }
00293 if (isRef(t,l)) return (l == level) ? id : t;
00294 if (isRec(t,body)) return rec(substitute(body, level+1, id));
00295
00296 int ar = t->arity();
00297
00298 tvec br(ar);
00299 for (int i = 0; i < ar; i++) {
00300 br[i] = substitute(t->branch(i), level, id);
00301 }
00302
00303 return CTree::make(t->node(), br);
00304 }
00305
00306
00307
00308
00309
00310
00311 struct Env {
00312 Tree fTree; Env* fNext;
00313 Env(Tree t, Env* nxt) : fTree(t), fNext(nxt) {}
00314 };
00315
00316 static void markOpen(Tree t);
00317 static int recomputeAperture(Tree t, Env* p);
00318 static int orderof (Tree t, Env* p);
00319
00320 void updateAperture(Tree t)
00321 {
00322 markOpen(t);
00323 recomputeAperture(t, NULL);
00324 }
00325
00326
00327
00328 static void markOpen(Tree t)
00329 {
00330 if (t->aperture() == INT_MAX) return;
00331 t->setAperture(INT_MAX);
00332 int ar = t->arity();
00333 for (int i = 0; i < ar; i++) {
00334 markOpen(t->branch(i));
00335 }
00336 }
00337
00338 static int recomputeAperture(Tree t, Env* env)
00339 {
00340 Tree var, body;
00341
00342 if (t->aperture() == 0) return 0;
00343
00344 if (isRef(t, var)) {
00345
00346 return orderof(var, env);
00347
00348 } else if (isRec(t, var, body)) {
00349
00350 Env e(var,env);
00351 int a = recomputeAperture(body, &e) - 1;
00352 if (a<=0) { t->setAperture(0); }
00353 return a;
00354
00355 } else {
00356
00357 int ma = 0;
00358 int ar = t->arity();
00359 for (int i = 0; i<ar; i++) {
00360 int a = recomputeAperture(t->branch(i), env);
00361 if (ma < a) ma = a;
00362 }
00363 if (ma <= 0) { t->setAperture(0); }
00364 return ma;
00365 }
00366 }
00367
00368
00369 static int orderof (Tree t, Env* p)
00370 {
00371 if (p == NULL) return 0;
00372 if (t == p->fTree) return 1;
00373
00374 int pos = 1;
00375 while (p != NULL) {
00376 if (t == p->fTree) return pos;
00377 p = p->fNext;
00378 pos++;
00379 }
00380 return 0;
00381 }