Table

The Table programming language is an esoteric programming language by User:Rdococ. It is a basic data description language extended with a minimal set of features to make it Turing-complete.

Semantics

A table is a set of key-value pairs. Keys are always symbols, while values can be any expression. An expression can be another table, a symbol, an 'index' or an 'update'.

• An 'index' takes a table and a symbol, and if the table has an entry for the symbol, it will produce the corresponding expression. The table may be omitted, in which case the search covers all enclosing tables, inner-to-outer.
• An 'update' takes two tables, producing a new table with the entries from both. The second table overrides the first.

If a recursive table is created, it is considered to have infinite structure rather than cyclical. The 'update' operation applied to such a table will not update self-references.

Execution consists of trying to reduce the program expression into a form where no more reductions can occur, similar to the lambda calculus. 'Index' and 'update' terms should not be reduced if its would-be result could be reduced further.

Syntax

A table is written as a comma-separated list of entries wrapped in braces, and each entry is written as a colon-separated pair.

{
    apples: 1,
    bananas: 1,
    satchel: {
        pies: 1,
        bandages: 2
    },
    currentItem: pies
}

An 'index' operation is written with the table expression on the left and the symbol expression on the right.

[leftOmitted]
[satchel][apples]
[satchel][[currentItem]]

An 'update' operation is written as an ampersand-separated pair.

[satchel] & {unicornHorns: 1}

Precedence order from highest-to-lowest:

• Unary index (omitted left side)
• Binary index
• Update

Parentheses for grouping are fair game.

Examples

Boolean logic

{
    constTrue: {
        true: true,
        false: true
    },
    constFalse: {
        true: false,
        false: false
    },
    id: {
        true: true,
        false: false
    },
    and: {
        true: [id],
        false: [constFalse]
    },
    or: {
        true: [constTrue],
        false: [id]
    }
}

Truth machine

For input, edit the input entry.

{
    input: 0,
    choices: {
        0: {output: 0},
        1: {output: 1, next: [1]},
    },
    output: [choices][[input]]
}[output]

Lambda calculus

A table with a missing 'input' entry & unevaluated output entry works as a lambda.

{id: {output: [input]}, test: ([id] & {input: test})[output]}

This makes Table a Turing-complete language. Here is a translation from the lambda calculus to Table:

LC	Table
\V.E	{V: [input], output: E}
X	[X]
F X	(F & {input: X})[output]