Re: [stack] sweetening concatenative syntax

On Mar 7, 2008, at 3:13 PM, William Tanksley, Jr wrote:

> John Nowak <[email protected]> wrote:
>> William Tanksley, Jr wrote:
>>>> Small point: You forgot the initial swap to put the list on top of
>>>> the stack. The type system would've saved you of course.
>>> I didn't forget it; I was imitating your lambda code, in which the
>>> list is already on top of the stack. Isn't that what "xs -> f i"
>>> implies? So is your lambda code also wrong?
>
>> No, it's correct. The list wasn't already on the top of the stack,  
>> the
>> function was. By binding the function to 'f', we remove it from the
>> stack, causing the list to be on top. This is why the call to  
>> 'unlist'
>> makes sense.
>
> The *function*?? I'm confused. The function can't possibly be at the
> top of the stack. Here's your code (slightly bugfixed).
>
>>   f map = [pop nil]
>>           [xs -> f i xs f map cons]
>>         unlist

Er, almost. It does need to call 'nil' in the first quote, but not  
pop. (Maybe it *was* buggy before as I forgot the null, I can't even  
recall at this point.)

Perhaps I should break it down so this is all crystal clear.

Here's the type for map:

    map :: {a} [a -> b] -> {b}

What this says is that the top element of the stack must be a  
function. The element below the top must be a list. If the list is of  
elements of type 'a', the function must be one that can transform  
elements of type 'a' to type 'b'. The result of calling map is then a  
list of type 'b'.

Alright, so when we're writing the map function, we have to keep in  
mind that the function passed in will be on top of the stack.

Now let's review the type of unlist again:

    unlist :: A {b} [A -> C] [A b {b} -> C] -> C

This is somewhat complicated. What it says is that the top two items  
on the stack must be functions. The third item must be a list. The  
function on top of the stack gets called with the list unconsed if the  
list is not null. The other function gets called with nothing on the  
stack if the list is null. 'A' and 'C' represent "the rest of the  
stack". It isn't too important to full understand them here.

Here's a quick example that might help:

    add-ignoring-list  = 1 2 null        [+] [pop pop +] unlist
    add-ignoring-list2 = 1 2 {"hi" "lo"} [+] [pop pop +] unlist

(The curly braces indicate a list literal.)

Both functions will return "3". In the first, the list is null, so +  
is just called on the stack '1 2' (the list has been permanently  
killed at this point). In the second, the list is not null, so the  
other function gets called with the list unconsed. At this point, the  
stack is '1 2 "hi" {"lo"} null'. After we pop twice, we add 1 and 2  
together yielding 3.

If you go back now and look at the type, maybe it makes some sense.

So let's look at pointfree map again:

    map = swap
          [pop null]
          [rot dup 2dip map cons]
        unlist

Now when map gets called, the function supplied to map will be on the  
top. Therefore, the first thing we need to do is 'swap' so that the  
list is on top as unlist needs it as the third argument. After the  
swap, the stack looks something like this:

    <fn> <list of a>

We then push on the quotations:

    <fn> <list of a> [pop null] [rot dup 2dip map cons]

And then we call unlist. Now if the list is null, we get this scenario:

    <fn> pop null

In that case, we pop the function and push on a new null list.  
Therefore, mapping a function over null yields null.

Now, if the list isn't null, we get this scenario:

    <fn> a <list of a> rot dup 2dip map cons

So we rotate and dup:

    a <list of a> <fn> <fn> 2dip map cons

2dip is the same as dip except that it saves and restores the top two  
elements instead of only the top element. This is the same as '2keep'  
in factor (I think). Therefore, 2dip calls the top function with the  
list and the other function off the stack, and then restores them when  
finished. So we get something like this, where 'fn(a)' is the result  
of applying 'fn' to 'a':

    fn(a) <list of a> <fn> map cons

Right, so now we're back in the situation with a function on top and a  
list below it. We can call 'map' again. It should be understandable  
from this point on I think.

Now let's look at the pointful translation:

    f map = [null]
            [xs -> f i xs f map cons]
          unlist

This version of 'map' binds the top element passed to 'map' to 'f'. As  
before, the top element passed to map must be a function, so we bind  
this function to 'f'. This binding in effect *removes* the function  
from the stack. Therefore, when map gets called, we have something  
like this:

    <list of a>
    f = <fn>

Right. So the list is on the top and the function is in 'f'. Now we  
push on the quotations:

    <list of a> [null] [xs -> f i xs f map cons]
    f = <fn>

Assuming the list is null, we get this scenario:

    null
    f = <fn>

And so the final result is null as we want after evaluating 'null' to  
push a new null onto the stack.

If the list isn't null, we get this:

    a f i xs f map cons
    f  = <fn>
    xs = <list of a>

Normally '<list of a>' would be on the stack above 'a' (as before),  
but we bind the top element to 'xs' instead. Evaluating 'f' then  
pushes 'f' onto the stack and 'i' calls it to apply it to a. We then  
have this:

    fn(a) xs f map cons
    f  = <fn>
    xs = <list of a>

So we go ahead and push on 'xs':

    fn(a) <list of a> f map cons
    f  = <fn>
    xs = <list of a>

And then 'f':

    fn(a) <list of a> <fn> map cons
    f  = <fn>
    xs = <list of a>

And then you can see we are right where we were before the recursion  
in the pointfree example.

If you managed to read that, hopefully it cleared things up a bit. If  
it helps, you can think of lambdas as a more powerful shuffle  
notation. Where you might write 'abc--cabb', you can write '[a b c ->  
c a b b] i' instead.

- John