Table

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

Semantics

A Table program is an expression. An expression can be:

• A table -- a list of key-value entries where the key is a symbol and the value is an expression.
• A symbol -- a sequence of alphanumeric characters.
• An 'index' -- an operation that takes two expressions. The result of the right expression is used to retrieve a value from the result of the left.
• An 'update' -- an operation that takes two tables and creates a new table with the entries from both.

If the left side of an index expression is left empty, the current table and its parents are indexed. This permits the creation of recursive tables. There is also a special key symbol, ^, which resolves an index operation to the table's parent. Index operations cannot be substituted until the corresponding entry exists.

The 'update' operation is a deep copy: updated recursive tables maintain copies of the original in their recursive references. This may result in infinite data structures which must then be generated lazily by the implementation.

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

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
    }
}

An 'index' operation is written either as a dot-separated pair, if the right side is a symbol, or with the classic a[b] notation otherwise.

satchel.pies
satchel[.item]

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

satchel & {unicornHorns: 1}

Precedence order from highest-to-lowest:

• Unary index (if the left side is implicit)
• 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: {r: .v},
    test: (.id&{v: test}).v
}

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

LC	Table
\[var].[expr]	{[var]: .v, r: [expr]}
[var]	.[var]
[func] [expr]	([func]&{v: [expr]}).r