Re: [stack] disallowing recursive definitions

On Feb 28, 2008, at 6:47 PM, Joe Bowbeer wrote:

> As a former Schemer and fan of continuations, I'm conditioned to  
> view (tail)
> recursion as the simpler, more powerful concept.  Not looping.

I have a Scheme background as well.

> Functional programming languages rely on recursion and still boast of
> referential transparency: the ability to substitute function  
> applications by
> their definitions.  But they don't take the substitution as far as  
> you'd
> like to...

Indeed.

> Functional languages favor recursion over looping because looping
> traditionally requires a loop variable whose value changes: a side  
> effect.

What's surprising is how easily the stack lets you write code in an  
imperative style while remaining purely functional. Here's a small  
example where, given a natural number, we construct a list from 1 to  
that number:

    ; Scheme, via recursion

    (define (foo n)
      (let f ((n n) (xs '()))
        (if (zero? n)
            xs
            (f (- n 1) (cons n xs)))))

    ; Joy-like, via recursive combinator

    foo = null swap ((cons) keep pred) (zero?) until pop

    ; Another Joy-like version
    ; (prec :: A int int (A int -> A) -> A)

    foo = null swap 1 (cons) prec

- John