Re: [stack] disallowing recursive definitions

On Thu, Feb 28, 2008 at 3:44 PM, John Cowan <[email protected]> wrote:
> John Nowak scripsit:
> > Recently, I mentioned that if you disallow recursive definitions, then
> > definitions can be thought of as macros or rewrite rules.
>
> Sure, but then you can only compute primitive-recursive functions
> (roughly speaking, ones in which all loops are bounded at compile time).

I don't believe this is true. The approach I take is to pass the
function definition as a named parameter to the function, and perform
the point-free conversion.

In Cat I can write the fibonnacci function (a tree recursive
procedure) to take its body as an argument:

>> define fibrec { \f.\n.[n 1 <= [1] [f n 1 - f apply f n 2 - f apply +] if] }

Which my horrible horrible abstraction algorithm translates to:

[dup dup [[[dup dup dup] dip [[[[id 1 <= [1]] papply dip] papply dip]
papply dip] papply dip] dip] dip [[[[[[id] dip id 1 -] papply dip id
apply] papply dip id] dip id 2 -] papply papply dip id apply +] papply
papply papply papply papply papply if]

>> define fib { fibrec swap fibrec apply }
>> 5 fib
8

Incidentally this managed to completely corrupt my type checker, thanks a lot!
:-)

- Christopher