recursion and JVM stack

[gedden]

Hi,

I am new to clojure and lisp coming from functional programming where
I have played with mainly erlang for a while. But what I really want
is to have functional programming on the JVM

One of the issues I have had with java and functional programming is
that the calling stack is so small in the JVM. With the default
stacksize A recursive program breaks down after just a few thousand
recursions.

A program that would process a little file on a character by character
basis will be impossible, if the file is larger than 5k.

Of course, you can increase the stack with a JVM startup parameter,
but this will apply to every thread in your program and seems to be
kind of preallocated, so it will soon eat all resources in your
system.

This, I percieve as a major roadblock for using the JVM for functional
programming. If you have to start thinking about workarounds for
recursion every time you need to process a list, then you have quickly
lost the productivity gains ...

Recently, I noticed Clojure, and thought, great, this will solve my
problems. But it seems, the use of stack space is just as
simpleminded.

First thing I implemented was foldr, (similar to reduce but starting
from the back of the list). foldr is not tail recursive. My recursive
call breaks down (stack overflow) after just 4-5000 recursions.

Being new to lisp, I have to ask, is this really acceptable in the
lisp world? Is it not the intension to use recursion instead of
loping. Surely, you cannot be expected to rewrite all your problems
into tail recursive representations?

How do you cope with the lack of tail recursion in closure?

And, would it not be possible to implement closure in a way so it did
not eat java stack space, but instead allocated its own stack from the
heap ?

[gedden]

Sorry, a little correction,

What I meant was:

How do you closure-lispers get around the stack limitations?

(and not, how do you live with the lack of tail recursion)

gedden

[Chouser]

On Sun, Jun 1, 2008 at 10:38 AM, gedden <sgro...@gmail.com> wrote:
> First thing I implemented was foldr, (similar to reduce but starting
> from the back of the list). foldr is not tail recursive. My recursive
> call breaks down (stack overflow) after just 4-5000 recursions.

(defn foldr [f s] (reduce f (reverse s))

Of course that's just one case, but it is a useful example. In this
case the problem of deep recursion is avoided by using a
tail-recursive function (reverse) to build the data structure we need
so that we can use another tail-recursive function (reduce) to get our
answer.

In other cases you may be able to solve the problem using lazy functions.

In practice it turns out to be rare that you have to break down and
use iteration.

--Chouser

[Rich Hickey]

I think most of us never encounter stack limitations. And that does
imply that we are usually not using recursion to process lists, except
by doing so lazily, using lazy-cons, where that is appropriate.

Otherwise, there is a good library of higher-order lazy sequence
functions, map/reduce(foldl)/filter etc. foldr can be defined in terms
of reverse and reduce.

Clojure could have been implemented with a heap-based stack, with a
cost in performance and call-compatibility with Java. I chose not to
do so, and am very happy with the results. It's not an aspect of
Clojure that is going to change.

I hope you appreciate that functional languages can differ - lazy/
strict, interpreted/compiled, statically/dynamically typed etc.
Clojure, a compiled, strict (but with lazy sequences), dynamically
typed language with an intimate relationship with its host platform
sits at a unique point. As such, it has its own set of idioms.

I recommend you take a look through boot.clj. After a brief stint at
the top where the language bootstraps itself on top of very little,
the remaining code is generally idiomatic Clojure, and should give you
a feel for how to get things done.

Rich

[cliffc]

Lobby Sun to put tail-call optimizations into HotSpot.

Cliff

[Rich Hickey]

On Jun 2, 10:51 am, cliffc <cli...@acm.org> wrote:
> Lobby Sun to put tail-call optimizations into HotSpot.
>

I'm all for it, and have done. Unfortunately, they seem to be more
focused on the needs of JRuby/Jython/Groovy, none of which seem the
least bit interested, as such recursive tail-calling would be non-
idiomatic in those languages.

Of course, were the JVM to do pervasive or guarantee-able TCO, such
recursion might become idiomatic, even in Java.

Rich

[Randall R Schulz]

On Monday 02 June 2008 08:35, Rich Hickey wrote:
> ...

>
> I'm all for it, and have done. Unfortunately, they seem to be more
> focused on the needs of JRuby/Jython/Groovy, none of which seem the
> least bit interested, as such recursive tail-calling would be non-
> idiomatic in those languages.

I wonder if the Scala principals might be natural allies in this matter?
Have you contacted them?

> ...
>
> Rich

Randall Schulz

[MikeM]

> I'm all for it, and have done. Unfortunately, they seem to be more
> focused on the needs of JRuby/Jython/Groovy, none of which seem the
> least bit interested, as such recursive tail-calling would be non-
> idiomatic in those languages.
>

Have you seen this ? http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm

Nutter's comments seem to support adding tail-calls to the JVM.

[Dudley Flanders]

I don't think they're opposed to adding tail-calls, but it's not very
high on their list of priorities. In the MLVM[0] project they've
listed it as medium[1].

:dudley

[0] http://openjdk.java.net/projects/mlvm
[1] http://openjdk.java.net/projects/mlvm/subprojects.html