[Prev][Next][Index][Thread]

Re: lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Bruce Hoult <brucehoult@pobox.com> wrote:
>In article <slrn85jfje.b13.neelk@brick.cswv.com>, neelk@alum.mit.edu wrote:
>
>> No problem. I've added the changes Bruce suggested [...]
>
>Oh well, so much for my aim of triggering discussion... :-(

What's there to discuss? You were clearly correct! :)

Seriously, I thought about this some, and decided that having an
explicit slot for the memoized? attribute was not the best idea. 

As you pointed out, the implemenation already has to keep this
information available in order to be able to return an answer for the
slot-initialized? function. So this is just redundant information.

I thought about it a little more, and then realized that the situation
might even be a little worse than I imagined. If the generated code
implements slot-initialized? as, say, a test for a NULL pointer, then
any access into a potentially unitialized slot will require that test
to guarantee safety.[*]

This check is subject to a stronger invariant than usual: namely, once
an a slot is initialized it can never be unitiialized. So a dataflow
analysis might be able to eliminate this check in a lot of cases.
However, it seems to me that only the mythical Sufficiently Smart
Compiler could infer that the same invariant holds wrt to the
memoized? slot and then do the same analysis for it. Note that I've
never written an optimizing compiler, so I could be wrong about
this. But since I'm being pessimistic I doubt it. :)

So it makes sense to implement memoized? as a call to
slot-initialized? -- then inlining and dataflow analysis would
eliminate it where it's not needed automagically, since the compiler
could plausibly know about it.

To keep this from being completely hypothetical, I compiled it in
d2c. When memoized? is implemented as:

  define method memoized?(s :: <suspension>)
    slot-initialized?(s, vals)
  end method memoized?;

it compiles to 

  descriptor_t * lazyZlazyZmemoizedQUERY_METH(
                      descriptor_t *orig_sp, 
		      heapptr_t A0 /* s */)
  {
      descriptor_t L_vals; /* vals */
      descriptor_t L_temp;
  
  
      #line 19 "./lazy.dylan"
      L_vals = SLOT(A0, descriptor_t, 8);
      L_temp.heapptr = ((L_vals.heapptr != NULL) ? obj_True : obj_False);
      L_temp.dataword.l = 0;
      orig_sp[0] = L_temp;
      return orig_sp + 1;
  }

which is basically just a NULL pointer check. So the change was 
warranted. :)


Neel

[*] I can't seem to find where the DRM mandates it, though. But GD
throws an exception when I try to access an unitialized slot, and I
vaguely recall Fun-Dev 1.2 doing the same thing.
Follow-Ups: References: