Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par C.Ret »

zpalm a écrit : 28 oct. 2011 13:25Et voici une version un peu plus condensée:

Code : Tout sélectionner

     10 DEF FNM(N)=VAL("FNM(FNM(N+11))N-10"[1+14*(N>100),14+4*(N>100)])
     20 INPUT N@PRINT FNM(N)
Oui, mais l'utilisation de la fonction VAL n'est pas indispensable, on peut faire en deux lignes avec la structure DEF FN ... END DEF :

Code : Tout sélectionner

10 DEF FNM(N) @ IF N>100 THEN FNM=N-10 ELSE FNM=FNM(FNM(N+11))
20 END DEF @ INPUT N @ DISP N;FNM(N)
C'est donc plus condensé, mais pas autant de cette version qui fonctionne pour tout nombre positif ou négatif, non nécessairement entier:

Code : Tout sélectionner

10 INPUT N @ DISP N;MAX( N-10 , 91+MOD(N,-1) )
L'algorithme est inspiré de la remarque formulée par gege et en tenant compte du comportement de la fonction MOD avec un second argument négatif.
gege a écrit : 27 oct. 2011 01:06EDIT : J'ai l'impression que M(x) vaut :
-- x > 100 => M(x) = x - 10
-- x <= 100 et entier => M(x) = 91
-- x <= 100 et non entier => M(x) = 90 + Frac(x)
C'est beaucoup plus rapide mais moins concis à programmer.
Evidemment, je ne suis pas du même avis que gege concernant l'effort à fournir pour implémenter cet algorithme, surtout sur une machine comme l'HP-71B. Concernant certaines autres machines, je suis de son avis. En particulier, je n'ai pas trouver d'astuce aussi fulgurante pour SHARP PC-E500 alors que je parcourais cet MPO à la recherche d'un bon code pour cette nouvelle acquisition.

Code : Tout sélectionner

10:INPUT N:IF N>100 THEN PRINT N-10 ELSE PRINT 91+N+INT -N
ou plus directement

Code : Tout sélectionner

