recursion is too hard

[John Nowak]

A non-controversial title...

One issue I have with stack-based languages is that operating on  
recursively-defined data structures is awkward and has subtle  
pitfalls. To keep this simple, I'll use a list; this problem is only  
magnified with more complex structures however.

Assume these operations (where curly braces denote lists):

    cons   = \((s, x), xs) -> (s, x:xs)
    uncons = \(s, x:xs) -> ((s, x), xs)

Here's an implementation of 'map' in a second-order concatenative  
language; I use the second-order approach as 'map' with a first-class  
function is more difficult and obscures the issue:

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

Can you spot the problem? Is there a *general* method for avoiding it?

To prove my point that the stack is to blame, I note that the exact  
same definition in a language that uses tuples to bundle elements only  
when necessary does not have the same problem. Its primitives would  
work as follows:

    cons   = \(x, xs) -> x:xs
    uncons = \(x:xs) -> (x, xs)

- John

P.S. Apologies for the Haskell, but I needed a uniform syntax for  
giving the semantics of the primitives in both languages.

[John Nowak]

On Mar 9, 2009, at 5:41 PM, John Nowak wrote:

> Assume these operations (where curly braces denote lists):
>
>    cons   = \((s, x), xs) -> (s, x:xs)
>    uncons = \(s, x:xs) -> ((s, x), xs)

Sorry. Ignore that parenthetical. ':' denotes 'cons' and (,) denotes a  
tuple as in Haskell.

- John

[William Tanksley, Jr]

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?

I hope you get a clueful reply. I'll speak for all whose answer is "no"
to say, "no, I don't spot the problem."

> - John

-Wm

[John Nowak]

On Mar 9, 2009, at 6:06 PM, 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?
>
> I hope you get a clueful reply. I'll speak for all whose answer is  
> "no"
> to say, "no, I don't spot the problem."

I'll give a (big) hint then. Here's the fixed version:

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

- John

[John Nowak]

On Mar 9, 2009, at 6:06 PM, 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?
>
> I hope you get a clueful reply. I'll speak for all whose answer is  
> "no"
> to say, "no, I don't spot the problem."

Alright, if no one will bite...

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  
solution is to swap the values out of the way, call 'map(F)' below the  
values to be later consed on, and then swap them back before the cons:

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

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.

- John

[Chris Double]

On Thu, Mar 12, 2009 at 7:35 PM, John Nowak <john@...> wrote:
> 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'.

So is this the issue whereby you want the quotation passed to 'map' in
the Factor example below to be able to access the values on the stack
to use in the calculation?

5 { 1 2 3 } [ over + ] map nip
 => { 6 7 8 }

Combinators require that calls to the quotation can't see
implementation details on the stack and this makes them hard to write?
Of so, I agree and I often fall back to locals to implement them (in
Factor).

Chris.
--
http://www.bluishcoder.co.nz

[John Nowak]

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

> On Thu, Mar 12, 2009 at 7:35 PM, John Nowak <john@...>  
> wrote:
>> 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'.
>
> So is this the issue whereby you want the quotation passed to 'map' in
> the Factor example below to be able to access the values on the stack
> to use in the calculation?

Yes; or at least not have access to intermediate states of its own  
computation.

> 5 { 1 2 3 } [ over + ] map nip
> => { 6 7 8 }
>
> Combinators require that calls to the quotation can't see
> implementation details on the stack and this makes them hard to write?
> Of so, I agree and I often fall back to locals to implement them (in
> Factor).

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.

- John

[Chris Double]

On Thu, Mar 12, 2009 at 10:18 PM, John Nowak <john@...> 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? I don't know what 'spread' does and I didn't know whether the
language given is like joy, in that it preserves the stack, or like
Factor, in that it doesn't.

Chris.
--
http://www.bluishcoder.co.nz

[John Nowak]

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

> On Thu, Mar 12, 2009 at 10:18 PM, John Nowak <john@...>  
> 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

[William Tanksley, Jr]

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

[John Nowak]

On Mar 12, 2009, at 11:05 AM, William Tanksley wrote:

> 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).

They wouldn't copy it in a real implementation. I only explain it that  
way because you can understand it without getting into types.

> 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.

The problem is that this is just a pain in the ass to use.

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.  
The results of the quotations would then be concatenated to the main  
stack. More precisely, it would work as such:

    S {T} cat  ==  S T
    S `x `y [F] [G] jn-spread  ==  S {`x F} cat {`y G} cat

This is simple and doesn't require you to explain things in terms of  
types. The downside is that F and G can't access the rest of the  
stack. The only way to make this happen is to use "smart" combinators  
that only make sense if you know the types. Such combinators would  
need to inspect the types of the functions they were given in order to  
work properly. I can give a description of how this might work if  
anyone is interested, but it's downright tedious to explain so I won't  
do it here.

Instead of the type-introspective approach, an easy workaround is to  
provide a 'spread-with' word that takes another argument which is a  
stack to use in both quotations:

    S x y {T} [F] [G] jn-spread-with  ==  S {x T F} cat {y T G} cat

It's true that neither of these suggestions would make writing a  
Factor-style map that uses the entire stack as an accumulator easier  
to write. The type-introspective version would, but given that I don't  
even want to explain it, I can't imagine I'd endorse using it.

I should also note that none of these suggestions are currently  
typeable because they would require row variable concatenation.

- John

[William Tanksley, Jr]

John Nowak wrote:
> William Tanksley wrote:
> > 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).

> 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.

> > 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.

I still think this is the essential part of any solution.

> > 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.

> The problem is that this is just a pain in the ass to use.

I should have emphasised this -- my "knee-jerk solution" is AKA a
"programmer wants to code a solution before understanding the problem".
Yes, it's a PITA to use, which is characteristic of attempts to
construct a generalized solution to a non-problem.

However, in order to understand the problem, it helps to understand it
in general. (Sadly, my quickly constructed idea isn't _fully_ general.)

> 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.

> This is simple and doesn't require you to explain things in terms of  
> types. The downside is that F and G can't access the rest of the  
> stack. The only way to make this happen is to use "smart" combinators  
> that only make sense if you know the types.

Not completely true -- my solution can also allow access to "the rest of
the stack" without a smart combinator, so long as all the parallel
quotations access the stack the same way. The 'before-each' quotation
provides that access.

If the quotations don't all access the stack the same way, neither my
solution nor a smart combinator will help.

> Such combinators would  
> need to inspect the types of the functions they were given in order to  
> work properly. I can give a description of how this might work if  
> anyone is interested, but it's downright tedious to explain so I won't  
> do it here.

Nope, I already know how they work -- essentially, they'd infer the
stack effects and generate a before-each and after-each function :-).

> Instead of the type-introspective approach, an easy workaround is to  
> provide a 'spread-with' word that takes another argument which is a  
> stack to use in both quotations:
>     S x y {T} [F] [G] jn-spread-with  ==  S {x T F} cat {y T G} cat

That seems (in general) harder than writing before-each and after-each,
actually.

> I should also note that none of these suggestions are currently  
> typeable because they would require row variable concatenation.

Except mine -- we talked about that earlier.

> - John

-Wm

[John Nowak]

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