tail recursivity - recursivite terminale

R12y wrote on 29/08/05 :

La récursivité ça m'a impressionné :-).

La plupart des langages savent faire ça, à commencer par le C. Mais si
il n'y a plus de pile, ça pète quelque soit le langage. La récursivité
n'est pas conseillée en production si la vie des gens est en jeu
(avionique, nucléaire, médecine...). Ca reste un concept très
universitaire...

Ah bon. Et comment crois-tu que les systèmes d'exploitation balaient une
arborescence de répertoires
quand on recherche un fichier ?
Il y a tout de même longtemps que la récursivité s'est "échappée" des
laboratoires...

Jacti

Jacti wrote:

http://en.wikipedia.org/wiki/Parsing_expression_grammar

ah ! ah ! ah !
Je ne sais pas qui a écrit cet article du wikipedia mais alors là, je
rigole franchement tellement il est nul.

Hop. C'est ton domaine... plus qu'à corriger (en essayant de rester
accessible). La beauté des wikis.

Jacti wrote:

[...]
Commentaire : allons-y, mélangeons allègrement les expressions régulières

C'est ce qui s'appelle de la vulgarisation ou encore métaphore/analogie...
Quand je dis qu'un camion c'est une voiture en plus gros c'est faux et
pourtant c'est compréhensible !

[...]
Et puis des performances en temps exponentiel, bonjour les dégâts !!!

C'est là où il faut lire correctement ! Les performances sont linéaires !
http://pdos.csail.mit.edu/~baford/packrat/
http://www.cs.nyu.edu/rgrimm/xtc/rats.html

[...]
En conclusion, je ne vois pas ce que les PEG apportent de nouveau. C'est
même plutôt une régression.

Ben justement lit les articles correspondants et tu verras qu'il y a un
intérêt. D'autant plus que les langages reconnus par les uns et les
autres ne sont identiques...
De plus, comme définition, les PEG sont plus simples car elles enlève
l'ambiguïté du if/then/else par exemple. Elles sont donc meilleurs comme
*norme* même si rien ne t'empêche (selon le langage) ensuite
d'implémenter un parseur LALR ou LL.

http://citeseer.ist.psu.edu/cis?q=Packrat&submit=Search+Documents&cs=1

[...]

De plus, pour qui la lecture est le plus important ? le programmeur ou
l'ordinateur ?

Je répondrai à cette question en disant : par les 2 car on peut toujours
"inventer" des formes syntaxiques
"agréables" pour le programmeur mais quasi inimplémentable par un
algorithme (donc illisible par un ordinateur),
ou peut-être en temps exponentiel ;-)

Décidément, quand on ne fait pas d'effort et qu'on lit en travers...

--
Yermat

Jacti wrote:

[...]
Commentaire : allons-y, mélangeons allègrement les expressions régulières

C'est ce qui s'appelle de la vulgarisation ou encore métaphore/analogie...
Quand je dis qu'un camion c'est une voiture en plus gros c'est faux et
pourtant c'est compréhensible !

[...]
Et puis des performances en temps exponentiel, bonjour les dégâts !!!

C'est là où il faut lire correctement ! Les performances sont linéaires !
http://pdos.csail.mit.edu/~baford/packrat/
http://www.cs.nyu.edu/rgrimm/xtc/rats.html

Si, si, j'ai lu. Les performances sont linéaires si on mémorise tout mais c'est
la dichotomie
bien connue en informatique entre le temps et l'espace...

C'est le problème avec les langages de type 1de Chomsky (langages
context-sensitive) qui sont reconnaissables par des amlb (Automates à Mémoire
Linéairement Bornée).
Il leur faut une mémoire qui peut être égale au volume du texte à reconnaître,
donc c'est souvent impraticable. Par exemple le langage qui est constitué de
tous les mots contenant un nombre premier de 'a' est de type 1. On sait donc
construire un amlb qui reconnaît tous ces mots. On sait donc facilement
reconnaître les nombres premiers sauf que pour reconnaître un nombre premier
aux environs de 10^80, il faudra consommer autant de mémoire...

[...]
En conclusion, je ne vois pas ce que les PEG apportent de nouveau. C'est
même plutôt une régression.

