Piet


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
White #FFFFFF
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 ).

Data Structure

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.

Execution

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:
DP CC Selected Codel
Right Left Upper end
Right Lower end
Low Left Right end
Right Left end
Left Left Lower end
Right Upper end
Top Left Left end
Right Right end
  • 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
+0 +1 +2
Changing color +0 Push pop
+1 Add Subtract Multiply
+2 Divide Mod Not
+3 Greater point Switch
+4 Duplicate Roll In (number)
+5 In (character) Out (number) Out (character)

Special case

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.

Instructions

Piet has 17 instructions executed according to the change of color when the interpreter passes from one block to another.

Instruction Meaning
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

Examples

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

Abstract Art

Some programs Piet can recall the abstract works of the painter Dutch eponymous Piet Mondrian .

Pixel art

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.

Turing-completeness

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.

Appendices

Related articles

  • Exotic programming language

Notes and references

  1. ↑ David Morgan-Mar, ” Piet [ archive ] (accessed 20 August 2010 )
  2. ↑ ( en ) ” Brainfuck interpreter in Piet [ archive ] , on www.matthias-ernst.eu
  3. ↑ ( en ) ” Brainfuck is Turing-complete [ archive ] , on www.iwriteiam.nl
  4. ↑ ( en ) ” Piet – Computational class [ archive ] , on esolangs.org