Haskell implemented without a stack?

Question

from How does a stackless language work?

Haskell (as commonly implemented) does not have a call stack; 
evaluation is based on graph reduction.

Really? That's interesting, because while I've never experienced it myself, I've read that if you don't use the strict versions of the fold functions and then force the evaluation of an infinite fold you get a stack overflow. Surely that indicates the presence of a stack. Can anyone clarify?

Answer 1

I'm not by any means an expert on this, but I think the answer you quoted is not entirely accurate. Haskell doesn't have the straightforward kind of stack most imperative languages have, where you can trace a path of calls through a program. Because of its laziness, evaluation is based on graph reduction, which you can read about here, but calls are still eventually placed in a stack. According to this page, "The “stack“ in GHC's execution engine bears little resemblance to the lexical call stack." So yes, there's a stack, but it's very different from one you would find in an imperative language, and it's created using graph reduction.

Answer 2

Haskell is not "stackless" or anything like it. Code generated from Haskell source still has some kind of symbols and execution shows some stack traces but they're very loosely related to source code. Here's some information about attempts of simplifying debugging/tracing/profiling:

http://www.haskell.org/wikiupload/9/9f/HIW2011-Talk-Marlow.pdf