Ben justement lit les articles correspondants et tu verras qu'il y a un
intérêt. D'autant plus que les langages reconnus par les uns et les
autres ne sont identiques...
De plus, comme définition, les PEG sont plus simples car elles enlève
l'ambiguïté du if/then/else par exemple. Elles sont donc meilleurs comme
*norme* même si rien ne t'empêche (selon le langage) ensuite
d'implémenter un parseur LALR ou LL.

http://citeseer.ist.psu.edu/cis?q=Packrat&submit=Search+Documents&cs=1

Enfin on ne va pas faire toute une montagne de "l'ambiguïté" du if/then/else
non plus.
Si c'était le cas (mais ça ne l'ai pas), je serais tenté de dire "tout ça pour
ça".
Il y a des ambiguïtés bien plus terribles dans les langages comme les tableaux
de labels
à plusieurs dimensions en PL/1, par exemple (l'ambiguïté ne peut être levée que
par des "actions sémantiques").

Ce ne sont d'ailleurs pas des "normes" mais juste des représentations qui
possèdent certaines propriétés.

Enfin j'ai téléchargé ce document : Alexander Birman's Ph.D. thesis from 1970,
référencé en bas de la page
http://pdos.csail.mit.edu/~baford/packrat/ et je suis heureux de voir que
Ullman était son directeur de thèse.

[...]

De plus, pour qui la lecture est le plus important ? le programmeur ou
l'ordinateur ?

Je répondrai à cette question en disant : par les 2 car on peut toujours
"inventer" des formes syntaxiques
"agréables" pour le programmeur mais quasi inimplémentable par un
algorithme (donc illisible par un ordinateur),
ou peut-être en temps exponentiel ;-)

Décidément, quand on ne fait pas d'effort et qu'on lit en travers...

Je n'ai pas lu de travers mais j'ai passé sous silence pour
les raisons évoquées plus haut.

Jacti

Jacti wrote:

(snip)

De toute façon, je considère Python comme un très mauvais langage

Tu n'a pas toujours dit ça... Il y a une paire d'année, tu te
retranchais derrière tes années d'expérience comme enseignant pour
affirmer que c'était un mauvais *premier* langage, je cite:

"""
Je ne dis pas que Python est un mauvais langage, c'est un mauvais langage
pour apprendre la programmation, ce qui est différent...
"""

Je te laisse le soin de retrouver le contexte - vu ton expérience, ça ne
devrait pas te poser de problème !-)

Non ça ne me pose pas de problème et je me rappelle très bien la discussion.
Mais maintenant je considère que c'est un mauvais langage tout court.

Heu... Tu a bien lu le warning en haut du message, et regardé sur quel
ng tu postais ?-)

Oui, et alors ?

Oh, rien...

j'ai travailler dans les compilateurs et je connais plus de 30 langages de
programmation et, donc,
je sais de quoi je parle...

Au lieu d'affirmer péremptoirement, tu pourrais peut-être argumenter ?

