www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - lazy evaluation

reply Pierre Habouzit <pierre.habouzit m4x.org> writes:
  The behaviour of lazy in wrt lazy arguments, and it did not worked
like I expected. let's take the following code as an example:

--------------------------------------------
import std.stdio;

int foo() {
    static int i = 0;
    return i++;
}

void baz(lazy int i)
{
    writefln("baz %d", i());
}

void bar(lazy int i) {
    baz(i);
    writefln("bar %d", i());
}

int main()
{
    bar(foo());
    return 0;
}
--------------------------------------------

(small remark, I regret the very handy __func__ variable from C99
here...)

  if you compile that code, the output will be :

baz 0
bar 1

  Whereas I would have expected 0 and ... 0. I know the code I show is
well, nasty as the lazy expression has a side effect, but it was just a
way for me to test if lazy expressions were memoized (what I really
expected) or not. It appears they are not, and well, that's not good.

  On digitalmars website we can read that lazy can be used to avoid
computation. Let's say for logging purposes. Good example: the
programmer could have two optional backend for logging, e.g. on stderr
and in the syslog. and if he does not uses an intermediate variable to
store the lazy epxressions, it will be evaluated two times. Of course
doing so is completely defeating the very purpose of lazy.

  There is another language that has some kind of lazy expression
support, not only for function parameters but as a type attribute,
python users would say decorators, it's Ocaml. See how it works:

--------------------------------------------
$ ocaml
        Objective Caml version 3.09.2

# let a = ref 0;;
val a : int ref = {contents = 0}
# let counter () = let result = !a in a := !a + 1; result;;
val counter : unit -> int = <fun>
# counter();;                 
- : int = 0
# counter ();;
- : int = 1
# let laz = lazy (counter ());;
val laz : int lazy_t = <lazy>
# Lazy.force laz;;
- : int = 2
# Lazy.force laz;;
- : int = 2
--------------------------------------------

  lazy types are supported through the Lazy module, and forcing the
evaluation of a lazy type is done through Lazy.force expr rather than
expr() like in D. Though, like you can see, once forced, the lazy
expression sees its value memoized.

  I'm wondering:
  * why lazy types in D don't work like that for lazy parameters,
    because it's really what makes sense and is the most predictible
    behaviour ;
  * also why it's not a generic type attribute either and only used as a
    function parameter. Not knowing the implementation gory details, I
    don't know if it makes sense at all anyway.


-- 
·O·  Pierre Habouzit
··O                                                madcoder debian.org
OOO                                                http://www.madism.org
Jun 01 2007
next sibling parent reply Pierre Habouzit <pierre.habouzit m4x.org> writes:
On Fri, Jun 01, 2007 at 07:35:03PM +0000, Pierre Habouzit wrote:
   The behaviour of lazy in wrt lazy arguments, and it did not worked
 like I expected. let's take the following code as an example:

Wow sorry for that sentence, I meant: I tried the lazy arguments feature, and it did not worked like I expected. let's take the following code as an example: [...] --=20 =C2=B7O=C2=B7 Pierre Habouzit =C2=B7=C2=B7O madcoder debia= n.org OOO http://www.madism.org
Jun 01 2007
parent Johan Granberg <lijat.meREM OVEgmail.com> writes:
Pierre Habouzit wrote:

 On Fri, Jun 01, 2007 at 07:35:03PM +0000, Pierre Habouzit wrote:
   The behaviour of lazy in wrt lazy arguments, and it did not worked
 like I expected. let's take the following code as an example:

Wow sorry for that sentence, I meant: I tried the lazy arguments feature, and it did not worked like I expected. let's take the following code as an example: [...]

This is by design, one example was a do_times that evaluated the lazy expression n times.
Jun 01 2007
prev sibling next sibling parent reply Tyler Knott <tywebmail mailcity.com> writes:
Pierre Habouzit wrote:
   lazy types are supported through the Lazy module, and forcing the
 evaluation of a lazy type is done through Lazy.force expr rather than
 expr() like in D. Though, like you can see, once forced, the lazy
 expression sees its value memoized.
 
   I'm wondering:
   * why lazy types in D don't work like that for lazy parameters,
     because it's really what makes sense and is the most predictible
     behaviour ;
   * also why it's not a generic type attribute either and only used as a
     function parameter. Not knowing the implementation gory details, I
     don't know if it makes sense at all anyway.
 
 

