Smartboxes
Smartboxes is an esoteric programming language that takes the idea that functions are the same as lookup tables to the logical conclusion.
The name is based on Alan Kay's comment that all a language needs is smart boxes that hold other smart boxes.
A function is a (potential infinite) set of mappings from key->value.
(Pure Prolog can be thought of as a mapping from key->key.)
Syntax
<map> ::= "{}" | "{" <clauses> "}"
<clauses> ::= <clause> | <clause> <separator> <clauses>
<separator> ::= " " | ","
<clause> ::= <key> [":-" <predicates> ";"] ["->" <body>]
<key> ::= <literal>
<predicates> ::= <key> | <key> <separator> <predicates>
<body> ::= <literal>
<literal> ::= anything that is made up of solely letters and numbers
<lookup> ::= <map> "." <key>
I borrowed the syntax for maps from Connection Machine Lisp's xappings
maps
A map is an unordered set of ordered pairs, each ordered pair has an key and a value which can be any kind of object But the keys have to be distinct.
{yertle->turtle horton->elephant}
If there is no value, the value is the same as the key.
{ball->red orange grass->green black}
is the same as
{ball->red orange->orange grass->green black->black}
vectors
a vector is a map where the keys are consecutive integers starting with zero. We can abbreviate it by writing its values in order surrounded by brackets.
<vector> ::= "[]" | "[" <bodies> "]"
<bodies> ::= <body> | <body> <separator> <bodies>
<map> ::= "{}" | "{" <clauses> "}" | <vector>
{1->on 2->pop 0->hop}
may be written as
[hop on pop]
retrieval
We can retrieve the values with dot notation.
{green->ugly blue->beautiful}.green
=> ugly
We can also make some keys depend on the existence of other keys
{sunbathe:-sunny,warm;->cocobeach, sunny cold}.sunbathe
=> nil
{sunbathe:-sunny,warm;->cocobeach sunny warm}.sunbathe
=>cocobeach
infinite maps
This is all depressingly finite. If we want to abstract over values we're going to need variables.
<variable> ::= "_" <literal> <key> ::= <variable> | <literal> | <map> <body> ::= <key> | <lookup> (this means that keys can be arbitrarily nested and contain the results of looking up a function)
There are three sorts of infinite maps.
A constant map has the same value for every index.
{_a->3}
The universal map is the set of all objects.
{_a}
A lazy map uses a function to compute a value given the index.
{_z->sqrt._z}
Infinite maps may have a finite number of explicit exceptions.
{1->5 10->3 100->3.14 _x->0}
unification
unification is used for lookups, allowing for programming in logic
{[bird dove] [flies _x]:-[bird _x];}.[flies _a]
=> [flies dove]
evaluation
Mathematical functions like difference and product take a vector of values.
{[fact 0]->1 [fact _X]->product.[_X [fact difference.[_X 1]]]}.[fact 3]
=> 6
As execution proceeds the first form is looked up in its static environment and then the next form is looked up in the result, this continues until there are no more forms to look up. I haven't fully worked out how to properly indicate which environment various forms are looked up in, and when.
Examples
If we define an integer as a linked-list Church numeral, basic arithmetic can be implemented(if inefficiently).
{[same _Y _Y]
[dec 0]->err
[dec _X] :-
[same _self {
[_acc [1 _acc]]->_acc
[_acc _X]-> _self.[[1 _acc] _X]
}];-> _self.[0 _X]
}.[dec [1 [1 [1 0]]]]
=> [1 [1 0]]