Lazy evaluation and nested thunks eating up memory

Question

I'm working on a tiny lambda calculus engine which I want it to be lazy as Haskell. I'm trying to, at least for now, stick to Haskell's rules so that I don't have to rethink everything, but I don't want to do this blindly.

I understand Haskell will not evaluate a term until its value is needed. Here is my first doubt. I understand a value is "needed" when is an argument to a built in function (so in (func x), x is needed if func is a built in function and (func x) is needed) or because is a function to be called (so in (x y), x would be needed if (x y) is needed).

My second problem is, say I have this recursive function:

let st = \x -> (st x)

The way I've implemented it so far is, if I call this like (st "hi"), "hi" won't be evaluated but wrapped in a thunk which contains the term and its scope, that will be added as "x" to the scope of the body of st. Then, when evaluating st again, another thunk will be created around the x in (st x), which will contain the term x and its scope, which contains another definition of x, that is, "hi". This way, nested thunks will keep building up until I run out of memory.

I tested my code above in GHCI and memory was OK. Then I tested this:

let st = \x -> (st (id x))

and memory built up until the application crashed. So apparently GHCI (or Haskell?) only use thunks when the argument is a function call; in every other case it uses the term's value. Which is something I could easily implement.

Another option I thought of, is not allowing nested thunks by, right before evaluating a function call and creating thunks for the arguments, evaluating the whole current scope to make sure no new thunk will contain another thunk. I think this should still let me create infinite lists and get some (or all?) of the benefits of lazy evaluation, and would even prevent the application from crashing when the let st = \x.(st (id x)) function is called.

I'm sure there are plenty of ways to implement lazy evaluation, but is hard to figure out what the pros and cons of each way is. Is there some list containing the most common implementations of lazy evaluation together with their pros and cons? And also, how does Haskell do it?

Answer 1

This is far from a full answer, but maybe it'll be enough to make progress.

First, the function

let st = \x -> (st x)

binds st to a lambda. This may be a thunk pointing to a lambda, or it may not be (the Haskell Report only specifies non-strict evaluation. If the compiler can prove that evaluating a thunk early doesn't change the semantics of the program, it's free to do so; it's trivial to prove that a lambda in the source code can be evaluated to WHNF without changing the semantics).

Regardless, suppose you force evaluation of st "hi". After applying the lambda (beta reduction), the next step is st "hi". So this beta reduction loops endlessly, but it never creates new data. That is, there's no need to wrap anything in a thunk. So though it loops forever, this application doesn't allocate memory.

Compare this to

let st = \x -> (st (id x))

Here, if we beta reduce:

st "hi"
st (id "hi")
st (id (id "hi"))
st (id (id (id "hi")))

etc. Here, because the argument to st is never evaluated, it builds up an endless chain of thunks wrapping a new id application, consuming increasing memory.

I think the problem you're having with your implementation is that you're wrapping "hi" underneath the lambda. Instead, whatever produces "hi" should create the thunk which then gets passed around until it's evaluated. Then "hi" only gets wrapped once instead of at each step.

Edit: forgot to answer your first question, but I can't do better than @leftaroundabout's suggestion to read up on Weak Head Normal Form. There are other questions on SO too, e.g. Haskell: What is Weak Head Normal Form? and Weak head normal form and order of evaluation