10:INPUT N:PRINT N-10-(N<=100)*(101+INT -N)
EDIT: Attention de ne pas confondre ces deux versions pour un BASIC "évolués" de SHARP PC-E500 qui renvoient respectivement 0 et -1 lorsque (N<=100) est respectivement faux ou vrai avec les versions adaptées aux SHARP ancestrales au comportement plus serein (enfin c'est vous qui voyez):
MPO 10 McCarthy function 91 - SHARP PC-1211 def-M.gif
MPO 10 McCarthy function 91 - SHARP PC-1211 def-M.gif (17.44 Kio) Vu 2218 fois
MPO 10 McCarthy function 91 - SHARP EL-5150 AER local variable style code.gif
MPO 10 McCarthy function 91 - SHARP EL-5150 AER local variable style code.gif (17.75 Kio) Vu 2218 fois

P.S.: Je sais pas/plus si c'était mieux avant, mais toutes ces versions me donnent bien du mal ! :) :)(Certains ont essayé autrement, ils ont eut des problèmes!)
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par FLISZT »

Un programme avec une variable compilée; il ne fonctonne pas sinon.
La vitesse d'exécution est comparable aux versions (rapides :mrgreen: ) RPL déjà proposées.

Code : Tout sélectionner

<<

     << −> n							@ déclaration de la fonction :  <−Mc
        << n 100 >
	   IF
	   THEN n 10 −
	   ELSE n 11 +
	        <−Mc EVAL
	        <−Mc EVAL
	   END
	>>
     >> 
     −> <−Mc
     
     << <− Mc EVAL						@ appel de la fonction
     >>
     
>>
cgh a écrit : 28 oct. 2011 13:33
zpalm a écrit :Et voici une version un peu plus condensée:

Code : Tout sélectionner

     10 DEF FNM(N)=VAL("FNM(FNM(N+11))N-10"[1+14*(N>100),14+4*(N>100)])
     20 INPUT N@PRINT FNM(N)
Puissant la fonction VAL du HP-71B 8O . En fait, elle évalue la chaîne de caractères et ne contente pas de transformer une chaine représentant un nombre en sa valeur. L'EVAL du RPL n'était pas loin...
EVAL existe en LISP… et je suppose fortement que cette instruction trouve son origine dans ce langage.

Code : Tout sélectionner

>(eval '(+ 1 2))
3
eval force l'évaluation de '(+ 1 2), évaluation bloquée par le guillemet simple appelé quote en LISP.

(eval '(+ 1 2)) est l'équivalent en RPL de : '1 + 2' suivi de EVAL.
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par C.Ret »

FLISZT a écrit : 24 janv. 2023 19:37EVAL existe en LISP… et je suppose fortement que cette instruction trouve son origine dans ce langage.
Tout à fait, et je pense que c'est à cause de cette inspiration mutuelle que certains appellent le RPL (Reverse Polish Lisp). Je n'aime pas cette dénomination car le RPL est par trop d'aspect très diffèrent Lisp, notamment par son fondement procédural. Alors que le Lisp est surtout un language fonctionnel.

Mais, c'est à cause de cet affiliation avec le Lisp, que je ne présente jamais un code RPL avec des guillemets '»' orphelines. Je regroupe toujours les symboles de 'fermeture' en fin de ligne avec du contenu. Car, si je ne me trompe pas, en Lisp, la parenthèse fermante orpheline est strictement interdite.

Ainsi, j'aurai présenté le programme RPL publié ci-dessus de cette façon:

Code : Tout sélectionner

« « → n « IF n 100 > THEN n 10 −                                                @ déclaration de la fonction:  ←Mc
	             ELSE n 11 + ←Mc EVAL ←Mc EVAL END » » → ←Mc « ←Mc EVAL » » @ appel de la fonction
Mais au fait, ce code de FLIST, ne serait-il pas un plagiat du code de CGH que l'on trouve sur la première page ?
Je suis un peu déçu, je m'attendais à ce que FLISZT produise quelque chose de plus personnel ou à défaut, une évolution vers l'idée proposée par Gilles59 mais sans pour autant utiliser une fonction utilisateur. Tiens ! Le RPL n'est pas que procédural, autre point commun au Lisp, le RPL s'exploite aussi par programmation fonctionnelle :)
Gilles59 a écrit : 26 oct. 2011 13:17

Code : Tout sélectionner

« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » 'M' STO
(Qui marche très bien sur HP 28, 48 et 50)

Après tout, il s'agit d'optimiser et de faire plus court (je me permets de vous rappeler qu'il s'agit ici d'un MPO). En douze ans, même les moins rapides d'entre nous auraient pu éventuellement trouver un peu de temps pour y arriver.

Je m'attendais à quelque chose de concis, un peu comme:

Code : Tout sélectionner

« 100   OVER   <
  «   10   -   »
  « 11 + Mc Mc »  IFTE »  'Mc'   STO
Il n'y a pas d'EVAL qui trainent, car comme il n'y a pas de variable locale, il n'y a pas besoin de forcer l'évaluation du programme interne qui est global et dont les arguments sont pris simplement et directement dans la pile. Cela n'empêche pas que l'exécution est bien lente surtout pour les nombres inférieurs à 100.

Alternativement, quelque chose de court et surtout très rapide:

Code : Tout sélectionner

«       DUP
         10  -
  SWAP 
    -1  MOD
         91  +  MAX »
                 'MC'  STO
Mais, bon le principe de ces calculs est donné presque à la dernière page de ce, maintenant , très long fil...
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par FLISZT »

C.Ret a écrit : 25 janv. 2023 18:16
FLISZT a écrit : 24 janv. 2023 19:37EVAL existe en LISP… et je suppose fortement que cette instruction trouve son origine dans ce langage.
Mais, c'est à cause de cet affiliation avec le Lisp, que je ne présente jamais un code RPL avec des guillemets '»' orphelines. Je regroupe toujours les symboles de 'fermeture' en fin de ligne avec du contenu. Car, si je ne me trompe pas, en Lisp, la parenthèse fermante orpheline est strictement interdite.
Le Lisp, d'après ce que j'en ai retenu, n'a jamais été normalisé contrairement à ces sucesseurs directs : le Common Lisp ou le Scheme.
Le seul Lisp dont je dispose est un Common Lisp GNU sous Linux.

Pour ce qui est de la parenthèse orpheline, je ne sais pas trop. J'ai donc ouvert une fenêtre système sur mon portable et lancé "clisp".
.
CLISP.png
CLISP.png (43.97 Kio) Vu 2139 fois
Apparemment, une parenthèse fermante isolée en début de ligne ne pose (ici… ) pas de problème.
C.Ret a écrit : 25 janv. 2023 18:16 Ainsi, j'aurai présenté le programme RPL publié ci-dessus de cette façon:

Code : Tout sélectionner

« « → n « IF n 100 > THEN n 10 −                                                @ déclaration de la fonction:  ←Mc
	             ELSE n 11 + ←Mc EVAL ←Mc EVAL END » » → ←Mc « ←Mc EVAL » » @ appel de la fonction
En tout cas, cette idée de présentation, ne serait-ce que d'un point de vue visuel, … j'aime bien ! :)

C'est vrai que mon programme ressemble à celui de cgh. Ça vient probablement du fait que tous les deux (mais aussi gege, entre autres, avec son prog pour TI-89) avons écrit un programme qui "colle" à la définition de la fonction.

Je dirais aussi que ça correspond à ma manière de programmer en RPL : je préfère le côté Lisp du RPL à son côté Forth, même si ce dernier peut s'avérer bien pratique.

Mon programme a quand même une différence notable d'avec celui de cgh, c'est l'utilisation d'une variable locale au sein même de la fonction. Comme, de plus, la fonction s'appelle elle-même, cette dernière doit être stockée dans une variable locale compilée.

Bien que peut-être plus complexe en apparence, mon programme avec la valeur 1 prend 1,66 s contre 2,04 s pour celui proposé par cgh.
J'ai écrit une version utilisant la struture test {…} {…} IFTE, mais je ne l'ai pas publiée. Elle ne semblait pas plus rapide ( … moins (!) je viens d'en avoir la confirmation : 1,68 s),

Pour info, la version algébrique prend 20,55 s !! (toujours avec 1)
Gilles59 a écrit : 26 oct. 2011 13:17

Code : Tout sélectionner

« → n 'IFTE(n>100 , n-10 , M(M(n+11)))' » 'M' STO

Dans les MPO d'antant (ceux des magazines) le facteur temps était aussi pris en compte.

Avec la version RPL 100% algébrique (étonnament lente), celles de cgh, de Gilles59 et la tienne (C.Ret) 100% "stack" (1,18 s), il ne doit pas rester beaucoup d'autres possibilités en RPL… faudrait que je me mette au sysRPL. :wink:

La version avec MAX est un peu de la triche dans le sens où ce n'est pas une traduction de la fonction mais une interprétation basée sur les résultats - heureusement qu'il n'y en a que deux… - obtenus avec cette fonction. C'est une lecture "après coup".
Mais bon ça fait une version de plus ! :)
C.Ret a écrit : 25 janv. 2023 18:16 Tout à fait, et je pense que c'est à cause de cette inspiration mutuelle que certains appellent le RPL (Reverse Polish Lisp). Je n'aime pas cette dénomination car le RPL est par trop d'aspect très diffèrent Lisp, notamment par son fondement procédural. Alors que le Lisp est surtout un language fonctionnel.
Selon William C. Wickes, lui-même, RPL veut dire Reverse Polish Lisp. D'autres, comme Charles Patton (Theo dans Les Tontons Flingeurs : « C'est pas ma marque préférée ! » :lol: ) ont parlé de ROM-based Procedural Language.

Les deux explications semblent tenir la route :
- il y a bien du Lisp dans le RPL mais à la mode "reverse" (quoique pas à 100%, notamment au niveau des structures de branchement) ;
- la deuxième signification est liée au fonctionnement interne du RPL (appels de routinesen ROM).

Donc… en même temps ! ;)

