[Nickle] Mutual tail-recursion

Keith Packard keithp at keithp.com
Mon Feb 20 09:36:12 PST 2006

On Mon, 2006-02-20 at 08:37 -0500, Michel Salim wrote:

> Ah, OK. That's rather interesting - so an anonymous function
> declaration bound to a variable (oddp = bool func (int n) {return
> false;}; ) is not *exactly* identical as a type signature declaration
> (bool oddp(int); ) ?

What you have done is effectively:

> poly oddp = bool func (int n) { return false; };

We allow variable declarations at the top level to leave off the type
declaration for convenience. If, instead, you had done:

> bool(int n) oddp = bool func (int n) { return false; };

then 'oddp' would have had the precise type needed to skip the
typechecking on the recursive returns. The short hand notation:

> bool oddp (int n) { return false; }

is just syntactic sugar for the second form.

> It seems that the run-time typechecking could be optimized (though
> it's probably not worth the trouble): since in this case evenp and
> oddp are called recursively every other function call, if the virtual
> machine could detect that this is the case, then perhaps the type
> checking could be deferred to the innermost evenp and oddp call? (this
> gets more complicated in case there are >2 functions that call each
> other, but for a function f, for every pair of (f, g_n) only the
> innermost f needs to typecheck the return value of g_n.

There's nothing preventing you from reassigning a new value to 'oddp' or
'evenp' after the functions have been compiled, so the only opportunity
for optimization is to check the return type for the dynamically bound
values and conditionally tail-call. With the proper types declared at
compile time, there isn't any way you can assign a function that would
have the wrong type afterwards.

keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : /pipermail/nickle/attachments/20060220/1d4deecd/attachment.pgp

More information about the Nickle mailing list