Turnstyle
Turnstyle
The program is encoded as an image. A lossless image format should be used so exact colors are preserved. The use of PNG is recommended because of its wide support and decent compression.
We assume that the reader is somewhat familiar with Lambda Calculus. If you want to learn more about Lambda Calculus, we recommend this video with Graham Hutton or this paper by Raúl Rojas for a good introduction.
Turnstyle programs are evaluated by reading and evaluating expressions from the image. An expression is read using a given position (represented as integral (x, y) coordinates) and heading (right, down, left or up).
The top-level expression of a program is found at the center of the left side of the image (0, floor (image height / 2)), and the initial heading is right.
To read an expression, we consider the Turnstyle shape of the pixels surrounding the current position and facing the current heading. If any of these four pixels lies outside of the image, the program should terminate with an error.
Here is the Turnstyle shape illustrated for all four headings, with the current position indicated by the small circle, and the heading represented using an arrow:
For brevity, in all further illustrations in the specification we will assume we are heading right.
We use the following names to refer to the four pixels that make up the Turnstyle shape: Left, Center, Front, and Right.
Turnstyle programs can use any colors, as long as we can compare two colors for (in-)equality. This gives us 15 unique patterns. Here is a cheatsheet:
The pattern determines the expression that we read evaluate. There are five kinds of expressions:
In Turnstyle, we use colors as variable names. Depending on the pattern, we pick the color of the pixel indicated by the letters LCFR:
This evaluates to the value assigned to the variable. If the variable is unassigned, the program should terminate with an error.
Lambda abstraction evaluates to the anonymous function (λv.e), where the variable v is the color of the pixel indicated with the letters LCR, and e is the expression at the Turnstyle shape indicated by the arrow.
Function application evaluates the expression (f x), where f is the Turnstyle shape indicated by the solid arrow (→) and x is the Turnstyle shape indicated by the dashed arrow (⇢).
If you visualize standing on the image and looking towards the front, the left-hand side of the application will always be to the left of the right-hand side of the application.
Symbols encode literals in the program. We compare the relative areas of the left, front and right pixels.
An area is defined as the number of pixels in a contiguous color region. Pixels of the same color that only touch diagonally are not considered contiguous.
Just like application patterns in Turnstyle, symbols are read in a clockwise direction. The kind of symbol is defined by area(L).
For all other patterns, we evaluate the expression at the Turnstyle indicated by the arrow (→). You can visualize this as following the color of the line.
This is an overview of the different primitive functions and what they do.
| Opcode | Description |
|---|---|
| 1 | ((in_num k) l) reads a number x from stdin, then evaluates (k x). If stdin is closed or an exception occurs, l is evaluated instead. |
| 2 | ((in_char k) l) reads a character c from stdin, then evaluates (k c). If stdin is closed or an exception occurs, l is evaluated instead. |
| Opcode | Primitive |
|---|---|
| 1 | ((out_number x) k) outputs x as a number to stdout, and then evaluates k. |
| 2 | ((out_char x) k) outputs x as an Unicode character to stdout, and then evaluates k. |
| Opcode | Primitive |
|---|---|
| 1 | ((num_add x) y) evaluates to x + y. |
| 2 | ((num_sub x) y) evaluates to x - y. |
| 3 | ((num_mul x) y) evaluates to x * y. |
| 4 | ((num_div x) y) evaluates to x / y. |
| 5 | ((num_mod x) y) evaluates to x % y. Both operands must be integral numbers. |
Turnstyle has no primitive boolean type, and uses Church encoding instead, i.e. true = λxy.x and false = λxy.y.
| Opcode | Primitive |
|---|---|
| 1 | ((((cmp_eq x) y) t) f) evaluates t if x = y, and f otherwise. |
| 2 | ((((cmp_lt x) y) t) f) evaluates t if x < y, and f otherwise. |
| 3 | ((((cmp_gt x) y) t) f) evaluates t if x > y, and f otherwise. |
| 4 | ((((cmp_lte x) y) t) f) evaluates t if x ≤ y, and f otherwise. |
| 5 | ((((cmp_gte x) y) t) f) evaluates t if x ≥ y, and f otherwise. |
| Opcode | Primitive |
|---|---|
| 1 | (inexact_sqrt x) evaluates to the square root of x. |
Turnstyle uses call-by-need evaluation. The interpreter or compiler is free to use other evaluation strategies and optimizations, but the semantics of the primitives must be respected; and effect ordering must be consistent with call-by-need evaluation. For example:
((((cpm_eq 1) 2) t) f) should not evaluate t.((λf. f (f 1)) (out_num 2)) should output 2 twice before
producing exit code 1.The Turnstyle position and direction can be manipulated in a way that it ends up in a previously visited shape. In that case, there is no finite corresponding expression in the lambda calculus.
Turnstyle borrows its numeric precision concepts from Scheme:
Scheme numbers are either exact or inexact. A number is exact if it was written as an exact constant or was derived from exact numbers using only exact operations. A number is inexact if it was written as an inexact constant, if it was derived using inexact ingredients, or if it was derived using inexact operations. Thus inexactness is a contagious property of a number.
The following primitives in Turnstyle are inexact:
inexact_sqrt