[Caml-list] Ca marche pas, et ca m'enerve

[Caml-list] Ca marche pas, et ca m'enerve

[Nicolas FRANCOIS]

[-- Attachment #1: Type: text/plain, Size: 1075 bytes --]

Mais c'est pas trop gros, donc je joins en attachement pour que d'autres
testent.

Mon probleme : ce programme explore les machines de Turing a n etats, pour
decouvrir les "castors actifs", i.e. les MdT ecrivant le plus de 1 sur la
bande avant de s'arreter. Si l'on cherche les CA a deux etats (ligne " 
and tablesize = 2 in" dans le fichier main.ml), ca marche. Par contre,
j'ai une erreur de Stack Overflow si je lance le programme avec tablesize
= 3.

Ca semble venir des incessantes manipulations de listes representant le
macro-ruban (fichier macro_strip.ml). C'est bizarre, je pensais que les
pointeurs de "cons-cells" n'etaient pas affectes sur la pile. Ca plante,
avec ocamldebug, au pas 770000 et quelques, sur une operation sur une
liste.

Mes manipulations sur les listes sont-elles incorrectes ? Comment faire
pour aider le garbage collector a se rendre compte qu'un pointeur ne sera
plus jamais utilise ?

Merci pour tout conseil.

\bye

-- 

Nicolas FRANCOIS
http://nicolas.francois.free.fr

We are the Micro$oft.
Resistance is futile.
You will be assimilated.

[-- Attachment #2: castor.tar.gz --]
[-- Type: application/octet-stream, Size: 16005 bytes --]

Re: [Caml-list] Ca marche pas, et ca m'enerve

[Nicolas Cannasse]

> Mais c'est pas trop gros, donc je joins en attachement pour que d'autres
> testent.
>
> Mon probleme : ce programme explore les machines de Turing a n etats, pour
> decouvrir les "castors actifs", i.e. les MdT ecrivant le plus de 1 sur la
> bande avant de s'arreter. Si l'on cherche les CA a deux etats (ligne "
> and tablesize = 2 in" dans le fichier main.ml), ca marche. Par contre,
> j'ai une erreur de Stack Overflow si je lance le programme avec tablesize
> = 3.
>
> Ca semble venir des incessantes manipulations de listes representant le
> macro-ruban (fichier macro_strip.ml). C'est bizarre, je pensais que les
> pointeurs de "cons-cells" n'etaient pas affectes sur la pile. Ca plante,
> avec ocamldebug, au pas 770000 et quelques, sur une operation sur une
> liste.
>
> Mes manipulations sur les listes sont-elles incorrectes ? Comment faire
> pour aider le garbage collector a se rendre compte qu'un pointeur ne sera
> plus jamais utilise ?
>
> Merci pour tout conseil.

Cela veut surement dire que certaines de tes fonctions ne sont pas
"tail-recursive" :

http://www.google.fr/search?q=tail+recursive+function&ie=UTF-8&hl=fr&meta=

Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Ca marche pas, et ca m'enerve

[Damien Doligez]

On Jun 12, 2004, at 03:13, Nicolas FRANCOIS (AKA El Bofo) wrote:

> Mes manipulations sur les listes sont-elles incorrectes ? Comment faire
> pour aider le garbage collector a se rendre compte qu'un pointeur ne 
> sera
> plus jamais utilise ?

Rien a voir avec les listes ni avec le GC.  Ta fonction run_aux (ligne 
49
de macro_machine.ml) n'est pas tail-rec parce que son appel recursif se
trouve dans un bloc try...with.  Du coup, elle doit empiler a chaque 
appel,
et elle finit par faire deborder la pile.  Tu peux essayer d'augmenter 
la
taille de la pile:

   bash$ OCAMLRUNPARAM="l=1G" ./bb

Malheureusement, j'ai l'impression que ca ne t'aidera pas car ton
programme a l'air de boucler.

-- Damien

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Ca marche pas, et ca m'enerve

[Nicolas FRANCOIS]

Le Sat, 12 Jun 2004 12:24:08 +0200 Damien Doligez
<damien.doligez@inria.fr> a écrit :

> On Jun 12, 2004, at 03:13, Nicolas FRANCOIS (AKA El Bofo) wrote:
> 
> > Mes manipulations sur les listes sont-elles incorrectes ? Comment
> > faire pour aider le garbage collector a se rendre compte qu'un
> > pointeur ne sera
> > plus jamais utilise ?
> 
> Rien a voir avec les listes ni avec le GC.  Ta fonction run_aux (ligne 
> 49
> de macro_machine.ml) n'est pas tail-rec parce que son appel recursif se
> trouve dans un bloc try...with.  Du coup, elle doit empiler a chaque 
> appel,
> et elle finit par faire deborder la pile.  Tu peux essayer d'augmenter 
> la
> taille de la pile:
> 
>    bash$ OCAMLRUNPARAM="l=1G" ./bb
> 
> Malheureusement, j'ai l'impression que ca ne t'aidera pas car ton
> programme a l'air de boucler.

Eh bien voila ! Je savais bien qu'on me resoudrait mon probleme :-) Je
dois donc des excuses pour le ton peremptoire avec lequel j'ai affirme que
mon programme etait parfaitement programme. Comme quoi, quand on n'est pas
sur, on ferait mieux de fermer sa grande g... (c'est d'ailleurs a ca qu'on
reconnait ceux qui n'y connaissent rien : ce sont ceux qui beuglent le
plus fort).

Je ne savais pas que l'imbrication dans un bloc try...with bloquait la
detection de la recursion terminale. je vais modifier mon approche pour
eviter ca, ca me parait plus sur que d'augmenter la pile.

Normalement, mon programme ne devrait pas boucler, mais je n'ai pas encore
implemente les filtres necessaires pour eliminer les machines qui ne vont
_visiblement_ pas s'arreter (Rq : le probleme etant indecidable, il n'y a
aucune chance de construire un programme qui les eliminera toutes, mais on
peut quand meme esperer que pour des machines pas trop grosses (donc en
limitant le nombre d'etats), on arrive a une classification complete).
Donc c'est sans doute normal que ca boucle, surtout que le nombre de
machines a envisager est assez enorme.

J'ai trouve sur Internenette une tres interessante transposition de ce
probleme en termes de machines a registres. Ca semble plus simple a
programmer, et je pense que ca peut faire un excellent sujet de TIPE pour
les eleves de l'option informatique. Peut-etre serait-il d'ailleurs
interessant de regrouper des idees de projets et des debuts de bouts de
code pour constituer une "base de donnees" de projets pour les eleves (ou
les collegues, d'ailleurs). Un projet un peu similaire s'est lance sur
gna.org pour des projets d'etudiants.

Merci encore a Damien et Nicolas pour avoir mis le doigt sur les
imperfections de mon code, et mes excuses renouvelees pour la reaction un
peu (completement) prematuree.

\bye

-- 

Nicolas FRANCOIS
http://nicolas.francois.free.fr

We are the Micro$oft.
Resistance is futile.
You will be assimilated.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners