Re: [stack] Advantages of cat, joy ..?

On Feb 24, 2009, at 4:03 PM, William Tanksley wrote:

> This looks very much like an applicative language with optional
> parentheses for single-argument functions.

Aye, that's the idea.

>> Essentially, you make heavier use of a cleave-like form to add some
>> useful "nesting" to the language.
>
> I agree with the concept of adding nesting to express forms; but I  
> don't
> see the form in this case.

Not quite sure what you mean by "don't see the form".

> My understanding is that "an FP approach" (function-level programming)
> works very well with a stack, so I'm not particularly enlightened on
> what this means.

Oh, the stack does work for functional-level programming. By "an FP  
approach", I simply meant something more like Backus's FP language.  
Getting rid of the stack though is necessary to make cleave more useful.

One problem with cleave in a stack-based language is that you need one  
version for every number of items you want to pass to the cleave. This  
is because the entire state of the program is passed to every function  
and you need to "tell" the cleave how many items it cases about. This  
is not the case in FP.

Additionally, functions do not return a list/stack in the FP approach  
when just returning a "single" value. This allows you to do something  
like '[id, id] 5' and get '[5, 5]' instead of a tuple of two stacks  
containing 5 (which is considerably more difficult to operate on).  
This works because the '5' is just '5', not a stack containing '5'.

Another benefit of the FP approach to construction is that functions  
in the construction cannot interact. This is not the case with cleave  
as I've pointed out previously.

Finally, construction in FP always returns N elements where N is the  
number of functions used in the construction. This is *much& easier to  
deal with than cleave in a stack-based language where the output of  
each cleave is essentially concatenated together into a flat stack.  
For example, say you have the program 'hd [foo, bar]'. If you know  
that 'bar' terminates, you can simplify this program to 'foo' without  
knowing the arities of 'foo' and 'bar'. You cannot do this with cleave  
in a stack-based language. Similarly, you get nice properties like  
distributivity that allows you to convert '[foo, bar] baz quux' to  
'[foo baz, bar baz] quux', and so on.

Hopefully that ramble makes some sense. I've done a lot of thinking  
about why cleave works better in FP, but I'm still having a bit of  
trouble articulating it.

>> for conditionals is also useful. For example:
>>    map[F] = null? -> id; cons[F head, map[F] tail]
>
> Here you're clearly defining an adverb, and your language doesn't  
> allow
> functions to be passed on the stack.

Yes that's true. To be clear, the earlier example I gave did offer  
first class functions.

> I like this, but once again, this isn't an example of a  
> concatenative language without a stack, because there's no  
> concatenation happening.

Well there is, just not much of it in that particular example. All of  
the usual associative laws of concatenative languages apply:

    APPENDING:
    a c == b c IF a == b

    PREPENDING:
    c a == c b IF a == b

    FACTORING:
    a f d == e IF f == b c AND a b c d == e

You also get new distributive laws related to construction as  
mentioned above.

> You haven't offered an example of a concatenative language without
> shufflers. Your best approach was (in the wikipedia thread):
> ...
> hypot = sqrt + [sq a, sq b]

This is the same language I just used to give the map example except  
that I swapped the meaning of () and []. I'll go back to using [] to  
mean construction.

> ...the problem is that in this language even this trivial example
> requires the 'hd' and 'tl' shufflers.

Yes, but they're not really "shufflers" like swap, rot, tuck, dup,  
etc. You can even define pseudo-variables in terms of 'hd' and 'tl'.  
For example:

    hypot[length, width] = sqrt +[sq length, sq width]

Here, 'length' is really 'hd' and 'width' is really 'hd tl'. A simple  
substitution of 'hd' for 'length' and 'hd tl' for 'width' will get you  
a point-free program. The compiler can check that the pseudo-variables  
are not used in a way that would prevent this trivial substitution  
from being valid. For example, the following would be illegal because  
'x' cannot be easily replaced with 'hd' to get a point-free program:

    foo[x, y] = x[y, x]

The rule for what is and isn't legal is a bit more than I want to  
state here but it's not too bad. It's never something I have to think  
about when programming; it tends to flow naturally.

I should note that Backus's FL and Felix's FP offer such a mechanism  
for defining pseudo-variables. The important thing to remember here is  
that they're just syntactic sugar and not a core part of the semantics  
like they are in languages based on substitution.

> Conceptually, the big difference between this and a stack-based  
> language
> -- if I'm reading it correctly -- is that this language uses a data  
> tree
> rather than a data stack. That's fascinating!

Yes, that's exactly it! Much better way of putting it than I've been  
using.

> So how do nodes of this tree get constructed? I can see that once  
> they're constructed your language can pass them around and generate  
> new trees (or, equivalently, mutate the existing tree), but I don't  
> see how to express a cons.

I'm not quite sure what you're asking here, so I'll guess.

Construction doubles as a list syntax. For example, the function '[1,  
2, 3, 4, 5]' always returns a list containing the numbers one through  
five. This is because '1' is just a constant function that, when  
applied to anything, returns the value 1. This is different from a  
stack-based language where '1' is a function that pushes the value 1  
onto the stack.

(Note that Backus's FP is a different here: '~1' denotes the function  
that returns the value 1 and '1' denotes the value one. I dislike this  
as it is incompatible with the property of concatenative languages  
where the simplification of a function is another function. This is  
why I've adopted the approach of having '1' represent a constant  
function.)

Not sure if that helps at all. Probably not. Feel free to try again...

- John