Piet
# Piet

Piet est un langage de programmation exotique créé par David Morgan-Mar, dont les programmes sont des images matricielles inspirées des travaux du peintre néerlandais Piet Mondrian.

## Fonctionnement

### Constitution des images

Les programmes en Piet sont des images matricielles composées de 18 couleurs auxquelles s'ajoutent le blanc et le noir, comme le résume le tableau suivant :

noir #000000 :

| blanc #FFFFFF ||||||
| - | - | - | - | - | - |
| rouge clair #FFC0C0 | jaune clair #FFFFC0 | vert clair #C0FFC0 | cyan clair #C0FFFF | bleu clair #C0C0FF | magenta clair #FFC0FF |
| rouge #FF0000 | jaune #FFFF00 | vert #00FF00 | cyan #00FFFF | bleu #0000FF | magenta #FF00FF |
| rouge foncé #C00000 | jaune foncé #C0C000 | vert foncé #00C000 | cyan foncé #00C0C0 | bleu foncé #0000C0 | magenta foncé #C000C0 |

Les couleurs autres que le blanc et le noir s'enchaînent dans deux cycles :

* Teinte : rouge → jaune → vert → cyan → bleu → magenta → rouge → ...
* Luminosité : clair → normal → foncé → clair → ...

Par exemple le cyan possède trois teintes de plus que le rouge, et le jaune deux teintes de plus que le magenta. De même une couleur foncée est deux pas de luminosité plus loin qu'une couleur claire, tandis qu'une couleur claire est un pas de luminosité plus loin qu'une couleur foncée.

Les images sont évidemment constituées de pixels comme toutes les images matricielles, mais peuvent être agrandies pour faciliter la lisibilité des détails ou rendre l'image graphiquement plus intéressante. Chaque groupe carré de pixels correspondant à un pixel de l'image originale est alors interprété comme un seul et même pixel que l'on appelle codel pour éviter la confusion. Il est ainsi nécessaire de préciser la taille des codels de l’image utilisée lors de l'exécution du programme.

Un groupe de codels juxtaposés (deux codels positionnés en diagonale ne sont pas considérés comme juxtaposés) de couleur identique constitue un bloc ainsi délimité soit par le bord de l'image soit par des codels d'une autre couleur. Ces blocs peuvent être de n'importe quelle forme, et même posséder des "trous". Le nombre de codels constituant le bloc permet de représenter un entier (mais en aucun cas une instruction).

### Structure de données

Le langage utilise pour le stockage des données une structure en pile (ou stack en anglais) fondé sur le principe LIFO. Cette pile ne contient que des entiers, et il n'y a en théorie pas de limite à sa taille.

### Exécution

L’interpréteur commence l'exécution du programme dans le codel situé en haut à gauche de l'image. Le déplacement de l'interpréteur dans l'image est ensuite géré par un pointeur directionnel (Direction Pointer ou DP en anglais) initialisé vers la droite et pouvant pointer quatre directions (droite, bas, gauche, haut) et un sélectionneur de codel (Codel Chooser ou CC en anglais) initialisé vers la gauche et pouvant prendre deux valeurs (gauche et droite). L'interpréteur suit alors les mêmes règles de déplacement tout au long de l'exécution :

* l'interpréteur détermine, au sein du bloc dans lequel il se trouve, le bord qui est le plus loin dans la direction du DP ;
* l'interpréteur détermine le codel de ce bord qui est le plus loin dans la direction du CC par rapport au sens du DP. Le tableau suivant explicite ce choix du codel :

| DP | CC | Codel choisi |
| - | - | - |
| Droite | Gauche | Extrémité supérieure |
| Droite | Droite | Extrémité inférieure |
| Bas | Gauche | Extrémité droite |
| Bas | Droite | Extrémité gauche |
| Gauche | Gauche | Extrémité inférieure |
| Gauche | Droite | Extrémité supérieure |
| Haut | Gauche | Extrémité gauche |
| Haut | Droite | Extrémité droite |

* l'interpréteur passe alors dans le bloc immédiatement situé après ce codel dans la direction du DP, en exécutant l'instruction correspondant au changement de teinte et de luminosité entre les couleurs des deux blocs, en fonction du tableau suivant :

| | | Changement de luminosité | Changement de luminosité | Changement de luminosité |
| - | - | - | - | - |
| | | +0 | +1 | +2 |
| Changement de teinte | +0 | | push | pop |
| Changement de teinte | +1 | add | subtract | multiply |
| Changement de teinte | +2 | divide | mod | not |
| Changement de teinte | +3 | greater | pointer | switch |
| Changement de teinte | +4 | duplicate | roll | in (nombre) |
| Changement de teinte | +5 | in (caractère) | out (nombre) | out (caractère) |

