Parallel computing is concatenative
r_v_dalen — 2006-11-11 14:06:27
In this post I argue that parallel programs are most naturally expressed in a concatenative
language.
We start our discussion by outlining a typical parallel computational strategy:
1 Big units of work are split into smaller units of work.
2 Smaller units are scattered across different threads/nodes.
3 Each thread/node computes a (partial) result in parallel.
4 Partial results are gathered from the threads/nodes.
5 Finally, all partial results are merged into one end result.
To summarise: most parallel and distributed computations are based on a divide and
conquer strategy (via explicit scatter/gather steps).
In array oriented languages (such as APL or K) it is rather easy to harness this kind of
parallelism. For example, one can split an array (operation) into smaller array (operations)
like this:
[1 2 3 4] add [5 6 7 8] ==
([1 2] add [5 6]) join ([3 4] add [7 8])
..
[1 2] add [5 6] => [6 8]
[3 4] add [7 8] => [10 12]
..
[6 8] join [10 12] => [6 8 10 12]
However, a concatenative language such as Joy adds another opportunity for
parallelization: concatenative programs can be can split into smaller ones (at any position)
while their computational results can be concatenated just as easily (to any other
program).
1 2 + 3 4 + + ==
..
1 2 + => 3
3 4 + => 7
..
3 7 + => 10
One may wonder why this is so. One explanation is that concatenative programs and their
(intermediate) results are absolutely indistinguishable. For example, every reduction-step
is also a valid program:
1 2 + 3 4 + +
3 3 4 + +
3 7 +
10
Concatenative programs carry no global state, no bindings and no variables. Also, their
operands and operators are always in very close proximity. This means that computational
semantics can be kept extremely simple and very localised, which is demonstrated by the
following rules:
1) scan for an operator.
2) is the operator monadic?
2.1) is the single element left to the monadic operator, an operand?
2.2) reduce.
3) the operator is dyadic.
3.1 are the two elements left to the dyadic operator, operands?
3.2 reduce.
Of course, these rules would only apply if we restrict the operators to be either monadic
and dyadic. Nevertheless, these rules are more or less shared by all other concatenative
languages.
It can be argued that exactly this 'principle of locality' allows the opportunity for parallel
computation in the first place. For example, in languages where global state previals, it is
usually much harder to find opportunities for parallelization.
A striking observation is that every concatenative program with more than 1 possible
reduction (redex) is a parallel program. In that sense, concatenative languages can be
regarded as the most explicit parallel languages of them all.
I'll wrap up with an example of an Enchilada program. This program will demonstrate how
one can reformulate an implicit parallel array operation into an explicit parallel
concatenative program:
dac == cut max [mul] mul max
...
[1 2 3 4 5 6 7 8] dac ==
[1 2 3 4 5 6 7 8] cut max [mul] mul max
[1 2 3 4] [5 6 7 8] max [mul] mul max
[1 5;2 6; 3 7;4 8] [mul] mul max
[1 5;2 6;3 7;4 8] [mul; mul; mul] max
[1 5 mul;2 6 mul;3 7mul;4 8 mul]
...
[1 2 3 4 5 6 7 8] dac dac dac dac lift ==>
[1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul] lift ==>
1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul
One of the goals of the Enchilada language is to provide a simple, efficient core for doing
parallel and distributed computations. For more info: see
http://my.opera.com/rapido/
blog/ and
http://enchilada.javaforge.com/
Robbert van Dalen — 2006-11-11 14:30:49
[REPOST: YAHOO MAIL DISTROYED MY PREVIOUS POST)
In this post I argue that parallel programs are most
naturally expressed in a concatenative language.
We start our discussion by outlining a typical
parallel computational strategy:
1 Big units of work are split into smaller units of
work.
2 Smaller units are scattered across different
threads/nodes.
3 Each thread/node computes a (partial) result in
parallel.
4 Partial results are gathered from the
threads/nodes.
5 Finally, all partial results are merged into one
end result.
To summarise: most parallel and distributed
computations are based on a divide and conquer
strategy (via explicit scatter/gather steps).
In array oriented languages (such as APL or K) it is
rather easy to harness this kind of parallelism. For
example, one can split an array (operation) into
smaller array (operations) like this:
[1 2 3 4] add [5 6 7 8] ==
([1 2] add [5 6]) join ([3 4] add [7 8])
..
[1 2] add [5 6] => [6 8]
[3 4] add [7 8] => [10 12]
..
[6 8] join [10 12] => [6 8 10 12]
However, a concatenative language such as Joy adds
another opportunity for parallelization: concatenative
programs can be can split into smaller ones (at any
position) while their computational results can be
concatenated just as easily (to any other program).
1 2 + 3 4 + + ==
..
1 2 + => 3
3 4 + => 7
..
3 7 + => 10
One may wonder why this is so. One explanation is that
concatenative programs and their (intermediate)
results are absolutely indistinguishable. For example,
every reduction-step is also a valid program:
1 2 + 3 4 + +
3 3 4 + +
3 7 +
10
Concatenative programs carry no global state, no
bindings and no variables. Also, their operands and
operators are always in very close proximity. This
means that computational semantics can be kept
extremely simple and very localised, which is
demonstrated by the following rules:
1) scan for an operator.
2) is the operator monadic?
2.1) is the single element left to the monadic
operator, an operand?
2.2) reduce.
3) the operator is dyadic.
3.1 are the two elements left to the dyadic operator,
operands?
3.2 reduce.
Of course, these rules would only apply if we restrict
the operators to be either monadic and dyadic.
Nevertheless, these rules are more or less shared by
all other concatenative languages.
It can be argued that exactly this 'principle of
locality' allows the opportunity for parallel
computation in the first place. For example, in
languages where global state previals, it is usually
much harder to find opportunities for parallelization.
A striking observation is that every concatenative
program with more than 1 possible reduction (redex) is
a parallel program. In that sense, concatenative
languages can be regarded as the most explicit
parallel languages of them all.
I'll wrap up with an example of an Enchilada program.
This program will demonstrate how one can reformulate
an implicit parallel array operation into an explicit
parallel concatenative program:
dac == cut max [mul] mul max
...
[1 2 3 4 5 6 7 8] dac ==
[1 2 3 4 5 6 7 8] cut max [mul] mul max
[1 2 3 4] [5 6 7 8] max [mul] mul max
[1 5;2 6; 3 7;4 8] [mul] mul max
[1 5;2 6;3 7;4 8] [mul; mul; mul] max
[1 5 mul;2 6 mul;3 7mul;4 8 mul]
...
[1 2 3 4 5 6 7 8] dac dac dac dac lift ==>
[1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul] lift ==>
1 2 mul 3 4 mul mul 5 6 mul 7 8 mul mul mul
One of the goals of the Enchilada language is to
provide a simple, efficient core for doing parallel
and distributed computations. For more info: see
http://my.opera.com/rapido/blog/ and
http://enchilada.javaforge.com/
____________________________________________________________________________________
Yahoo! Music Unlimited
Access over 1 million songs.
http://music.yahoo.com/unlimited
Magnus Jonsson — 2006-11-11 18:36:00
I would argue the opposite, that the stack model is lousy for
expressing parallel programs because it forces everything to be sequenced
by the programmer. Simple relationships between inputs and outputs are
obscured by stack shuffling.
compare:
length x y z = sqrt (square x + square y + square z)
: length ( x y z -- length )
square rot square rot square rot sqrt ;
How can you parallelize length without essentially abandoning the stack
shuffling representation of your program?
/ Magnus
Magnus Jonsson — 2006-11-11 18:43:23
On Sat, 11 Nov 2006, Magnus Jonsson wrote:
> : length ( x y z -- length )
> square rot square rot square rot sqrt ;
That should of course have been:
: length ( x y z -- length )
square rot square rot square rot + + sqrt ;
or
square swap square + swap square + sqrt
Robbert van Dalen — 2006-11-11 19:35:21
> I would argue the opposite, that the stack model is
> lousy for
> expressing parallel programs because it forces
> everything to be sequenced
> by the programmer. Simple relationships between
> inputs and outputs are
> obscured by stack shuffling.
I think you bring up a fair counter argument. Stack
shuffling is indeed synonymous to explicit sequencing.
Perhaps one could argue that algorithms that need
stack shuffling are inherently sequential. So yes,
such algorithms are more naturally expressed in
applicative form.
My feeling is that most operations don't need more
then two arguments at most.
But when certain operations do need more then two, my
intuitions say that such operations can be split into
smaller operations - and that such operations can be
performed in parallel.
> compare:
>
> length x y z = sqrt (square x + square y + square z)
>
> : length ( x y z -- length )
> square rot square rot square rot sqrt ;
>
> How can you parallelize length without essentially
> abandoning the stack
> shuffling representation of your program?
I would say that the shuffling of three arguments
doesn't give much opportunity for parallelism. But to
take the length of a million operands is another
matter I would say.
In Enchilada parallel squaring can be done as follows
(similar to map)
[a;b;c; ....] [square] mul max =>
[a square; b square; c square; ...]
Then if we define dac as follows:
dac == cut max [add] mul max
and apply dac multiple times we get:
[a square b square add c square d square add add ...]
which obviously can be reduced parallel.
> / Magnus
- Robbert.
____________________________________________________________________________________
Do you Yahoo!?
Everyone is raving about the all-new Yahoo! Mail beta.
http://new.mail.yahoo.com
Christopher Diggins — 2006-11-11 20:52:48
Some forms of concatenative programs are trivially parallelized, while
others aren't. Consider the following definition for length in Cat:
define length { square rot square rot square rot + + sqrt }
While this is hard to parallelize, the following equivalent program:
define length { triple [square] map [+] reduce sqrt }
is trivial to parallelize (map and reduces can be implemented as
concurrent primitives).
The challenge is to automatically transform arbitrary Cat programs
into an easily parallelized form. I am working on the specification
for a sequel to Cat (tentatively called Mutt) which would allow the
definition of macros. Mutt would enable the definition of
transformation rules, so that we can automatically convert Cat
programs into more easily parallelized programs:
The following is a how the neccessary transform might look in in Mutt:
transform {
x:(A:any)->(B:any) rot x rot x rot
y:(B:any B)->(B:any) y
}
-> {
cons cons
[x] map
[y] reduce
}
This form indicates that x is a function from a single type A to
another type B (like sqr which has type (int)->(int)) and y is a
function which consumes two values of type B and produces a single
value of type B (like + which has type (int int)->(int)).
So what I am proposing with Mutt is a language for rewriting typed
concatenative programs.
On 11/11/06, Magnus Jonsson <magnus@...> wrote:
>
>
> I would argue the opposite, that the stack model is lousy for
> expressing parallel programs because it forces everything to be sequenced
> by the programmer. Simple relationships between inputs and outputs are
> obscured by stack shuffling.
>
> compare:
>
> length x y z = sqrt (square x + square y + square z)
>
> : length ( x y z -- length )
> square rot square rot square rot sqrt ;
>
> How can you parallelize length without essentially abandoning the stack
> shuffling representation of your program?
>
> / Magnus
Magnus Jonsson — 2006-11-11 21:12:52
Hi Robert,
On Sat, 11 Nov 2006, Robbert van Dalen wrote:
> But when certain operations do need more then two, my
> intuitions say that such operations can be split into
> smaller operations - and that such operations can be
> performed in parallel.
I doubt that you are lucky enough to get programs like
1 2 + 3 4 + +
in reality, because most functions take some input and probably have to do
a little bit of shuffling to get them into the right place of the
expression.
>> : length ( x y z -- length )
>> square rot square rot square rot sqrt ;
>>
>> How can you parallelize length without essentially
>> abandoning the stack
>> shuffling representation of your program?
>
> I would say that the shuffling of three arguments
> doesn't give much opportunity for parallelism. But to
> take the length of a million operands is another
> matter I would say.
What about:
length x y = sqrt (square x + square y)
: length square swap square + sqrt ;
Even here the parallelism is somewhat obscured but I can see how a clever
compiler could notice this pattern.
I think if the stack model was extended with some a naming mechanism we
could write it more naturally and make the parallelism explicit as well:
: length >y >x x square y square + sqrt ;
or using a pattern matching syntax for function definitions:
: x y length = x square y square + sqrt ;
> In Enchilada parallel squaring can be done as follows
> (similar to map)
>
> [a;b;c; ....] [square] mul max =>
> [a square; b square; c square; ...]
>
> Then if we define dac as follows:
>
> dac == cut max [add] mul max
>
> and apply dac multiple times we get:
>
> [a square b square add c square d square add add ...]
>
> which obviously can be reduced parallel.
Yes, if you can do this most of the time then I think you have a valid
approach. I admit I didn't fully understand the above but the gist seems
to be vector computing.
Best,
Magnus Jonsson
Magnus Jonsson — 2006-11-11 21:29:55
On Sat, 11 Nov 2006, Christopher Diggins wrote:
> While this is hard to parallelize, the following equivalent program:
>
> define length { triple [square] map [+] reduce sqrt }
>
> is trivial to parallelize (map and reduces can be implemented as
> concurrent primitives).
Good point.
> transform {
> x:(A:any)->(B:any) rot x rot x rot
> y:(B:any B)->(B:any) y
> }
> -> {
> cons cons
> [x] map
> [y] reduce
> }
>
> So what I am proposing with Mutt is a language for rewriting typed
> concatenative programs.
You are probably aware of this already, but I'll mention it anyway: This
approach has been used with great success in the haskell community to
express library specific optimizations. The brightest example is
the ByteString library.
http://web.mit.edu/ghc/www/users_guide/rewrite-rules.html
/ Magnus
> On 11/11/06, Magnus Jonsson <magnus@...> wrote:
>>
>>
>> I would argue the opposite, that the stack model is lousy for
>> expressing parallel programs because it forces everything to be sequenced
>> by the programmer. Simple relationships between inputs and outputs are
>> obscured by stack shuffling.
>>
>> compare:
>>
>> length x y z = sqrt (square x + square y + square z)
>>
>> : length ( x y z -- length )
>> square rot square rot square rot sqrt ;
>>
>> How can you parallelize length without essentially abandoning the stack
>> shuffling representation of your program?
>>
>> / Magnus
>
Christopher Diggins — 2006-11-11 21:49:11
On 11/11/06, Magnus Jonsson <
magnus@...> wrote:
> On Sat, 11 Nov 2006, Christopher Diggins wrote:
>
> You are probably aware of this already, but I'll mention it anyway: This
> approach has been used with great success in the haskell community to
> express library specific optimizations. The brightest example is
> the ByteString library.
>
> http://web.mit.edu/ghc/www/users_guide/rewrite-rules.html
>
> / Magnus
I wasn't aware that this was implemented as a language extension in
the GHC compiler. I had only heard second hand discussion, and read a
couple papers about deforestation. This is great news for me since it
lends some academic credibility to the idea of a stand-alone
transformation language. Thanks for sharing the link with me.
I believe a rewriting language like Mutt could also be useful for
writing the actual implementation of a compiler of a concatenative
language by rewriting the program as an arbitrary assembly language. I
also think that concatenative languages are probably significantly
easier to rewrite than languages like Haskell, due to their algebraic
simplicity.
Cheers,
Christopher
Robbert van Dalen — 2006-11-12 20:34:38
Hi Magnus,
> I doubt that you are lucky enough to get programs
> like
>
> 1 2 + 3 4 + +
I would say we wouldn't be so lucky - programmers
should push their programs to such forms, ie. make
parallism more explicit.
> in reality, because most functions take some input
> and probably have to do
> a little bit of shuffling to get them into the right
> place of the
> expression.
Yes, that's true. But just because there can be little
bit of shuffling from time to time I wouldn't cast all
concatenative languages as being opposite of parallel
languages?
> What about:
>
> length x y = sqrt (square x + square y)
>
> : length square swap square + sqrt ;
>
> Even here the parallelism is somewhat obscured but I
> can see how a clever
> compiler could notice this pattern.
Sure, the postfix form:
1 2 + 3 4 + +
can be as easily rewritten to infix:
(1 + 2) + (3 + 4)
which is just as 'parallel' as the postfix version.
I think what give concatenative languages the
advantage is that you can cut any (postfix) expression
anywhere you want without ending up with illegal
expressions.
It's a matter of keeping things simple, i.e. KISS.
>
> I think if the stack model was extended with some a
> naming mechanism we
> could write it more naturally and make the
> parallelism explicit as well:
>
> : length >y >x x square y square + sqrt ;
>
> or using a pattern matching syntax for function
> definitions:
>
> : x y length = x square y square + sqrt ;
>
Although that would be nice, such construct also
forces the introduction of scope, which could destroy
some of the 'principles of locality' that is so
important for parallel computation to work.
> > In Enchilada parallel squaring can be done as
> follows
> > (similar to map)
> >
> > [a;b;c; ....] [square] mul max =>
> > [a square; b square; c square; ...]
> >
> > Then if we define dac as follows:
> >
> > dac == cut max [add] mul max
> >
> > and apply dac multiple times we get:
> >
> > [a square b square add c square d square add add
> ...]
> >
> > which obviously can be reduced parallel.
>
> Yes, if you can do this most of the time then I
> think you have a valid
> approach. I admit I didn't fully understand the
> above but the gist seems
> to be vector computing.
You can safely ignore the Enchilada speak. What I
wanted to say is that the parallization of vector
operations is pretty much straightforward.
What I'm after is *explicit* parallism in the most
dense form. So one of the example programs I've have
given rewrote the following *implicit* parallel vector
program:
[1;2;3;4] [7;8;9;10] add
into the following *explicit* parallel concatenative
program:
1 7 + 2 8 + + 3 9 +4 10 + + +
- Robbert.
____________________________________________________________________________________
Cheap talk?
Check out Yahoo! Messenger's low PC-to-Phone call rates.
http://voice.yahoo.com
Magnus Jonsson — 2006-11-12 21:23:28
On Sun, 12 Nov 2006, Robbert van Dalen wrote:
> given rewrote the following *implicit* parallel vector
> program:
>
> [1;2;3;4] [7;8;9;10] add
>
> into the following *explicit* parallel concatenative
> program:
>
> 1 7 + 2 8 + + 3 9 +4 10 + + +
I see. I'm going to defer my judgement about this :)
/ Magnus Jonsson
William Tanksley, Jr — 2006-11-13 14:58:21
Robbert van Dalen <
r_v_dalen@...> wrote:
> Hi Magnus,
> > I doubt that you are lucky enough to get programs
> > like
> > 1 2 + 3 4 + +
> I would say we wouldn't be so lucky - programmers
> should push their programs to such forms, ie. make
> parallism more explicit.
Before I start, let me emphasise that I'm a concatenative language
fanatic. I have every reason and desire to have a positive opinion
about concatenative languages in every way.
But I just don't see this as an actual feature of concatenative
languages in general. (Enchilada is an exception.)
The fact is that although you _can_ write programs that are capable of
parallelization, the language format itself does not offer you any
help or visual assistance -- good parallel programs do NOT look better
than good serial programs when in concatenative form.
I've always been of the opinion that concatenative languages are good
for optimization, because a well-formatted and tidy concatenative
program contains as few stack shuffles as possible in order to be
readable -- which concidentally means it moves data around as little
as possible, so it's fast and highly cache-local. There's a direct
feedback between a good-looking concatenative program and a
fast-running concatenative program.
But that handy link between looks and behavior doesn't seem to me to
hold for parallelism. I just don't see it.
Now, I could imagine a simple dataflow graph generator for a
concatenative language; such a thing would produce a graph in linear
time (it takes longer to generate a dataflow for an applicative
language), and then could parallelize the execution of the graph. But
again, there's nothing about the language that makes this uniquely
possible or interesting, and especially there's nothing about the
language that makes the programmer able to help with what's going on.
> > in reality, because most functions take some input
> > and probably have to do
> > a little bit of shuffling to get them into the right
> > place of the
> > expression.
> Yes, that's true. But just because there can be little
> bit of shuffling from time to time I wouldn't cast all
> concatenative languages as being opposite of parallel
> languages?
No, but that doesn't mean concatenativity is a natural boon to
parallelism either.
> I think what give concatenative languages the
> advantage is that you can cut any (postfix) expression
> anywhere you want without ending up with illegal
> expressions.
By the way, the ability to cut "anywhere" isn't really a property of
concatenative languages (although I keep thinking it _should_ be,
because it very nearly is); it's a property of "flat" languages.
Concatenativity only promises that you can _join_ any two valid
programs to produce a third valid program.
Anyhow, the problem with cutting and rejoining is that they are serial
operations -- in general, you must know the final result of the first
section in order to begin computation on the second section. There are
specific exceptions, and there's plenty of stack algebra you can do to
find them, but that's not something that "concatenativity" buys you.
> > I think if the stack model was extended with some a
> > naming mechanism we
> > could write it more naturally and make the
> > parallelism explicit as well:
> > : length >y >x x square y square + sqrt ;
> > or using a pattern matching syntax for function
> > definitions:
> > : x y length = x square y square + sqrt ;
> Although that would be nice, such construct also
> forces the introduction of scope, which could destroy
> some of the 'principles of locality' that is so
> important for parallel computation to work.
Yup. It would also destroy concatenativity.
> You can safely ignore the Enchilada speak. What I
> wanted to say is that the parallization of vector
> operations is pretty much straightforward.
Enchilada, and array languages in general, are nice and natural for
parallelism. I'd like to see much more work on array concatenative
languages like X, XY, cK, Enchilada, and so on. By people who
understand array languages well, of course (which rules me out -- I
like 'em, I think I can read 'em, but I'm no expert).
> What I'm after is *explicit* parallism in the most
> dense form. So one of the example programs I've have
> given rewrote the following *implicit* parallel vector
> program:
> [1;2;3;4] [7;8;9;10] add
That looks to me like an explicitly parallel vector program.
> into the following *explicit* parallel concatenative
> program:
> 1 7 + 2 8 + + 3 9 +4 10 + + +
And that looks like a serially written program; the parallelism is at
best implicit, and at that it's implicit because of a property of the
"+" function that not all functions have.
> - Robbert.
-Billy
Robbert van Dalen — 2006-11-13 21:13:09
Hi Billy,
Many, many thanks for putting so much effort in
proving me wrong! I *really* do appreciate it.
> Before I start, let me emphasise that I'm a
> concatenative language
> fanatic. I have every reason and desire to have a
> positive opinion
> about concatenative languages in every way.
Before I start, let me emphasise that I'm *not* a
concatenative language fanatic ;)
But I do like the simplicity and the unusual
properties.
> But I just don't see this as an actual feature of
> concatenative
> languages in general. (Enchilada is an exception.)
I don't feel that Enchilada is an exception - except
that Enchilada's implementation of a concatenative
language is very different.
> The fact is that although you _can_ write programs
> that are capable of
> parallelization, the language format itself does not
> offer you any
> help or visual assistance -- good parallel programs
> do NOT look better
> than good serial programs when in concatenative
> form.
I think I agree - partially. But may be it is just me,
but I can see the inherent parallism when I'm
eyeballing the following expression:
1 2 + 3 4 + +
here is how I go about it:
.... scanning for an operator.....
..found one
1 2 + 3 4 + +
^
is it reducable? yes!
.... scanning for another operator....
....found another
1 2 + 3 4 + +
^ ^
Now we've got two possible reductions. Moreover, it
doesn't matter which of the two we are going to reduce
first.
I think that the former is also the most simple and
explicit form of a parallel program. (but of course,
you and I could have eye-balled that expression
completely different!)
>
> I've always been of the opinion that concatenative
> languages are good
> for optimization, because a well-formatted and tidy
> concatenative
> program contains as few stack shuffles as possible
> in order to be
> readable -- which concidentally means it moves data
> around as little
> as possible, so it's fast and highly cache-local.
> There's a direct
> feedback between a good-looking concatenative
> program and a
> fast-running concatenative program.
I think you are absolutely right: the cache-local
argument is synonymous to the 'principle of locality'
argument.
> But that handy link between looks and behavior
> doesn't seem to me to
> hold for parallelism. I just don't see it.
May be you'll see it when you free your mind from
stacks ;)
But seriously, as Manfred has pointed out before me,
Joy or any concatenative language doesn't need to be
implemented on top of a stack.
> Now, I could imagine a simple dataflow graph
> generator for a
> concatenative language; such a thing would produce a
> graph in linear
> time (it takes longer to generate a dataflow for an
> applicative
> language), and then could parallelize the execution
> of the graph.
Thanks for bringing up the dataflow argument! In fact,
the ability to compile Enchilada into a dataflow
runtime is/was one of the main design goals.
(shameless plug:
http://syrup.sourceforge.net/)
Anyway, concatenative programs can be thought of
serialized dataflow graphs (not quite but close).
Another nice example of the relationship between
dataflow and concatenative languages is Slava's
dataflow visualiser:
http://factorcode.org/dataflow-ui.png
> But
> again, there's nothing about the language that makes
> this uniquely
> possible or interesting, and especially there's
> nothing about the
> language that makes the programmer able to help with
> what's going on.
Programmers would be helped a lot of they just scan
for reducable operators ;)
But yes, it is not a concatenative feature perse. The
following infix expression would do just as well:
(1 + 2) + (3 + 4)
> By the way, the ability to cut "anywhere" isn't
> really a property of
> concatenative languages (although I keep thinking it
> _should_ be,
> because it very nearly is); it's a property of
> "flat" languages.
> Concatenativity only promises that you can _join_
> any two valid
> programs to produce a third valid program.
I tend to disagree. I'm not sure, but I think you run
into a serious contradiction when a language allows
you to concatenate any valid program but not cut them.
But may be my idea of "flatness" is different from
what has been discussed on the concatenative list
previously. For instance, I think Joy is perfectly
flat. For instance, this is a valid Joy program:
1 2 + [3 4 +] i
.. and when we cut it at a random point:
1 2 +
[3 4 +] i
.. and cut further into:
1
2 +
[3 4 +]
i
.. we get 4 perfectly valid programs.
now one would say that the cutting of [3 4 +] cannot
be done and hence Joy is not flat. Syntactically that
is a true statement, but semantically one could split
a quotation without any problem:
[3] [4 +]
> Anyhow, the problem with cutting and rejoining is
> that they are serial
> operations -- in general, you must know the final
> result of the first
> section in order to begin computation on the second
> section.
No, the cutting and joining of expressions isn't
serial - that's an implementation detail. In Enchilada
you can cut an expression of a million operands and
operators non-serially in O(log(million)).
> There are
> specific exceptions, and there's plenty of stack
> algebra you can do to
> find them, but that's not something that
> "concatenativity" buys you.
In Enchilada it is not an exception - but that's an
implementation detail.
> Enchilada, and array languages in general, are nice
> and natural for
> parallelism. I'd like to see much more work on array
> concatenative
> languages like X, XY, cK, Enchilada, and so on. By
> people who
> understand array languages well, of course (which
> rules me out -- I
> like 'em, I think I can read 'em, but I'm no
> expert).
I'm no expert either. Such important stuff should be
left to the popcorn lovers ;)
> > What I'm after is *explicit* parallism in the most
> > dense form. So one of the example programs I've
> have
> > given rewrote the following *implicit* parallel
> vector
> > program:
> > [1;2;3;4] [7;8;9;10] add
>
> That looks to me like an explicitly parallel vector
> program.
Under a certain interpretation, yes.
>
> > into the following *explicit* parallel
> concatenative
> > program:
> > 1 7 + 2 8 + + 3 9 +4 10 + + +
> And that looks like a serially written program; the
> parallelism is at
> best implicit, and at that it's implicit because of
> a property of the
> "+" function that not all functions have.
I hope that my arguments can change that 'serial' view
somewhat.
> -Billy
- Robbert.
____________________________________________________________________________________
Cheap talk?
Check out Yahoo! Messenger's low PC-to-Phone call rates.
http://voice.yahoo.com
Robbert van Dalen — 2006-11-14 09:37:10
William Tanksley, Jr — 2006-11-15 20:54:42
Robbert van Dalen <
r_v_dalen@...> wrote:
> Many, many thanks for putting so much effort in
> proving me wrong! I *really* do appreciate it.
You're very welcome -- but I don't expect to prove you wrong; I just
want to see elaboration of what you mean. Thank you for exploring your
ideas; you've definitely mixed some interesting new things into my
head.
I wouldn't have EVER thought that a tally-based number system would be
interesting; it would "OBVIOUSLY" be too slow. Well, a guy can be
wrong, and it looks like I was wrong.
> > But I just don't see this as an actual feature of
> > concatenative
> > languages in general. (Enchilada is an exception.)
> I don't feel that Enchilada is an exception - except
> that Enchilada's implementation of a concatenative
> language is very different.
Different? It looks like you have the basic features pretty much the
same... Yes, you implement quotations differently, but Forth doesn't
implement quotations _at all_, and it's still concatenative.
Enchilada is still very different from any other concatenative
language, of course. I didn't mean to imply that it was boring :-).
> > The fact is that although you _can_ write programs
> > that are capable of
> > parallelization, the language format itself does not
> > offer you any
> > help or visual assistance -- good parallel programs
> > do NOT look better
> > than good serial programs when in concatenative
> > form.
> I think I agree - partially. But may be it is just me,
> but I can see the inherent parallism when I'm
> eyeballing the following expression:
> 1 2 + 3 4 + +
Hmm... But when basic concatenative properties are applied to it (such
as factoring), the "visible" parallelism goes away. I'm not even sure
it's all that visible -- you can see it because you know very well
certain properties of "+" and numeric literals.
I'm not sure you're wrong, either... I just don't see how to apply
your algorithm in general, nor do I see how the algorithm would make a
non-parallel mistake "feel" wrong, even to an experienced programmer.
(A slow dataflow "feels" wrong because the resulting code gets ugly
with "stack noise".)
> here is how I go about it:
> .... scanning for an operator.....
> ..found one
> 1 2 + 3 4 + +
> ^
> is it reducable? yes!
> .... scanning for another operator....
> ....found another
> 1 2 + 3 4 + +
> ^ ^
Hmm. "Operator" isn't a term the concatenative community uses. Perhaps
we should. How would you define it? I also don't really know what
"reducible" means, although I think it means that a JIT optimizer
could choose whether or not to execute the code right then and there
without any dependancies on stuff that might be out of its sight.
> Now we've got two possible reductions. Moreover, it
> doesn't matter which of the two we are going to reduce
> first.
Makes sense.
> I think that the former is also the most simple and
> explicit form of a parallel program. (but of course,
> you and I could have eye-balled that expression
> completely different!)
It's not explicit, though; it's implicit. An explicitly parallel
program would *explicitly* mark the parallel lines of computation,
showing where the diverge and where they come back together. I seem to
recall that there's a version of the K language that works this way,
and it looks similar to Enchilada.
> > I've always been of the opinion that concatenative
> > languages are good
> > for optimization, because a well-formatted and tidy
> > concatenative
> > program contains as few stack shuffles as possible
> > in order to be
> > readable -- which concidentally means it moves data
> > around as little
> > as possible, so it's fast and highly cache-local.
> > There's a direct
> > feedback between a good-looking concatenative
> > program and a
> > fast-running concatenative program.
> I think you are absolutely right: the cache-local
> argument is synonymous to the 'principle of locality'
> argument.
Right. Interestingly, a stack-based language encourages the programmer
to arrange ALL the data roughly in order of need, so that an optimizer
can distribute the data across multiple levels of cache in what I
imagine would be a pretty simple and effective way.
> > But that handy link between looks and behavior
> > doesn't seem to me to
> > hold for parallelism. I just don't see it.
> May be you'll see it when you free your mind from
> stacks ;)
> But seriously, as Manfred has pointed out before me,
> Joy or any concatenative language doesn't need to be
> implemented on top of a stack.
That's a possible claim. I've seen it made, and I've agreed with the
basic principle. The problem is that I've never seen any
counterexample for its denial. If I told you that "every concatenative
language is a stack language", how would you argue with me?
Actually, take a look at the short name of this group, which appears
at the start of every message title.
So although I very well understand the mathematical properties which
gave rise to our understanding of compositional concatenative
languages, I simply have no idea how they can be done without LIFO
semantics -- i.e. a stack.
Oh, and even the fundamental mathematical property of function
composition is inherently serial.
> > Now, I could imagine a simple dataflow graph
> > generator for a
> > concatenative language; such a thing would produce a
> > graph in linear
> > time (it takes longer to generate a dataflow for an
> > applicative
> > language), and then could parallelize the execution
> > of the graph.
> Thanks for bringing up the dataflow argument! In fact,
> the ability to compile Enchilada into a dataflow
> runtime is/was one of the main design goals.
That's very cool. I definitely do agree that automatic dataflow
annotations would make parallelism easy to see... But I don't see how
or why to make that part of the language.
> (shameless plug: http://syrup.sourceforge.net/)
That's COOL! Thanks!
> Anyway, concatenative programs can be thought of
> serialized dataflow graphs (not quite but close).
I don't see the "not quite" part -- that seems to me to be exactly
what they are.
> Another nice example of the relationship between
> dataflow and concatenative languages is Slava's
> dataflow visualiser:
> http://factorcode.org/dataflow-ui.png
That's something I'd like to see in an editor. I've often thought of
it, but I lack the GUI skill.
> > But
> > again, there's nothing about the language that makes
> > this uniquely
> > possible or interesting, and especially there's
> > nothing about the
> > language that makes the programmer able to help with
> > what's going on.
> Programmers would be helped a lot of they just scan
> for reducable operators ;)
That's a great example of programmers helping themselves, yes. I would
call that a code review.
> But yes, it is not a concatenative feature perse. The
> following infix expression would do just as well:
> (1 + 2) + (3 + 4)
That makes sense to me.
> > By the way, the ability to cut "anywhere" isn't
> > really a property of
> > concatenative languages (although I keep thinking it
> > _should_ be,
> > because it very nearly is); it's a property of
> > "flat" languages.
> > Concatenativity only promises that you can _join_
> > any two valid
> > programs to produce a third valid program.
> I tend to disagree. I'm not sure, but I think you run
> into a serious contradiction when a language allows
> you to concatenate any valid program but not cut them.
It's not a contadiction -- of course you must be able to cut where you
joined. The question is, can you cut ANYWHERE, and if not, what are
the restrictions on where you can cut? If you can't state the
restrictions, or if they're so strong that most places in most
programs can't be cut, the claim of being able to cut programs seems a
lot weaker than it should be.
> But may be my idea of "flatness" is different from
> what has been discussed on the concatenative list
> previously. For instance, I think Joy is perfectly
> flat. For instance, this is a valid Joy program:
Manfred created a dialect of Joy called "floy", a flat Joy, so he
doesn't think Joy is perfectly flat.
> 1 2 + [3 4 +] i
> .. and when we cut it at a random point:
> 1 2 +
> [3 4 +] i
That's not random enough :-). More accurately, there are 8 plausible
cut points in the sequence, and only 4 of them can be cut (assuming
you only try to cut between tokens, which seems right to me). If you
cut inside the quotation, the resulting two programs are not valid --
for example, "1 2 + [" is not a valid program in Joy.
In Joy, that program is 50% flat.
> now one would say that the cutting of [3 4 +] cannot
> be done and hence Joy is not flat. Syntactically that
> is a true statement, but semantically one could split
> a quotation without any problem:
> [3] [4 +]
But that's not semanticly the same, either -- that's not a split
quotation, but rather is two quotations. Even there, you've added two
syntactic things to the function that weren't there before.
Flatness is a syntactic property. If it were semantic, EVERY
(Turing-complete) language would be flat, and it would be boring.
> > Anyhow, the problem with cutting and rejoining is
> > that they are serial
> > operations -- in general, you must know the final
> > result of the first
> > section in order to begin computation on the second
> > section.
> No, the cutting and joining of expressions isn't
> serial - that's an implementation detail. In Enchilada
> you can cut an expression of a million operands and
> operators non-serially in O(log(million)).
The source code is serial; the cutting is serial. You may represent
the source code non-serially (perhaps as a dataflow graph), but that
doesn't change how the programmer sees it until you make that graph
the main language, at which point we're not really talking about a
concatenative language anymore.
> > There are
> > specific exceptions, and there's plenty of stack
> > algebra you can do to
> > find them, but that's not something that
> > "concatenativity" buys you.
> In Enchilada it is not an exception - but that's an
> implementation detail.
I've seen Enchilada, and it definitely isn't flat. (I don't think it
should be; perfect flatness is a painful thing.)
> > Enchilada, and array languages in general, are nice
> > and natural for
> > parallelism. I'd like to see much more work on array
> > concatenative
> > languages like X, XY, cK, Enchilada, and so on. By
> > people who
> > understand array languages well, of course (which
> > rules me out -- I
> > like 'em, I think I can read 'em, but I'm no
> > expert).
> I'm no expert either. Such important stuff should be
> left to the popcorn lovers ;)
I've mentioned K now... Perhaps we'll learn something about how array
languages do it...
> > > What I'm after is *explicit* parallism in the most
> > > dense form. So one of the example programs I've
> > have
> > > given rewrote the following *implicit* parallel
> > vector
> > > program:
> > > [1;2;3;4] [7;8;9;10] add
> > That looks to me like an explicitly parallel vector
> > program.
> Under a certain interpretation, yes.
Explicitness doesn't lend itself to interpretation.
> > > into the following *explicit* parallel
> > concatenative
> > > program:
> > > 1 7 + 2 8 + + 3 9 +4 10 + + +
> > And that looks like a serially written program; the
> > parallelism is at
> > best implicit, and at that it's implicit because of
> > a property of the
> > "+" function that not all functions have.
> I hope that my arguments can change that 'serial' view
> somewhat.
The key word isn't "serial"; it's "explicit" versus "implicit". That
code may have implicit parallelism that a smart compiler or programmer
(or a dumb one) can find; but it doesn't make the parallelism
explicit. The code is still written in a serial manner; there's one
symbol, than the next, then the next, in a series of symbols. Compare
your vector code above -- there's no defined way to read that
serially. Even the dumbest compiler has to impose SOME order on it,
and has to admit that the order is arbitrary.
> - Robbert.
-Billy
John Cowan — 2006-11-15 21:06:42
William Tanksley, Jr scripsit:
> Hmm. "Operator" isn't a term the concatenative community uses. Perhaps
> we should. How would you define it?
I'd define it as "a word which does something other than pushing itself
(or its corresponding value, depending on your ontology) on the stack",
with the usual translation from talk of "the stack" to talk of
tuple-valued functions, if you like.
--
Andrew Watt on Microsoft: John Cowan
Never in the field of human computing
cowan@...
has so much been paid by so many
http://www.ccil.org/~cowan
to so few! (pace Winston Churchill)
William Tanksley, Jr — 2006-11-16 01:20:14
Robbert van Dalen <
r_v_dalen@...> wrote:
> I've just posted on my blog, which hopefully gives
> some more food for thought.
> http://my.opera.com/rapido/blog/
It does indeed. I'm not sure what to think, though; this is very challenging.
The idea he's presenting is called "sticky operators". Read his blog
to see how he presents them.
Although I think they look cool, there's a problem: they're hard to use.
Suppose we have the two sticky functions " '1 '+ "; from what I can
see, that sequence would increment all incoming data. Well, what does
"incoming data" mean in a concatenative language? It can only mean the
entire stack, right? This means that for normal programs, a function
written using sticky functions can never be reused in a different
context -- the sticky function will gum up everything on the stack.
-Billy
stevan apter — 2006-11-16 12:48:26
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, November 15, 2006 3:54 PM
Subject: Re: [stack] Parallel computing is concatenative
> Robbert van Dalen <r_v_dalen@...> wrote:
:
> > May be you'll see it when you free your mind from
> > stacks ;)
> > But seriously, as Manfred has pointed out before me,
> > Joy or any concatenative language doesn't need to be
> > implemented on top of a stack.
>
> That's a possible claim. I've seen it made, and I've agreed with the
> basic principle. The problem is that I've never seen any
> counterexample for its denial. If I told you that "every concatenative
> language is a stack language", how would you argue with me?
by offering an algorithm (or general directions for constructing
an algorithm) which translates concatenative programs into applicative
functions.
for example, consider P
dup + swap pop *
we can prove that P requires at least three items on the stack:
.. x y z dup + swap pop *
.. x y z a + swap pop *
.. x y b swap pop *
.. x b y pop *
.. x b *
.. c
so we know that fP, the applicative function, takes three arguments:
fP:{[x;y;z] .. }
and returns c.
the algorithm should produce a series of functions corresponding to
tokens in P:
f1:{[x;y;z] f2[x;y;z;z]}
f2:{[x;y;z;a] f3[x;y;z+a]}
f3:{[x;y;b] f4[x;b;y]}
f4:{[x;b;y] f5[x;b]}
f5:{[x;b] x*b}
so:
fP:{[x;y;z]f1[x;y;z]}
or:
fP:f5 . f4 . f3 . f2 . f1 .
where 'f .' maps the elements of an incoming sequence to the arguments
of f.
> Actually, take a look at the short name of this group, which appears
> at the start of every message title.
>
> So although I very well understand the mathematical properties which
> gave rise to our understanding of compositional concatenative
> languages, I simply have no idea how they can be done without LIFO
> semantics -- i.e. a stack.
>
> Oh, and even the fundamental mathematical property of function
> composition is inherently serial.
>
> > > Now, I could imagine a simple dataflow graph
> > > generator for a
> > > concatenative language; such a thing would produce a
> > > graph in linear
> > > time (it takes longer to generate a dataflow for an
> > > applicative
> > > language), and then could parallelize the execution
> > > of the graph.
>
> > Thanks for bringing up the dataflow argument! In fact,
> > the ability to compile Enchilada into a dataflow
> > runtime is/was one of the main design goals.
>
> That's very cool. I definitely do agree that automatic dataflow
> annotations would make parallelism easy to see... But I don't see how
> or why to make that part of the language.
>
> > (shameless plug: http://syrup.sourceforge.net/)
>
> That's COOL! Thanks!
>
> > Anyway, concatenative programs can be thought of
> > serialized dataflow graphs (not quite but close).
>
> I don't see the "not quite" part -- that seems to me to be exactly
> what they are.
>
> > Another nice example of the relationship between
> > dataflow and concatenative languages is Slava's
> > dataflow visualiser:
> > http://factorcode.org/dataflow-ui.png
>
> That's something I'd like to see in an editor. I've often thought of
> it, but I lack the GUI skill.
>
> > > But
> > > again, there's nothing about the language that makes
> > > this uniquely
> > > possible or interesting, and especially there's
> > > nothing about the
> > > language that makes the programmer able to help with
> > > what's going on.
>
> > Programmers would be helped a lot of they just scan
> > for reducable operators ;)
>
> That's a great example of programmers helping themselves, yes. I would
> call that a code review.
>
> > But yes, it is not a concatenative feature perse. The
> > following infix expression would do just as well:
> > (1 + 2) + (3 + 4)
>
> That makes sense to me.
>
> > > By the way, the ability to cut "anywhere" isn't
> > > really a property of
> > > concatenative languages (although I keep thinking it
> > > _should_ be,
> > > because it very nearly is); it's a property of
> > > "flat" languages.
> > > Concatenativity only promises that you can _join_
> > > any two valid
> > > programs to produce a third valid program.
>
> > I tend to disagree. I'm not sure, but I think you run
> > into a serious contradiction when a language allows
> > you to concatenate any valid program but not cut them.
>
> It's not a contadiction -- of course you must be able to cut where you
> joined. The question is, can you cut ANYWHERE, and if not, what are
> the restrictions on where you can cut? If you can't state the
> restrictions, or if they're so strong that most places in most
> programs can't be cut, the claim of being able to cut programs seems a
> lot weaker than it should be.
>
> > But may be my idea of "flatness" is different from
> > what has been discussed on the concatenative list
> > previously. For instance, I think Joy is perfectly
> > flat. For instance, this is a valid Joy program:
>
> Manfred created a dialect of Joy called "floy", a flat Joy, so he
> doesn't think Joy is perfectly flat.
>
> > 1 2 + [3 4 +] i
> > .. and when we cut it at a random point:
> > 1 2 +
> > [3 4 +] i
>
> That's not random enough :-). More accurately, there are 8 plausible
> cut points in the sequence, and only 4 of them can be cut (assuming
> you only try to cut between tokens, which seems right to me). If you
> cut inside the quotation, the resulting two programs are not valid --
> for example, "1 2 + [" is not a valid program in Joy.
>
> In Joy, that program is 50% flat.
>
> > now one would say that the cutting of [3 4 +] cannot
> > be done and hence Joy is not flat. Syntactically that
> > is a true statement, but semantically one could split
> > a quotation without any problem:
>
> > [3] [4 +]
>
> But that's not semanticly the same, either -- that's not a split
> quotation, but rather is two quotations. Even there, you've added two
> syntactic things to the function that weren't there before.
>
> Flatness is a syntactic property. If it were semantic, EVERY
> (Turing-complete) language would be flat, and it would be boring.
>
> > > Anyhow, the problem with cutting and rejoining is
> > > that they are serial
> > > operations -- in general, you must know the final
> > > result of the first
> > > section in order to begin computation on the second
> > > section.
>
> > No, the cutting and joining of expressions isn't
> > serial - that's an implementation detail. In Enchilada
> > you can cut an expression of a million operands and
> > operators non-serially in O(log(million)).
>
> The source code is serial; the cutting is serial. You may represent
> the source code non-serially (perhaps as a dataflow graph), but that
> doesn't change how the programmer sees it until you make that graph
> the main language, at which point we're not really talking about a
> concatenative language anymore.
>
> > > There are
> > > specific exceptions, and there's plenty of stack
> > > algebra you can do to
> > > find them, but that's not something that
> > > "concatenativity" buys you.
>
> > In Enchilada it is not an exception - but that's an
> > implementation detail.
>
> I've seen Enchilada, and it definitely isn't flat. (I don't think it
> should be; perfect flatness is a painful thing.)
>
> > > Enchilada, and array languages in general, are nice
> > > and natural for
> > > parallelism. I'd like to see much more work on array
> > > concatenative
> > > languages like X, XY, cK, Enchilada, and so on. By
> > > people who
> > > understand array languages well, of course (which
> > > rules me out -- I
> > > like 'em, I think I can read 'em, but I'm no
> > > expert).
>
> > I'm no expert either. Such important stuff should be
> > left to the popcorn lovers ;)
>
> I've mentioned K now... Perhaps we'll learn something about how array
> languages do it...
>
> > > > What I'm after is *explicit* parallism in the most
> > > > dense form. So one of the example programs I've
> > > have
> > > > given rewrote the following *implicit* parallel
> > > vector
> > > > program:
> > > > [1;2;3;4] [7;8;9;10] add
>
> > > That looks to me like an explicitly parallel vector
> > > program.
>
> > Under a certain interpretation, yes.
>
> Explicitness doesn't lend itself to interpretation.
>
> > > > into the following *explicit* parallel
> > > concatenative
> > > > program:
> > > > 1 7 + 2 8 + + 3 9 +4 10 + + +
> > > And that looks like a serially written program; the
> > > parallelism is at
> > > best implicit, and at that it's implicit because of
> > > a property of the
> > > "+" function that not all functions have.
>
> > I hope that my arguments can change that 'serial' view
> > somewhat.
>
> The key word isn't "serial"; it's "explicit" versus "implicit". That
> code may have implicit parallelism that a smart compiler or programmer
> (or a dumb one) can find; but it doesn't make the parallelism
> explicit. The code is still written in a serial manner; there's one
> symbol, than the next, then the next, in a series of symbols. Compare
> your vector code above -- there's no defined way to read that
> serially. Even the dumbest compiler has to impose SOME order on it,
> and has to admit that the order is arbitrary.
>
> > - Robbert.
>
> -Billy
>
Robbert van Dalen — 2006-11-16 13:05:44
I think *now* I understand why my arguments have not
made any sense:
Enchilada does *not* use a stack model for the
evaluation of expressions, but instead performs
rewritings of expressions (similar to how a functional
VM rewrites graphs). That's why I call evaluations ->
reductions.
So in Joy the following expression:
+ 2 3 + 4 5 +
wouldn't reduce, as where in Enchilada it would:
+ 2 3 + 4 5 +
+ 2 3 + 9
+ 5 9
Also, the re-writing '4 5 +' and '2 3 +' could be done
in parallel.
I'll define a toy concatenative (integer arithmetics)
language to demonstrate how this can be done:
syntax:
Expression := Term*
Term := Operand | Operator
Operand := Number
Operator := "+" | "*" | "/" | "-"
Number := ["1"-"9"] ["0"-"9"]*
auxilary functions/procedures:
- boolean reducable(Expression e)
- Expression reduce(Expression e)
- Expression cat(Expression e1, Expression e2)
- Pair cut(Expression e) (cuts the expression in two)
- Expression left(Pair p)
- Expression right(Pair p)
examples:
reducable(1 2 +) => true
reduce(1 2 +) => 3
split(1 2 + 3 4 +) => [1 2 +;3 4 +]
left([1 2 +;3 4 +]) => 1 2 +
right([1 2 +;3 4 +]) => 3 4 +
now we can formulate the parallel reduction algorithm:
reduce_p(Expression e)
{
if (reducable(e))
{
Pair s = e.cut();
left_r = reduce_p(left(s));
right_r = reduce_p(right(s));
result = cat(left_r, right_r);
return reduce(result);
}
}
where the computation of left_r and right_r can be run
in parallel.
Now in Enchilada, reducable()is O(1) and cat() and
split() are O(log(N). Next to that, no information is
destroyed: everything expression is immutable and all
operations are purely functional.
So if we were to reduce the following enormous
expression with one redex in the middle:
1 2 3 ....... 4999999 5000000 + ..... 9999999
that would cost us O(log(n)*log(n)) time (if my
calculations are correct)
Also, the following 'dataflow' expression can be
processed in parallel like this:
1 2 3 4 5 6 7 8 '+ '+ '+
1 2 3 4 5 6 '+ 15 '+ '+
1 2 3 4 '+ 11 15 '+ '+
1 2 '+ 7 '+ 26 '+
'+ 3 7 '+ 26 '+
'+ '+ 10 26 '+
'+ '+ '+ 36
Now a final question to you: would you call this toy
language flat?
I would call it flat, because I consider every pure
arithmetical postfix expression (without variables) to
be flat. But with your definition of flatness we
should also be allowed to cut numbers, right?
But cutting numbers makes no sense to me, ie.
reduce(12 + -) => 12 + -
ie. doesn't reduce, but:
cut(12 + -) => [1 2; + -] ?
left(cut) => 1 2
right(cut) => + -
reduce(cat(left,right)) => 1 2 + - => 3 => _3
reduces.
- Robbert
--- "William Tanksley, Jr" <
wtanksleyjr@...>
wrote:
> Robbert van Dalen <r_v_dalen@...> wrote:
> > I've just posted on my blog, which hopefully gives
> > some more food for thought.
> > http://my.opera.com/rapido/blog/
>
> It does indeed. I'm not sure what to think, though;
> this is very challenging.
>
> The idea he's presenting is called "sticky
> operators". Read his blog
> to see how he presents them.
>
> Although I think they look cool, there's a problem:
> they're hard to use.
>
> Suppose we have the two sticky functions " '1 '+ ";
> from what I can
> see, that sequence would increment all incoming
> data. Well, what does
> "incoming data" mean in a concatenative language? It
> can only mean the
> entire stack, right? This means that for normal
> programs, a function
> written using sticky functions can never be reused
> in a different
> context -- the sticky function will gum up
> everything on the stack.
>
> -Billy
>
Robbert van Dalen — 2006-11-16 13:26:58
My last post contained some typos:
syntax:
Expression := Term*
Term := Operand | Operator
Operand := Number
Operator := "+" | "*" | "/" | "-"
Number := ["1"-"9"] ["0"-"9"]*
auxilary functions/procedures:
- boolean reducable(Expression e)
- Expression reduce(Expression e)
- Expression cat(Expression e1, Expression e2)
- Pair cut(Expression e) (cuts the expression in two)
- Expression left(Pair p)
- Expression right(Pair p)
examples:
reducable(1 2 +) => true
reduce(1 2 +) => 3
cut(1 2 + 3 4 +) => [1 2 +;3 4 +]
left([1 2 +;3 4 +]) => 1 2 +
right([1 2 +;3 4 +]) => 3 4 +
the parallel reduction algorithm:
reduce_p(Expression e)
{
if (reducable(e))
{
Pair s = cut(e);
left_r = reduce_p(left(s));
right_r = reduce_p(right(s));
result = cat(left_r, right_r);
return reduce(result);
}
}
William Tanksley, Jr — 2006-11-16 14:29:14
stevan apter <
sa@...> wrote:
> > > But seriously, as Manfred has pointed out before me,
> > > Joy or any concatenative language doesn't need to be
> > > implemented on top of a stack.
> > That's a possible claim. I've seen it made, and I've agreed with the
> > basic principle. The problem is that I've never seen any
> > counterexample for its denial. If I told you that "every concatenative
> > language is a stack language", how would you argue with me?
> by offering an algorithm (or general directions for constructing
> an algorithm) which translates concatenative programs into applicative
> functions.
Okay, I see what he meant. I misunderstood, and he's right. Yes, you
can easily translate into applicative continuation-passing style,
removing thereby *all* need for a stack in the underlying
implementation.
I was thinking (incorrectly) that he meant that some other semantics
is possible aside from LIFO when executing concatenated functions.
We've speculated that there might be some type of data object aside
from a LIFO stack that could form the basis of a concatenative
language, but nobody's been able to come up with one. (Yes, we know
there are auxillary structures aside from the data stack, but the
stack is still there.)
-Billy
William Tanksley, Jr — 2006-11-16 15:11:08
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> Enchilada does *not* use a stack model for the
> evaluation of expressions, but instead performs
> rewritings of expressions (similar to how a functional
> VM rewrites graphs). That's why I call evaluations ->
> reductions.
No, I can see that's what you're doing... But you still have a model.
I'm interested to hear if your model isn't a stack model, though.
Intriguing.
> So in Joy the following expression:
> + 2 3 + 4 5 +
> wouldn't reduce, as where in Enchilada it would:
> + 2 3 + 4 5 +
> + 2 3 + 9
> + 5 9
Well, in Joy no expression "reduces" as part of the language; they
either execute or they don't. That expression would execute with no
problem in Joy, and the result would be equivalent to executing the
expression you got after reduction.
> I'll define a toy concatenative (integer arithmetics)
> language to demonstrate how this can be done:
> Now in Enchilada, reducable()is O(1)
How do you determine reducible() without looking at least at every
token, i.e. O(n)? My gut feeling is that it's an O(n*log(n)) problem,
since I'd expect to have to keep a lookup table.
> and cat() and split() are O(log(N).
Obviously you're preloading the source into a tree of some kind.
> Next to that, no information is
> destroyed: everything expression is immutable and all
> operations are purely functional.
Right.
> So if we were to reduce the following enormous
> expression with one redex in the middle:
> 1 2 3 ....... 4999999 5000000 + ..... 9999999
> that would cost us O(log(n)*log(n)) time (if my
> calculations are correct)
*I see* now why you said that (a long time) before.
> Also, the following 'dataflow' expression can be
> processed in parallel like this:
> 1 2 3 4 5 6 7 8 '+ '+ '+
> 1 2 3 4 5 6 '+ 15 '+ '+
> 1 2 3 4 '+ 11 15 '+ '+
> 1 2 '+ 7 '+ 26 '+
> '+ 3 7 '+ 26 '+
> '+ '+ 10 26 '+
> '+ '+ '+ 36
That's no problem; it certainly makes sense to do textual
transformations when possible. And of course, with your engine, it's
natural to do so. But when do the sticky operators *stop* sticking?
It's easy to show with a "toy" problem like that one, but in a real
program with functions calling other functions, do the sticky
operators act on all the results of a called function?
1 2 3 somefunction '+
You can't just commute somefunction and '+. What do you do?
Also, what if someotherfunction has a '+ inside of it (suppose that's
ALL it is). What is the result of
1 2 3 someotherfunction
?
> Now a final question to you: would you call this toy
> language flat?
It's not complex enough to be flat -- there's no syntax for function
definition. If all you can do is write a single expression, there's no
way to split that expression into two (the language can't handle the
concept of "two expressions").
Aside from that, it's flat.
> I would call it flat, because I consider every pure
> arithmetical postfix expression (without variables) to
> be flat.
You also have to be without quotations or other groupings. But yes.
> But with your definition of flatness we
> should also be allowed to cut numbers, right?
> But cutting numbers makes no sense to me, ie.
It makes no sense to me either -- I specifically stated that you
should cut only on the boundaries between tokens (lexemes). A number
is a single token and can't be interpreted otherwise.
It's imaginable to make a language which has only two possible tokens,
and which therefore could be expressed as a fully cuttable bitstream.
I don't know what that language would look like. The corresponding
applicative language is Jot and Iota, and neither one is flat. I tried
to make a similar concatenative language and failed, but I'm working
out a new approach.
> - Robbert
-Billy
stevan apter — 2006-11-16 21:06:34
but now, having read robbert's post in which he describes
his rewriting algorithm, i think i was wrong, or at least
over-hasty.
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, November 16, 2006 9:29 AM
Subject: Re: [stack] Parallel computing is concatenative
> stevan apter <sa@...> wrote:
> > > > But seriously, as Manfred has pointed out before me,
> > > > Joy or any concatenative language doesn't need to be
> > > > implemented on top of a stack.
> > > That's a possible claim. I've seen it made, and I've agreed with the
> > > basic principle. The problem is that I've never seen any
> > > counterexample for its denial. If I told you that "every concatenative
> > > language is a stack language", how would you argue with me?
>
> > by offering an algorithm (or general directions for constructing
> > an algorithm) which translates concatenative programs into applicative
> > functions.
>
> Okay, I see what he meant. I misunderstood, and he's right. Yes, you
> can easily translate into applicative continuation-passing style,
> removing thereby *all* need for a stack in the underlying
> implementation.
>
> I was thinking (incorrectly) that he meant that some other semantics
> is possible aside from LIFO when executing concatenated functions.
> We've speculated that there might be some type of data object aside
> from a LIFO stack that could form the basis of a concatenative
> language, but nobody's been able to come up with one. (Yes, we know
> there are auxillary structures aside from the data stack, but the
> stack is still there.)
>
> -Billy
>
Manfred Von Thun — 2006-11-17 07:19:39
It occurred to me that mathematicians have been using another
concatenative notation that deserves to be looked at.
Let x y z be numbers (or variables standing for numbers)
Let f g h be unary functions on numbers
(such as successor, square, negative ..)
Consider the expression "xyz", normally taken to
be the product of the three numbers, with the binary
multiplication symbol suppressed. This is done quite
often, and only addition is written with an explicit
symbol. So this is x * y * z
Consider "fxy", the result of applying f to the
product of two numbers. So this is f(x * y).
Or "fgx" , the result of applying f to the result
of applying g to x. This is f(g(x)), or the
result of applying the composition f.g to x.
Or "xfy", the result of multiplying x by the
result of applying f to y. This is x * f(y).
But what about "xyf" ? this looks like a function
that is still in need of an argument. Similarly
"xfg" and "fgh" are functions in need of an argument.
But if the last three still need an argument, why
don't the earlier ones?
Answer: they all need an argument, and it is always
implicit, and that argument is just the number one
(1), the identity element for multiplication. Each
of the expressions "x", "y", "xy" "xyz" denote
unary functions which take one argument and return
one value. "x" is denotes the unary function which
multiplies its argument by the number x. The
concatenation "xy" denotes a unary function which
is the composition of the functions denoted by
its parts, this unary function multiplies its
argument by the product x*y. Other concatenations
like "fg" also denote the compositions of the
functions denoted by their parts.
The upshot of all this: each of "x" "y" "z"
"f" "g" "h" denotes a unary function from
numbers to numbers, and the concatenation of any
two or more denotes the function which is the
composition of the functions denoted by the parts.
Sound familiar? Of course. Its like concatenative
languages operating on a stack, possibly of several
variables. Here numerals "42" do no mean a number
but the operation "push 42", a unary function from
stacks to stacks, and the stack is initially empty.
In the multiplicative language we operate on a single
number. Here numerals "42" do not mean a number
but the operation of "multiply by 42", a unary
function from numbers to numbers, and the initial
number is the number one, (1).
Of course this is not restricted to plain old
integers, reals or complex numbers. You could have
matrices instead, or the weirdest gizmos mathematicians
could invent. You just need a notion of multiplication
(not necessarily commutative), but I think it has
to be a multiplication with an identity element -
in other words a monoid. The functions of a
concatenative language do not have to operate on a
stack.
But, you say, a stack that is always just of size one
is still a stack, isn't it? Well, yes, OK. But the
difference lies in what a single numeral "42" denotes:
a number, as in ordinary notation? Or a push operation
as in concatenative stack languages? Or a multiplication
by that number, as in the concatenative product language?
I think the last two are both concatenative, but in a
different way: one has its unary functions operate on stacks,
the other has is unary functions operate on numbers or
other creatures.
- Manfred
Robbert van Dalen — 2006-11-17 14:11:24
>
>> So in Joy the following expression:
>> + 2 3 + 4 5 +
>> wouldn't reduce, as where in Enchilada it would:
>> + 2 3 + 4 5 +
>> + 2 3 + 9
>> + 5 9
>
> Well, in Joy no expression "reduces" as part of the language; they
> either execute or they don't. That expression would execute with no
> problem in Joy, and the result would be equivalent to executing the
> expression you got after reduction.
When I execute '+ 2 3 + 4 5 +' in Joy I get the following error:
'run time error: two parameters needed for +'
>
>> I'll define a toy concatenative (integer arithmetics)
>> language to demonstrate how this can be done:
>
>> Now in Enchilada, reducable()is O(1)
>
> How do you determine reducible() without looking at least at every
> token, i.e. O(n)? My gut feeling is that it's an O(n*log(n)) problem,
> since I'd expect to have to keep a lookup table.
>
I use a balanced binary tree that has a flag 'reducible' at each node.
So I just have to query the top parent node.
>> and cat() and split() are O(log(N).
>
> Obviously you're preloading the source into a tree of some kind.
>
Yes. But 'the source' could also be generated at runtime, for
instance by manipulating Joy quotations:
[1 2 +] dup dup cat cat cat i =>
[1 2 +] [1 2 +] [1 2 +] cat cat cat i =>
[1 2 + 1 2 + 1 2 +] i
3 3 3
>
>> Next to that, no information is
>> destroyed: everything expression is immutable and all
>> operations are purely functional.
>
> Right.
>
>> So if we were to reduce the following enormous
>> expression with one redex in the middle:
>> 1 2 3 ....... 4999999 5000000 + ..... 9999999
>> that would cost us O(log(n)*log(n)) time (if my
>> calculations are correct)
>
> *I see* now why you said that (a long time) before.
>
>> Also, the following 'dataflow' expression can be
>> processed in parallel like this:
>
>> 1 2 3 4 5 6 7 8 '+ '+ '+
>> 1 2 3 4 5 6 '+ 15 '+ '+
>> 1 2 3 4 '+ 11 15 '+ '+
>> 1 2 '+ 7 '+ 26 '+
>> '+ 3 7 '+ 26 '+
>> '+ '+ 10 26 '+
>> '+ '+ '+ 36
>
> That's no problem; it certainly makes sense to do textual
> transformations when possible. And of course, with your engine, it's
> natural to do so. But when do the sticky operators *stop* sticking?
> It's easy to show with a "toy" problem like that one, but in a real
> program with functions calling other functions, do the sticky
> operators act on all the results of a called function?
>
> 1 2 3 somefunction '+
>
> You can't just commute somefunction and '+. What do you do?
Enchilada has no functions, only monadic or dyadic operators. So
let's say somefunction is an monadic operator (neg), then we get:
1 2 3 somefunction '+
1 2 3 neg '+
1 2 _3 '+
1 '+ _1
>
> Also, what if someotherfunction has a '+ inside of it (suppose that's
> ALL it is). What is the result of
>
> 1 2 3 someotherfunction
rephased in Enchilada terms:
1 2 3 ['+] lft
1 2 3 '+
1 '+ 5
>
>> But with your definition of flatness we
>> should also be allowed to cut numbers, right?
>> But cutting numbers makes no sense to me, ie.
>
> It makes no sense to me either -- I specifically stated that you
> should cut only on the boundaries between tokens (lexemes). A number
> is a single token and can't be interpreted otherwise.
>
OK, I forgot about the lexical rule: my wrong.
> It's imaginable to make a language which has only two possible tokens,
> and which therefore could be expressed as a fully cuttable bitstream.
> I don't know what that language would look like. The corresponding
> applicative language is Jot and Iota, and neither one is flat. I tried
> to make a similar concatenative language and failed, but I'm working
> out a new approach.
That would be a very interesting and fundamental result.
Could you tell us something more about your new approach?
>
>> - Robbert
>
> -Billy
William Tanksley, Jr — 2006-11-17 16:06:21
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> >> So in Joy the following expression:
> >> + 2 3 + 4 5 +
> >> wouldn't reduce, as where in Enchilada it would:
> >> + 2 3 + 4 5 +
> >> + 2 3 + 9
> >> + 5 9
> > Well, in Joy no expression "reduces" as part of the language; they
> > either execute or they don't. That expression would execute with no
> > problem in Joy, and the result would be equivalent to executing the
> > expression you got after reduction.
> When I execute '+ 2 3 + 4 5 +' in Joy I get the following error:
> 'run time error: two parameters needed for +'
Execution isn't the same thing as reduction. Joy can define and use a
function whose body is '+ 2 3 + 4 5 +', but its execution will be
stack-dependant. Enchilada's made for reduction, which is one of the
reasons it's so interesting.
> >> I'll define a toy concatenative (integer arithmetics)
> >> language to demonstrate how this can be done:
> >> Now in Enchilada, reducable()is O(1)
> > How do you determine reducible() without looking at least at every
> > token, i.e. O(n)? My gut feeling is that it's an O(n*log(n)) problem,
> > since I'd expect to have to keep a lookup table.
> I use a balanced binary tree that has a flag 'reducible' at each node.
> So I just have to query the top parent node.
Yup, and a balanced tree is n*log n, so I was right :-). But yes,
caching the results is a great idea. Very nice.
> >> and cat() and split() are O(log(N).
> > Obviously you're preloading the source into a tree of some kind.
> Yes. But 'the source' could also be generated at runtime, for
> instance by manipulating Joy quotations:
> [1 2 +] dup dup cat cat cat i =>
> [1 2 +] [1 2 +] [1 2 +] cat cat cat i =>
> [1 2 + 1 2 + 1 2 +] i
> 3 3 3
Oh, sure -- and you can generate the tree at runtime too. No problem.
Many languages parse into a tree; your tree is semantic rather than
syntactic. Great idea.
I have a question. In Enchilada turing-complete? I know you can do
arbitrary loops; can you also do recursions?
> >> Also, the following 'dataflow' expression can be
> >> processed in parallel like this:
> >> 1 2 3 4 5 6 7 8 '+ '+ '+
> >> 1 2 3 4 5 6 '+ 15 '+ '+
> >> 1 2 3 4 '+ 11 15 '+ '+
> >> 1 2 '+ 7 '+ 26 '+
> >> '+ 3 7 '+ 26 '+
> >> '+ '+ 10 26 '+
> >> '+ '+ '+ 36
> > That's no problem; it certainly makes sense to do textual
> > transformations when possible. And of course, with your engine, it's
> > natural to do so. But when do the sticky operators *stop* sticking?
> > It's easy to show with a "toy" problem like that one, but in a real
> > program with functions calling other functions, do the sticky
> > operators act on all the results of a called function?
> > 1 2 3 somefunction '+
> > You can't just commute somefunction and '+. What do you do?
> Enchilada has no functions, only monadic or dyadic operators.
Oh! But Enchilada does have quotations, which serve as functions.
> So
> let's say somefunction is an monadic operator (neg), then we get:
> 1 2 3 somefunction '+
> 1 2 3 neg '+
> 1 2 _3 '+
> 1 '+ _1
Let me put it another way -- what happens when '+ runs up against a
non-reducible operand?
> > Also, what if someotherfunction has a '+ inside of it (suppose that's
> > ALL it is). What is the result of
> > 1 2 3 someotherfunction
> rephased in Enchilada terms:
> 1 2 3 ['+] lft
> 1 2 3 '+
> 1 '+ 5
Okay -- it seems clear to me that the textual transformation is
equivalent to the operational behavior of:
1. Executing up to the actual location of '+.
2. Breaking the stack up into adjacent pairs.
3. Replacing each pair with its sum.
4. If the number of items on the stack was odd, place the '+ token on
the stack above the odd remaining item.
So a possible whole-stack effect picture would be:
'* ( a b c d e -- a '* bc de )
In a general, software engineering sense, it doesn't seem very useful.
In a computer science/language theory sense, it's kind of nice because
it gives you a smooth and predictable way to commute certain
operators. Understanding that can only possibly increase our
understanding of concatenative languages, which will help all of us.
> > It's imaginable to make a language which has only two possible tokens,
> > and which therefore could be expressed as a fully cuttable bitstream.
> > I don't know what that language would look like. The corresponding
> > applicative language is Jot and Iota, and neither one is flat. I tried
> > to make a similar concatenative language and failed, but I'm working
> > out a new approach.
> That would be a very interesting and fundamental result.
> Could you tell us something more about your new approach?
Yes: it failed too. :-)
My problem is that I'm too uneducated.
I'm trying to use Kerby's
http://tunes.org/~iepos/joy.html brief
exploration of concatenative combinators to design a combinator set
which does not _also_ require the reams of quotations that his
combinators require. Such a language would be purely concatenative and
purely flat, both by the strictest definitions I could give -- after
all, in a sense the quotation syntax [] is an applicative function
q(x), which returns x quoted into a list.
I started with his {cake,k} base, and tried to express some things in
it -- but I found that even the simple result [] was unattainable. I
realized that I'd need quoted forms of cake and k, so I tried the base
{cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's
needed for many fundamental expressions. I could try
{cake,k,[cake],[k],[]}, but now it's getting clear that something's
missing... The applicative quotation operator q() is secretly very
important to the so-called concatenative combinator theory.
My ingenuity and knowledge is hitting its limits... I don't know
enough about combinator theory to work anything out here.
I'm getting some ideas about combinators that, in addition to having a
pattern effect as we're used to, also return a constant value which
happens to be some other quoted combinator. In that way all the
combinators can be generated onto the stack, where they can be
captured into a pattern by a later combinator. But I don't know how to
determine whether such a combinator "base" is actually complete, so
I'm not eager to go to the work to construct one that merely looks
complete to me.
Does anyone have any ideas?
My ultimate goal is to build a flat bitstring encoding for a friend of
mine who's researching genetic algorithms. Flatness, as you can
imagine, would be a huge benefit to a genetic algorithm encoding -- it
really would be nice to be able to cut a gene at any site.
-Billy
William Tanksley, Jr — 2006-11-17 18:24:13
Manfred Von Thun <
m.vonthun@...> wrote:
> It occurred to me that mathematicians have been using another
> concatenative notation that deserves to be looked at.
I haven't seen any uses of that notation, except in Herstein, in which
case it's written the other way around (i.e. f(x) is written xf). One
problem with the notation is that the operations of multiplication and
function applications are very different in their algebraic
properties. (Herstein gets away with it because he only uses it for
functions, so multiplication is not a concern.)
> could invent. You just need a notion of multiplication
> (not necessarily commutative), but I think it has
> to be a multiplication with an identity element -
> in other words a monoid. The functions of a
> concatenative language do not have to operate on a
> stack.
I think you may be right here -- you've shown, I believe, that the
words of a concatenative language must form a monoid under
concatenation, so implicit multiplication is therefore concatenative.
That means that functions defined in terms of the same operations can
freely be substituted for the operations themselves.
Okay, then; we know that numeric multiplication, matrix
multiplication, and function composition where the functions take a
stack to return a stack are all concatenative. Numbers aren't very
powerful; matrices are reasonably powerful; function composition is
Turing-complete. What else is there? Is there some monoid more
computationally powerful than matrices but more amenible to textual
analysis than function composition?
Hmm. Another statement of the same question: we know that regular
expressions are concatenative (they're usually defined that way). We
also know that recursively enumerable languages are concatenative
(since f(stack)->stack composition can compute anything a Turing
machine can). Are there any concatenatively computable languages in
between those two? Might it be possible to build a concatenative
language that can accept only context-free languages?
This, by the way, is the first time I realized that the usual way to
express regular expressions is an impurely concatenative language
(impure because it has a grouping operator).
More and more example of concatenative languages that do NOT require
the functions on stacks! Wonderful! Sometimes it's pleasant to be
proven wrong, and I'm enjoying this one.
> - Manfred
-Billy
Robbert van Dalen — 2006-11-17 19:12:14
>
>> I use a balanced binary tree that has a flag 'reducible' at each
>> node.
>> So I just have to query the top parent node.
>
> Yup, and a balanced tree is n*log n, so I was right :-). But yes,
> caching the results is a great idea. Very nice.
The only difficult thing is to keep the tree balanced. Now the whole
Enchilada thing started with having a very efficient balanced tree
data structure in the first place.
That's why unary numbers didn't scare me - they can be implemented
rather efficiently on top of balanced binary trees.
>
> Oh, sure -- and you can generate the tree at runtime too. No problem.
> Many languages parse into a tree; your tree is semantic rather than
> syntactic. Great idea.
>
> I have a question. In Enchilada turing-complete? I know you can do
> arbitrary loops; can you also do recursions?
Yes, I'm sure it's Turing complete. And Enchilada doesn't need the do/
while operator to be Turing complete.
See:
http://my.opera.com/rapido/blog/2006-10-11-dowhilesolution
>
>> Enchilada has no functions, only monadic or dyadic operators.
>
> Oh! But Enchilada does have quotations, which serve as functions.
>
Right.
>
> Let me put it another way -- what happens when '+ runs up against a
> non-reducible operand?
>
Let me rephrase the reduction rules to answer your question:
1) scan for an operator
2) is it monadic?
2.1) is the element left to the monadic operator, not an operator?
2.2) reduce.
3) it's dyadic
3.1) are the two elements left to the dyadic operator, not operators?
3.2) reduce.
'+ is an operator (albeith sticky)
so:
* '+
doesn't reduce because of 3.1
1 '+
doesn't reduce, again because of 3.1
2 1 '+
'+ 3
reduces, but doesn't destroy '+. Alternatively:
2 1 +
3
reduces, but destroys +
>
> Okay -- it seems clear to me that the textual transformation is
> equivalent to the operational behavior of:
>
> 1. Executing up to the actual location of '+.
> 2. Breaking the stack up into adjacent pairs.
> 3. Replacing each pair with its sum.
> 4. If the number of items on the stack was odd, place the '+ token on
> the stack above the odd remaining item.
Replace 1. with 1) and I think everything turns out to have much
simpler semantics.
>
> So a possible whole-stack effect picture would be:
>
> '* ( a b c d e -- a '* bc de )
>
> In a general, software engineering sense, it doesn't seem very useful.
> In a computer science/language theory sense, it's kind of nice because
> it gives you a smooth and predictable way to commute certain
> operators. Understanding that can only possibly increase our
> understanding of concatenative languages, which will help all of us.
Can you elaborate on your notation? It's rather alien to me.
>
>>> It's imaginable to make a language which has only two possible
>>> tokens,
>>> and which therefore could be expressed as a fully cuttable
>>> bitstream.
>>> I don't know what that language would look like. The corresponding
>>> applicative language is Jot and Iota, and neither one is flat. I
>>> tried
>>> to make a similar concatenative language and failed, but I'm working
>>> out a new approach.
>
>> That would be a very interesting and fundamental result.
>> Could you tell us something more about your new approach?
>
> Yes: it failed too. :-)
>
> My problem is that I'm too uneducated.
Never mind that. Education never taught me to appreciate fresh and
new ideas (mostly boring and obvious ones).
>
> I'm trying to use Kerby's http://tunes.org/~iepos/joy.html brief
> exploration of concatenative combinators to design a combinator set
> which does not _also_ require the reams of quotations that his
> combinators require. Such a language would be purely concatenative and
> purely flat, both by the strictest definitions I could give -- after
> all, in a sense the quotation syntax [] is an applicative function
> q(x), which returns x quoted into a list.
You are very strict, indeed!
And your observation that quotations are essentially applicative is
very interesting. I tend to agree but I'm not sure why.
>
> I started with his {cake,k} base, and tried to express some things in
> it -- but I found that even the simple result [] was unattainable. I
> realized that I'd need quoted forms of cake and k, so I tried the base
> {cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's
> needed for many fundamental expressions. I could try
> {cake,k,[cake],[k],[]}, but now it's getting clear that something's
> missing... The applicative quotation operator q() is secretly very
> important to the so-called concatenative combinator theory.
It's a very hidden secret not know to many ;)
So 'how to get rid of q() without losing Turing completeness?' is the
challenge that you meet?
>
> My ingenuity and knowledge is hitting its limits... I don't know
> enough about combinator theory to work anything out here.
I would say, don't restrict yourself - let your thoughts and
ingenuity not be hampered by any theories.
>
> I'm getting some ideas about combinators that, in addition to having a
> pattern effect as we're used to, also return a constant value which
> happens to be some other quoted combinator. In that way all the
> combinators can be generated onto the stack, where they can be
> captured into a pattern by a later combinator. But I don't know how to
> determine whether such a combinator "base" is actually complete, so
> I'm not eager to go to the work to construct one that merely looks
> complete to me.
Please show us the work. Then may be someone on the list can
determine if your base is complete.
>
> Does anyone have any ideas?
Your ideas surely deserve another post, different from this 'parallel
computing is concatenative' post.
>
> My ultimate goal is to build a flat bitstring encoding for a friend of
> mine who's researching genetic algorithms. Flatness, as you can
> imagine, would be a huge benefit to a genetic algorithm encoding -- it
> really would be nice to be able to cut a gene at any site.
Yes. But there is a difference between genotype (the program) and
phenotype (the result). Moreover, DNA is not encoded in a binary form
so we shouldn't restrict ourselves to that.
But I do think that pure flatness would blend the concepts of
genotype and phenotype in very interesting ways.
>
> -Billy
- Robbert
janvanlent — 2006-11-19 12:50:50
--- In
concatenative@yahoogroups.com, "William Tanksley, Jr"
<wtanksleyjr@...> wrote:
> > > It's imaginable to make a language which has only two possible
tokens,
> > > and which therefore could be expressed as a fully cuttable
bitstream.
> > > I don't know what that language would look like. The corresponding
> > > applicative language is Jot and Iota, and neither one is flat. I
tried
> > > to make a similar concatenative language and failed, but I'm working
> > > out a new approach.
>
> > That would be a very interesting and fundamental result.
> > Could you tell us something more about your new approach?
>
> Yes: it failed too. :-)
>
> My problem is that I'm too uneducated.
>
> I'm trying to use Kerby's http://tunes.org/~iepos/joy.html brief
> exploration of concatenative combinators to design a combinator set
> which does not _also_ require the reams of quotations that his
> combinators require. Such a language would be purely concatenative and
> purely flat, both by the strictest definitions I could give -- after
> all, in a sense the quotation syntax [] is an applicative function
> q(x), which returns x quoted into a list.
>
> I started with his {cake,k} base, and tried to express some things in
> it -- but I found that even the simple result [] was unattainable. I
> realized that I'd need quoted forms of cake and k, so I tried the base
> {cake,k,[cake],[k]}. Again, [] wasn't evidently attainable, and it's
> needed for many fundamental expressions. I could try
> {cake,k,[cake],[k],[]}, but now it's getting clear that something's
> missing... The applicative quotation operator q() is secretly very
> important to the so-called concatenative combinator theory.
>
> My ingenuity and knowledge is hitting its limits... I don't know
> enough about combinator theory to work anything out here.
>
> I'm getting some ideas about combinators that, in addition to having a
> pattern effect as we're used to, also return a constant value which
> happens to be some other quoted combinator. In that way all the
> combinators can be generated onto the stack, where they can be
> captured into a pattern by a later combinator. But I don't know how to
> determine whether such a combinator "base" is actually complete, so
> I'm not eager to go to the work to construct one that merely looks
> complete to me.
>
> Does anyone have any ideas?
You could have a look at the following papers by Chris Okasaki. His
book has been mentioned on this list before, I'm surprised these haven't.
Flattening Combinators: Surviving Without Parentheses by Chris
Okasaki. Journal of Functional Programming, 13(4):815-822, July 2003.
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03
Techniques for Embedding Postfix Languages in Haskell by Chris
Okasaki. Haskell Workshop, October 2002, pages 105-113.
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#hw02
The embedding of a postfix language in Haskell could also be of
interest to people studying type inference of postfix languages.
> My ultimate goal is to build a flat bitstring encoding for a friend of
> mine who's researching genetic algorithms. Flatness, as you can
> imagine, would be a huge benefit to a genetic algorithm encoding -- it
> really would be nice to be able to cut a gene at any site.
You might be interested in the work of Lee Spector.
http://hampshire.edu/lspector/push.html
From
http://hampshire.edu/lspector/push3-description.html
"Push achieves its combination of syntactic simplicity and semantic
power through the use of a stack-based execution architecture that
includes a stack for each data type. A CODE data type, with its own
stack and an associated set of code-manipulation instructions,
provides many of the more interesting features of the language. Push
instructions, like instructions in all stack-based languages, take any
arguments that they require and leave any results that they produce on
data stacks. To provide for "stack safe" execution of arbitrary code
Push adopts the convention, used widely in stack-based genetic
programming, that instructions requiring arguments that are not
available (because the relevant stacks are empty) become NOOPs; that
is, they do nothing. Because Push's stacks are typed, instructions
will always receive arguments and produce results of the appropriate
types (if they do anything at all), regardless of the contexts in
which they occur."
There has been other work on genetic programming using stack based
languages or other "linear" program representations, but I don't have
any references at hand.
> -Billy
jan
stevan apter — 2006-11-19 19:47:46
----- Original Message -----
From: "janvanlent" <jan.vanlent+concatenative@...>
You could have a look at the following papers by Chris Okasaki. His
book has been mentioned on this list before, I'm surprised these haven't.
Flattening Combinators: Surviving Without Parentheses by Chris
Okasaki. Journal of Functional Programming, 13(4):815-822, July 2003.
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03
this is a wonderful paper - thanks!
William Tanksley, Jr — 2006-11-21 19:21:40
janvanlent <jan.
vanlent+concatenative@...> wrote:
> You could have a look at the following papers by Chris Okasaki. His
> book has been mentioned on this list before, I'm surprised these haven't.
> Flattening Combinators: Surviving Without Parentheses by Chris
> Okasaki. Journal of Functional Programming, 13(4):815-822, July 2003.
> http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03
Wow. That answers all my questions. Well, I don't understand what the
X combinator does, but why after all should I expect to :-).
A complete, TWO word, concatenative language. Perfect. And a
reasonably clear explanation, too! Thank you.
> You might be interested in the work of Lee Spector.
> http://hampshire.edu/lspector/push.html
I'd seen it a long time ago, but I'm glad you found it -- my friend
should find it more immediately useful. I've seen some other work in
Forthlike program evolution -- the advantages have seemed obvious to
others as well.
> jan
-Billy
Manfred Von Thun — 2006-11-28 08:01:45
I have been trying to make a more methodical search for
possible concatenative languages. Here is what I have
come up with so far.
First, define ³concatenative²:
A functional language is concatenative iff
the concatenation PQ of two programs P and
Q denotes the composition of the functions
denoted by the two programs.
Let T and U be two types (not necessarily
distinct), and let t1 t2 t3 .. be literals of type T.
(We might also need u1 u2 u3 .. literals of type U,
but probably not.)
Both T and U might themselves be complex
unions of simpler types, but this will not be important.
In what follows, let f,g,h be unary functions
taking an argument of type U and producing
a value of type U:
f ,g,h.. : U -> U
These functions will of course depend very
much on the nature of the type U.
I am now looking for a general method for
constructing further functions like these,
by using literals of type T and just one
binary function b which takes a T and a U
as arguments and produces a U as value:
b : T * U -> U
Here follow several examples where U
is ³container of type T² for various kinds
of containers, and where b is an operation
of putting an element of type T into a
container U:
1. U = stack/list-of-T, and b = push/cons
push : T * stack-of-T -> stack-of-T
cons : T * list-of-T -> list-of-T
Assume S : stack-of-T, then
push(t1, S) = S with new element t1
Now turn the literal t1 into a unary operator
and write S t1 in postfix order. So t1 is
now a unary operator on stacks.
This is just our familiar stack notation. We
can also have pop dup swap, and other
unary operators + - * / on stacks which
depend on the type T.
Needless to say, we start with an empty stack
which is the implicit initial operand.
Instead of stacks we could have queues,
or double-ended-queues (³deque²), and then
the postfix operators t1 could operate on
either end of the deque.
2. U = set-of-T, and b = insert
insert : T * set-of-T -> set of T
Assume S : Set-of-T, then
insert(t1, S) = S augmented with
new member t1 (if t1 was not a
member already).
In set notation,
insert(t1, S) = {t1} union S
Now turn the literal t1 into a unary operator
and write S t1 in postfix order. So t1 is
now a unary operator on sets.
We start with an empty set which is the implicit
initial operand.
Since sets are unordered, we cannot have pop dup
and swap, so there is no way of describing
which of the elements are to be affected.
However, if the type T has an ordering
(as for example numbers have), then we can
always pick out the smallest or the largest
and remove that. But that does not remove
the most recently added element. I cannot
see how sets could be useful as the basis of
a concatenative programming language.
3. The container type bag-of-T is less
well known than stack/list-of-T or
set-of-T. Bags are somewhat in between:
they are like lists but not ordered,
and like sets but allow repetitions.
U = bag-of-T, and b = add-another
add-another : T * bag-of-T -> bag-of-T
Assume B : bag-of-T, then
add-another(t1, B) = B with one more t1.
For example:
add-another(3, {2 2 2 3 5 5}) = {2 2 2 3 3 5 5}
Now turn literal t1 into a unary operator
and write B t1 in postfix order. So t1 is now a unary
operator on bags.
The implicit initial operand has to be the empty bag.
Again, since bags are unordered, we cannot have pop
dup and swap, but if T has an ordering, we could
have remove operations as for sets. Also, since
each element in the bag has a ³multiplicity², we
can operate on those.
Useful as a basis for a language? Marginally more
interesting than sets, but not too promising.
Other container types are possible, in particular
trees of various sorts, or lists-of-lists-of-T or even
arbitrarily deep nesting of lists. I¹ll take just one
example:
4. U = stack-of-stack-of-T, and b is the
operation of pushing t1 onto the top
stack S on the stack of stacks SS
Now turn t1 into a unary postfix operator as before.
We can now have pop, dup, swap as usual, and also
the usual + - * and so on, but now operating on the
top stack S of the stack-of-stacks SS. In addition we can
now have operations POP, DUP, SWAP operating on
the stack-of-stacks SS. Useful? maybe.
Much of this can already be done in Joy with the
infra combinator, though in a round-about-way.
I now turn to cases where U is not a container type.
My main examples have U and T the same type.
5. T = U = numbers (natural, integer, real ..)
b = multiplication
As before, assume that we have unary
functions f,g,h but now we use binary multiplication
to create unary operators on numbers. The implicit
initial operand has to be the number 1. Then
2 5 f 8 4
means: multiply by 2, then by 5, then take the f,
then multiply by 8 then by 4. If f is the unary squaring
function, then this evaluates to the function which
which multiplies by 3200, and using the double-speak
that we concatenators barely notice, ³it evaluates
to 3200².
This is of some interest if the numbers are naturals.
Then any multiplication by anything greater than 1
leaves its trace in the factors of the number. For
example
6 10 => 60
which is (2 * 2 * 3 * 5), and these prime factors
are preserved by any multiplication by 1 or greater.
An interestingly, any natural number can be seen
a bag of its prime factors. There is some relation
to Goedel numbering that might deserve closer
examination.
6. T = U = numbers,
b = addition/exponentiation/whatnot
Addition would take 0 as the initial implicit operand,
but I cannot see any use. Maybe there are other
binary operators worth exploring as a basis for
concatenative languages.
7. T = U = strings/lists/sequences-of-type-X
(take X to be characters, for example)
b = concatenation of strings (of characters)
Take the nullstring ³² to be the initial implicit
operand, and take t1, t2 to be strings, which
now denote a unary operation ³append t1²
Thus ³peter ³ is the unary operation of appending
that string to an operand string. Then
³pe² ³ter li² ³kes do² ³gs² => ³peter likes dogs²
Unlike a stack language the result string does not
say how it was constructed, but at least we can
do dup swap pop to the result string, operating just
on the last few characters.
If T and U are sequences of something more
interesting than characters, say numbers, then
essentially we end up with a stack language
in which pushes are not of single items but of
sequences of items. Barely anything dramatically new.
8. T = U = sets of strings = languages.
e.g. English = { ..., ³He runs², ... }
French = { ..., ³Elle mange², ...}
b = concatenation of languages, all
those strings formed by taking a member
of one concatenated with a member of
another:
English French = { ..., ³He runsElle mange²,...}
Sounds crazy, but we use it all the time in regular
expressions and in grammars.
Initial implicit operand is the one element language
consisting of just the nullstring ³². Now a t1 such as
English is the unary operation of concatenating
every string in the argument with every string in English.
A less preposterous example:
L1 = a | b | c = the language {³a², ³b², ³c²}
L2 = d | e = the language {³d², ³e²}
L1 L2 = their concatennation:
{³ad² , ³bd², ³cd², ³ae², ³be², ³ce²}
Since sets do not allow any sensible dup swap pop,
as mentioned earlier, nothing much doing here.
BUT: since the elements of the sets are sequences,
we can do dup swap pop on these sequences:
L1 L2 dup =
{³add², ³bdd², ³cdd², ³aee², ³bee², ³cee²}
Furthermore, if the sequences are not character strings,
but sequences of numbers, then all sorts of other
unary operations become possible, i.e. unary
operations on sets of sequences of numbers -
or other whatnots.
I must go.
- Manfred
Well, I¹ll leave the discussion to another day or to
somebody else.
[Non-text portions of this message have been removed]
Manfred Von Thun — 2006-12-07 08:45:31
Ever wondered what factorial(20000) might be?
[Yes, that was twenty-thousand]
A big number, and it has over 77000 digits.
You need a bignum cruncher for that, and the
unix utility dc (Desk Calculator) is just the right thing for that.
I had known about it for many years, and also that it is
probably the oldest concatenative language, but never had any
need to use it. But recently I did need something for bignums,
so I looked at it with more care.
It has numbers that are pushed onto the stack, the usual
arithmetic operators, a few stack shufflers,
some fancy stuff to do with input and output bases
and with precision. Whatever is on the stack
can also be stored in one of the 256 registers, or loaded
back from a register to the main stack.
* Chris Diggins, note: the meaning of store and load in dc
* is the opposite of what you have on your ³primitives² table.
* You might search the literature to see which is most common.
You can also put strings on the stack, store in and load from
registers, print them, and execute them as programs.
Strings are written like [hello world], but the usual
string operations like concatenation, extracting or deleting
parts, are not available. Strings are really meant as programs.
The interesting thing is that as programs they can contain
other strings (which would make no sense in other languages).
The string [11 22 33] when executed will push the three
numbers, leaving 33 topmost. The string [11 22 [33 44]]
when executed will push two numbers, 11 and 22,
and then push the string [33 44] on top of that. The
string [33 44] might then be executed in turn.
There are no lists in dc, but using these program strings
one can mimic some list operations. Consider the
string [11 [22 [33 [44 [55]]]]]. Like the previous examples
these look just like Joy lists or quotations. But as lists
in Joy the last example is different from [11 22 33 44 55].
There is also an interesting connection between these
two forms of Joy lists and the two Lisp notations:
(11 22 33 44 55) as a Lisp list is just shorthand for
(11 . (22 . (33 . (44 . (55 . ())))))), where the dot
is the (infix) operator ³cons², separating the left
³car²-part and the right ³cdr²-part. But the two
notations mean exactly the same in Lisp.
However, in Joy the two lists [11 22 33 44 55]
and [11 [22 [33 [44 [55]]]]] do not mean the same
at all. The first is the usual notation for lists, and the
second I have never really used. Looking at dc made
me wonder whether perhaps one should.
Joy: [11 [22 [33 [44 [55]]]]] i ==
[11 [22 [33 [44 [55]]]]] uncons
dc: [11 [22 [33 [44 [55]]]]] x # x = i in Joy
The three programs above (two Joy, one dc) all
do exactly the same to the stack. We can repeat the
i or uncons in Joy or the x in dc a further 4 times
to end up with all the five numbers on the stack. This is the
closest I can come to an kind of list manipulation in dc.
There seems to be no way of constructing lists
by concatenation or cons.
As an aside, let us ask what
happens when what we have inside all those brackets
are not just numbers but other program fragments,
i.e. of the form [A [B [C [D [E]]]]], where A..E are
literals or operators (and even combinators, which
can in fact be defined in dc as well as in Joy).
For example
[1 2 [+ [dup [dup * [*]]]]] # Joy
[1 2 [+ [d [d * [*]]]]] # dc
By doing 5 times i in Joy, or 5 times x in dc, we
should be left with 27 on top of the stack. But
we can also do it in steps:
x .. x .. x .. x .. x
where at the four points .. something else is done,
most likely with dip somewhere below the remaining
quotation. What uses this has in Joy I do not know.
The dc utility also allows the 256 registers to be
used as stacks, with shifts between the main stack
and the register stacks. I have not explored this
at all. Obviously this is the way to implement a
dip combinator, using one of these register stacks
in the manner of the Forth return stack. But there
is no way of putting a register stack on top of the
main stack, or vice versa. So all these stacks cannot
do duty for lists.
Since strings can be stored in the registers, they
are the right sort of place for definitions. I wrote
my (recursive) factorial function as a 10 or 12
character dc string, stored of course in register f.
The Gnu extension of dc also allows the registers
or the register stacks to hold arrays. I have not
explored this at all.
I hope that some of you will look at dc, the
grandfather of all concatenative languages. Maybe
you will find something stimulating for your
own concatenative languages.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2006-12-09 00:54:25
Manfred Von Thun <
m.vonthun@...> wrote:
> I hope that some of you will look at dc, the
> grandfather of all concatenative languages. Maybe
> you will find something stimulating for your
> own concatenative languages.
The first Forth was written in 1958 (by Chuck Moore). dc was written
in the B language on a PDP-7, so it couldn't have been written before
the late 1960s. So Forth is still older.
The two share no common ancestry, of course. (Obviously.) There's no
common grandfather yet... convergent evolution? :-)
> - Manfred
-Billy
Christopher Diggins — 2006-12-09 18:44:25
> * Chris Diggins, note: the meaning of store and load in dc
> * is the opposite of what you have on your ³primitives² table.
> * You might search the literature to see which is most common.
Thanks for pointing that out to me Manfred!
- Christopher
Manfred Von Thun — 2006-12-12 05:16:09
On 7/12/06 7:45 PM, "Manfred Von Thun" <m.vonthun@...> wrote:
[..]
OOOPS - a little error:
in the 7-th line below, replace the ³uncons² by ³uncons first².
> However, in Joy the two lists [11 22 33 44 55]
> and [11 [22 [33 [44 [55]]]]] do not mean the same
> at all. The first is the usual notation for lists, and the
> second I have never really used. Looking at dc made
> me wonder whether perhaps one should.
>
> Joy: [11 [22 [33 [44 [55]]]]] i ==
> [11 [22 [33 [44 [55]]]]] uncons
>
> dc: [11 [22 [33 [44 [55]]]]] x # x = i in Joy
>
> The three programs above (two Joy, one dc) all
> do exactly the same to the stack.
[Non-text portions of this message have been removed]