Un langage qui utilise l'indentation comme forme syntaxique de bloc
ne peut pas être un "bon" langage... (c'est inexprimable en BNF).

Ce n'est pas la première fois que tu nous la sors, celle-là !-)

Bon, à part que *tu* n'aimes pas ce principe - ce qui es ton droit le
plus strict-, la seule chose que ça prouve est le formalisme BNF est
limité. Je pense que tu connais assez la POO et des langages comme
Smalltalk ou CLOS pour avoir sous la main des idiomes courant dans ces
langages qui sont à peu près inexprimables en UML. Si oui, celà
implique-t'il que Smalltalk et CLOS soient de mauvais langages objets ?-)

Non ça prouve que c'est UML qui n'a pas su s'adapter car ces langages existaient
avant
et comme l'approche OO s'est construite de façon bottom-up...

Pourquoi les informaticiens ont-ils toujours des attirances pour les plus
mauvais langages
(C, C++, Python, Visual Basic, par exemple) ?

Cherchez l'intrus... Si tu place Python et VB dans la même catégorie, je
crains que tu ne saches pas si bien que ça de quoi tu parles...

Bien sûr que VB n'est pas sur le même plan que Python (tout de même !), VB
étant le "Canada Dry" des LOO

<hs>
Crois-le ou non, mais il y a pire que VB. Si si, c'est possible...
</hs>

mais du point de vue qui nous occupe ici,
ils sont aussi "sales" (même si ce n'est pas le même type de saletés).

Jugement de valeur encore. 30 ans d'expérience ne suffisent pas à faire
passer un jugement de valeur pour une critique argumentée.

On verra bien quand il faudra, dans le moyen terme, maintenir tout le code qui
s'écrit avec ces langages. Sauf à considérer que tout ça c'est jetable...

(snip)

En ce qui me concerne, Python me permet de faire ce que j'ai à faire
simplement et rapidement. Effectivement avec d'infâmes bidouilles, comme
par exemple :
- les fonctions en tant qu'objets de première classe
- les fermetures
- les expressions de liste
- les générateurs
- les descripteurs
- les métaclasses

C'est vraiment la redécouverte de la poudre !

Non, pas la "redécouverte", juste l'utilisation. PAQJS, il n'y a rien de
nouveau en Python - et je n'ai jamais vu personne le prétendre (en tout
cas personne ayant un minimum de culture dans ce domaine). Là encore, je
te trouve de bien mauvaise foi.

Ce n'est pas de la mauvaise foi, c'est un constat.

Bref, si l'on mets de côté les deux derniers points, d'infâmes
bidouilles très ouvertements inspirées des langages fonctionnels...

Ah, oui, c'est vrai, pas de macros, pas de joli modèle mathématique, une
préférence marquée pour la simplicité et la lisibilité... C'est vrai que
c'est minable, Python, quand on y pense.

Bonjour la simplicité syntaxique de Python !!

Je n'ai pas parlé de "simplicité syntaxique", mais de simplicité
d'utilisation. Mais si tu veux aller sur ce terrain, je veux bien que tu
me démontre en quoi l'utilisation de *deux* point-virgules à la fin
d'une expression relève de la "simplicité syntaxique" !-)

Contrairement à ce que tu crois, je ne suis pas forcément un farouche partisan de la
syntaxe
de Caml. Par contre c'est un très bon langage du point de vue de la puissance
d'expression (sémantique).

<ironie>
Quant à la simplicité d'utilisation, il faut bien avouer que les
entrées/sorties en Haskell sont d'une simplicité remarquables
</ironie>

On est d'accord...

Bref, le purisme, c'est bien beau, mais ça a des limites...

Je ne suis pas puriste mais il y a des limites aux arguments des défenseurs du
"pragmatisme".

On ne peut pas faire un VRAI système d'exploitation

C'est quoi un "VRAI" système d'exploitation ?-)

Ben des choses comme UNIX par exemple.
Je voulais exclure des "choses" comme Windows.

sans un mécanisme
de macros

M'en fiche, je ne fais pas d'OS. Ni de contrôle de missiles, d'ailleurs.

Oui mais pas moi car j'en ai fait.

Dernière remarque : loin de moi l'idée d'un troll. J'utilise Usenet depuis 1985
et je connais les règles.

Avec tout le respect que j'ai pour ton éminente expérience (non, ce
n'est pas de l'ironie - enfin, à moitié seulement...), je me permets
d'attirer ton attention sur le fait que l'un n'empêche pas l'autre - au
contraire...

Mais bon, on a déjà eu plusieurs fois l'occasion de troller^Mdébattre de
ces sujets, et, hélas, la seule chose que ça m'a appris est que tu a 30
ans d'expérience et que tu sais de quoi tu parles...

Il me semblait pourtant avoir argumenté suffisamment, au moins par le passé,
et rappelé certaines connaissances que certains semblent avoir oubliées (pour rester
optimiste).

Jacti

(snip)

Maintenant, comme il y a des langages qui ne spécifient pas la
dérécursivation terminale automatique, et comme il y a des algorithmes
récursifs non-terminaux, un programmeur doit savoir dérécursiver
manuellement de toutes façons. (C'est trivial si on utilise une pile
explicite).

