Re: [stack] recursion is too hard

John Nowak wrote:
> William Tanksley wrote:
> > John Nowak wrote:
> >>    map(F) = ifte(null?, id, uncons spread(F, map(F)) cons)
> >> Can you spot the problem? Is there a *general* method for avoiding  
> >> it?
> The problem is that all calls to 'F' except the first see the values  
> meant to be later consed onto the list from previous calls of 'F'. One  

Got it (sorry, I was busy).

> My alternative "elegant" solution to this is a spread combinator  
> variant that hides the result of the first function from the second.  
> Slava has said this is possible to implement efficiently using smart  
> combinators.

> Despite some strong reservations about having semantics depend on  
> types or stack effects, I think that smart combinators should probably  
> be used more heavily. Producing better smart combinators is probably  
> the most interesting "practical" research topic that could be worked  
> on in the context of stack-based languages at the moment. I hope  
> someone here is interested in pursuing it.

With a first-order language like yours, smart combinators make a lot of
sense. With Factor's combinators it's a little harder to justify
(although, again, it's possible).

My preference is to rethink the combinator to not _need_ to be so smart.
The first "smartness" these combinators have is that they share the
stack between all the executions (some of your variants copy the stack,
which I absolutely hate).

The first thing I'd want is to _completely_ isolate the functions from
each other by running each infra their own fresh stack. The problem then
becomes how to get the data into each combinator, and how to pull it
out.

My first knee-jerk solution is to have the programmer provide two
_additional_ quotations, one that runs before each quotation on the main
data stack to return a tuple that'll be used as the infra stack and the
other one to run after after each quotation on the result stack of each
quotation and return a tuple that'll be expanded onto the stack after
the entire execution.

: split-dataflow-parallel ( before-each {quotations} after-each -- ?? )

I've named it "-parallel" simply because the quotations themselves have
no effect on each other. A "-sequential" version would work like
Factor's current combinators in allowing each quotation to access
previous work (but would give the same problem in Nowak's case).

Some specialized variants are imaginable.

 * obviously a version that required each quotation to take and produce
a single array wouldn't require any before-after quotations (at the cost
of the array production and consumption code in each quotation, and at
the cost of "manually" adding the desired arguments to an array before).

 * Using type inference, we can obviously make a smart variant. I agree
with you that smart combinators are a little tricky, but perhaps if we
understand the "dumb" underlying combinator well enough this one'll
work.

> - John

-Wm