The Lambda Calculus and Lazy Evaluation

For quite some time I've been looking into building a programming language that is both functional and supports lazy evaluation.  I may not have the energy to actually write the code, but I do keep thinking about it.

First thing I should have realized earlier: studying the theoretical foundations of functional languages (ie. The lambda calculus) would help me achieve my goals.

First, what is lazy evaluation?  Essentially, an expression is only evaluated as long as the calculations lead to the final result.  In a Haskell-like fictional language, I would say function "Pi" calculates Pi to an infinite number of digits.  Then "take 100 Pi" would take the first 100 digits of Pi and stop computing any further digits.

My initial mental model of this process was very convoluted.  Essentially, requiring back-tracking on the stack.  Now, looking at the lambda calculus, it makes a lot more sense.

Recall that the lambda calculus consists of a series of variables and production rules.  Rules are of the form: \xy.yx, where \ is a make-shift lambda, xy are the input, and yx the output.  Essentially flipping the values.

Execution in a functional language starts with a function.  Let's call it R.  Well, R does nothing on its own, so let's evaluate it.  We get T 3 P.  Yup, same as the pseudo-Haskell above, except 3 digits.  Let's try parsing this.

First, some syntax.  : means element in a list.  So x:P means x is the first element from P...

I expand it to something like:

(a:b:c.P)

At each step in T n, we take the head of the list from P and recursively call T (n-1).  In the end, we are matching a set of 3 elements to the infinite list P.  Notice that once P evaluates 3 elements, the matching is complete and any further evaluation of P is not needed.

This is what escaped me!  That means structured properly I could evaluate and match expressions and get lazy evaluation for free!  Or so I believe.  I'll keep on reflecting on the corner cases, but for now "early match and discard" seems to do the trick.