Outils pour utilisateurs

Outils du site


profgra:polonaise

La notation polonaise

Quand les données sont du code (et le code des données)

Cette page a été rédigée dans le cadre d’ateliers aux Journées Nationales de l’APMEP 2017 et 2018.

URL réduite : huit.re/polonaise

L’idée est d’utiliser une syntaxe simple pour créer des langages (de programmation ou non) servant à construire différentes activités. Ce panorama assez large pourra vous inspirer et vous donner envie de créer vous-mêmes un langage, exécutable ou non.

Diaporama

Travaux et instructions

Supposons qu’un travail à effectuer $T$ :

  • nécessite des informations $i_1$, $i_2$… $i_n$ pour être réalisé (on appelle $n$ l’arité de $T$) ;
  • produise une information $i$.

Si c’est possible, ce travail $T$ pourrait de plus :

  • prendre d’autres informations dans l’environnement de celui qui l’effectue ;
  • agir sur l’environnement de celui qui l’effectue.

Remarque : le terme travail est ici un terme générique détaché de tout contexte, qui nous permet de généraliser les notations à beaucoup de sujets, dont les mathématiques et l’algorithmique, mais pas seulement !

Nous avons différentes façons de noter l’exécution de $T$ sur les $i_k$ produisant $i$ :

  • $i = i_1 T i_2$ en notation infixée
  • $i = i_1 i_2 T$ en notation postfixée, ou notation polonaise inversée (RPN in english)
  • $i = T i_1 i_2$ en notation préfixée

Nous appellerons instruction un tel membre de droite, qui décrit « ce qu’il y a ça faire », c’est-à-dire ici exécuter le travail $T$ sur les informations $i_1$ et $i_2$.

Voir l’article Wikipedia pour des détails sur ces notations.

Imbrication des travaux

Supposons que l’on veuille utiliser $i$ (le résultat de $T$ sur $i_1$ et $i_2$) d’une part et une information $i_3$ d’autre part, comme informations pour un travail $T'$, $T'$ produisant une information $i'$.

  • $i' = i T i_3$ en notation infixée
  • $i' = i i_3 T$ en notation postfixée
  • $i' = T i i_3$ en notation préfixée

En écrivant $i$ avec $T$, $i_1$ et $i_2$ :

  • $i' = (i_1 T i_2) T' i_3$ en notation infixée, où le parenthésage est nécessaire s’il n’y a pas d’autre convention
  • $i' = (i_1 i_2 T) i_3 T'$ en notation postfixée
  • $i' = T' (T i_1 i_2) i_3$ en notation préfixée

Dans les deux derniers cas, le parenthésage est nécessaire seulement si on ne connaît pas l’arité des travaux $T$ et $T'$. Néammoins, les parenthèses permettent de faciliter la lecture des instructions.

Attention, le rôle des parenthèses est donc quelque peu différent de leur rôle habituel.

Les instructions seront mises les unes à la suite des autres ou imbriquées pour constituer des programmes.

Pour disposer les instructions « les unes à la suite des autres », ou séquentiellement, il peut suffire de passer à la ligne entre chaque.

Préfixée à parenthèses

Dans toute la suite de l’exposé, nous nous concentrerons sur la dernière notation, la notation préfixée, avec :

  • délimitation des informations, valeurs ou arguments
    • par des espaces et/ou des guillemets,
    • par d’éventuels retours à la ligne par souci de présentation ;
  • parenthèsage systématique
    • des instructions à imbriquer,
    • des instructions séquentielles.

Un exemple :

(Ouvrir "les volets")
(Boire (Verser_dans "tasse" (Chauffer "reste café") "sucre"))

Verser est un travail qui attend comme informations :

  • $i_1$ le récipient
  • $i_2$ un premier ingrédient
  • $i_3$ un éventuel autre ingrédient
  • $i_4$ un éventuel autre ingrédient

L’ordre d’exécution d’un tel programme est détaillé ici. D’autres parcours sont possibles (voir l’article Wikipedia correspondant, en anglais).

parcours en profondeur suffixe

D’autres exemples plus mathématiques :

(Calculer (Somme (Produit 2 3) 1))
(Opposé (Quotient (Diff (Produit a (Racine b)) (Image_par f (Inverse c))) (Carré (somme x y z))))
(Opposé (Quotient (Diff (Produit a (Racine b))
                        (Image_par f (inverse c)))
                  (carre (somme x y z))))

C’est ce qui a été choisi pour Lisp (voir l’article Wikipedia), une famille (très ancienne car plus que cinquantenaire !) de langages de programmation. MicroAlg se réclame de cette famille, et c’est ce langage que nous utiliserons ici.

Nous allons progressivement définir un tel langage à l’aide de MicroAlg, qui est lui-même un tel langage. Parfois MicroAlg aura été légèrement modifié, nous indiquerons pourquoi et comment. Il y aurait de quoi lancer un débat qui rappellerait celui de la poule et de l’œuf, mais gardons ça pour la fin de l’atelier !

