Re: Lazy evaluation alternative
"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. 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.
ones #<procedure> (ones) (1 . #<procedure>) (cdr (ones)) #<procedure> ((cdr (ones))) (1 . #<procedure>)
Of course, if we wanted *lazy* evaluation, we would want to avoid performing the cons more than once if it is demanded more than once. We have to use something other than lambda for that:
(define ones (delay (begin (printf "forcing...~n") (cons 1 ones)))) ones #<procedure> (force ones) forcing... (1 . #<procedure>) (force ones) (1 . #<procedure>) (cdr (force ones)) #<procedure> (force (cdr (force ones))) (1 . #<procedure>)
Notice how many times (cons 1 ones) got evaluated. So your trick *is* used to implement lazy evaluation in other languages. It's not very pleasant if you write a lot of lazy code, because you have to explicitly suspend evaluation of values using delay and explicitly demand evaluation using force. Thus, we have lazy languages that make the laziness implicit. -- Kevin S. Millikin Architecture Technology Corporation Research Scientist Specialists in Computer Architecture (952)829-5864 x. 162 http://www.atcorp.com
On Fri, 24 Jan 2003 09:18:47 -0600 "Kevin S. Millikin" <kmillikin@atcorp.com> wrote:
So your trick *is* used to implement lazy evaluation in other languages. It's not very pleasant if you write a lot of lazy code, because you have to explicitly suspend evaluation of values using delay and explicitly demand evaluation using force.
In ocaml, there is the lazy module, that does exactly the simulation of lazynes with lambda abstractions. Vince
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))
participants (3)
-
Chris Clearwater -
Kevin S. Millikin -
Nick Name