In D lazy parameters are implemented as anonymous delegates. This means that void baz(lazy int i) { writefln("baz %d", i); } is transformed to void baz(int delegate() i) { writefln("baz %d", i()); } where the delegate i references is whatever code you used for that argument. So in your example each time i evaluated you call an anonymous function that calls foo() and returns its return value. If you want the value to stay consistent between evaluations of i use a temporary variable to store the result of it or make it non-lazy.
Jun 01 2007
next sibling parent reply Pierre Habouzit <pierre.habouzit m4x.org> writes:
On Fri, Jun 01, 2007 at 03:26:34PM -0500, Tyler Knott wrote:
 Pierre Habouzit wrote:
  lazy types are supported through the Lazy module, and forcing the
evaluation of a lazy type is done through Lazy.force expr rather than
expr() like in D. Though, like you can see, once forced, the lazy
expression sees its value memoized.
  I'm wondering:
  * why lazy types in D don't work like that for lazy parameters,
    because it's really what makes sense and is the most predictible
    behaviour ;
  * also why it's not a generic type attribute either and only used as a
    function parameter. Not knowing the implementation gory details, I
    don't know if it makes sense at all anyway.

In D lazy parameters are implemented as anonymous delegates. This means that void baz(lazy int i) { writefln("baz %d", i); } is transformed to void baz(int delegate() i) { writefln("baz %d", i()); } where the delegate i references is whatever code you used for that argument. So in your example each time i evaluated you call an anonymous function that calls foo() and returns its return value. If you want the value to stay consistent between evaluations of i use a temporary variable to store the result of it or make it non-lazy.

hmm okay, so lazy is just syntaxic sugar then. That's a pity, because I believe it's restrictive, but well... too bad :) -- ·O· Pierre Habouzit ··O madcoder debian.org OOO http://www.madism.org
Jun 01 2007
parent reply Pierre Habouzit <pierre.habouzit m4x.org> writes:
On Sat, Jun 02, 2007 at 03:01:44AM +0000, Denton Cockburn wrote:
 On Fri, 01 Jun 2007 20:47:45 +0000, Pierre Habouzit wrote:
 On Fri, Jun 01, 2007 at 03:26:34PM -0500, Tyler Knott wrote:
 In D lazy parameters are implemented as anonymous delegates.  This means 
 that
 
 void baz(lazy int i)
 {
 	writefln("baz %d", i);
 }
 
 is transformed to
 
 void baz(int delegate() i)
 {
 	writefln("baz %d", i());
 }
 
 where the delegate i references is whatever code you used for that 
 argument.  So in your example each time i evaluated you call an anonymous 
 function that calls foo() and returns its return value.  If you want the 
 value to stay consistent between evaluations of i use a temporary 
 variable to store the result of it or make it non-lazy.

hmm okay, so lazy is just syntaxic sugar then. That's a pity, because I believe it's restrictive, but well... too bad :)

well, if you don't want it to re-evaluate on each instance, why not just... int main() { int f = foo(); bar(f); return 0; }

