Re: [stack] recursion is too hard

On Mar 12, 2009, at 5:32 AM, Chris Double wrote:

> On Thu, Mar 12, 2009 at 10:18 PM, John Nowak <[email protected]>  
> wrote:
>>
>> Not sure how locals would fix this particular problem. In the example
>> I gave, the function provided was already pulled in via substitution.
>> Maybe you can give an example so I can understand what you mean.
>
> I didn't actually understand your example, sorry. Can you break down
> your example, explaining what each word does and what stack effect it
> has?

Sure thing.

    map(F) = ifte(null?, id, uncons spread(F, map(F)) cons)

1. 'map(F) = ...' declares a second-order function named 'map' that  
takes some statically-known function 'F' as an argument

2. 'ifte' is the same as Joy's 'ifte' function; the first argument is  
the conditional, the second is the "then" branch, and the last is the  
"else" branch; the stack is saved before the conditional and restored  
for the "then" or "else" branch

3. 'id' is the identify function

4. spread(F, G)  ==  dip(F) G

5. 'uncons' takes a list and returns the head of the list and the tail  
of the list (with the tail on the top of the stack); 'cons' does the  
reverse

The equivalent code in Factor would be as follows, with the exception  
that the function wouldn't actually be passed on the stack:

    : uncons ( xs -- x xs ) [ first ] [ rest ] bi ;
    : cons ( x xs -- xs ) ... ; ! the inverse of 'uncons'
    :: map ( xs f -- ys )
       xs dup [ empty? ] [ ] [ uncons [ f ] [ f map ] bi* cons ] if ;

- John