Un travail $T$ sera souvent désigné par un verbe, désormais appelé une commande, et les informations $i_k$ seront appelées des valeurs. De plus, les parenthèses seront colorées pour aider à se retrouver dans les imbrications.

exemple avec couleurs

Dans les premiers programmes, les valeurs seront des nombres ou des fragments de texte (notés entre guillemets). De plus, nous utiliserons les commandes prédéfinies :

  • Definir et Retourner qui nous permettent de créer de nouvelles commandes ;
  • Afficher qui permet d’afficher des résultats à l’écran ;
  • Joindre qui concatène ou « met bout à bout » des valeurs (n’existe pas dans MicroAlg mais simplifiera grandement les programmes, sinon il faut utiliser Texte et Concatener).

Le Club des Expressions

Dans cette partie, nous allons créer un mini-langage qui pourrait être le cœur d’un travail sur la structure des expressions mathématiques.

Ajouter

Définissons un premier travail Ajouter, qui concatène les deux informations données (notées a et b) en ajoutant le signe $+$ entre les deux.

À l’exécution de Ajouter, les paramètres formels a et b seront remplacés par les paramètres effectifs (appelés aussi arguments) 2 et 3.

Quel est le rôle de ce programme ?

Ajouter et multiplier

Définissons maintenant deux commandes Ajouter et Multiplier.

A-t-on un problème avec le dernier programme, et si oui comment le résoudre ?

Démonstration du Club

Le Club est en cours de réécriture. Il y a le Club actuel, et le Club futur.

Notez que le Club transige à la convention « un travail est un verbe » en utilisant des noms de commandes comme Somme, Produit

Gestion des lettres

Lors de l’exécution du programme ci-dessus, le langage considère que x est une variable. Comme elle n’a pas été initialisée, elle est considérée comme vide. On s’en sort en affectant une valeur aux lettre que l’on veut pouvoir utiliser, et ceci avec une nouvelle commande: Affecter_a.

Dérivation formelle

Jusqu’ici nous avons écrit des programmes qui manipulaient des informations assez simples : des nombres et des variables. Mais pour dériver une expression telle que :
(Produit (Somme (Produit 2 x) 1) (Somme x 2))
en l’expression :
(Somme (Produit 4 x) 5),
nous allons devoir manipuler du code.

Homoiconicité

Un concept intéressant ici : « code is data ».

Nous ne voulons pas exécuter (Produit (Somme (Produit 2 x) 1) (Somme x 2)) en tant que programme, mais travailler sur (Produit (Somme (Produit 2 x) 1) (Somme x 2)) en tant que valeur, ou encore comme donnée.

C’est encore plus facile de passer de l’un à l’autre quand on utilise un langage homoiconique (voir l’article Wikipedia correspondant). En effet, les structures de données d’un langage homoiconique s’écrivent comme s’écrit le langage lui-même.

Lisp est homoiconique car (elt_1 elt_2 elt_3 ...) est à la fois l’écriture d’une liste de valeurs et l’écriture d’une instruction.

Préparatifs

Voici les nouveautés dont nous allons avoir besoin.

Geler

Geler empêche une expression d’être évaluée comme du code.

Méta-programmation

Instruction permet de fabriquer une instruction à l’aide de l’évaluation d’autres instructions.

Type

Type retourne, suivant le type d’argument passé : "nombre", "variable" ou "expression". C’est une version modifiée par rapport à celle de MicroAlg.

Nature

Nature n’existe pas dans MicroAlg. Cette commande extrait la nature de l’expression, sous forme de texte ("Somme" pour (Somme (Produit 2 x) 1)).

Arguments

Arg1 et Arg2 n’existent pas dans MicroAlg. Ces commandes permettent d’extrairent les informations sur lesquelles travaillent une commande ($i_1$ et $i_2$ dans l’introduction).

Si et Égal

= teste l’égalité entre deux valeurs et Si met en place une structure conditionnelle. Ce sont des commandes de base de MicroAlg.

Dans ce programme, les valeurs "oui" et "non" auraient pu être des résultats donnés par les commandes que nous venons de voir :

Dérivons

Instruction a été renommée Instr.

Reste à simplifier l’écriture !!!

Exercice : Programmer la dérivée d’un quotient.

Annexes

Remerciements

Le code pour modifier MicroAlg

(setq Afficher println) # pb avec Geler
(setq Joindre pack)     # pas besoin pour la dérivée
(de Instruction @
  (rest))
(de Type (expr)
  (cond ((num? expr)  "nombre")
        ((== 'x expr) "variable")
        ((lst? expr)  "expression")
        (T "type inconnu")))
(de Nature (expr)
  (pack (car expr)))
(de Arg1 (expr)
  (cadr expr))
(de Arg2 (expr)
  (caddr expr))

C’est en fait comme ceci que MicroAlg est lui-même programmé (voir microalg.l).

Quelques liens connexes

Je serais intéressé par d’autres liens.

Resterait à traiter

  • Afficher l’arbre de calcul correspondant à une expression
  • Présenter MicroAlg
profgra/polonaise.txt · Dernière modification: 2018/07/19 10:01 par profgra