Piet is a programming language exotic created by David Morgan-Mar , whose programs are bitmaps inspired by the work of painter Dutch Piet Mondrian 1 .
How it works
Constitution of images
Piet programs are matrix images composed of 18 colors to which are added white and black, as summarized in the following table:
|Black # 000000|
|light red# FFC0C0||pale yellow# FFFFC0||light green# C0FFC0||Light cyan# C0FFFF||light blue# C0C0FF||Light magenta# FFC0FF|
|red# FF0000||yellow# FFFF00||green# 00FF00||Cyan# 00FFFF||blue# 0000FF||magenta# FF00FF|
|dark red# C00000||dark yellow# C0C000||dark green# 00C000||Dark cyan# 00C0C0||dark blue# 0000C0||Dark magenta# C000C0|
The colors other than white and black are linked in two cycles:
- Hue : red → yellow → green → cyan → blue → magenta → red → …
- Brightness : light → normal → dark → light → …
For example cyan has three shades more than red, and yellow two shades more than magenta. Similarly a dark color is two steps of brightness farther than a light color, while a light color is a brightness step farther than a dark color.
The images are obviously made up of pixels like all the matrix images, but can be enlarged to make the details easier to read or make the image graphically more interesting. Each square group of pixels corresponding to a pixel of the original image is then interpreted as one and the same pixel which is called codel to avoid confusion. It is thus necessary to specify the size of the codels of the image used during the execution of the program.
A group of juxtaposed codels (two codels positioned diagonally are not considered juxtaposed) of identical color constitutes a block thus delimited either by the edge of the image or by codels of another color. These blocks can be of any shape, and even possess “holes”. The number of codels constituting the block makes it possible to represent an integer (but in no case an instruction ).
The language uses a stack structure for data storage based on the LIFO principle . This stack contains only integers, and there is in theory no limit to its size.
The interpreter begins executing the program in the codel located at the top left of the image. The moving of the interpreter in the image is then managed by a directional pointer ( Direction Pointer or DP in English) initialized to the right and able to point four directions (right, bottom, left, top) and a codel selector ( Codel Chooser or CC) initialized to the left and can take two values (left and right). The interpreter then follows the same rules of movement throughout the execution:
- The interpreter determines, within the block in which it is located, the edge that is furthest in the direction of the DP.
- The interpreter determines the codel of that edge which is furthest in the direction of the CC with respect to the direction of the DP. The following table explains this choice of codel:
- The interpreter then passes into the block immediately after this codel in the direction of the DP, executing the instruction corresponding to the change in hue and brightness between the colors of the two blocks, according to the following table:
|Change in brightness|
|+5||In (character)||Out (number)||Out (character)|
The black blocks and the edges of the image act on the interpreter identically: if the latter attempts to pass through such a block or across an edge, the CC is reversed. If it is a new failure, the DP is rotated clockwise. If the CC and the DP return to their initial configuration without the interpreter being able to move (corresponding to eight attempts), the program stops.
On the other hand, the blocks of white color represent areas where the interpreter is never stopped: when it leaves a colored block to a white block, it moves in the direction of the DP until, It encounters a colored block, a black block, or an edge. Moreover, to leave a white block to another block will not execute any command, whatever the block: it is thus a means of changing the current color without executing a command, in particular to make loops.
Piet has 17 instructions executed according to the change of color when the interpreter passes from one block to another.
|Push||Stacks the value of the block that has just been left|
|pop||Unsets the value at the top of the stack|
|Add||Unpack the two values at the top of the stack and stack their sum|
|Substance||Unpack the two values at the top of the stack and stack the difference of the second minus the first|
|Multiply||Unpack the two values at the top of the stack and stack their product|
|Divide||Unpack the two values at the top of the stack and stack the Euclidean division quotient of the second by the first|
|Mod||Unpack the two values at the top of the stack and stack the Euclidean division remainder of the second by the first|
|Not||Replaces the value at the top of the stack by 1 if it is zero, and by 0 otherwise|
|Greater||Unpack the two values at the top of the stack and stack 1 if the second is larger than the first or 0 otherwise|
|point||Unsets the value at the top of the stack and rotates the directional pointer clockwise as many times as the value (counterclockwise if the value is negative)|
|Switch||Unsets the value at the top of the stack and inverts the code selector as many times as the value|
|Duplicate||Stacks the value at the top of the stack|
|Roll||Unpack the two values at the top of the stack and “roll” the stack to a depth of the second value, as many times as the first value.|
|In (number)||Reads a value as a number and the stack|
|In (character)||Reads a value as a character and the stack|
|Out (number)||Unsets the value at the top of the stack and displays it as a number|
|Out (character)||Unsets the value at the top of the stack and displays it as a character|
Many just created program can display short strings like “Piet” or the famous ” Hello world! “, But some allow you to execute algorithms relatively simple, as the calculation of Fibonacci numbers , checking The primality of an integer , the calculation of a factorial , or the determination of the greatest common divisor of two integers with the Euclidean algorithm .
Piet and art
Some programs Piet can recall the abstract works of the painter Dutch eponymous Piet Mondrian .
Despite the constraints associated with the principle of language, some programmers write functional programs by giving them a certain aesthetic quality, particular forms or by adding text within the matrix image itself.
Since it is possible to program Piet a Brainfuck 2 interpreter , and this other exotic language is Turing-complete 3 , Piet is necessarily 4 also Turing-complete. It is thus theoretically possible to write any computer program in Piet.
However, to date there is no direct formal evidence to demonstrate this property.
- Exotic programming language
Notes and references
- ↑ David Morgan-Mar, ” Piet ” [ archive ] (accessed 20 August 2010 )
- ↑ ( en ) ” Brainfuck interpreter in Piet ” [ archive ] , on www.matthias-ernst.eu
- ↑ ( en ) ” Brainfuck is Turing-complete ” [ archive ] , on www.iwriteiam.nl
- ↑ ( en ) ” Piet – Computational class ” [ archive ] , on esolangs.org