[Nickle] Mutual tail-recursion

[Bart Massey]

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
usual.

> 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;};

Just
  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,
actually...

> 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