### Cas particulier

Les blocs de couleur noire et les bords de l'image agissent sur l’interpréteur de façon identique : si ce dernier essaye de passer dans un tel bloc ou à travers un bord, le CC est inversé. S'il s'agit d'un nouvel échec, le DP est tourné dans le sens horaire. Si le CC et le DP reviennent à leur configuration initiale sans que l'interpréteur ait pu se déplacer (ce qui correspond à huit essais), le programme s'arrête.

D'autre part les blocs de couleur blanche représentent des zones ou l'interpréteur n'est jamais arrêté : lorsqu'il sort d'un bloc coloré vers un bloc blanc, il se déplace dans la direction du DP jusqu'à ce qu'il rencontre un bloc coloré, un bloc noir, ou un bord. De plus, sortir d'un bloc blanc vers un autre bloc n'exécutera aucune commande, quel que soit le bloc : c'est ainsi un moyen de changer la couleur actuelle sans exécuter de commande, afin notamment de réaliser des boucles.

### Instructions

Piet possède 17 instructions exécutées en fonction du changement de couleur lors du passage de l'interpréteur d'un bloc à un autre.

| Instruction | Signification |
| - | - |
| push | Empile la valeur du bloc venant d'être quitté |
| pop | Désempile la valeur au sommet de la pile |
| add | Désempile les deux valeurs au sommet de la pile et empile leur somme |
| substract | Désempile les deux valeurs au sommet de la pile et empile la différence de la deuxième moins la première |
| multiply | Désempile les deux valeurs au sommet de la pile et empile leur produit |
| divide | Désempile les deux valeurs au sommet de la pile et empile le quotient de division euclidienne de la deuxième par la première |
| mod | Désempile les deux valeurs au sommet de la pile et empile le reste de la division euclidienne de la deuxième par la première |
| not | Remplace la valeur au sommet de la pile par 1 si elle est nulle, et par 0 sinon |
| greater | Désempile les deux valeurs au sommet de la pile et empile 1 si la deuxième est plus grande que la première ou 0 dans le cas contraire |
| pointer | Désempile la valeur au sommet de la pile et tourne le pointeur directionnel dans le sens horaire autant de fois que la valeur (dans le sens anti-horaire si la valeur est négative) |
| switch | Désempile la valeur au sommet de la pile et inverse le sélectionneur de codel autant de fois que la valeur |
| duplicate | Empile la valeur au sommet de la pile |
| roll | Désempile les deux valeurs au sommet de la pile et "roule" la pile d'une profondeur de la deuxième valeur, autant de fois que la première valeur. |
| in (nombre) | Lit une valeur en tant que nombre et l'empile |
| in (caractère) | Lit une valeur en tant que caractère et l'empile |
| out (nombre) | Désempile la valeur au sommet de la pile et l'affiche en tant que nombre |
| out (caractère) | Désempile la valeur au sommet de la pile et l'affiche en tant que caractère |

## Exemples

Beaucoup de programme créés permettent simplement d'afficher de courtes chaînes de caractères comme "Piet" ou encore le fameux "Hello world!", mais certains permettent d'exécuter des algorithmes relativement simples, comme le calcul des nombres de Fibonacci, la vérification de la primalité d'un entier, le calcul d'une factorielle, ou encore la détermination du plus grand commun diviseur de deux entiers avec l'algorithme d'Euclide.

## Piet et art

### Art abstrait

Certains programmes en Piet peuvent rappeler les œuvres abstraites du peintre néerlandais éponyme Piet Mondrian.

* Composition with Yellow, Blue and Red. Piet Mondrian, 1937-1942, huile sur toile, 72,7 × 69,2 cm, Londres, Tate Modern.
* Composition en rouge, jaune, bleu et noir, Piet Mondrian, 1926, huile sur toile, La Haye, Musée municipal de La Haye

### Pixel art

Malgré les contraintes liées au principe du langage, certains programmeurs écrivent des programmes fonctionnels en leur conférant une certaine qualité esthétique, des formes particulières ou en ajoutant du texte au sein même de l'image matricielle.

## Turing-complétude

Puisqu'il est possible de programmer en Piet un interpréteur de Brainfuck, et que cet autre langage exotique est Turing-complet, Piet est nécessairement lui aussi Turing-complet. Il est donc théoriquement possible d'écrire n'importe quel programme informatique en Piet.

Néanmoins, il n'existe à ce jour pas de preuve formelle directe pour démontrer cette propriété.

