explosion du type-checker

Giuseppe Castagna Giuseppe.Castagna at ens.fr
Thu Nov 27 21:36:23 CET 2003


Si l'on fait

select x from x in [1 2 3 4 5 6 7] where 3 = 3

ca donne

 [1 2 3 4 5 6 7]

avec le type suivant

[ 6 7 | 5 7 | 5 6 | 5 6 7 | 4 7 | 4 6 | 4 6 7 | 4 5 | 4 5 7 | 4 5 6 | 4
5 6
7 | 3 7 | 3 6 | 3 6 7 | 3 5 | 3 5 7 | 3 5 6 | 3 5 6 7 | 3 4 | 3 4 7 | 3 4 6 |
3 4 6 7 | 3 4 5 | 3 4 5 7 | 3 4 5 6 | 3 4 5 6 7 | 2 7 | 2 6 | 2 6 7 | 2 5 | 2
5 7 | 2 5 6 | 2 5 6 7 | 2 4 | 2 4 7 | 2 4 6 | 2 4 6 7 | 2 4 5 | 2 4 5 7 | 2 4
5 6 | 2 4 5 6 7 | 2 3 | 2 3 7 | 2 3 6 | 2 3 6 7 | 2 3 5 | 2 3 5 7 | 2 3 5 6 |
2 3 5 6 7 | 2 3 4 | 2 3 4 7 | 2 3 4 6 | 2 3 4 6 7 | 2 3 4 5 | 2 3 4 5 7 | 2 3
4 5 6 | 2 3 4 5 6 7 | 1 7 | 1 6 | 1 6 7 | 1 5 | 1 5 7 | 1 5 6 | 1 5 6 7 | 1
4 | 1 4 7 | 1 4 6 | 1 4 6 7 | 1 4 5 | 1 4 5 7 | 1 4 5 6 | 1 4 5 6 7 | 1 3 | 1
3 7 | 1 3 6 | 1 3 6 7 | 1 3 5 | 1 3 5 7 | 1 3 5 6 | 1 3 5 6 7 | 1 3 4 | 1 3 4
7 | 1 3 4 6 | 1 3 4 6 7 | 1 3 4 5 | 1 3 4 5 7 | 1 3 4 5 6 | 1 3 4 5 6 7 | 1
2 | 1 2 7 | 1 2 6 | 1 2 6 7 | 1 2 5 | 1 2 5 7 | 1 2 5 6 | 1 2 5 6 7 | 1 2 4 |
1 2 4 7 | 1 2 4 6 | 1 2 4 6 7 | 1 2 4 5 | 1 2 4 5 7 | 1 2 4 5 6 | 1 2 4 5 6
7 | 1 2 3 | 1 2 3 7 | 1 2 3 6 | 1 2 3 6 7 | 1 2 3 5 | 1 2 3 5 7 | 1 2 3 5 6 |
1 2 3 5 6 7 | 1 2 3 4 | 1 2 3 4 7 | 1 2 3 4 6 | 1 2 3 4 6 7 | 1 2 3 4 5 | 1 2
3 4 5 7 | 1 2 3 4 5 6 | 1 2 3 4 5 6 7 | 7 | 6 | 5 | 4 | 3 | 2 | 1? ]


Si vous regardez bien il s'agit de l'union de toutes les sous-sequences de
[1 2 3 4 5 6 7] (et di vous ne le voyaez pas essayez avec [1 2 3] et ca 
sera clair.

Ce qui est extremement precis mais qui en ajoutant quelque petit nombre a la 
sequence fait exploser de maniere exponentielle le temps de type-checking. Il 
faudrait peut etre trouver des heuristiques pour eviter cela non?

---Beppe---





More information about the Cduce-devel mailing list