stack overflow vs scheme

[john.holland]

I was studying clojure for a while, and took a break to work on SICP in scheme. I found that they do numerous things that are against advice in Clojure having to do with the tail recursion.
I got to thinking about that Clojure recur/loop stuff and wondered how you would do a quicksort with it. So I went to rosetta code and looked at what they had for scheme and for clojure.


In scheme I can do a quicksort which makes two calls to itself and it can scale pretty high before running out of RAM.  I went up to 10000 sorting from worst (reversed) order to forward order. I do get
stack overflows beyond that though.

In clojure, the same algorithm produces the dreaded StackOverflow after 1000 values.
I tried giving the JVM a gig of RAM, no help.

Below are the (trvial) procedures.

I understand that the advice in clojure is to use loop/recur etc, however, a big part of the charm for me of something like scheme is that I can write code that is a straightforward statement of a mathematical approach to the problem.


Although quicksort is really simple, the idea of doing it with loop/recur baffles me. 

After a while with the scheme stuff clojure seems very complex and this, which seems like a fundamental issue, is not going well for it.

Can anyone post a quicksort that doesn't give stack overflows in clojure?

John

====scheme quicksort============================================

 (define (quicksort l)
(if (null? l)
    '()
    (append (quicksort (filter (lambda (x) (> (car l) x)) (cdr l)) )
            (list (car l))
            (quicksort (filter (lambda (x) (< (car l) x)) (cdr l)) ))))

=================scheme utility to make data sets================
(define (nums x) (if (< x 0) '() (cons x (nums (- x 1)))))

======================scheme call=================
(quicksort  (nums 10000))

===============================clojure quicksort====================
 (defn qsort [[pivot & xs]]
  (when pivot
 (let [smaller #(< % pivot)]
 (lazy-cat (qsort (filter smaller xs))
  [pivot]
    (qsort (remove smaller xs))))))

=================clojure utility to make data sets================
(def nums (fn [lim] (loop [limx lim acc []] (if (< limx 0) acc (recur (- limx 1) (cons limx acc)) ))))

====clojure call==================================================
(quicksort  (nums 10000))

[David Nolen]

If you run out stack in Scheme the code is not properly tail recursive. Who care when it blows?

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[David Nolen]

I didn't mean the response to sound overly curt. You can set the stack size on JVM.

But the point is, that quick sort is simply wrong if you do not want to grow the stack, whether in Scheme or in Clojure.

[Michael Gardner]

Try increasing the JVM's stack size with -Xss.

[Stuart Sierra]

There are versions of Quicksort that don't use recursive function calls. Instead they simulate recursion by maintaining a stack of indices. (Search the web for "quicksort without recursion.") You could do that in Clojure with loop/recur.

-S

[Mark Engelberg]

Here's the simplest way to adapt your code so that it won't blow the
stack. Just shuffle the input list first:

(defn quicksort [l]
(letfn [(qsort [[pivot & xs]]

(when pivot
(let [smaller #(< % pivot)]
(lazy-cat (qsort (filter smaller xs))
[pivot]

(qsort (remove smaller xs))))))]
(qsort (shuffle l))))

[Nils Bertschinger]

Hi,

the Scheme version of quicksort is not tail-recursive since append is
called on the return value of the recursive calls. Thus, also in
Scheme this eats up your stack. That your Scheme code can sort larger
sequences simple means that your Scheme implementation has a larger
stack than the JVM with standard settings.
Basically, the only difference between Scheme and Clojure with respect
to tail-recursion is that Scheme automatically optimizes the recursive
call when it appears in a tail-call position whereas in Clojure you
have to explicitly call recur (or trampoline for mutual recursion) if
you want tail-call optimization.

Since quicksort requires two recursive calls which then have to be
combined it is not completely trivial to implement it in a tail-
recursive, i.e. iterative, fashion. There is a general method which
can be applied, namely continuation passing style (CPS), but it might
look a little odd if you haven't seen it before. Basically, you use a
variable holding a chain of closures which resemble the stack. I found
a rather nice exposition in this blog post:
http://www.enrico-franchi.org/2011/09/clojure-quicksort-in-continuation.html

Cheers,

Nils

[john.holland]

Thanks for all the replies. It seems to me that as  general solutions to stack overflow, trampoline and recur are
very valuable. I had gotten the mistaken idea that Scheme was somehow immune to the problem.
 My experiments in Scheme seemed to get to higher amounts of recursion before blowing up than my Clojure did,
but they are both susceptible to it. Are there things like trampoline and recur in Scheme? In Lisp?

John Holland

[Nils Bertschinger]

Well yes, but they are not explicitly specified since Scheme
automatically optimizes tail calls. Consider this example:
(define (fact n)
(if (< n 2)
1
(* n (fact (- n 1)))))
This is not tail recursive and eventually blows the stack ... in
Scheme and in Clojure.
(define (fact-accu n res)
(if (< n 2)
res
(fact-accu (- n 1) (* n res))))
Here, the recursive call is in tail position and gets optimized by the
Scheme compiler. In Clojure you would have to call recur instead,
otherwise your stack grows. In Scheme this is not necessary since the
optimization is always done if possible. Thus, there is no special
syntactic marker, i.e. reserved word, for this. (Same holds for mutual
recursion <-> trampoline).
In Common Lisp the situation is somewhat unfortunate, since tail call
optimization is implementation dependent. So, you cannot rely on it
and therefore loop/tagbody etc are your friends there.

Hope this helps,

Nils
>
> John Holland

[Peter Danenberg]

Quoth john.holland on Sweetmorn, the 44th of The Aftermath:

> It seems to me that as general solutions to stack overflow,
> trampoline and recur are very valuable. I had gotten the mistaken
> idea that Scheme was somehow immune to the problem.

Trampoline and recur are a poor man's tail-call-optimization; and, if
by "the problem," you mean that a call-stack grows linearly with its
recursive depth: yeah, even Scheme is susceptible to stack-growth if
your calls aren't "properly tail-recursive."

See R5RS s. 3.5 [1], "Proper tail recursion":

A tail call is a procedure call that occurs in a tail context;
e.g. the last expression within the body of a lambda expression.

William Clinger wrote a paper that formalizes proper tail recursion in
more depth [2].

Suffice to say, the na�ve recursive implementation of quick sort
contains at least one non-tail-call; and, just for kicks, here's an
implementation of quicksort in Joy (a so-called concatenative
language):

[small] [] [uncons [>] split] [swapd cons concat] binrec

Joy, too, implements recursion (through `binrec') without growing the
call-stack.

Footnotes:
[1] http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5
[2] ftp://ftp.ccs.neu.edu/pub/people/will/tail.pdf