# Toi

**Toi** (the name means nothing) is an esoteric language designed by Oklopol.

## Contents

## Overview

Toi stores all data in sets (of sets of sets of ...). There is a context S (which is a set) that all instructions modify. Execution is Brainfuck-style, left to right, one character instructions, loops. Brackets have to match, otherwise everything's a legal program. There is no set called the error set. The language is suspected to be Turing complete.

## Instructions

Toi has 16 instructions (counting loops as single instructions). In the following "ordinal" refers to the Von Neumann ordinals. Zero is the empty set, and the number n is represented by the set containing the sets corresponding to all numbers below n.

The instructions are the following:

- '<...>' adds the set '<...>' to S. The syntax is usual LISP style, '<<> <<> <>>>' ~ (() (() ())), except they're sets. Also to clarify, '<<>>' adds the set {{}}, not the set {}. Base 10 numbers are interpreted as synonyms for the corresponding ordinal.
- '-<...>' removes the set '<...>' from S. Numbers work as expected here too.
- '(A{B}' is a type of for-each. For each s in S the Toi program A is run with s as the context. If after running A the context of A is a nonempty set, B is run with s as context, and s is replaced in S by the resulting context after running B. Changes to S are done after the for-each.
- '-(A{B}' works like '(A{B}' but the condition is running A results in an empty set.
- '(A[B]' is a while loop. While running A with context S results in a nonempty set, run B with context S, changing S to B's result after running B.
- '-(A[B]' works like '(A[B]', but the condition on A's result is that it's empty.
- '.' prints '.'.
- ':' prints ':'.
- 'e' works like '<>'.
- 'E' does not add the error set to S.
- 'n' prints a newline.
- 'd' prints the set S in the format in which sets are usually input in code. A subset that is an ordinal is printed as a base 10 number corresponding to that ordinal.
- 'r' changes S to {t | t ∈ s, s ∈ S} (this is decrement if S is an ordinal).
- 'a' changes S to S ∪ {t | t ∈ s, s ∈ S}.
- 'u' changes S to {S}.

## Examples

### Printing the naturals

<> ([(<>{.} uan ]

Should be obvious how this works. 'ua' works as the successor function on the ordinal S. '(<>{B}' maps B over all of S.

## Useful algorithms

(Essentially from a discussion on the #esoteric irc channel)

To clear S regardless of its initial value:

([r]

To turn any S except the empty set into {{}}:

({([r]}

To remove every element of S except the empty set (can be used to test if S has the empty set as an element):

({([r]u}-<<>>

An ordered tuple (x,y) of two sets x and y can be implemented as the set

{ {{},{{x}}}, {{y}} }

To turn S into the tuple (S,S):

uuueua-e

To apply A to just the first coordinate of a tuple in S:

( ({([r]u}-<<>> { rrr A uuue }

To apply B to just the second coordinate of a tuple in S:

-( ({([r]u}-<<>> { rr B uu }

To extract the first coordinate of a tuple in S:

-( ({([r]u}-<<>> { ([r] } rrrr

To extract the second coordinate of a tuple in S:

( ({([r]u}-<<>> { ([r] } rrr

Addition: Turn S = (x,y) into S = x+y, for ordinals x and y.

( ( ({([r]u}-<<>> { ([r] } rrr [ ( ({([r]u}-<<>> { rrr ua uuue } -( ({([r]u}-<<>> { rr r uu } ] -( ({([r]u}-<<>> { ([r] } rrrr

## External resources

- Toi interpreter (the interpreter does not currently implement all of Toi, and is definitely not a reference implementation, it is also incredibly space consuming, hopefully the author will fix it tomorrow)