Good news!
The design of the SPREAD programming language has been completed, while the quick-and-dirty implementation is almost done. I've put
a lot of effort into SPREAD's syntax and semantics, and the final result is - to what I believe - a pretty unique language. You may disagree.
But for me the central question is: how should one classify SPREAD?
At first sight, I believe the
array language J resembles SPREAD the most. Firstly, because of J's powerful array operators, and secondly, because of J's terseness and tacitness.
SPREAD: an array language?
But SPREAD has much more to offer than J. It has a more economical
FORTH like postfix syntax; it also has
SCHEME like symbolic manipulation and hygienic 'macros', together with
PROLOG's non-determinism and unification (not resolution). Next to that, SPREAD has
spreadsheet semantics, while remaining a pure functional language. So?
SPREAD: a concatenative language?
SPREAD: a symbolic macro language?
SPREAD: a non-deterministic language?
SPREAD: a functional reactive language?
To good to be true? May be not, because there is a catch:
SPREAD is also a total function language which means that self referential structures cannot be expressed directly in SPREAD (as in pure spreadsheets). Luckily, there is one - subtle - exception to this prohibition of self-referentiality:
A SPREAD number is an infinite map of maps of itself !
With some imagination, SPREAD numbers can be considered as a type of
co-data. However, it's still an open question whether such numbers makes SPREAD
Turing-complete. But more about that later. Still, my gut feeling says SPREAD is not Turing-complete, but that it is still powerful enough to do any meaningful computation.
SPREAD: A non-Turing complete language?
Least but not least, SPREAD keeps and judiciously memoizes all (re)computations. Moreover, traces of computation can be manipulated and queried as first class objects. This
retro-active property alone is what - I believe - really differentiates SPREAD from other programming languages.
SPREAD: a retro-active programming language!
Now that I've more or less settled SPREAD's classification, are
you now ready for this retro-active way of programming? If so, let me pique your interest some more by demonstrating
real SPREAD programs:
Basic arithmetics
add: 1 2 + => 3
multiply: 3 4 * => 12
maximum: 4 5 | => 5
minimum: 4 5 & => 4
negate: 4 - => _4
compound: 1 2 + 3 _1 + * => (1 2 + => 3) (3 _1 + => 2) * => 6
The first thing you'll notice is that each value has a backward 'trace' (the left of =>) that has lead to itself (unless a value is atomic). Traces are first-class in SPREAD and they enable SPREAD to be retro-active.
Alternatively, non-determinacy is achieved via the cartesian combination and operation over multisets. Next to multisets, SPREAD also has first class multimaps (multisets -> multisets) which - just like multisets - can be combined with the same standard arithmetical operators.
Multisets
add: {1,2,3} {2,4} + => {3,4,2:5,6,7}
multiply: {1,2,3} {2,4} * => {2,2:4,6,8,12}
maximum: {1,2,3} {2,4} | => {2:2,3,3:4}
minimum: {1,2,3} {2,4} & => {2:1,3:2,3}
negate: {1,2,_2:3} - => {_1,_2,_2:_3}
compound: {1,2} 3 + 5 * => ({1,2} 3 + => {4,5}) 5 * => {20,24}
(Multi)Maps
add: [a=1,b={2:2}] [b={3:2,3},c=4] + => [a=1,b={5:2,3},c=4]
multiply: [a=1,b={2:2}] [b={3:2,3},c=4] * => [b={6:2}]
maximum: [a=1,b={2:2}] [b={3:2,3},c=4] | => [a=1,b={3:2,3},c=4]
minimum: [a=1,b={2:2}] [b={3:2,3},c=4] & => [b={2:2}]
negate: [b={3:2,3},c=4] - => [b={_3:2,_1:3},c={_1:4}]
alts: {[a=1],[b=1}] [a=2] + => {[a={1,2}],[a=2,b=1]}
Still with me? Good! There is more to come.
Binding Labels
SPREAD defines a label type and a target type, both of which are expressions. A label and its corresponding target can be alternatively interpreted as 'this label is bound to that target'. It is possible for a label to be bound to an empty target which we call an "unbound label". It's the (re)binding of labels with other targets what is the basis of SPREAD's retro-active (and spreadsheet like) computations. More about that later.
bind: [a=x'1 4 +,b=y' 5 *] [x=2,y=3] ! => [a=x'2 4 +,b=y'3 5 *]
Evaluate
Unevaluated expressions in a map can be evaluated ($). This operation allows the precise control over
what and
when to compute something.
eval: [a=x'2 4 +] $ => [a=((x'2 => 2) 4 + => 6)]
Wipe
Optionally, computational traces in a map can be wiped (#) to yield the actual, and most recent value. Effectively, wiping also detaches labels from their targets.
wipe: [a=((x'2 => 2) 4 + => 6),b=(y'2,2)] # => [a=6,b=2]
Sequences
SPREAD acknowledges the fact that a sequence is just a special kind of map with consecutive domain values as integers (starting from 0). Syntactically, SPREAD separates range values with dots, ignoring corresponding domain values. For example:
a.b.c
.. is just efficient syntactic sugar for:
[0=a,1=b,2=c]
add: 1.2.3 4.2 + => {1,4}.{2:2}.3
multiply: 1.2.3 4.2 * => [1=2]
maximum: 1.2.3 4.2 | => 4.2.3
minimum: 1.2.3 4.2 & => 1.2
negate: 1.2.3 - => {_1:1}.{_1:2}.{_1:3}
Sequences (which are ultimately maps) can be concatenated with the aid of the special purpose infix (;) operator. Rephrased as SPREAD's ironical rule:
Every SPREAD operator has postfix syntax, except the concatenation operator, which has infix syntax
Concatenation
concat1: 1.2.3;4.5.6 => 1.2.3.4.5.6
concat2: 0;[a=1,b=2,c=3] => 1.2.3
concat3: [a=b,c=d];[f=h,i=k] => b.d.h.k
The arithmetical operations on multisets and (multi)maps is what makes SPREAD a 'basic' array language. But to make 'arrays' work harder, SPREAD also defines three higher-order operators: fold, runfold and foreach. To emphasise, higher-order operators are different from ordinary operators because they take other operators as an argument.
Folding
The fold operator (%) takes two arguments: a map argument and a binary operator argument. When a fold is evaluated, it folds the binary operator argument over all the range values of the argument map, in sequence:
sum: 1.2.3.4 +% => 10
product: 1.2.3.4 *% => 24
max: 1.2.3.4 |% => 4
min: 1.2.3.4 &% => 1
bind: [a=b'].[b=c'].[c=2] !% => [a=b'(c'2)]
Run-folding
The run-fold operator (@) takes two arguments: a map argument and a binary operator argument. When a run-fold is evaluated, it run-folds the binary operator argument over all the range values of the map argument, in sequence:
sum: 1.2.3.4 +@ => 1.3.6.10
product: 1.2.3.4 *@ => 1.2.6.24
max: 1.2.3.4 |@ => 1.2.3.4
min: 1.2.3.4 &@ => 1.1.1.1
bind: [a=b'].[b=c'].[c=2] !@ => [a=b'].[a=b'(c')].[a=b'(c'2)]
For-each
The for-each operator (/) takes two arguments: a map argument and an unary operator argument. When for-each is evaluated, it applies the unary operator argument over all the range values of the map argument, in sequence:
add1: 1.2.3.4 (1 +)/ => 2.3.4.5
mul2: 1.2.3.4 (2 *)/ => 2.4.6.8
bind: [a=b'].[b=c'].[c=2] !/ => [a=b'(c'2)]
Retro-active
With higher-order operators we can do a lot of fancy stuff. But SPREAD's real fanciness is solely due to its retro-activity - achieved via the re-binding of labels which triggers consecutive automatic evaluation. Here are an example:
react1: [a=(((b'1 => 1) 2 + => 3) (3 4 + =>7) * => 21)] [b=2] ! # =>
[a=(((b'2 => 2) 2 + => 4) (3 4 + =>7) * => 28)] # =>
[a=28]
Back(s)lash
A trace can be recast as a sequence via the back(s)lash(\) operator. This allows an interesting importunity to manipulate traces of computations.
back1: 1 2 + 3 _1 + * \ => (1 2 + => 3) (3 _1 + => 2) * \ => 6 \ =>
(1 2 + 3 _1 + * \).((1 2 + => 3) (3 _1 + => 2) * \).6
Turn
Turning(~) a map turns the domain and range of a map. This may be of use to be able to fold over the domain, for example:
turn1: [a=b,c=d] ~ => [b=a,d=c]
turn2: [a=b,c=b] ~ => [b={a,c}]
turn3: [2=3,4=5] ~ +% => [3=2,5=4] +% => 6
WEIRD, BUT IMPORTANT LAST BITS!
Numbers
A SPREAD number is syntactic sugar for an infinite recursive map, defined as follows:
num1: 4 == [0={4:0}]
Examples:
num2: [0={2:0}] [0={3:0}] + == 2 3 + => 5 == [0={5=0}]
num3: [a=1] 3 + => [0={3:0},a=1]
Unification
Finally, the prolog style unification (?) of two maps is SPREAD's most versatile operator. BUT it is also most difficult to implement correctly and efficiently. Here are some preliminary examples, as I've not completely settled for its semantics:
uni1: 1.2.3.4 1.2.3.4 ? => [0]
uni2: 1.2.3.4 1.x'.3.x' ? => 0
uni3: 1.2.3.4 1.x'.3.y' ? => [[x=3,y=4]]
uni4: x'.2.3 1.y'.z' ? => [[x=1,y=2,z=3]]
uni5: 1.2.3 x';y' ? =>
[[x=0,y=1.2.3],[x=[0=1],y=[1=2,2=3]],[x=1.2,y=[2=3]],[x=1.2.3,y=0]]
What's left?
Unification needs to be further developed. This will be the main topic of my next post. Next to that, there are some additional operators that need a definition (I've still got some ASCII characters left!)
Hopefully you will give me some suggestions to improve the SPREAD language! Care to comment on this post? Please feel free to do so.
(EDIT: The for-each examples were botched - they are now fixed)
Copyright 2013 - Robbert van Dalen