PS : mes mesures ont été effectuées sur hp-50g (la noire).

Ce n'est pas facile de chronométrer un programme contenant une fonction qui s'appelle elle-même… :mrgreen:
Je suis donc passé par un autre programme :

Code : Tout sélectionner

<< 
	1					@ n = 1
	TICKS SWAP
	nom_prog_à_chronométrer
	TICKS ROT
	− B→R
	8192 /
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par C.Ret »

FLISZT a écrit : 25 janv. 2023 21:47Apparemment, une parenthèse fermante isolée en début de ligne ne pose (ici… ) pas de problème.
C'est bien que les interpréteurs ne soient pas allergiques aux parenthèses orphelines. Ce n'étaient pas le cas des implémentations que j'ai utilisé, il y a longtemps à la Fac. Mais je me souviens que c'étaient surtout les profs qui se fâchaient quand on ne suivait pas, dans nos copies la bonne pratique.

Par exemple, on trouve toujours les codes Lisp écrt de cette façon :

Code : Tout sélectionner

(defun factorial (n)
    (if (zerop n) 1
        (* n (factorial (1- n)))))
Avec toutes les parenthèses rassemblées à la fin sans tenir compte de leur niveau d'imbrication. Par contre, l'indentation est bien utilisée pour mettre en relief les niveaux d'imbrication.

