L'algorithme de l'addition

[Stephane]

Bonjour,

Je ne suis pas sur que qui que ce soit soit à l'écoute sur le forum,
mais tant pis, je me lance.

Depuis quelques mois, j'ai commencé à m'intéresser à Lisp (Common Lisp
et Emacs Lisp). Le plus intéressant a été d'apprendre Lisp à une époque
ou même l'addition n'était pas une fonction de base.

À l'époque, Lisp n'avait même pas de commande pour réaliser une boucle,
mais cela n'est pas grave parce cela n'est pas utile nous explique le
prof du MIT dans ce cours des années 80 que l'on trouve encore sur
Youtube.

(defun plus (x y)
(if (= x 0) y
(if (< x 0) (plus (incf x) (decf y))
(plus (decf x) (incf y)))))

[Stéphane CARPENTIER]

Le 22-07-2021, Stephane <step...@invalid.org> a écrit :
>
> Je ne suis pas sur que qui que ce soit soit à l'écoute sur le forum,
> mais tant pis, je me lance.

C'est vrai que ça a l'air un peu vide ici.

> À l'époque, Lisp n'avait même pas de commande pour réaliser une boucle,

Normalement, je dirais que tu peux toujours éviter d'utiliser une
boucle en utilisant la récursivité. Le problème de la récursivité, c'est
que ça peut être très gourmand en mémoire.

--
Si vous avez du temps à perdre :
https://scarpet42.gitlab.io

[Stephane Tougard]

On 2021-07-24, Stéphane CARPENTIER <s...@fiat-linux.fr> wrote:
> Normalement, je dirais que tu peux toujours éviter d'utiliser une
> boucle en utilisant la récursivité. Le problème de la récursivité, c'est
> que ça peut être très gourmand en mémoire.

D'après ce que j'ai compris, au niveau de la machine, il n'y a pas de
différence fondamentale entre une fonction récursive et une boucle,
les deux utilisent les mêmes code en language machine.

Peut-être ai-je tout faux sur ça.

En attendant, essaye de faire ça sans la récursivité :

(defun parse-j(j s)
(if (or (not (listp j)) (null j)) ()
(progn
(if (and (listp (car j)) (equalp (caar j) (car s)))
(if (= (length s) 1)
(car j)
(parse-j (car j) (cdr s)))
(parse-j (cdr j) s)))))


Ça sert à parser une liste retourné par la fonction decode-json du
package cl-json.

