Lazy evaluation alternative

[Chris Clearwater]

On Fri, Jan 24, 2003 at 09:18:47AM -0600, Kevin S. Millikin wrote:
> >>>>> "Chris" == Chris Clearwater <chris@sharkzone.com> writes:
> 
>     Chris> LIAR. You want to steal my idea for yourself! It's MINE! :)
> 
> I hate to be the one to break it to you, but we used to routinely show
> this trick to Intro to CS students.

Sarcasm, Kevin, sarcasm. :)

> 
>     Chris> But anyways, it was to show that when a list is defined
>     Chris> like that, (natural m) becomes a list itself because it is
>     Chris> of the form: \c -> c hd tl after partial evaluation.
> 
> Yes.  But it's not the CPS that delays evaluation, it's just the
> lambda. Switching to a strict language, Scheme, one would write:
> 
> > (define ones (lambda () (cons 1 ones)))
> 
> Explicitly delaying the evaluation of (cons 1 ones) by putting it
> under a lambda.  We *could* perform the CPS translation, but it's not
> necessary to delay evaluation, lambda does that all by itself.

The difference is with the CPS way it is implicit. For example take the
Y combinator written using both methods (again this is pseduo code, not
intended to be real haskell code or run in hugs)

Using the lambda way:
Y f = f (lazy Y f)
Then writing ones would be something like:
ones_fix f = 1:(force f)

Now the CPS way:
Y f c = c (f (Y f))
Now writing ones:
ones_fix f c = c 1:f

Notice how the CPS way behaves as if it were actually passed itself, while
the lambda way behaves as if it were passed itself quoted with lambda.
The lambda way seems like a hack while the CPS way feels consistant.

And yes, I still realize that a list can't have a function as a tail.
Pretend it is a custom datatype with a function as a tail. If you want
real code, here is some proof of concept python:

Y = lambda f: lambda c: c(f(Y(f)))
ones_fix = lambda f: lambda c: c(1, f)

def output(hd, tl): print hd, tl
Y(ones_fix)(lambda ones: ones(output))