Moi, j'ai eu une fois zéro au TP Lisp (module 2.1) parce que j'avais présenté ma définition ainsi:

Code : Tout sélectionner

(defun factorial (n)
    (if (zerop n) 1
        (* n (factorial (1- n)))
    )
)

FLISZT a écrit : 25 janv. 2023 21:47En tout cas, cette idée de présentation, ne serait-ce que d'un point de vue visuel, … j'aime bien ! :)
C'est surtout le second code qui a des alignements curieux. C'est parce que le fichier texte ne donne pas autant d'information que la présentation graphique:
MPO 10 McCarthy function 91 - Graphical RPL view.gif
MPO 10 McCarthy function 91 - Graphical RPL view.gif (10.31 Kio) Vu 2105 fois
Ou celle plus proche du notepad habituel sur l'écran de nos HP-RPL:
MPO 10 McCarthy function 91 - Virtual RPL view.gif
MPO 10 McCarthy function 91 - Virtual RPL view.gif (5 Kio) Vu 2105 fois
Cette dernière présentation met en évidence la géométrie "Lisp Reversé" du RPL :

Code : Tout sélectionner

((( x 10 -)(( x -1 mod) 91 +) max)
                       (x) 'MC' defun)
au lieu d'un plus classique et moins tordu :

Code : Tout sélectionner

(defun mc91 (x)
   (max (- x 10)(+ (mod x -1) 91)))
On notera cependant, qu'il y a un petit écueil en RPL, l'argument (x) n'est pas explicité (tout au moins ici où aucune structure de variable locale n'et utilisée) mais se fait par le truchement ésotérique des mouvements cachés et mystérieux de la pile.

Code : Tout sélectionner

((( 1: 10 -)(( 1: -1 mod) 91 +) max)
                             'MC' defun)
« DUP 10 -  SWAP -1 MOD 91 +  MAX » 'MC' STO
FLISZT a écrit : 25 janv. 2023 21:47Les deux explications semblent tenir la route :
- il y a bien du Lisp dans le RPL mais à la mode "reverse" (quoique pas à 100%, notamment au niveau des structures de branchement) ;
- la deuxième signification est liée au fonctionnement interne du RPL (appels de routines en ROM).
Une troisième pourrait être que RPL est un acronyme d'APL; certains des aspects ésotériques du RPL et l'unicité des règles d'éxecution quelque soit l'instruction me laisse songeur. D'ailleurs Schraf à pa railleurs sur le forum démontré que l'APL se traduit assez facilement et systématiquement en RPL.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par FLISZT »

Je n'ai jamais suivi de formation en Lisp. Mais il paraît plus logique d'éviter les parenthèses isolées, un peu comme en maths finalement
Ces parenthèses orphelines viennent, probablement, des habitudes que l'on peut prendre après avoir suivi des cours d'algo et autres langages de programmation structurée.

