lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan 
Author Message
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Hello,

I've written a tiny little module to do SML/NJ or SICP-style lazy
evaluation with Dylan. It will delay evaluation and memoize prior
computations, in just 20-odd lines of code! While mostly for
educational/entertainment purposes, it is genuinely useful when
implementing certain amortized-time algorithms.

You can find it at

  <URI: http://www.*-*-*.com/ ;

Neel



Mon, 03 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:

> I've written a tiny little module to do SML/NJ or SICP-style lazy
> evaluation with Dylan.

I see where the results of several prior threads just got used... :-)

I've got a weenie micro-optomisation style question (I don't have a real
opinion but I'd like to know what others think)...

In ...

define class <suspension> (<object>)
  slot memoized? :: <boolean>,
    init-value: #f;
  slot expression :: <method>,
    required-init-keyword: expression:;
  slot vals :: <sequence>;
end class <suspension>;

... are "memoized?" and "vals" declared optimally?  Since "vals" doesn't
have a required initializer it is going to have to have a reserved value
to indicate "not initialized" somehow, which will take up space and always
have a runtime check that slows down access to the slot value.  And yet
slot-initialized?(vals) will always have exactly the same value as
"memoized?".

Do you think you should dump the "memoized?" slot, and just test
slot-initialized?(vals) in the force() method?  If you want mnemonic value
then you could always implement "memoized?" as a method that tests
slot-initialized?.

Alternatively, you could explicitly initialize "vals" to a globally-unique
object that is an instance of <sequence> that serves as a "null" value.
In which case you still don't need "memoized?" :-)

-- Bruce



Mon, 03 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:

> I've written a tiny little module to do SML/NJ or SICP-style lazy
> evaluation with Dylan. It will delay evaluation and memoize prior

Cool! If you don't mind, I'll put that into the contributions
directory on the Gwydion Dylan FTP server.

Andreas

--
"We should be willing to look at the source code we produce not as the
end product of a more interesting process, but as an artifact in its
own right. It should look good stuck up on the wall."
 -- http://www.ftech.net/~honeyg/progstone/progstone.html



Mon, 03 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:


>> I've written a tiny little module to do SML/NJ or SICP-style lazy
>> evaluation with Dylan. It will delay evaluation and memoize prior

>Cool! If you don't mind, I'll put that into the contributions
>directory on the Gwydion Dylan FTP server.

No problem. I've added the changes Bruce suggested, so you should
grab the file from:

  <URI:http://www.sff.net/people/neelk/open-source/lazy-0.2.tgz>

Neel



Tue, 04 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:

> No problem. I've added the changes Bruce suggested, so you should
> grab the file from:

>   <URI:http://www.sff.net/people/neelk/open-source/lazy-0.2.tgz>

Oh well, so much for my aim of triggering discussion... :-(

-- Bruce



Tue, 04 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:


>> 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.



Tue, 04 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:

> [*] 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.

As a newbie-weenie, one of the first things I learned is that Fun-Dev
2.0 beta throws an exception for access to an uninitialized slot.


Tue, 04 Jun 2002 03:00:00 GMT  
 lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

Quote:

> 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.[*]

Right.  Including the use of "apply(values, s.vals)" in force().

Quote:
> 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.

Good point.  I'd be suprised if any current compiler actually manages to
take advantage of this though, in situations where it couldn't do the same
for a memoized? slot.

The current d2c, for example, still checks for a null "vals" slot in
"apply(values, s.vals)" even if I make the memoized? function inline :-(
so even the logic of...

   if not X
     set X
   use X

... is too tough for it to follow.  This may well be a bug, though, as it
*does* follow such logic for local bindings even though it doesn't for
slots of objects.

Quote:
> 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.

How about my other suggestion of using a distinguiished "not initialized" value?

define constant *not-memoized* = make(<sequence>);

define class <suspension> (<object>)
  slot expression :: <method>, required-init-keyword: expression:;
  slot vals :: <sequence>, init-value: *not-memoized*;
end class <suspension>;

define method memoized?(s :: <suspension>)
  s.vals ~== *not-memoized*;
end method memoized?;

In this case all slots are always initialized (which I like,
stylistically), which also means that no compiler-generated tests for
slot-initialized? are ever needed.

This perhaps (as per your point about slots not being able to be made
uninitialized after having previously been initialized) makes it very
slighly harder for a smart compiler to prove that the test in memoized?()
isn't required in some cases, but it certainly doesn't make it impossible.

-- Bruce

p.s. someone called Natarajan just told me he's the handsome one.



Wed, 05 Jun 2002 03:00:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. lazy (non-eager) Scheme ??? (lazy, but eager me)

2. lazy (non-eager) Scheme ??? (lazy, but eager me)

3. Lazy evaluation in Scheme?

4. lazy.py 0.7 - Lazy expressions and datastructures

5. How lazy is lazy?

6. lazy.py 0.7 - Lazy expressions and datastructures

7. Tech Report on Pattern Matching (in ML and Lazy Languages)

8. Lazy evaluation?

9. Lazy evaluation in Common Lisp

10. Monads and Lazy Evaluation

11. lazy evaluation, minimax, and alpha-beta pruning

12. eager/lazy evaluation

 

 
Powered by phpBB® Forum Software