Post by William Tanksley, JrPost by Don GrovesOf course, any concatentative language doesn't have to use a stack,
it's just most convenient.
"Convenient" is kind of vague. A stack is the only parameter-passing
data structure we know of that's computationally complete/Turing
equivalent and doesn't require application. You can also make a
concatenative language using a single integer accumulator, for
example, and it's simple to implement and understand (but it's
ridiculously weak). Since a stack is the only one we know about it's
of course the most convenient one we know about... But what ones don't
we know about?
The stack works essentially as a sort of caching structure. Whichever caching strategy you choose determines the data structure.
Last in, first out = queue
Highest/lowest weighted out = priority queue
First in, first out = stack
There can be only one = a single item (accumulator)
I can't think of any other strategies that have a single unambiguous "top" element. FIFO seems to be the only reasonable caching strategy, though.
That's a clever approach. Although I liked it at first glance, I think
it's not quite complete. We know concatenative languages that use an
accumulator and ones that use a stack; we also know ones that use
multiples of each (for example, ANS Forth can have a separate floating
point stack, and Machine Forth uses a memory fetch register; note that
the return stack in Forth does NOT count, since accessing that makes
the program NOT concatenative). The problem is that the choice between
stack and accumulator changes the language in a profound way. So if it
were possible to arrange a queue in some way instead of a stack, what
would the resulting language look like? We have no semantics for such
a language (yet).
I'm also thinking about the statement that there should be only one
unambiguous "top" element. This is essentially right, of course;
accepting that when there are two top elements they can be
disambiguated by the word that's needing the data (as with ANS Forth's
floating point vocabulary, whose words may pull from a distinct
stack). There are more details, of course, since some words accept
more than one parameter, so at the time the word is called the
structure must provide ALL of its elements to it unambiguously (so not
just the top item).
A stack meets that requirement by imposing a total ordering of all of
its contents at all times. I think it's fair to say that an
accumulator does as well (consider a language over matrices or quantum
mechanical operators instead of over the integers). If the only
possible data structure must impose a total ordering, then a stack is
the only possibility. BUT... does peg impose a total ordering? Doesn't
the nondeterminism hint that there's something other than a total
ordering?
Actually, because a peg program must be parsed backward, it occurs to
me to take a lesson from Stevan Apter, and make the language's parse
structure explicit. In order to be parsed backward, it would make
sense to describe the start of a parse as pushing the REVERSE of the
initial program onto a stack (which plays the same role as Forth's
return stack and xy's dequeue.
I'd better send this -- otherwise I'll never finish writing it.
Undeniably peg is stack-based, but there's a lot more going on in
terms of data structures and algorithms than just the usual return
stack-data stack pair, and I think the additional stuff is
interesting.
Post by William Tanksley, JrHere's another question: is peg _formally_ concatenative? That is,
given two valid programs, is their concatenation also a valid program?
Are the semantics of the resulting program the composition of the
semantics of the original two?
I think the answer is "no". A program "a1" and "a2", both of which
deterministically execute something like "False assert" or an
undefined word (which means that they always halt). The concatenation
"a1 a2" will perform (deterministically) the semantics of a2, but
never a1.
Peg is a pure functional language, so it doesn't matter if a1 is executed if a2
yields no results; the execution of a1 has no observable effects.
Oh, so I actually completely misunderstood. "False assert" doesn't
halt the PROGRAM; rather, it halts the PARSE; it actually sends the
program into a "never terminates" state. That makes perfect sense; and
seems quite clever.
The exception is if a1 performs I/O. Unfortunately, I can't see any way to fix
this, because the Peg interpreter could never perform any I/O for fear of an
unseen 'False assert' being concatenated to the right.
Then let's just note that performing IO renders undefined results in
the presence of nonterminating programs. Good ol' "undefined results".
1. The expression to the right must be fully evaluated before evaluation of a sub-expression containing an IO token.
That seems like a nice rule.
2. Concatenation must be performed on the Cartesian products of the results of evaluation of the sub-expressions
You MIGHT mean composition rather than concatenation. Is that the case?
If so, you've discovered a new subvariant of a "concatenative
language". The usual rule is "the syntax of concatenation implies the
semantics of composition", but for your language the rule is "the
syntax of concatenation implies the semantics of composition of all
Cartesian products".
I like it.
Now, Enchilada did something similar, but IIRC it didn't do it with
mere concatenation (van Dalen?); I don't know enough about Ripple to
say anything, but it either did this or allowed some explicit
operations to cause it (fortytwo, are you listening?).
Either way, I just learned something new.
-Wm