gmane.comp.lang.concatenative

Re: [stack] peg: a lazy, non-deterministic concatenative language

dustin.deweese — 2012-04-25T11:38:10


--- In concatenative< at >yahoogroups.com, Joshua Shinavier <parcour< at >...> wrote:


Peg also uses lazy evaluation, but the pureness of the language means that:

    1 2 +
    3
    7 4 -

are all equivalent and indistinguishable, whether evaluated or not, because observing them requires evaluation.

Because expressions need to terminate first in order to use the Cartesian composition rule, non-termination does not pose a problem either.

Also, in Peg, an expression will not reduce, rather than yielding no solutions, if an argument to a word is missing i.e. the expression is a partially applied function.  So,

    10 + --> 10 +

which is different from

    "ten" + --> no (no results)

Re: [stack] peg: a lazy, non-deterministic concatenative language

dustin.deweese — 2012-04-25T11:12:52


--- In concatenative< at >yahoogroups.com, eas lab <lab.eas< at >...> wrote:

This is why I prefer a pencil to a pen.

Oh well. Point and laugh.


I considered having separate stacks for each type in Peg.  Each argument to a word would be taken from the appropriate stack depending on the type required. Then, values could be wrapped in semantic types to minimize stack manipulation.

For instance a word 'greeting' could require a 'name' and a 'title', both of which are simply wrappers for strings, and the greeting would return "Hello [title] [name]!" regardless of the order of arguments. It would just use the title and name on the top of their respective stacks.

I decided against this, because it would complicate many other things.

Re: [stack] peg: a lazy, non-deterministic concatenative language

eas lab — 2012-04-25T09:54:24

Didn't anybody pick up this 'typo'?

Think rather in term of the 'most recent' element.

] 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).
I disagree: it's the concept of LIFO/most-recent, and not the implementation
details, that count..

Consider the following real-life-task:
papers are 'stacked' in their order of creation;
we need to present them to the emperor in their order of creation;
so we could sequentially 'pop' them to another 'pile';
and than 'pop & present' from that 'pile'.

NB. I distinguish between the stack and the pile;
where the pile is stack2 of pop(stack).

If some of the papers may not be handled by the 'presenter',
they could be piled on a separate/floating-point-pile.

But then we've destroyed/lost the <sequence markers>,
by bifubricating the stack/pile.

I'm guessing that in FORTH, when/if you ADD a floating-point-facility,
you must have a mechanism to keep the 2nd [or more] stack 'syncronised'.
So effectively/conceptually there's only ONE stack.  Or?

== Chris Glur.

Re: [stack] peg: a lazy, non-deterministic concatenative language

Joshua Shinavier — 2012-04-23T04:24:58

On Fri, Apr 20, 2012 at 1:21 PM, William Tanksley, Jr <wtanksleyjr< at >gmail.com


Present, just lazy :-)

That's an interesting property, but it's not true of Ripple, and lazy
evaluation is the reason it's not true.  Suppose we split a Ripple program
arbitrarily and evaluate the fragments, e.g.

    4 sqrt. 10 add.

to

    4 sqrt.

and

    10 add.

They're both valid programs, yet the right-hand-side program has no
solutions while the complete program has two solutions ([8] and [12], or
(8) and (12) in Ripple syntax).  Any time the right-hand-side does have a
solution, e.g. if the program had been (4 sqrt. 10), which is already fully
reduced, the left-hand-side will never be reduced in the complete program,
so it doesn't matter what its solutions are.

If Ripple used an eager evaluation strategy instead, the "cartesian
composition" rule would more or less hold.


Best,

Josh






[Non-text portions of this message have been removed]



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

Yahoo! Groups Links

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

<*> Your email settings:
    Individual Email | Traditional

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

<*> To change settings via email:
    concatenative-digest< at >yahoogroups.com 
    concatenative-fullfeatured< at >yahoogroups.com

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe< at >yahoogroups.com

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

Re: [stack] peg: a lazy, non-deterministic concatenative language