(parse-j a '(:DATA :XPUB :XPUB :BALANCE)

Ou a est la liste en question et la liste correspond à l'entrée
recherchée dans cette liste.

[Stéphane CARPENTIER]

Le 24-07-2021, Stephane Tougard <step...@unices.org> a écrit :
> On 2021-07-24, Stéphane CARPENTIER <s...@fiat-linux.fr> wrote:
>> Normalement, je dirais que tu peux toujours éviter d'utiliser une
>> boucle en utilisant la récursivité. Le problème de la récursivité, c'est
>> que ça peut être très gourmand en mémoire.
>
> D'après ce que j'ai compris, au niveau de la machine, il n'y a pas de
> différence fondamentale entre une fonction récursive et une boucle,
> les deux utilisent les mêmes code en language machine.
>
> Peut-être ai-je tout faux sur ça.

C'est possible qu'aujourd'hui ça ait changé, mais il y a longtemps,
quand j'avais découvert le LISP à la fac, la récursivité prenait plus de
mémoire et ça se voyait. C'était facile de trouver un nombre assez grand
pour que la factorielle explose en récursivité alors qu'en boucle ça
allait beaucoup plus loin. Je ne sais pas comment ça pourrait être fait
maintenant pour que ça ne prenne pas plus de mémoire.

Le principe de la boucle est que tu mets ta boucle en mémoire avec les
variables et que tu calcule l'évolution de tes variables à chaque
itération.

Alors qu'avec la récursivité, tu ne peux pas connaître la valeur de ta
variable de retour tant que tu n'es pas allé jusqu'à la dernière
itération. Il faut donc dupliquer en mémoire la fonction récursive avec
l'état de ses variables à chaque itération. C'est possible qu'il y ait
des techniques qui permettent d'éviter la duplication de la mémoire,
mais je ne vois pas comment.

> En attendant, essaye de faire ça sans la récursivité :

N'inverse pas ce que j'ai écrit. J'ai écrit que tu peux remplacer une
boucle en utilisant la récursivité. Pas l'inverse. D'ailleurs, c'est toi
qui suppose l'inverse puisque tu dis que le code en langage machine est
le même. C'est donc qu'il y a une méthode automatique de passer de la
récursivité à la boucle.

[Stephane Tougard]

On 2021-07-25, Stéphane CARPENTIER <s...@fiat-linux.fr> wrote:
> Le principe de la boucle est que tu mets ta boucle en mémoire avec les
> variables et que tu calcule l'évolution de tes variables à chaque
> itération.

Si on traduisait ça en assembleur ?

Je veux dire, il y pas de mécanisme de boucle en assembleur, pas de
mécanisme de récursivité non plus d'ailleurs.

> N'inverse pas ce que j'ai écrit. J'ai écrit que tu peux remplacer une
> boucle en utilisant la récursivité. Pas l'inverse. D'ailleurs, c'est toi
> qui suppose l'inverse puisque tu dis que le code en langage machine est
> le même. C'est donc qu'il y a une méthode automatique de passer de la
> récursivité à la boucle.

En effet, mais en fait, je faisais juste du "show off" avec un algo
récursif dont je suis assez fier.

En fait, une des grandes différences entre Lisp et un autre language,
c'est que tu peux passer 4 heures sur 3 lignes de codes pour justement
que ce soient les 3 bonnes lignes. Je crois n'avoir quasiment fait du
récursif en Python/Perl (alors que c'est tout à fait supporté
d'ailleurs).

[Yliur]

Le Sat, 24 Jul 2021 19:39:29 +0000, Stephane Tougard a écrit :

> On 2021-07-24, Stéphane CARPENTIER <s...@fiat-linux.fr> wrote:
>> Normalement, je dirais que tu peux toujours éviter d'utiliser une
>> boucle en utilisant la récursivité. Le problème de la récursivité,
>> c'est que ça peut être très gourmand en mémoire.

Ça entasse surtout des données dans la pile, là où on stocke les
variables locales et les adresses de retour des fonctions (pour mémoriser
l'endroit auquel il faut reprendre une fois qu'on a terminé d'exécuter
une fonction appelée). L'espace alloué à la pile étant limité, un trop
grand nombre d'appels de fonctions imbriqués peut la faire déborder. Il
reste plein de mémoire disponible dans la machine, ce n'est pas le
problème (en tout cas sur des ordinateurs modernes, sur des machines
anciennes je ne sais pas).

On peut rappeler que le tas, par opposition à la pile, est une zone dans
laquelle on alloue des données n'importe où et sans limite de durée
(alors que les données placées sur la pile par une fonction disparaissent
quand la fonction se termine).

Quelques articles trouvés rapidement, si ça vous éclaire :
https://www.journaldunet.fr/web-tech/developpement/1202909-que-sont-
la-pile-stack-et-le-tas-heap/
https://n-pn.fr/t/2431-la-pile-en-assembleur-x86
https://www.fil.univ-lille1.fr/~sedoglav/C/Cours08-2x3.pdf

> D'après ce que j'ai compris, au niveau de la machine, il n'y a pas de
> différence fondamentale entre une fonction récursive et une boucle, les
> deux utilisent les mêmes code en language machine.

Normalement si :
- Une boucle est traduite de manière directe, avec des branchements
("goto").
- Dans le cas d'un appel récursif, le code exécuté entasse bien sur la
pile les variables locales et les adresses de retour (il y a bien
un mécanisme d'appels de fonction dans le code machine, on peut voir
ça dans les articles ci-dessus).

Par contre dans certains cas le compilateur peut traduire un appel
récursif en boucle : si la dernière chose qu'une fonction doit exécuter
est un appel récursif, il n'y a pas besoin de conserver les variables
locales et l'endroit où on se trouvait dans la fonction (puisqu'on n'a
plus rien à y exécuter). Dans ce cas, le compilateur peut générer du code
exécutable sans appel de fonction.

Petit exemple avec la factorielle...
(je vire les cas d'erreur pour simplifier)

Version classique :
(defun factorielle (n)
(if (= n 0)
1
(* n (factorielle (1- n)))))

Version avec accumulateur :
(defun factorielle (n &optional (accumulateur 1))
(if (= n 0)
accumulateur
(factorielle (1- n) (* n accumulateur))))

Dans la deuxième version on voir qu'une fois l'appel récursif terminé il
n'y aura plus rien à faire en revenant à la fonction appelante (rien
d'autre que tout dépiler pour renvoyer le résultat), donc le compilateur
peut éviter d'entasser sur la pile de nouvelles variables locales et
l'adresse de retour et se contenter d'un code similaire à celui d'une
boucle.

En Common Lisp ce n'est pas pas garanti (contrairement à Scheme je
pense), mais en pratique les compilateurs le font en général. Sauf peut-
être dans le cas où on les configure pour le débogage plutôt que pour les
performances, parce qu'on peut préférer garder les appels récursifs dans
la pile pour les traces en cas d'erreur.

> Peut-être ai-je tout faux sur ça.
>
> En attendant, essaye de faire ça sans la récursivité :
>
> (defun parse-j(j s)
> (if (or (not (listp j)) (null j)) ()
> (progn
> (if (and (listp (car j)) (equalp (caar j) (car s)))
> (if (= (length s) 1)
> (car j)
> (parse-j (car j) (cdr s)))
> (parse-j (cdr j) s)))))
>
>
> Ça sert à parser une liste retourné par la fonction decode-json du
> package cl-json.
>
> (parse-j a '(:DATA :XPUB :XPUB :BALANCE)
>
> Ou a est la liste en question et la liste correspond à l'entrée
> recherchée dans cette liste.

En théorie il me semble qu'il est toujours possible de transformer une
boucle en appel récursif et inversement. Pour ce deuxième cas, en général
il faut gérer une pile comme structure de données dans le code et ça peut
être plus ou moins compliqué selon les situations.

On remarque que dans le cas de ton code les appels récursifs sont des
appels terminaux, donc la traduction en boucle ne doit pas être
difficile. Exemple en remplaçant simplement l'appel récursif par une mise
à jour des valeurs locales de j et s (et en passant implicitement à
l'itération suivante). Note : (return ...) sort de la boucle, pas de la
fonction ; ici c'est pareil mais sinon il faudrait utiliser (return-from
parse-j ...)).

(defun parse-j (param-j param-s)
(do ((j param-j)
(s param-s))
(nil)

(if (or (not (listp j))
(null j))

(return ())

(if (and (listp (car j))
(equalp (caar j) (car s)))
(if (= (length s) 1)

(return (car j))
(progn
(setf j (car j))
(setf s (cdr s))))
(progn
(setf j (cdr j))
(setf s s))))))

Il se peut que je n'aie pas compris à quoi sert la fonction, mais j'ai
ces résultats :
- Ce cas me renvoie un résultat :
(parse-j '((:data) :truc) '(:DATA))
- Ces cas ne me renvoient rien :
(parse-j '(:bidule (:machin (:data)) :truc) '(:DATA))
(parse-j '((:d1 :d2) :truc) '(:d1 :d2))
(parse-j '((:d1 :d00) (:d1 :d2) :truc) '(:d1 :d2))

Et dans le code initial, le progn me semble inutile (il ne fait
qu'enfermer un unique if) et le code est mal indenté. Il se peut que ce
ne soit qu'un détail et que la fonction effectue correctement son
traitement, ou bien qu'il s'agisse d'une erreur et que le code ne fasse
pas ce qui est prévu, je ne sais pas.

[Stephane Tougard]

On 2021-07-26, Yliur <yl...@free.fr> wrote:
>
> Version classique :
> (defun factorielle (n)
> (if (= n 0)
> 1
> (* n (factorielle (1- n)))))
>
> Version avec accumulateur :
> (defun factorielle (n &optional (accumulateur 1))
> (if (= n 0)
> accumulateur
> (factorielle (1- n) (* n accumulateur))))
>
> Dans la deuxième version on voir qu'une fois l'appel récursif terminé il
> n'y aura plus rien à faire en revenant à la fonction appelante (rien
> d'autre que tout dépiler pour renvoyer le résultat), donc le compilateur
> peut éviter d'entasser sur la pile de nouvelles variables locales et
> l'adresse de retour et se contenter d'un code similaire à celui d'une
> boucle.

C'est le "tail récursif" ?

Version corrigée de la fonction (ça change rien)

(defun parse-j(j s)
(if (or (not (listp j)) (null j)) ()

(if (and (listp (car j)) (equalp (caar j) (car s)))
(if (= (length s) 1)
(car j)
(parse-j (car j) (cdr s)))
(parse-j (cdr j) s))))

> (defun parse-j (param-j param-s)
> (do ((j param-j)
> (s param-s))
> (nil)
> (if (or (not (listp j))
> (null j))
> (return ())
> (if (and (listp (car j))
> (equalp (caar j) (car s)))
> (if (= (length s) 1)
> (return (car j))
> (progn
> (setf j (car j))
> (setf s (cdr s))))
> (progn
> (setf j (cdr j))
> (setf s s))))))

Ton code fonctionne correctement (testé en cas réèl, les deux
fonctions retournent la même chose sur le même code JSON traité par cl-json).

[Yliur]

Le Mon, 26 Jul 2021 03:00:48 +0000, Stephane Tougard a écrit :

> On 2021-07-26, Yliur <yl...@free.fr> wrote:
>>
>> Version classique :
>> (defun factorielle (n)
>> (if (= n 0)
>> 1
>> (* n (factorielle (1- n)))))
>>
>> Version avec accumulateur :
>> (defun factorielle (n &optional (accumulateur 1))
>> (if (= n 0)
>> accumulateur (factorielle (1- n) (* n accumulateur))))
>>
>> Dans la deuxième version on voir qu'une fois l'appel récursif terminé
>> il n'y aura plus rien à faire en revenant à la fonction appelante (rien
>> d'autre que tout dépiler pour renvoyer le résultat), donc le
>> compilateur peut éviter d'entasser sur la pile de nouvelles variables
>> locales et l'adresse de retour et se contenter d'un code similaire à
>> celui d'une boucle.
>
> C'est le "tail récursif" ?

Oui. En français on trouve les termes « récursion finale/terminale » ou
« appel récursif terminal ». En anglais je connais le terme « tail call
optimization », pour l'optimisation des compilateurs consistant à
transformer ces formes en itérations.

[Stéphane CARPENTIER]

Le 26-07-2021, Yliur <yl...@free.fr> a écrit :
>
> En théorie il me semble qu'il est toujours possible de transformer une
> boucle en appel récursif et inversement.

Oui, c'est aussi ce que j'ai entendu dire. mais :

> Pour ce deuxième cas, en général
> il faut gérer une pile comme structure de données dans le code et ça peut
> être plus ou moins compliqué selon les situations.

Voilà, des fois c'est plus compliqué. Ce qui ne veut pas dire que c'est
impossible. Quand j'étais à la fac, j'avais essayé essayé de programmer la
tour de Hanoï. Je voulais écrite hanoi(N), avec N le nombre de disques, et
je ne m'en sortais pas. Quand quelqu'un m'a dit d'essayer en récursif,
j'ai résolu le problème très vite.

[Stéphane CARPENTIER]

Le 25-07-2021, Stephane Tougard <step...@unices.org> a écrit :
> Je crois n'avoir quasiment fait du
> récursif en Python/Perl (alors que c'est tout à fait supporté
> d'ailleurs).

Pareil. J'ai fait du récursif en Pascal à la fac pour voir que ça
marchait aussi, mais c'est tout. Les seuls programmes récursifs que j'ai
faits sont en lisp (il y a longtemps).