Il 'est vrai aussi que…

Code : Tout sélectionner

IF
THEN
ELSE
END
… se comprend sans peine, alors que…

Code : Tout sélectionner

(…(…)
 (… (…)
  (…)
  (… (… (…)))
 )
)
… on s'y perd plus facilement car rien ne ressemble plus à ")" que ")"…
C.Ret a écrit : 26 janv. 2023 22:14 Moi, j'ai eu une fois zéro au TP Lisp (module 2.1) parce que j'avais présenté ma définition ainsi:

Code : Tout sélectionner

(defun factorial (n)
    (if (zerop n) 1
        (* n (factorial (1- n)))
    )
)
C'était amplement mérité ! :pirat:
Et aussi privé de "quatre heures", j'espère. :lol:
C.Ret a écrit : 26 janv. 2023 22:14 Cette dernière présentation met en évidence la géométrie "Lisp Reversé" du RPL :

Code : Tout sélectionner

((( x 10 -)(( x -1 mod) 91 +) max)
                       (x) 'MC' defun)
au lieu d'un plus classique et moins tordu :

Code : Tout sélectionner

(defun mc91 (x)
   (max (- x 10)(+ (mod x -1) 91))
)
On notera cependant, qu'il y a un petit écueil en RPL, l'argument (x) n'est pas explicité (tout au moins ici où aucune structure de variable locale n'et utilisée) mais se fait par le truchement ésotérique des mouvements cachés et mystérieux de la pile.

Code : Tout sélectionner

((( 1: 10 -)(( 1: -1 mod) 91 +) max)
                             'MC' defun)
« DUP 10 -  SWAP -1 MOD 91 +  MAX » 'MC' STO
Oui, cet écueil est le côté obscur du Forth !
Plus sérieusement (quoique je ne plaisantais qu'à moitié), je me rends à tes arguments, et je vais considérer les << et >> du userRPL différemment maintenant.
C.Ret a écrit : 26 janv. 2023 22:14 Une troisième pourrait être que RPL est un acronyme d'APL; certains des aspects ésotériques du RPL et l'unicité des règles d'éxecution quelque soit l'instruction me laisse songeur. D'ailleurs Schraf à pa railleurs sur le forum démontré que l'APL se traduit assez facilement et systématiquement en RPL.
Et grâce à Norman Brenner…
(que j'ai fait connaître dans "le monde entier"… ) 8) :wink: LOL !
http://www.silicium.org/forum/viewtopic ... 46&t=47276
https://www.hpmuseum.org/forum/thread-1 ... #pid167296


Un MPO très informatif.
Il ne manquerait guère plus qu'un exposé sur le lambda-calcul dans le RPL… :D

Edit : 2 coquilles
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par FLISZT »

Hello,

J'ai essayé d'écrire la Fonction 91 de McCarthy en Python :

Code : Tout sélectionner

>>> def Mc(n):
...     if n > 100:
...             print(n-10)
...     else:
...             print(Mc(Mc(n-11)))
... 
>>> Mc(99)
La syntaxe est à priori correcte.
Toutefois, je rencontre un problème de pile : "maximum recursion depth exceeded in comparison".

Même en modifiant (déraisonnablement) la taille de la pile (qui est de 1000 par défaut)…

Code : Tout sélectionner

>>> import sys
>>> sys.setrecursionlimit(150000)
… le problème reste le même. 8O

Comment fait une hp-28s avec bcp moins de mémoire ?!

Auriez-vous une idée (ou deux) ? :)
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: Misez p'tit, Optimisez - N°10 (hommage à J. McCarthy)

Message par FLISZT »

Version Python fonctionnelle (même sous Python 2.7) :


Code : Tout sélectionner

def Mc(n):
	if n > 100:
		return(n - 10)
	else:
		return(Mc(Mc(n + 11)))
 
print(Mc(99))                  # retourne 91
print(Mc(0))                   # retourne 91
print(Mc(108))                 # retourne 98
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Répondre

Retourner vers « Tous les Pockets »