[plt-scheme] Space/time behaviour of Lazy Scheme

From: Eli Barzilay (eli at barzilay.org)
Date: Tue Oct 16 20:13:00 EDT 2007

On Oct 17, jerzy.karczmarczuk at info.unicaen.fr wrote:
> A question, just for my general culture...
> Since, by design, there are no global replacements of once-evaluated
> promises by their results, somehow in my head I have - despite what
> you say - that the difference between lazy Scheme and, say, Haskell
> or Clean is still very profound, and an attempt to make a truly lazy
> Scheme would demand changing the compiler. Am I wrong?

I don't understand the question.  My guess is that in "replacements of
once-evaluated promises by the results" you mean somehow mutate
promises into being their results -- which is not necessary since a
promise and its value are treated in the same way as far as the lazy
programmer is concerned.

Let me use an extended example to make that point.  (NoteL I wrote
this with several interruptions, so it might not be too coherent.)

Say that you define some number like this:

  (define foo (+ 1 2))

In the implementation, `foo' is bound to a promise holding that
computation, and the addition is not actually performed until the
value is strictly needed.  One such strictness point is printing
values on the repl, so if you later type


that forces the promise and displays `3'.  `foo' is *still* bound to
a promise, but as a lazy programmer, you have no way of distinguishing
that from the resulting 3.

If my guess is correct, then what bothers you is that if after the
above you enter

  (list foo foo)

the result that you will see is:

  (#<promise!3> #<promise!3>)

The printer "just happens" to expose the fact that there are promises
in the value -- but this exposure is only something that concerns repl
users -- which are strict.  Now, "just happens" is not really the
whole story, of course, -- the decision was made to not make toplevel
evaluation force the result recursively.  The motivation for that is
that as a strict repl user, it's your job (you, being the strict user
that interacts with the repl) to determine the amount of force you
apply to results.  This is not something that affects the lazy
language itself, only the strict interactions that you do in the repl.

If you really wanted to force the above expression all the way
through, you'd use `!!' which forces the given value recursively:

  (!! (list foo foo))

would show `(3 3)'.  As a side note, the lazy Scheme language *does*
change the structure it is forcing, putting the values in places that
promises used to be when a value is forced recursively.  One way to
see that is to bind a name to that list, and after you force it
recursively you'll see that the promises are give (bear in mind that
the `bar' binding is still a promise, forced by the repl):

  > (define bar (list foo foo))
  > bar
  (#<promise!3> #<promise!3>)
  > (!! bar)
  (3 3)
  > bar
  (3 3)

Another example for this is the fact that you get a cyclic Scheme list
from a lazy recursive definition:

  > (define ones (cons 1 ones))
  > ones
  #0=(1 . #<promise!#0#>)
  > (!! ones)
  #0=(1 . #0#)
  > ones
  #0=(1 . #0#)

There is a global setting that determines the toplevel force that is
used.  It is set to `!' by default, forcing toplevel expressions just
enough to get a non-promise value.  You can change that to do the
recursive `!!' force with:

  (toplevel-forcer !!)

And from now on, repl interactions will force values recursively, just
like (I think) you expect them to.  So now

  (list foo foo)

shows `(3 3)'.  `foo' is still bound to a (forced) promise, but you
now cannot see that, since the repl is always forcing promises
recursively for you.  This means that an infinite list (that does not
happen to be a cyclic list like the above) will get your repl stuck
when it's forcing that value.

Going back to the decision to make `!' the default toplevel force,
there are two reasons for that.  The first is what I said above: we
don't want the repl to blindly force everything if that was not your
intention.  Ideally (and this is the future plan), you'll get a
DrScheme graphical representation of a promise, which you'll be able
to click to force it to turn into a value.  By that you will control
precisely which parts of the result you want to see, which of course
affects the way the computations are forced.

The second reason is that Lazy Scheme can be used to write modules:

  (module foo (lib "lazy.ss" "lazy")
    ... lazy code here ...)

And the question is what do you do with toplevel expressions that are
not definitions.  Currently, the same `toplevel-forcer' setting
applies to that as well -- these toplevel non-definitions are forced
with the same forcer.  This can be used to accomodate side effects
such as printouts (which are possible and are roughly equivalent to
Haskell's "unsafe" IO).  I think that in that context, `!!' will be
excessive force.

--- So, ---

Here's what I think I'll do:

* Separate the two settings -- one for module toplevel expressions,
  and one for repl toplevel expressions.

* Make the default repl toplevel forcer be `!!'.  I'm not completely
  sure about that one still, since it will also apply to using `load'.

* If the above is done, and given a future extension that renders
  promises as I described above, then DrScheme will set the Lazy
  Scheme top-level forcer back to `!'.  (Or maybe even no force at

* Yet another alternative will be to change the way that promises
  print themselves -- they could just print the forced value if they
  were in fact forced.  This is similar to what John wrote.  The
  reason I'm not sure about this is that Lazy Scheme lives inside the
  Strict Scheme world -- and in the latter there is a distinction
  between a promise and its value.  If there was no strict world
  involved, then the distinction goes away and changing the default
  printer makes sense.

If you have any opinions about this I'll be happy to hear them.
(Assuming that you got all the way down to here...)

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!

Posted on the users mailing list.