dustin.deweese — 2012-04-22T21:09:07




--- In concatenative< at >yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr< at >...> wrote:


The stack for any particular execution path has a total ordering.  You could use non-determinism to make the stack appear only partially-ordered, though, with an expression such as:

1 2 3 [] [swap] \/ $


The second rule wasn't worded very well.  I tried to make it more precise:

2. The composition of two sub-expressions is equivalent to concatenating each of the Cartesian products of the results of evaluating the sub-expressions individualy.

See this wiki page (https://github.com/HackerFoo/peg/wiki/Properties-of-Peg) for an example, as well as other information on the properties of Peg you might find interesting.

Re: [stack] peg: a lazy, non-deterministic concatenative language

William Tanksley, Jr — 2012-04-20T17:21:38


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.



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.


Then let's just note that performing IO renders undefined results in
the presence of nonterminating programs. Good ol' "undefined results".


That seems like a nice rule.


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

Re: [stack] peg: a lazy, non-deterministic concatenative language

dustin.deweese — 2012-04-19T08:53:39


--- In concatenative< at >yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr< at >...> wrote:

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.


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.  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.

For Peg, it is formally concatenative with some modifications:

1. The expression to the right must be fully evaluated before evaluation of a sub-expression containing an IO token.
2. Concatenation must be performed on the Cartesian products of the results of evaluation of the sub-expressions

Re: [stack] peg: a lazy, non-deterministic concatenative language

William Tanksley, Jr — 2012-04-19T05:49:57

That's a good question. You'd have to provide more structure than a
simple "graph", since a graph has no orientation. Obviously you've got
a root and at least one current position... But how do branches
happen, and how do mergers happen?


Since hackerfoo just joined the group, we may be soon receiving an
answer! I look forward to it.

-Wm

Re: [stack] peg: a lazy, non-deterministic concatenative language

Stephen De Gabrielle — 2012-04-17T15:46:08

On Tue, Apr 17, 2012 at 3:48 PM, William Tanksley, Jr <wtanksleyjr< at >gmail.com

possibility of a concatenative language that operated on a 'graph-structured
stack'? (and if such a thing would be useful)

Re: [stack] peg: a lazy, non-deterministic concatenative language

William Tanksley, Jr — 2012-04-17T14:48:21

"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?

Here'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.

This doesn't make "peg" a bad language... But it does suggest my
"formal" rule for testing concatenativity wants a weaker variant.
Another example of the need for a weakening is words that perform
control flow alteration, like "RETURN" and "call/cc", or Forth's R>
and EXIT.

For "peg" itself, it's easy to see that concatenativity DOES hold for
programs where the parse "continues" past the beginning of the
program. For Forth, concatenativity holds when certain words in the
dictionary are not used. Rice's theorem will tangle us up for both
languages, but in general it's easy to see when a Forth program is
concatenative. Parsing a peg program MIGHT be possible to explode to
O(2^n), but I think it'll always terminate.


-Wm

Re: [stack] peg: a lazy, non-deterministic concatenative language

John Nowak — 2012-04-17T12:48:39

Reddit thread (with comments) here:

http://www.reddit.com/r/haskell/comments/sc858/peg_a_lazy_nondeterministic_concatenative/

Re: [stack] peg: a lazy, non-deterministic concatenative language

Don Groves — 2012-04-17T12:36:20

Agreed. Peg is the most interesting variant I've seen in quite a while.
I haven't looked deeply yet but it seems to have an Icon flavor to it.

Of course, any concatentative language doesn't have to use a stack,
it's just most convenient.
--
don


On 17 Apr 2012, at 05:26, William Tanksley, Jr wrote:




[Non-text portions of this message have been removed]



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

Yahoo! Groups Links

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

<*> Your email settings:
    Individual Email | Traditional

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

<*> To change settings via email:
    concatenative-digest< at >yahoogroups.com 
    concatenative-fullfeatured< at >yahoogroups.com

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe< at >yahoogroups.com

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

Re: [stack] peg: a lazy, non-deterministic concatenative language

William Tanksley, Jr — 2012-04-17T12:26:43

Amazing... This is creative. He's parsing right to left, and executing
only what's needed to evaluate the last word. In cases where
evaluation is ambiguous, he chooses "nondeterministically" (I'm not
sure what that means). If execution fails, he backtracks to a previous
ambiguous point. Words are provided to force failures.

The language uses stack manipulation words, but I'm not sure that it's
actually a stack. Anyone have any discussion on that point?


-Wm

[stack] peg: a lazy, non-deterministic concatenative language

John Nowak — 2012-04-16T14:47:27

https://github.com/HackerFoo/peg

Not mine.

- jn

Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

William Tanksley, Jr — 2012-03-25T17:03:10

Computers with i/o are categorically different from ones without it,
capable of computing tasks in completely different time orders. Turing
machines help to define the Chomsky hierarchy (they're at the top),
but there are many types of Turing machines, not all of which are
equivalent (and i/o is the big difference).


Most significantly, zeroone, unlike a Turing machine, has no access to
its own code. This means that there is NO tape, no data left on the
tape, no writing to the tape. There is a stack, but the stack isn't a
simple list of symbols; rather, it's a stack of functions, and by
definition there's no way to interpret a function consistently. So
adding i/o is a major upgrade.


I'd clean forgotten that... Excellent, more citation materiel. Yes,
his goal is similar to mine.


I recall that, yes.


If by that you mean that comparing the size of the *same* program is
more useful than comparing the size of different programs -- I agree.
But I wouldn't expect the results to change -- although that's just my
gut feeling. The reason I expect that is that although a lambda
combinator requires more program-bits to express, it's always the
exact combinator that's needed, never an approximation that needs to
be corrected.

Meanwhile, a zeroone program carries no information in the arrangement
of program-bits that isn't already encoded in the interpreter.
Practically, this means that zeroone programs will always (well,
normally) be bigger than the same program written in either other
language.


More combinators certainly means the program will be shorter; the
worry is that one can define a combinator which makes the program VERY
short. I'm reminded of a UCSD processor design task where one of the
final goals was to run a median computation; I built a stack processor
and included hardware to implement a "perfect bitonic shuffle" on the
stack, which I'd made deep enough to handle all of the data on which
the median was being computed. Since the assignment was graded on how
many cycles our processor required to perform the tasks, my team broke
the grade curve. That was fun. Especially since the TA didn't believe
it would work at all.

But adding more combinators has long been a goal of mine. Particularly
because handling i/o will allow me to make a sensible comparison along
the same line as the above, but also because it seems perfectly
obvious that granting access to a neater selection of combinators
would allow for shorter, clearer programs. Interestingly, adding more
combinators should also force the interpreter's source code to be
larger, especially if it's expressed in a different language.

For this reason, I'd want to compare sizes of the language's
interpreter written in a standard language (compared to the other
interpreters written in the same standard language), then the sizes of
a standard program (your suggestion of a brainfuck interpreter is
perfectly valid) written in the language itself.

Sadly, adding more combinators has revealed some kind of bug in the
most important of my "tworing" utilities -- so I've got some work to
do.


Since zeroone not only loses the ability to define its own
combinators, but also loses the ability to have the beginning of the
program define the parse environment in which the latter part is read

[stack] Re: Jon Purdy: Why Concatenative Programming Matters

Ruurd — 2012-03-25T09:59:36

Hi,

You don't have to add i/o primitives to your language. All computers 
are permutations of a Turing machine and a Turing machine does not
have i/o.

First you put the brainfuck interpreter on tape, followed by the 
brainfuck program, followed by the input that the brainfuck program 
takes, if any.

You feed this tape to the program that interpretes the zeroone universal evaluator and after executing, whatever is left on the tape
is the output.
The interpreter can read the tape and output what is there.

You can find the competitor here: http://homepages.cwi.nl/~tromp/cl/cl.html

The commandline to produce 'Hello, world!' is either:

cat bf.Blc hw.bf | ./blc m8 uni8.lam

or:

cat bf.Blc hw.bf | perl blc.pl -8

That last one is very slow and is less beautifull, because it has
the interpreter encoded in perl instead of in the lambda calculus.
The author switched from combinatory calculus to the lamda calculus,
because the last one is more descriptive. The comparison was made,
based on the size of the self-interpreter. I think that a comparison
based on a brainfuck interpreter is more realistic. Also, the
combinatory calculus was restricted to just S and K and I wonder
what difference it will make if more combinators are added.
Also, I wonder if the comparison is still in favor of the lambda
calculus when concatenative combinators are used instead.

It is not my personal quest to find an answer, that's why I am
asking.

R.

<wtanksleyjr< at >...> wrote:

Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

William Tanksley, Jr — 2012-03-24T21:14:36


Informally, yes. Formally, nontermination. There are many ways of
doing that which aren't as simple to discover as infinite loops.


Okay, that's fine, then. I thought you were saying that every
expression has a normal form, and every expression will reduce to its
normal form no matter what path you take. The latter is definitely not
true.



That depends on what you mean by "reduce". As long as you stick to
term rewriting, it's true. But I don't have a term rewriting system
yet for zeroone; my past attempts indicated that such a system would
be very complex, and would depend very much on the specific base I
chose (and I still haven't picked out a single base).



Unless I'm badly wrong, it should mean that you'll always end that way
*in theory*. In practice, the average solvable problem is much harder.


You're right! I should have remembered that.


-Wm

Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

William Tanksley, Jr — 2012-03-24T20:51:05

I'm sorry -- I didn't realize that. Using the same notation as iepos' page:

[B] [A] q == [[B]] [A B]

So, q serves three purposes: it makes A and B into siblings in a list;
it swaps the order of A and B; and it adds a layer of quotation to B.

You noticed cake; it turns out that cake can serve in place of q,
since it does all of the above things (although in a more complex
way).


No, because zeroone's underlying machine has no i/o capability of any
kind. The obvious question pops to mind: is it possible to make a
zeroone with i/o? It's taken me a while, but I finally realized what I
needed -- the ability to pack an arbitrary number of primitives into
the "zero" pseudocombinator.

The zero combinator I used before was zero == [] [q] [k]. All three
components are important -- the empty list gives us a starting point
for building lists at runtime, the 'k' combinator allows us to take
lists apart, and 'q' is the universal constructor. The combinators can
be replaced by others that do similar jobs, though. I mentioned that
"q" can be replaced by the "cake" combinator you found, and indeed
anything that can do the same basic tasks that 'q' does can fill its
place.

So what I'm going to do is pack all those extra combinators into a
binary tree in place of the [q] combinator, and make it quick and easy
to climb that tree by making both 'k' and its stack-flipped version,
'z', easily available. Remember, the entire tree can be placed on the
stack by itself with the code "0011" (which doesn't actually depend on
what is inside the middle element of the 'zero' combinator);
therefore, I'll simply use the name "tree" for that.

So; let's make a tree that contains z, input, output, and q: [
[[input] [q]], [[output] [z]] ].

So to construct 'z' here, we write "tree 11"; read this as "get the
tree, execute the right branch, then the right branch again." (I
assume none of the spaces matter.) You'll recall that 'k' is simply
"1", so we now have both 'k' and 'z'; and for our special purposes
here, I'll use "left" and "right" as a synonym for "z" and "k",
respectively.

From this, we get q == "tree left right"; input == "tree left left",
and "output" == "tree right left".

Obviously, at this point we've proven that we can access anything in
ANY binary tree; we can use any number of primitives we want. (I know,
I haven't explained what "input" and "output" do. They do whatever we
want them to do, and now we can define and provide primitives that
manipulate what they produce.)

Another thing I haven't done is to figure out how to get a shorter
expression for "z". Right now it's much bigger than "k", and strong
asymmetry is usually a hint of non-optimality.


-Wm

Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

Robbert van Dalen — 2012-03-24T19:57:16

On Mar 24, 2012, at 5:35 PM, William Tanksley, Jr wrote:

of course, never to reach fixed point is an 'infinite loop'.
to reach fixed point is called the normal form of an expression.
see: http://en.wikipedia.org/wiki/Term_rewriting_system


i always understood that a flat language must have this property:
that *any* expression (albeit reduced) must be flat.


the chosen reduction order (or strategy) doesn't imply at all that you can test two different expressions for equivalence.
confluence means that you always end up with the same normal form, irrespective of reduction order.
(when there are multiple ways rewrite an expression).

confluence is a very nice property to have for a chosen reduction strategy.

consider for example the difference between lazy evaluation and eager evaluation.
with lazy evaluation, taking the first element of an (lazy) infinite list will yield a value.
not so with eager evaluation.


sure, names are good.


actually, what you describe is very much the 'enchilada' way of doing conditionals.
for example, the following expression:

10 ? [is_ten] * .

tests for 10 and reduces to is_ten if so

10 10 ? [is_ten] * .
1 [ten] * .
[ten] .
ten

5 10 ? [is_ten] * . 
0 [ten] * .
0 .
(empty).


cheers,

R.

Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

William Tanksley, Jr — 2012-03-24T16:35:22

Looking elsewhere in your email, I see the problem. This is a good
time to ask that implied question: "is there any difference between
[]k and drop, or between 0011 and q"?

No, it's not a problem, and there's no detectable difference. "01"
performs the action "drop" requires. There are other ways to implement
"drop" as well, all of them taking more bits, more time, and more
stack space. They're perfectly valid implementations of drop, but this
is the one I told you about. (There are good complexity theory reasons
to prefer "01" to any of the others.)


There are a countably infinite number of combinators, and zeroone can
express all of them. I'm not showing you [q] and [k] because they're
fairly ugly. [], on the other hand, is quick to produce from memory.
[] = "00101".

One effective way to prove that a base is complete is to use it to
produce all of the combinators in a known complete set. I'll do
that... But not now.


See above :-).



