Table

The Table programming language is a programming language by User:Rdococ. It was initially conceived as a language where tables are the only value, but there are also symbols.

Semantics

A Table program is an expression. An expression can be a table, a symbol, an index or an update. A table contains a set of key-value pairs called attributes, where both are expressions. A symbol is a name that can be used in table keys.

An index is an operation that, when reduced, indexes into a table with a specific key. If an index is not provided with a table, the current table is looked up. If an attribute cannot be found, the index cannot be reduced. ^ is a special attribute that refers to the table's lexical parent or an updated copy thereof. Reduction is lazy so that if even a reducible attribute refers to its lexical parent, updating the parent will also update references in the attribute.

An update returns one table with attributes replaced by the other. Subtables are copied so that .^ refers to the updated table, and this is done recursively. Recursive tables don't have their recursive references updated; i.e. recursive table structures are treated as if they were infinite trees for the purpose of updating, not as if they're cyclic graphs.

Execution consists of trying to reduce the program expression into a form where no more reductions can occur.

Syntax

Tables are enclosed by {} and contain key-value pairs of the form <key>: <value> separated by ,. An indexing operation is of the form <expr>.<expr> or .<expr>. An update is <expr>&<expr>. A symbol is just a sequence of alphanumeric characters.

Updates have a lower precedence than indexing and binary indexing has a lower precedence than unary indexing.

Examples

Boolean logic

{
    and: {true: {true: true, false: false}, false: {true: false, false: false}},
    or:  {true: {true: true, false: true},  false: {true: true, false: false}},
    not: {true: false, false: true},
}

Truth machine

Replace the 'input' attribute with 0 or 1.

{
    input: 0,
    choices: {0: {output: 0}, 1: {output: 1, next: .^.1}},
    output: .choices.(.input)
}.output

Lambda calculus

Create a table with an output attribute (let's say it's r), with an expression including irreducible attributes. You can apply the table by updating it with new attributes and taking the r attribute of the result.

{
    true: {r: .x},
    false: {r: .y},
    not: {r: (.x & {x: .^.^.false, y: .^.^.true})}
}

Table is thus Turing-complete. Here is a translation from the lambda calculus to Table:

LC	Table
\[var].[expr]	{r: [expr]}
[var]	.[var], .^.[var] etc. depending on level
[func] [expr]	([func] & {x: [expr]}).r