digitalmars.D - lazy evaluation
- Pierre Habouzit (73/73) Jun 01 2007 The behaviour of lazy in wrt lazy arguments, and it did not worked
- Pierre Habouzit (9/11) Jun 01 2007 Wow sorry for that sentence, I meant:
- Johan Granberg (3/11) Jun 01 2007 This is by design, one example was a do_times that evaluated the lazy
- Tyler Knott (16/30) Jun 01 2007 In D lazy parameters are implemented as anonymous delegates. This means...
- Pierre Habouzit (7/40) Jun 01 2007 hmm okay, so lazy is just syntaxic sugar then. That's a pity, because
- Denton Cockburn (8/45) Jun 01 2007 well, if you don't want it to re-evaluate on each instance, why not just...
- Pierre Habouzit (28/63) Jun 04 2007 My example is oversimplistic. Though if you are e.g. writing (not so
- Frits van Bommel (16/36) Jun 04 2007 How about something like this:
- Manfred Nowak (21/22) Jun 04 2007 You describe a generic pattern for memoizing the obvious result of
- Daniel Keep (30/30) Jun 04 2007 I'm not sure how you'd account for lazy arguments, but it should be
- Daniel Keep (81/81) Jun 04 2007 Ok; this time, the example does actually work. Sadly, it doesn't work
- =?UTF-8?B?SnVsaW8gQ8Opc2FyIENhcnJhc2NhbCBVcnF1aWpv?= (11/18) Jun 01 2007 If you want to use the result of the argument more than once you should
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
val a : int ref = {contents = 0}
val counter : unit -> int = <fun>
- : int = 0
- : int = 1
val laz : int lazy_t = <lazy>
- : int = 2
- : 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
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
Johan Granberg <lijat.meREM OVEgmail.com> Pierre Habouzit wrote:On Fri, Jun 01, 2007 at 07:35:03PM +0000, Pierre Habouzit wrote:This is by design, one example was a do_times that evaluated the lazy expression n times.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: [...]
Jun 01 2007
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
On Fri, Jun 01, 2007 at 03:26:34PM -0500, Tyler Knott wrote:Pierre Habouzit wrote: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.orglazy 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
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: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; }Pierre Habouzit wrote:hmm okay, so lazy is just syntaxic sugar then. That's a pity, because I believe it's restrictive, but well... too bad :)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
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: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.orgOn Fri, Jun 01, 2007 at 03:26:34PM -0500, Tyler Knott wrote: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; }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 :)
Jun 04 2007
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
Frits van Bommel wroteHow 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
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
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
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