[stack] SPREAD: another kid on the block

Let me introduce a new (concatenative?) programming language called SPREAD.
SPREAD has - what I believe - many properties that might interest you.

SPREADs most exciting property is its 'retroactive' property, which means t=
hat:

1) values may keep a reference to the historical computation(s) that lead h=
as led to themselves. Such history is called a trace.
2) traces (and traces of traces) can be rolled back, for instance when repl=
acing 'historical' values with 'future' values.
3) a trace that is rolled back (and then slightly altered) can be re-evalua=
ted, thus creating a new trace.

Such web of traces most likely resembles a version control system where dev=
elopers create branches, do merges, etc.
In SPREAD, such version control is 'built-in'.

But SPREAD has more desirable (programming language) properties:

1) Spreadsheet-like
2) Immutable
3) Declarative
4) Incremental
5) Reversible
6) Scaleable
7) Exception-less
8) Total (non-Turing complete)
9) Appealing (syntax)

For me personally, postfix format is the most appealing and efficient synta=
x of all (I hope you all agree!). That's why every SPREAD expression is in =
postfix format (with one exception: concatenation).

SPREAD is also a purely functional language, which means that *everything* =
is immutable (it needs to be, otherwise it wouldn't have version control)
You also cannot create infinite structures and loops in SPREAD (just like i=
n ordinary spreadsheets) which makes SPREAD non-Turing complete.
And there are no exceptions in SPREAD: every operation and function is comp=
letely specified.=20

So. let me now show you a canonical SPREAD program, to give you a first tas=
te:

1 2 + 3 4 + * =3D> (1 2 + =3D> 3) (3 4 + =3D> 7) * =3D> 21

The first thing to notice is the =3D> symbol. This indicates a step in a tr=
ace.
(Remember, every value may carry a trace).

In SPREAD, each value can be 'labeled' with another value. Labels give rise=
 to a very powerful computation model (similar to a lambda calculus, but di=
fferent).
Here is an example:

a'1 2 + 3 4 + * =3D> (a'1 2 + =3D> (a'1 =3D> 1) 2 + =3D> 3) (3 4 + =3D> 7) =
* =3D> 21

We can replace a'1 with a'5, which causes the above trace (and sub-trace) t=
o roll-back. Replacing is done via the bind operator !

a'1 2 + 3 4 + * [a=3D5] ! =3D> (a'1 2 + 3 4 + * =3D> (a'1 2 + =3D> (a'1 =3D=
> 1) 2 + =3D> 3) (3 4 + =3D> 7) * =3D> 21) [a=3D5] ! =3D> a'5 2 + (3 4 + =
=3D> 7) *

Still with me? Good!. Notice the last expression in the top-level trace:

a'5 2 + (3 4 + =3D> 7) *

To have this expression yield its final value, we use the evaluate operator=
 $:

a'1 2 + 3 4 + * [a=3D5] ! $ =3D> (a'1 2 + 3 4 + * [a=3D5] ! =3D> (a'1 2 + 3=
 4 + * =3D> (a'1 2 + =3D> (a'1 =3D> 1) 2 + =3D> 3) (3 4 + =3D> 7) * =3D> 21=
) [a=3D5] ! =3D> a'5 2 + (3 4 + =3D> 7) *) $ =3D> (a'5 2 + (3 4 + =3D> 7) *=
 =3D> (a'5 2 + =3D> (a'5 =3D> 5) 2 + =3D> 7) (3 4 + =3D> 7) * =3D> 49)

Yes indeed, all these traces become *very* unwieldy. Don't worry, traces ca=
n be put in the 'background' if you want.

Notice the value [a=3D5] which is a SPREAD (multi)map. But before I talk ab=
out maps, I first need to introduce 'alternatives':
(also, from now on, I'm going to abbreviate intermediate trace steps with =
=85)

Look at this expression:=20
{1,2} {3,4} * # =3D> =85. =3D> {3,4,6,8}

It says: multiplying {1 or 2} with {3 or 4} gives {3 or 4 or 6 or 8}. Here =
is another one:
{1,2} {3,4} + # =3D> .... =3D> {4,2:5,6}

.. or, adding {1 or 2} with {3 or 4} gives {3 or 4 or 4 or 6}.

So, SPREAD allows you to program with 'alternatives' (multisets) as first-c=
lass values.
Also notice the wipe # operator, but more about that in a follow-up post.

The multiset is the basis of a multimap, which just maps expressions to a m=
ultiset of expressions. Here are some examples:

simple map:
[a=3D1,b=3D2,c=3D3]

complex (nested) map:
[1=3D{1,2},b=3D3,2 3 +=3Da'[2=3Da,b] 1 *]

Maps can be combined with arithmetical operations, but first we need to int=
roduce arithmetical operations on numbers:

1 2 + =3D> 3 : add
2 4 - =3D> _2 : subtract
3 4 * =3D> 12 : multiply
4 5 | =3D> 5 : maximum
4 _5 & =3D> _5 : minimum

Here are the map equivalents:

[a=3D1,b=3D{2:2}] [b=3D{3:2,3},c=3D4] + =3D> [a=3D1,b=3D{5:2,3},c=3D4] : ad=
d
[a=3D1,b=3D{2:2}] [b=3D{3:2,3},c=3D4] - =3D> [a=3D1,b=3D{_1:2,_1:3},c=3D{_1=
:4}] : subtract
[a=3D1,b=3D{2:2}] [b=3D{3:2,3},c=3D4] * =3D> [b=3D{6:2}] : multiply
[a=3D1,b=3D{2:2}] [b=3D{3:2,3},c=3D4] | =3D> [a=3D1,b=3D{3:2,3},c=3D4] : ma=
ximum
[a=3D1,b=3D{2:2}] [b=3D{3:2,3},c=3D4] & =3D> [b=3D{2:2}] : minimum

SPREAD acknowledges the fact that a sequence is just a special kind of map =
with consecutive domain values as integers (starting from 0).=20
Syntactically, SPREAD separates range values with dots, syntactically ignor=
ing corresponding domain values.=20

For example:
a.b.c

.. is just efficient syntactic sugar for:
[0=3Da,1=3Db,2=3Dc]

The iota operator ~ builds a sequence - starting from 0, ascending up to it=
s argument (minus 1):
10 ~ =3D> 0.1.2.3.4.5.6.7.8.9

Range values in a map can be folded into one with the higher-order fold ope=
rator .:
10 ~ . + =3D> (10 ~ =3D> 0.1.2.3.4.5.6.7.8.9) . + =3D> 45

Each range value in a map can be manipulated with the higher-order foreach =
operator @:
5 ~ 1 +@ =3D> (5 ~ =3D> 0.1.2.3.4) 1 +@ =3D> 1.2.3.4.5

... foreach and fold combined:
5 ~ 1 +@ . * =3D> (5 ~ 1 +@ =3D> (5 ~ =3D> 0.1.2.3.4) 1 +@ =3D> 1.2.3.4.5) =
. * =3D> 120

Sequences can be also *concatenated* with the (ironical, infix operator) ;
1.2;3.4.5 =3D> 1.2.3.4.5

-------- I'll stop here ---------

There is much more to show and tell, but I don't want to overload this post=
.
An important topic that still needs coverage is SPREADs declarative propert=
y.

Care to give some comments? Why not give SPREAD a spin yourself?

The interpreter can be found here (you need to enable java in your browser)=
:
http://www.enchiladacode.nl/spread-applet.html

SPREAD THE WORD!

Cheers,
Robbert.




------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/concatenative/join
    (Yahoo! ID required)

<*> To change settings via email:
    [email protected]=20
    [email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/