Re: [stack] recursion is too hard

On Mar 12, 2009, at 1:09 PM, William Tanksley wrote:

> John Nowak wrote:
>
>> William Tanksley wrote:
>>
>> They wouldn't copy it in a real implementation. I only explain it  
>> that
>> way because you can understand it without getting into types.
>
> I know -- "copy the stack" is shorthand for "pass the same starting
> stack to every function, then merge the results together." Only  
> mutable
> stacks need to be actually copied.

Not sure what you mean. I've not proposed anything that would require  
any copying, any sub-stacks, or any persistent stacks. They'd all work  
in Factor with smart combinators. I wouldn't accept anything else on  
efficiency grounds.

>> Ideally, we'd have a 'spread' that just "does the right thing". One
>> way to do this is to allow each quotation access to *only* one value.
>
> This doesn't "do the right thing" in general; Factor's library uses  
> the
> two-argument versions of cleave and spread fairly frequently... If the
> quotations don't all access the stack the same way, neither my  
> solution
> nor a smart combinator will help.

A smart combinator could still work just fine, *and* it could always  
do the right thing without having multiple versions. Really, it can do  
most anything because it knows the effects of the functions involved.  
For example, you could make these work:

    "genius" spread:
    3 6 7 {|sq, +|}  ==  9 13
    3 6 7 {|+, sq|}  ==  9 49

    "genius" cleave:
    3 6 7 [|sq, +|]  ==  3 49 13
    3 6 7 [|+, sq|]  ==  3 13 49

Such "genius" combinators would always do the "right thing" and would  
not require versions for different arities. The only downside is that  
I think it's too hard to read as you need to know the effects involved  
for it to make any sense. Tool support would makes this easier (e.g. I  
could select a region of text and get the stack effect for the  
function it represents), but I think it's probably still intolerable.

Once you permit type introspection, you can go as far as you'd like;  
it's just a matter of it getting too difficult for the programmer to  
keep up. You also throw a lot of the simple reasoning benefits of  
concatenative languages out the window.

- John