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: **L**eft, **C**enter, **F**ront, and **R**ight.

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:

- Variables
- Lambda abstraction
- Function application
- Symbols (primitive operations and numeric literals)
- Identity (no-ops)

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)*.

- If
*area(L) = 1*, the Turnstyle evaluates to a**numeric**literal of the integer value*area(F)^area(R)*. Commonly,*area(R)*is 1. - If
*area(L) = 2*, the Turnstyle evaluates to a**primitive function**. In this case,*area(F)*determines the**primitive module**, and*area(R)*determines the**primitive opcode**. See also Primitives. - Symbols with
*area(L) > 2*are reserved for future updates to the specification.

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 | (( reads a number `in_num` k) l)`x` from `stdin` , then evaluates (k x). If `stdin` is closed or an exception occurs, l is evaluated instead. |

2 | (( reads a character `in_char` k) l)`c` from `stdin` , then evaluates (k c). If `stdin` is closed or an exception occurs, l is evaluated instead. |

Opcode | Primitive |
---|---|

1 | (( outputs `out_number` x) k)`x` as a number to `stdout` , and then evaluates k. |

2 | (( outputs `out_char` x) k)`x` as an Unicode character to `stdout` , and then evaluates k. |

Opcode | Primitive |
---|---|

1 | (( evaluates to `num_add` x) y)x + y. |

2 | (( evaluates to `num_sub` x) y)x - y. |

3 | (( evaluates to `num_mul` x) y)x * y. |

4 | (( evaluates to `num_div` x) y)x / y. |

5 | (( evaluates to `num_mod` x) y)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 | (((( evaluates `cmp_eq` x) y) t) f)t if x = y, and f otherwise. |

2 | (((( evaluates `cmp_lt` x) y) t) f)t if x < y, and f otherwise. |

3 | (((( evaluates `cmp_gt` x) y) t) f)t if x > y, and f otherwise. |

4 | (((( evaluates `cmp_lte` x) y) t) f)t if x ≤ y, and f otherwise. |

5 | (((( evaluates `cmp_gte` x) y) t) f)t if x ≥ y, and f otherwise. |

Opcode | Primitive |
---|---|

1 | ( evaluates to the square root of `inexact_sqrt` x)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:

- Evaluating
`((((cpm_eq 1) 2) t) f)`

should not evaluate`t`

. - Evaluating
`((λ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`