[Nickle] Mutual tail-recursion

Bart Massey bart at po8.org
Sat Feb 18 22:40:50 PST 2006

In message <883cfe6d0602182133j4c18f9a3s at mail.gmail.com> you wrote:
> I just learned of Nickle's existence earlier today (thanks to a
> reference by Lambda-the-Ultimate user po8, real identity unknown,
> though he seems to be involved here)

That's me :-).  Sorry for the whole 'nym thing; always hard
to know whether to just use a real name in these situations.
After all, I might say something even more stupid than

> and I'm finding it quite
> interesting (being able to print function definitions is really nice
> for prototyping and learning APIs)

Glad you like it!

> As per my standard practice when trying out languages with functional
> programming features, I subjected Nickle to recursively testing
> evenness:
> /* there's probably a better way to forward-declare a function */
> oddp = bool func(int n) { return false;};

  bool oddp(int);
will work. :-)

> evenp = bool func (int n) { if (0==n) return true; else return oddp(n-1); };
> oddp = bool func (int n) { if (0==n) return false; else return evenp(n-1); };

bool evenp(int n) { if (0==n) return true; else return oddp(n-1);}
bool oddp(int n) { if (0==n) return false; else return evenp(n-1);}

> Doing this in GCC, if I remember correctly, results in a stack
> overflow at n ~= 140000, unless sibling-call optimization is turned
> on. Nickle surprisingly managed to compute the result of testing n =
> 10 million, though the memory usage gets disquieting at that point. A
> byproduct of the call "stack" actually being heap-allocated to support
> continuations?

Call frames are indeed heap-allocated to support
closures/continuations, but this sounds more like a bug---we
(try to) do full tail-call.  I can't entirely reproduce the
bug, though.  With n=1e7 I get a response in maybe 20
seconds and end up with about 20M of memory used.  Further
runs at that level don't increase the memory, so it doesn't
seem to be a straight leak.

> My questions are, then:
> - Is tail optimization of mutually-recursive functions planned?

Already done.  Tail-call analysis is fun. :-)

> - Garbage collecting: after doing evenp(10000000) nickle was consuming
> 67.3% of 1.4GB of RAM. after about 10 minutes this has only gone down
> to 67.0% .. should it be holding on to the memory for that long? Is
> there a way to request a collection?

You can invoke the garbage collector with Debug::collect(),
although this is highly non-intuitive. :-)

> Also, I'll probably propose Nickle for submission to Fedora Extras
> (surprisingly, the original RPM spec was written by none other than
> Mike Harris, Red Hat's X developer).

Yeah, since Keithp is involved, we get a lot of those. :-)

> Is there any runtime dependency
> on the header files? I'm currently splitting the header files to a
> -devel package.

I'm not sure the header files are good for anything,

> PS the turtle/snowflake.5c and menace2.5c have their executable bits
> incorrectly set.

Ahh.  I'm guessing you're installing from the latest
"release" tarball---we discourage this. :-( Build from CVS
top of tree and let us know if you still have that bug on
your system. :-) For a 20-year-old language, we sure have an
immature release process.  Our apologies.

We're moving Nickle to GIT in the *very* near term.  Once I
do that, we'll check all the permissions and fix them.

Thanks for the feedback, and please continue to let us know
as you find bugs or misfeatures!

    Bart Massey
    bart at cs.pdx.edu

More information about the Nickle mailing list