Mutual recursion in Pure

[Michel S.]

Hello,

I found out about Pure from LLVM 2.5's release notes, and am now in
the process of packaging it for Fedora:

https://bugzilla.redhat.com/show_bug.cgi?id=488563

I'm already involved in packaging LLVM, so pure is a nice test case
for making sure our LLVM build actually works.

So far, I really like what I see -- Scheme-like dynamic typing with
Haskell-style pattern matching. I've not explored the different
evaluation semantics yet.

Mutual recursion appears to be unsupported:

oddp 0 = 0;
oddp n = evenp (n-1);

evenp 0 = 1;
evenp n = oddp (n-1);

evenp 100000;
1

evenp 1000000;
Segmentation fault

as far as I can tell, on my platform at least (x86_64), LLVM's fastcc
function call interface actually supports mutual tail recursion
optimization. Any reason why this example fails?

Thanks,

--
Michel Salim

[Albert Graef]

Hi Michel, welcome to the list!

Michel S. wrote:
> I found out about Pure from LLVM 2.5's release notes, and am now in
> the process of packaging it for Fedora:
>
> https://bugzilla.redhat.com/show_bug.cgi?id=488563

Cool! I added a link to that ticket to our frontpage. If you need any
help please just ask. Will you package the addons, too?

BTW, there's a nice and complete set of SUSE RPMs over at Packman
(http://packman.links2linux.de/search?scope=name&q=pure-). If nothing
else, you might want to check out Toni's specs for hints on how to build
things, especially the big generated interfaces like pure-gtk.

> I'm already involved in packaging LLVM, so pure is a nice test case
> for making sure our LLVM build actually works.

It's the first time I hear that Pure is being used as a test case for
LLVM. ;-) I guess that this is more convenient than running 'make check'
on LLVM... But please note that Pure doesn't really stress-test all of
LLVM's features. For a quick check it should do the trick, though.

> Mutual recursion appears to be unsupported:

Please RTFM:
http://pure-lang.googlecode.com/svn/trunk/pure/pure.html#stack-size-and-tail-recursion

Especially the last paragraph in that section.

The problem is not with LLVM or Pure's use of it, Pure already makes use
of LLVM's TCO facilities when it's possible. In fact your example will
work just fine if you use local functions instead:

evenp 1000000 with

oddp 0 = 0;
oddp n = evenp (n-1);
evenp 0 = 1;
evenp n = oddp (n-1);

end;
1

Local functions are always invoked through (LLVM-generated) direct
calls. Calls to *global* functions are handled indirectly through the
runtime, however. This is necessary because of Pure's highly dynamic
nature, which allows you to patch up the definition of a global function
with new equations at any time.

Now the runtime is written in (supposedly portable) C/C++, and thus it
cannot do tail calls. It might be possible to work around this
limitation with gcc (not sure how), but this depends on the available C
ABI on the target platform. I'm open to suggestions there. If you have
an idea how to fix this issue, please let me know.

This should probably go into the FAQ...

> evenp 1000000;
> Segmentation fault

Set PURE_STACK in your shell environment to get rid of the annoying
segfault and get an orderly Pure exception instead. This *is* in the FAQ
already. :)

Cheers,
Albert

--
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email: Dr.G...@t-online.de, a...@muwiinfa.geschichte.uni-mainz.de
WWW: http://www.musikinformatik.uni-mainz.de/ag

[John Cowan]

Albert Graef scripsit:

> Now the runtime is written in (supposedly portable) C/C++, and thus it
> cannot do tail calls. It might be possible to work around this
> limitation with gcc (not sure how), but this depends on the available C
> ABI on the target platform.

Try using the switch -foptimize-sibling-calls. This will induce gcc
use tail-call optimization for direct C calls to functions in the same
translation unit. This may or may not help, only works in some
versions of gcc, is architecture-dependent, and (like most optimizations)
sometimes pessimizes your code.

--
Here lies the Christian, John Cowan
judge, and poet Peter, http://www.ccil.org/~cowan
Who broke the laws of God co...@ccil.org
and man and metre.

[Michel S.]

On Mar 5, 8:42 am, John Cowan <co...@ccil.org> wrote:
> Albert Graef scripsit:
>
> > Now the runtime is written in (supposedly portable) C/C++, and thus it
> > cannot do tail calls. It might be possible to work around this
> > limitation with gcc (not sure how), but this depends on the available C
> > ABI on the target platform.
>
> Try using the switch -foptimize-sibling-calls.  This will induce gcc
> use tail-call optimization for direct C calls to functions in the same
> translation unit.  This may or may not help, only works in some
> versions of gcc, is architecture-dependent, and (like most optimizations)
> sometimes pessimizes your code.
>

This is enabled by default when compiling with -O2 or higher, so
that's not a problem.

Thanks for your replies! I'll start on the libraries when the
interpreter gets approved.

One question: is there no runtime dependency of pure on LLVM?
Requirement shown below:

Thanks,

--
Michel Salim

$ rpm -q --requires pure
libc.so.6()(64bit)
libc.so.6(GLIBC_2.2.5)(64bit)
libdl.so.2()(64bit)
libdl.so.2(GLIBC_2.2.5)(64bit)
libgcc_s.so.1()(64bit)
libgcc_s.so.1(GCC_3.0)(64bit)
libgcc_s.so.1(GCC_3.4)(64bit)
libgcc_s.so.1(GCC_4.0.0)(64bit)
libgmp.so.3()(64bit)
libgsl.so.0()(64bit)
libgslcblas.so.0()(64bit)
libm.so.6()(64bit)
libm.so.6(GLIBC_2.2.5)(64bit)
libpthread.so.0()(64bit)
libpthread.so.0(GLIBC_2.2.5)(64bit)
libpure-0.18.so()(64bit)
libreadline.so.5()(64bit)
libstdc++.so.6()(64bit)
libstdc++.so.6(CXXABI_1.3)(64bit)
libstdc++.so.6(GLIBCXX_3.4)(64bit)
libstdc++.so.6(GLIBCXX_3.4.11)(64bit)
libstdc++.so.6(GLIBCXX_3.4.9)(64bit)
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rtld(GNU_HASH)

[Albert Graef]

John Cowan wrote:
> Try using the switch -foptimize-sibling-calls. This will induce gcc
> use tail-call optimization for direct C calls to functions in the same
> translation unit. This may or may not help, only works in some
> versions of gcc, is architecture-dependent, and (like most optimizations)
> sometimes pessimizes your code.

It won't work at all in this case, because the function being called by
the runtime function is a variable (function pointer). :-P

[Albert Graef]

Sorry, I missed that one.

Michel S. wrote:
> One question: is there no runtime dependency of pure on LLVM?
> Requirement shown below:

No, LLVM is only required at build time. The LLVM libs are static ones,
and these get linked into the Pure runtime library. (That's why
libpure.so is so big.)