A répéter 10 fois le plus vite possible:
"Un bon programmeur doit savoir dérécursiver une récursion sans son
dérécursivateur terminal automatique"

Attention toutefois car : Un algorithme est dérécursivable si la fonction
enveloppante est associative et admet un élément neutre.
Tout algorithme n'est pas forcément dérécursivable.

Ok, je sors

Non, non, reste avec nous :-)

Jacti

Jacti wrote:

Un langage qui utilise l'indentation comme forme syntaxique de bloc
ne peut pas être un "bon" langage... (c'est inexprimable en BNF).

Celle là, il faut la coller dans un fortune consacré à Python.

Mais faites donc, c'est fait pour ça justement.

Jacti

Laurent Pointal wrote:

Jacti wrote:

Un langage qui utilise l'indentation comme forme syntaxique de bloc
ne peut pas être un "bon" langage... (c'est inexprimable en BNF).

Celle là, il faut la coller dans un fortune consacré à Python.

Oui, j'aime bien aussi ;-)

De toute façon la notion de bon langage est subjective et n'est

Ah bon ?
Je connais une application qui fait 60 000 lignes de Gnu Make :-)
As-tu essayé de comprendre un programme écrit en APL ?

aucunement liée à sa syntaxe. Je connais des gens qui programment comme
des cochons en ADA et des gens qui sont très rigoureux en python...

Bien sûr mais disons que certains langages forcent plus que d'autres à
écrire proprement.

Jacti

Jacti wrote:

Jacti wrote:

[ Attention: Xpost + follow-up ]

(snip)

[snip]

Ah, oui, c'est vrai, pas de macros, pas de joli modèle mathématique, une
préférence marquée pour la simplicité et la lisibilité... C'est vrai que
c'est minable, Python, quand on y pense.

Bonjour la simplicité syntaxique de Python !!
On ne peut pas faire un VRAI système d'exploitation sans un mécanisme
de macros (bien que je n'aime pas ça, mais c'est un mal nécessaire...).

Qui a dit que Python servait à faire des systèmes d'exploitation ? Et qui a
dis qu'il fallait un système de macro pour faire un OS de toute façon ?
Tellement d'erreurs en si peu de mots. Celui là aussi mérite une fortune !

Tu interprète à ta façon mes remarques (on pourrait appeler cela du "forcing
sémantique").
Je n'ai jamais dit que Python servait à faire des OS.
Par contre oui, j'affirme que pour faire un OS il préférable de disposer d'un
macroprocesseur (qui connaît
aujourd'hui encore le macroprocesseur M4 de Gnu ? tiens, il y en a encore
http://johann.jalix.org/tutoriels/) :
http://www.gnu.org/software/m4/ et aussi
http://www.seindal.dk/rene/gnu/whatis.htm

Il n'y a donc pas "tellement d'erreurs"...

Dernière remarque : loin de moi l'idée d'un troll. J'utilise Usenet depuis
1985 et je connais les règles.

Je ne pense pas que la définition de troll d'aujourd'hui soit si différente
de celle de 85. En tout cas rien qui ne change le fait que tu as posté un
gros troll baveux.

Tu pourrais au moins rester poli.

Jacti

À (at) Thu, 08 Sep 2005 15:27:07 +0200,
Jacti <jacti@jacti-antispam.com> écrivait (wrote):

Attention toutefois car : Un algorithme est dérécursivable si la fonction
enveloppante est associative et admet un élément neutre.
Tout algorithme n'est pas forcément dérécursivable.

... sans mettre en oeuvre une pile. Si on s'autorise une pile, ce
n'est plus pareil.

En programmation, on parle souvent (et abusivement) de
«dérécursivation» lorsqu'on passe d'une gestion de pile implicite (par
exemple celle des appels de fonctions) à une gestion explicite (par
une simple boucle et un tableau de taille plus ou moins
dynamique). L'intérêt étant, par exemple, de gagner du temps et de la
place (on n'empile que le strict nécessaire) et de pouvoir gérer
explicitement les cas de dépassement de pile.

Dans de rares cas (comme celui d'une récursivité terminale), cette
dérécursivation permet de supprimer complètement la pile.

--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>