Tautologos

Tautologos is an esoteric programming language by User:Rdococ and intended inverse to Table. The original pitch was that everything is a function, much like in the lambda calculus. (Apparently, I had not heard of the lambda calculus at the time.)

Table is basically a language for describing recursive data structures extended slightly to make it Turing-complete. Tautologos is sort of its inverse - a language for describing functions first and foremost, with the ability to solve its own halting problem.

Syntax

There is no distinction between statements and expressions. An expression can be:

• A variable name x
• A local variable definition x := y
• A variable assignment x = y
• A function definition fn (x, y, z...) {}
• A function call f(x, y, z...)
• A sequence of expressions expr; expr; expr

Semantics

Undefined variables are treated as global. Control flow is typical, except for the lack of control structures. Function call arguments are evaluated left to right. Variable definitions are not hoisted. A sequence of expressions returns its last value. The only values are functions.

A limited form of pattern matching is available where you can check the extensional equality of two functions by giving them the same parameter names in a function definition. All functions that perform the same side effects and return the same values (or lack thereof) when given the same inputs are considered equal.

If a variable is assigned a function that performs a pattern match, only the cases where those two arguments are equal are reassigned. You can use this to iteratively modify functions.

Examples

Church numerals

0 = fn(f, x) {x};
succ = fn(n) {fn (f, x) {f(n(f, x))}};

Comparing for equality

true = fn(x, y) {x};
false = fn(x, y) {y};
not = fn(b) {b(false, true)};
eq = fn(x, y) {false};
eq = fn(x, x) {true};

Solving the halting problem

forever = fn() {forever()};
halts = fn(program) {not(eq(program, forever))};
paradox = fn() {halts(paradox)(forever, fn() {false})()};

Trivia

• Tautologos is Greek for "repeating what is said."