Robbert van Dalen
2013-05-11 21:36:09 UTC
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 that:
1) values may keep a reference to the historical computation(s) that lead has led to themselves. Such history is called a trace.
2) traces (and traces of traces) can be rolled back, for instance when replacing 'historical' values with 'future' values.
3) a trace that is rolled back (and then slightly altered) can be re-evaluated, thus creating a new trace.
Such web of traces most likely resembles a version control system where developers 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 syntax 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 in ordinary spreadsheets) which makes SPREAD non-Turing complete.
And there are no exceptions in SPREAD: every operation and function is completely specified.
So. let me now show you a canonical SPREAD program, to give you a first taste:
1 2 + 3 4 + * => (1 2 + => 3) (3 4 + => 7) * => 21
The first thing to notice is the => symbol. This indicates a step in a trace.
(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 different).
Here is an example:
a'1 2 + 3 4 + * => (a'1 2 + => (a'1 => 1) 2 + => 3) (3 4 + => 7) * => 21
We can replace a'1 with a'5, which causes the above trace (and sub-trace) to roll-back. Replacing is done via the bind operator !
a'1 2 + 3 4 + * [a=5] ! => (a'1 2 + 3 4 + * => (a'1 2 + => (a'1 => 1) 2 + => 3) (3 4 + => 7) * => 21) [a=5] ! => a'5 2 + (3 4 + => 7) *
Still with me? Good!. Notice the last expression in the top-level trace:
a'5 2 + (3 4 + => 7) *
To have this expression yield its final value, we use the evaluate operator $:
a'1 2 + 3 4 + * [a=5] ! $ => (a'1 2 + 3 4 + * [a=5] ! => (a'1 2 + 3 4 + * => (a'1 2 + => (a'1 => 1) 2 + => 3) (3 4 + => 7) * => 21) [a=5] ! => a'5 2 + (3 4 + => 7) *) $ => (a'5 2 + (3 4 + => 7) * => (a'5 2 + => (a'5 => 5) 2 + => 7) (3 4 + => 7) * => 49)
Yes indeed, all these traces become *very* unwieldy. Don't worry, traces can be put in the 'background' if you want.
Notice the value [a=5] which is a SPREAD (multi)map. But before I talk about maps, I first need to introduce 'alternatives':
(also, from now on, I'm going to abbreviate intermediate trace steps with …)
Look at this expression:
{1,2} {3,4} * # => …. => {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} + # => .... => {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-class 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 multiset of expressions. Here are some examples:
simple map:
[a=1,b=2,c=3]
complex (nested) map:
[1={1,2},b=3,2 3 +=a'[2=a,b] 1 *]
Maps can be combined with arithmetical operations, but first we need to introduce arithmetical operations on numbers:
1 2 + => 3 : add
2 4 - => _2 : subtract
3 4 * => 12 : multiply
4 5 | => 5 : maximum
4 _5 & => _5 : minimum
Here are the map equivalents:
[a=1,b={2:2}] [b={3:2,3},c=4] + => [a=1,b={5:2,3},c=4] : add
[a=1,b={2:2}] [b={3:2,3},c=4] - => [a=1,b={_1:2,_1:3},c={_1:4}] : subtract
[a=1,b={2:2}] [b={3:2,3},c=4] * => [b={6:2}] : multiply
[a=1,b={2:2}] [b={3:2,3},c=4] | => [a=1,b={3:2,3},c=4] : maximum
[a=1,b={2:2}] [b={3:2,3},c=4] & => [b={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).
Syntactically, SPREAD separates range values with dots, syntactically ignoring corresponding domain values.
For example:
a.b.c
.. is just efficient syntactic sugar for:
[0=a,1=b,2=c]
The iota operator ~ builds a sequence - starting from 0, ascending up to its argument (minus 1):
10 ~ => 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 operator .:
10 ~ . + => (10 ~ => 0.1.2.3.4.5.6.7.8.9) . + => 45
Each range value in a map can be manipulated with the higher-order foreach operator @:
5 ~ 1 +@ => (5 ~ => 0.1.2.3.4) 1 +@ => 1.2.3.4.5
... foreach and fold combined:
5 ~ 1 +@ . * => (5 ~ 1 +@ => (5 ~ => 0.1.2.3.4) 1 +@ => 1.2.3.4.5) . * => 120
Sequences can be also *concatenated* with the (ironical, infix operator) ;
1.2;3.4.5 => 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 property.
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:
concatenative-***@yahoogroups.com
concatenative-***@yahoogroups.com
<*> To unsubscribe from this group, send an email to:
concatenative-***@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
SPREAD has - what I believe - many properties that might interest you.
SPREADs most exciting property is its 'retroactive' property, which means that:
1) values may keep a reference to the historical computation(s) that lead has led to themselves. Such history is called a trace.
2) traces (and traces of traces) can be rolled back, for instance when replacing 'historical' values with 'future' values.
3) a trace that is rolled back (and then slightly altered) can be re-evaluated, thus creating a new trace.
Such web of traces most likely resembles a version control system where developers 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 syntax 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 in ordinary spreadsheets) which makes SPREAD non-Turing complete.
And there are no exceptions in SPREAD: every operation and function is completely specified.
So. let me now show you a canonical SPREAD program, to give you a first taste:
1 2 + 3 4 + * => (1 2 + => 3) (3 4 + => 7) * => 21
The first thing to notice is the => symbol. This indicates a step in a trace.
(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 different).
Here is an example:
a'1 2 + 3 4 + * => (a'1 2 + => (a'1 => 1) 2 + => 3) (3 4 + => 7) * => 21
We can replace a'1 with a'5, which causes the above trace (and sub-trace) to roll-back. Replacing is done via the bind operator !
a'1 2 + 3 4 + * [a=5] ! => (a'1 2 + 3 4 + * => (a'1 2 + => (a'1 => 1) 2 + => 3) (3 4 + => 7) * => 21) [a=5] ! => a'5 2 + (3 4 + => 7) *
Still with me? Good!. Notice the last expression in the top-level trace:
a'5 2 + (3 4 + => 7) *
To have this expression yield its final value, we use the evaluate operator $:
a'1 2 + 3 4 + * [a=5] ! $ => (a'1 2 + 3 4 + * [a=5] ! => (a'1 2 + 3 4 + * => (a'1 2 + => (a'1 => 1) 2 + => 3) (3 4 + => 7) * => 21) [a=5] ! => a'5 2 + (3 4 + => 7) *) $ => (a'5 2 + (3 4 + => 7) * => (a'5 2 + => (a'5 => 5) 2 + => 7) (3 4 + => 7) * => 49)
Yes indeed, all these traces become *very* unwieldy. Don't worry, traces can be put in the 'background' if you want.
Notice the value [a=5] which is a SPREAD (multi)map. But before I talk about maps, I first need to introduce 'alternatives':
(also, from now on, I'm going to abbreviate intermediate trace steps with …)
Look at this expression:
{1,2} {3,4} * # => …. => {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} + # => .... => {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-class 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 multiset of expressions. Here are some examples:
simple map:
[a=1,b=2,c=3]
complex (nested) map:
[1={1,2},b=3,2 3 +=a'[2=a,b] 1 *]
Maps can be combined with arithmetical operations, but first we need to introduce arithmetical operations on numbers:
1 2 + => 3 : add
2 4 - => _2 : subtract
3 4 * => 12 : multiply
4 5 | => 5 : maximum
4 _5 & => _5 : minimum
Here are the map equivalents:
[a=1,b={2:2}] [b={3:2,3},c=4] + => [a=1,b={5:2,3},c=4] : add
[a=1,b={2:2}] [b={3:2,3},c=4] - => [a=1,b={_1:2,_1:3},c={_1:4}] : subtract
[a=1,b={2:2}] [b={3:2,3},c=4] * => [b={6:2}] : multiply
[a=1,b={2:2}] [b={3:2,3},c=4] | => [a=1,b={3:2,3},c=4] : maximum
[a=1,b={2:2}] [b={3:2,3},c=4] & => [b={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).
Syntactically, SPREAD separates range values with dots, syntactically ignoring corresponding domain values.
For example:
a.b.c
.. is just efficient syntactic sugar for:
[0=a,1=b,2=c]
The iota operator ~ builds a sequence - starting from 0, ascending up to its argument (minus 1):
10 ~ => 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 operator .:
10 ~ . + => (10 ~ => 0.1.2.3.4.5.6.7.8.9) . + => 45
Each range value in a map can be manipulated with the higher-order foreach operator @:
5 ~ 1 +@ => (5 ~ => 0.1.2.3.4) 1 +@ => 1.2.3.4.5
... foreach and fold combined:
5 ~ 1 +@ . * => (5 ~ 1 +@ => (5 ~ => 0.1.2.3.4) 1 +@ => 1.2.3.4.5) . * => 120
Sequences can be also *concatenated* with the (ironical, infix operator) ;
1.2;3.4.5 => 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 property.
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:
concatenative-***@yahoogroups.com
concatenative-***@yahoogroups.com
<*> To unsubscribe from this group, send an email to:
concatenative-***@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/