You later define "reduce" as "execute". I have to point out that some
expressions in any Turing-complete language never reach a fixed point
by execution.

Furthermore, you later assume that the reduced expression is itself
flat; that's not correct in my notation. It's actually possible to
build a formal logic where that does hold, but such a logic will be
both VERY complex and either incomplete or possible to express
contradictions in (per Godel). Using zeroone formally requires
understanding how zeroone works internally first, which is what we're
doing now. It's possible to perform all program transformations by
replacing substrings with different strings (that's called "formal
logic"), but before we can talk about how that works we have to
understand how to discover the meaning of a substring so that we can
prove that the two substrings have the same meaning.

I consider flat formal logic a "later" step, not for now. For now, we
use the semantics of the language to assist in proofs, rather than
doing things formally. Although we ARE using formal logic on the
semantics, it isn't a flat formal logic.


Whatever "reduce" means, it doesn't mean this. Sorry, but this would
imply that any two expressions of the same function will always reduce
to the same fixed form, thus allowing you to test in a finite amount
of time whether two functions are equivalent. That's impossible.


That's the only way I've really worked it out at this point, so I agree.


More importantly, it'll have syntax to allow user-defined names -- so
you can define any combinator you want using zeroone, and from then on
refer to it by name.



Implementing true/false/if/else actually isn't hard; it usually starts
by defining "false" as "drop", and "true" as "execute". The function (
func flag ) "if" would then simply be "execute" -- that is, it
executes the true/false flag, and if that's a 'true' it executes the
function; if it's a 'false' it drops the function.


-Wm

[stack] Re: Jon Purdy: Why Concatenative Programming Matters

Ruurd — 2012-03-24T09:12:16

Hi,

I can't find q on iepos' webpage, but I do find cake.
Is q the same as cake ?

Can zeroone be used to write a brainfuck interpreter in 112 bytes
or less ? That would be interesting.

R.

--- In concatenative< at >yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr< at >...> wrote: