33

I recently stumbled across the book Higher-order Perl, which basically suggests ways to do things in Perl in a functional way. The author explains that Perl has 6 out of 7 core features of Lisp, while C has none.

I had a problem which looked like a good candidate for a recursive solution, and I coded it in this fashion. But Perl complained about "deep recursion". I googled a bit and found a Perl monk explaining that "Perl is not Haskell". Apperently you get a complaint by default, when the recursion depth exceeds 100 levels.

There are ways to extend this limit or to turn it off entirely, but my question is:

  • Is there a reason that Perl is so uptight about recursion, while Haskell is not at all?

4 Answers 4

30

Because in Haskell, we have laziness & guarded recursion and tail call optimization and Perl has neither.

This essentially means that every function call allocates a set amount of memory called "the stack" until the function returns. When you write recursive code, you build up a huge amount of memory because of these nested function calls and eventually can stack overflow. TCO allows the unused chunks to be optimized away.

Without this it's not really a good idea to rely on recursion. For example, say you wrote a recursive version of map, it'd crash with any decent sized list. In Haskell, guarded recursion means that with large lists, the recursive solution is much faster than a "loop" like function.

TLDR: Haskell's implementations are designed to handle a functional/recursive style and perl's implementation is not and back in the good old days, 100 levels of function calls was a sane limit.

8
  • 12
    disagree; while perl doesn't have automatic recursion optimizations, the 100 limit is more from an assumption that it would indicate a program bug than that anything bad would happen (though obviously decades ago memory was more of a concern than now). you can write recursive code, and it will use memory, but not a "huge" amount.
    – ysth
    Dec 20, 2013 at 19:32
  • 6
    Perl does have tail call optimization - it's just not automatic - you need to use the goto keyword to do a tail call.
    – tobyink
    Dec 20, 2013 at 20:42
  • 2
    @tobyink goto isn't a call. But TCO often results in similar code to gotos. Also, if it's not automatic it's not really an implementation optimization Dec 20, 2013 at 20:50
  • 17
    The goto keyword in Perl performs several different duties. goto LABEL acts like a traditional "goto". goto $coderef and goto &subname do a tail call. They wipe all traces of the current sub off the stack and then call the coderef/sub. (In fact, internally they are implemented as an immediate return followed by a normal sub call.)
    – tobyink
    Dec 20, 2013 at 21:00
  • 3
    You can also use Sub::Call::Tail to make much neater tail-call using code.
    – LeoNerd
    Dec 23, 2013 at 16:51
26

The “deep recursion” warning is optional, and an indicator that something may have gone wrong: most of the time, a function calling itself over and over again isn't intended (Perl is a multi-paradigm language, and many people don't use functional idioms). And even when consciously employing recursion, it is far too easy to forget the base case.

It's easy to switch the “deep recursion” warning off:

use warnings;
no warnings 'recursion';

sub recurse {
  my $n = shift;
  if ($n) {
    recurse($n - 1);
  }
  else {
    print "look, no warnings\n";
  }
}

recurse(200);

Output:

look, no warnings

It is true that Perl does not perform tail recursion optimization, because that would mess up the caller output (which is vital for some things like pragmas or Carp). If you want to manually perform a tail call, then

return foo(@args);

becomes

@_ = @args; # or something like `*_ = \@args`
goto &foo;

although bad things can happen if you foolishly localized @_.

4

Runaway recursion will crash either a Perl program or a Haskell program after unbounded allocation eventually exhausts available memory. Both languages deal with this potential pitfall in different ways.


Perl

Perl is a multi-paradigm language but procedural at heart, and deep stack depth in that paradigm can indicate runaway recursion. The perldiag documentation on this diagnostic states as much, emphasis added.

  • Deep recursion on anonymous subroutine
  • Deep recursion on subroutine "%s"
    (W recursion) This subroutine has called itself (directly or indirectly) 100 times more than it has returned. This probably indicates an infinite recursion, unless you're writing strange benchmark programs, in which case it indicates something else.

It is merely a runtime warning, so if you believe it to be spurious, disable it with a pragma.

sub known_deep_recursion {
  no warnings 'recursion';

  ...;
}

A more drastic and evidently unnecessary way to achieve the same effect is described in the same section of the Perl documentation.

This threshold can be changed from 100, by recompiling the perl binary, setting the C pre-processor macro PERL_SUB_DEPTH_WARN to the desired value.


Haskell

Haskell is a purely functional language, where recursion is essential. Writing Haskell tail-recursively, as in

A recursive function is tail recursive if the final result of the recursive call is the final result of the function itself. If the result of the recursive call must be further processed (say, by adding 1 to it, or consing another element onto the beginning of it), it is not tail recursive.

takes advantage of compiler support for lazy evaluation and guarded recursion, which means well written Haskell code can be both concise and have excellent performance.

But Haskell is not immune to runaway allocations related to recursion. Poorly written Haskell code will have stack problems also, as noted on the Stack overflow page on HaskellWiki.

There is no call stack in Haskell. Instead we find a pattern matching stack whose entries are essentially case expressions waiting for their scrutinee to be evaluated enough that they can match a constructor (WHNF).

When GHC is evaluating a thunked [that is, unevaluated] expression it uses an internal stack. This inner stack for thunk evaluation is the one that can overflow in practice.

Haskell does not have a call stack like procedural languages, so these crashes are referred to as space leaks.

Haskell programs will sometimes consume a lot more memory than necessary, and this is often due to too much, or too little, laziness.

For example, the simple Haskell program below

mysum :: [Integer] -> Integer
mysum = foldr (+) 0

main = print (mysum [1..10000000000])

when run on my machine — if it does not on yours, increase the upper bound until it does — results in

mysum: Out of memory

Changing the program to

import Data.List (foldl')

mysum :: [Integer] -> Integer
mysum = foldl' (+) 0
 
main = print (mysum [1..10000000000])

takes a while to run but eventually terminates with the correct result. Reasoning about a Haskell program’s space usage can be tricky for beginners. Rooting out space leaks using the profiler is an advanced topic.


Summary

Both are excellent languages, especially in their respective niches. We programmers sometimes make mistakes. Resource limitations and the halting problem will always be out there conspiring against us. Programming languages deal with these limitations in their own way.

1

The default limit is too low, but was appropriate for the smaller machines Perl originally ran on. Now 100 is laughable if you are doing serious recursive work, but as you say it can be tuned. I assume Haskell has some other way of catching infinite recursion?

5
  • That's more realistic these days. Didn't know it got bumped. Thx. Dec 20, 2013 at 19:05
  • 1
    I would assume that Haskell optimizes tail recursion into a loop. In a more imperative language like perl, you just tell people to write a loop themselves ;) Dec 20, 2013 at 19:05
  • 3
    @UlrichSchwarz Actually haskell has tail call optimization, not just limited to recursion. This isn't possible to fake with just a loop. Dec 20, 2013 at 19:07
  • (Sorry, it hasn't been changed from 100. A similar setting in the debugger was changed to 1000. I meant to change that for Perl's warning too.)
    – ikegami
    Dec 20, 2013 at 19:11
  • 7
    Infinite recursion is not caught in Haskell for exactly the same reasons infinite loops aren't caught in imperative languages.
    – not my job
    Dec 20, 2013 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.