My example is oversimplistic. Though if you are e.g. writing (not so random example) an interpreter of some language, and for one or another reason you don't really want to go in the hassle of bytecode or intermediary language. One way to speed things up is to evaluate your parse tree lazily. Of course, that could be explicitely coded, but it's way easier if the language gives you that gratis. As a general rule, in many complex applications, you often have somehow complex operations (parse, compilation, hashing, whatever) that you do "just in case", because it's easier to suppose this operation has been done unconditionnaly, rather than using everywhere you need the parse/compilation/hash/... available things like: if (foo->did_i_parsed_it()) foo->parse(); use_parse_of_foo(foo->parseresult); Because one day, you'll forget about it. If you have the lazy expressions I'm talking about, then instead of doing the real parse in your program, you just need to write the lazy expression that once evaluated will compute the parse/compilation/whatever. Then you use your foo->parseresult member as a lazy expression, that will be evaluated iff your application really needed it. Though, maybe this don't need to be done with the D lazy construct though, but I didn't came with a satisfying implementation yet. (I mean one that has a light enough syntax for the lazy expression use). -- ·O· Pierre Habouzit ··O madcoder debian.org OOO http://www.madism.org
Jun 04 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Pierre Habouzit wrote:
   As a general rule, in many complex applications, you often have
 somehow complex operations (parse, compilation, hashing, whatever) that
 you do "just in case", because it's easier to suppose this operation has
 been done unconditionnaly, rather than using everywhere you need the
 parse/compilation/hash/... available things like:
 
   if (foo->did_i_parsed_it())
       foo->parse();
   use_parse_of_foo(foo->parseresult);
 
   Because one day, you'll forget about it. If you have the lazy
 expressions I'm talking about, then instead of doing the real parse in
 your program, you just need to write the lazy expression that once
 evaluated will compute the parse/compilation/whatever.
 
   Then you use your foo->parseresult member as a lazy expression, that
 will be evaluated iff your application really needed it.

How about something like this: --- class Foo { private bool parsed; private Tree parseresult_; Tree parseresult() { if (!parsed) parse(); return parseresult; } private void parse() { parseresult_ = ...; } } --- Then you can just use foo.parseresult without needing to explicitly re-check every time. Properties are very handy for stuff like this.
   Though, maybe this don't need to be done with the D lazy construct
 though, but I didn't came with a satisfying implementation yet. (I mean
 one that has a light enough syntax for the lazy expression use).

I think something like the above code combined with passing foo.parseresult as a lazy parameter might do pretty much what you're looking for.
Jun 04 2007
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Frits van Bommel wrote

 How about something like this:

You describe a generic pattern for memoizing the obvious result of calls; obvious in the sense of forgetting about side effects. The question Pierre's post rises: is there a way to implement this pattern in D in a way, which is easy to capture? As it seems there is currently no such way. If my remark above is true and if it is feasable, then D is in the need of a further paradigm, which at least allows for defining a `memo' qualifier for parameters, where `memo' has the obvious property of evaluating the parameter at most once lazily for each possible parameter value. As it seems such paradigm is infeasable in general because it must take care of parameters that are itself function calls with lazy parameters. Those calls are not distinguishable before hand even for only one instance, because each of the calls look the same. But because they are evaluated lazily without memoizing the obvious results may vary for consecutive calls. The question now is: for what kinds of parameters is memoizing allowed? Besides that: my former question in what cases general memoizing makes an algorithm indeed more efficient, stays unanswered. -manfred
Jun 04 2007
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
I'm not sure how you'd account for lazy arguments, but it should be
possible to abstract memorisation of function results.  Warning:
untested and likely non-compiling code follows, but it should at least
be in the right ballpark :)

	--Daniel

 --

template memoImpl(alias fn)
{
    alias typeof(&fn) fnT;
    private ReturnType!(fnT)[Tuple!(ParameterTypeTuple!(fnT))] results;

    ReturnType!(fnT) memo(ParameterTypeTuple!(fnT) args)
    {
        auto targs = tuple(args);
        if( !(targs in results) )
            results[targs] = fn(args);
        return results[targs];
    }
}

template memo(alias fn)
{
    alias memoImpl!(fn).memo memo;
}

class Foo
{
    int _foo(char[] bar)
    {
        // ... some complex calculation ...
    }

    alias memo!(_foo) foo;
}
Jun 04 2007
parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Ok; this time, the example does actually work.  Sadly, it doesn't work
if you try to memorise a member function; not sure how to work around
that as of yet.

	-- Daniel

 --

module memo;

import std.traits;

struct STuple(T...)
{
    alias T Type;
    alias STuple!(T) thisT;
    T values;

    int opEquals(thisT rhs)
    {
        foreach( i,v ; values )
            if( v != rhs.values[i] )
                return false;
        return true;
    }

    int opCmp(thisT rhs)
    {
        foreach( i,v ; values )
        {
            if( v == rhs.values[i] )
                {}
            else if( v < rhs.values[i] )
                return -1;
            else
                return 1;
        }
        return 0;
    }

    hash_t toHash()
    {
        hash_t result;
        foreach( v ; values )
            result ^= typeid(typeof(v)).getHash(&v);
        return result;
    }
}

STuple!(T) stuple(T...)(T args)
{
    STuple!(T) result;
    foreach( i,arg ; args )
        result.values[i] = arg;
    return result;
}

template memoImpl(alias fn)
{
    alias typeof(&fn) fnT;
    private ReturnType!(fnT)[STuple!(ParameterTypeTuple!(fnT))] results;

    ReturnType!(fnT) memo(ParameterTypeTuple!(fnT) args)
    {
        auto targs = stuple(args);
        if( !(targs in results) )
        {
            results[targs] = fn(args);
        }
        return results[targs];
    }
}

template memo(alias fn)
{
    alias memoImpl!(fn).memo memo;
}

import std.stdio;

uint _foo(char[] bar)
{
    writefln(`foo("%s") called!`, bar);
    return bar.length;
}

alias memo!(_foo) foo;

void main()
{
    writefln(`foo("abc") == %s`, foo("abc"));
    writefln(`foo("fuzzy") == %s`, foo("fuzzy"));
    writefln(`foo("abc") == %s`, foo("abc"));
    writefln(`foo("fuzzy") == %s`, foo("fuzzy"));
    writefln(`foo("Hello, World!") == %s`, foo("Hello, World!"));
    writefln(`foo("Hello, World!") == %s`, foo("Hello, World!"));
}
Jun 04 2007
prev sibling parent Denton Cockburn <diboss hotmail.com> writes:
On Fri, 01 Jun 2007 20:47:45 +0000, Pierre Habouzit wrote:

 On Fri, Jun 01, 2007 at 03:26:34PM -0500, Tyler Knott wrote:
 Pierre Habouzit wrote:
  lazy types are supported through the Lazy module, and forcing the
evaluation of a lazy type is done through Lazy.force expr rather than
expr() like in D. Though, like you can see, once forced, the lazy
expression sees its value memoized.
  I'm wondering:
  * why lazy types in D don't work like that for lazy parameters,
    because it's really what makes sense and is the most predictible
    behaviour ;
  * also why it's not a generic type attribute either and only used as a
    function parameter. Not knowing the implementation gory details, I
    don't know if it makes sense at all anyway.

In D lazy parameters are implemented as anonymous delegates. This means that void baz(lazy int i) { writefln("baz %d", i); } is transformed to void baz(int delegate() i) { writefln("baz %d", i()); } where the delegate i references is whatever code you used for that argument. So in your example each time i evaluated you call an anonymous function that calls foo() and returns its return value. If you want the value to stay consistent between evaluations of i use a temporary variable to store the result of it or make it non-lazy.

hmm okay, so lazy is just syntaxic sugar then. That's a pity, because I believe it's restrictive, but well... too bad :)

well, if you don't want it to re-evaluate on each instance, why not just... int main() { int f = foo(); bar(f); return 0; }
Jun 01 2007
prev sibling parent =?UTF-8?B?SnVsaW8gQ8Opc2FyIENhcnJhc2NhbCBVcnF1aWpv?= writes:
Pierre Habouzit wrote:
   Whereas I would have expected 0 and ... 0. I know the code I show is
 well, nasty as the lazy expression has a side effect, but it was just a
 way for me to test if lazy expressions were memoized (what I really
 expected) or not. It appears they are not, and well, that's not good.

If you want to use the result of the argument more than once you should store that in a local variable: void bar(lazy int i) { int j = i(); baz(j); writefln("bar %d", j); }
   * also why it's not a generic type attribute either and only used as a
     function parameter. Not knowing the implementation gory details, I
     don't know if it makes sense at all anyway.

Walter gave us indications that the behavior would change as part of the "const clean-up" currently undergoing. This seams like a good time to share your thoughts and improvements on the behavior of lazy.
Jun 01 2007