[stack] recursion is too hard

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.