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

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 y

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 m

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

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

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

[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-i

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 m

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 co

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 so

[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: