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?

Parhe

Let me apologize; I wrote that answer, and sometimes I make up good-sounding crap :) I've since learned that Spineless Tagless G-machine does not imply Stackless. – Disinclination

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.

Gaffrigged

Because of its laziness, evaluation is based on graph reduction - really? Is graph reduction necessary for laziness? Or is this just a design decision in some implementations of Haskell runtimes? – Novocaine

There's a lot about this in the haskell wikibook. I don't think it's necessary, but it seems like it's the best way to do it. – Gaffrigged

Would a stackless haskell mean that there wouldn't be instances of stack overflow problems? – Shiri

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

Gnawing