July 24, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | "Ben Hinkle" <ben.hinkle@gmail.com> wrote:
[...]
> In D a "Box" is a type whose run-time "type" can be anything
[...]
It is suggested to be. But is it really?
<code>
import std.boxer;
int f(){
return 1;
}
void main(){
Box b= box(&f);
if( unboxable!( int function())( b)) printf("true\n");
}
</code>
The above code is not linkable, although compiled with -release.
-manfred
|
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Manfred Nowak | "Manfred Nowak" <svv1999@hotmail.com> wrote in message news:dc17cj$hnm$1@digitaldaemon.com... > "Ben Hinkle" <ben.hinkle@gmail.com> wrote: > > [...] >> In D a "Box" is a type whose run-time "type" can be anything > [...] > > It is suggested to be. But is it really? > > <code> > import std.boxer; > > int f(){ > return 1; > } > > void main(){ > Box b= box(&f); > if( unboxable!( int function())( b)) printf("true\n"); > } > </code> > > The above code is not linkable, although compiled with -release. > > -manfred Are you on Linux? I just tried on Windows and it seems to work. |
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | "Ben Hinkle" <ben.hinkle@gmail.com> wrote: [...] > Are you on Linux? I just tried on Windows and it seems to work. WinXPPro, dmd 0.128 (fresh install) <output> E:\home\d\tests>dmd box -release e:\dmd\bin\..\..\dm\bin\link.exe box,,,user32+kernel32/noi; OPTLINK (R) for Win32 Release 7.50B1 Copyright (C) Digital Mars 1989 - 2001 All Rights Reserved box.obj(box) Error 42: Symbol Undefined __init_13TypeInfo_DFZi --- errorlevel 1 </output> And you? Do you have a fresh install or a recompiled phobos? -manfred |
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Manfred Nowak | "Manfred Nowak" <svv1999@hotmail.com> wrote in message news:dc20oe$151h$1@digitaldaemon.com... > "Ben Hinkle" <ben.hinkle@gmail.com> wrote: > > [...] >> Are you on Linux? I just tried on Windows and it seems to work. > > WinXPPro, dmd 0.128 (fresh install) > > <output> > E:\home\d\tests>dmd box -release > e:\dmd\bin\..\..\dm\bin\link.exe box,,,user32+kernel32/noi; > OPTLINK (R) for Win32 Release 7.50B1 > Copyright (C) Digital Mars 1989 - 2001 All Rights Reserved > > box.obj(box) > Error 42: Symbol Undefined __init_13TypeInfo_DFZi > --- errorlevel 1 > </output> > > And you? Do you have a fresh install or a recompiled phobos? fresh. very odd. Is box.obj stale perhaps? My obj file has init_typeinfo's for FZi and PFZi but no DFZi. Looking at the mangling rules D means "delegate" so somehow the compiler started thinking it needed a delegate instead of a regular function, I guess. |
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | "Ben Hinkle" <ben.hinkle@gmail.com> wrote: [...] > Is box.obj stale perhaps? [...] Sadly true. Must have been an .obj from a test with a delegate. But what is wrong now with this additional line? <code> int function() g= unbox!(int function())(b); </code> yields: <output> E:\home\d\tests>dmd box -release e:\dmd\bin\..\src\phobos\std\boxer.d(576): can't have array of int() e:\dmd\bin\..\src\phobos\std\boxer.d(577): can't have array of int() e:\dmd\bin\..\src\phobos\std\boxer.d(10): template instance std.boxer.unbox!(int(*)()) error instantiating </output> -manfred |
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Manfred Nowak | "Manfred Nowak" <svv1999@hotmail.com> wrote in message news:dc2qsi$1qkq$1@digitaldaemon.com... > "Ben Hinkle" <ben.hinkle@gmail.com> wrote: > > [...] >> Is box.obj stale perhaps? > [...] > > Sadly true. Must have been an .obj from a test with a delegate. > > But what is wrong now with this additional line? > > <code> > int function() g= unbox!(int function())(b); > </code> > > yields: > > <output> > E:\home\d\tests>dmd box -release > e:\dmd\bin\..\src\phobos\std\boxer.d(576): can't have array of int() > e:\dmd\bin\..\src\phobos\std\boxer.d(577): can't have array of int() > e:\dmd\bin\..\src\phobos\std\boxer.d(10): template instance > std.boxer.unbox!(int(*)()) error instantiating > </output> > > -manfred Looks like a bug. I suggest posting to D.bugs. It could be related to http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D.bugs/4218 or http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D.bugs/4444. Maybe I oversimplified when I said "the one wrinkle with using box..." I should have said "the most common wrinkle with using box..." |
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | Ben Hinkle wrote:
> "Tony" <talktotony@email.com> wrote in message news:dbvpm6$27db$1@digitaldaemon.com...
>
>>Hi.
>>
>>I was wondering if someone could demonstrate how to write a memoize function
>>in D?
>>
>>A memoize routine should accept a function as an argument, and return a new
>>function. This new function should return the same values as the original
>>function, but should also maintain a cache of results from previous calls
>>and return the value(s) from the cache rather than recalculating them,
>>whenever possible.
>>
>>This can be done quite simply in Lisp, and an example is available in Paul
>>Grahams "On Lisp" (freely available as a pdf) if anyone is interested.
>>
>>If there is an elegant solution to this in D, I will be very impressed.
>>
>>Tony
>>Melbourne, Australia
>
>
> It depends on how general you want the memoizable (is that a word?) functions to be. If you don't mind nailing down the signatures then it would be easy. The solutions in D are probably just like the solutions in C++. For example
> alias int function(int) Fcn;
> class Memoize {
> Fcn f;
> int[int] cache;
> this(Fcn f){ this.f = f; }
> int opCall(int x) {
> int y;
> int* v = x in cache;
> if (v) {
> y = *v;
> } else {
> y = f(x);
> cache[x] = y;
> }
> return y;
> }
> }
> Memoize memoize(Fcn f) {
> return new Memoize(f);
> }
> int fib(int n) {
> return n < 2 ? 1 : fib(n-1)+fib(n-2);
> }
> int main() {
> printf("%d\n",fib(8));
> Memoize m = memoize(&fib);
> printf("%d\n",m(8));
> return 0;
> }
This is just a stylistic difference, but I prefer to return delegates rather than class references:
int delegate(int) memoize(Fcn f) {
Memoize m = new Memoize(f);
return &m.opCall;
}
...
int main() {
...
int delegate(int) dg = memoize(&fib);
...
}
The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.
|
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Russ Lewis | > int delegate(int) memoize(Fcn f) {
> Memoize m = new Memoize(f);
> return &m.opCall;
> }
> ...
> int main() {
> ...
> int delegate(int) dg = memoize(&fib);
> ...
> }
>
> The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.
Good point. I agree. Here's a slightly shorter version of memoize:
int delegate(int) memoize(int function(int) f) {
struct Frame {
int function(int) f;
int call(int x){return f(x);}
}
Frame* frame = new Frame;
frame.f = f;
return &frame.call;
}
int fib(int n){return n+10;}
int main() {
int delegate(int) dg = memoize(&fib);
printf("%d\n",dg(5));
return 0;
}
|
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | Ben Hinkle wrote:
>>int delegate(int) memoize(Fcn f) {
>> Memoize m = new Memoize(f);
>> return &m.opCall;
>>}
>>...
>>int main() {
>> ...
>> int delegate(int) dg = memoize(&fib);
>> ...
>>}
>>
>>The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.
>
>
> Good point. I agree. Here's a slightly shorter version of memoize:
> int delegate(int) memoize(int function(int) f) {
> struct Frame {
> int function(int) f;
> int call(int x){return f(x);}
> }
> Frame* frame = new Frame;
> frame.f = f;
> return &frame.call;
> }
> int fib(int n){return n+10;}
> int main() {
> int delegate(int) dg = memoize(&fib);
> printf("%d\n",dg(5));
> return 0;
> }
Remember the caching functions.
Also note that the caching example given above is not thread-safe.
|
July 25, 2005 Re: Memoize function in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Russ Lewis | "Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:dc3df6$2a7d$1@digitaldaemon.com... > Ben Hinkle wrote: >>>int delegate(int) memoize(Fcn f) { >>> Memoize m = new Memoize(f); >>> return &m.opCall; >>>} >>>... >>>int main() { >>> ... >>> int delegate(int) dg = memoize(&fib); >>> ... >>>} >>> >>>The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible. >> >> >> Good point. I agree. Here's a slightly shorter version of memoize: >> int delegate(int) memoize(int function(int) f) { >> struct Frame { >> int function(int) f; >> int call(int x){return f(x);} >> } >> Frame* frame = new Frame; >> frame.f = f; >> return &frame.call; >> } >> int fib(int n){return n+10;} >> int main() { >> int delegate(int) dg = memoize(&fib); >> printf("%d\n",dg(5)); >> return 0; >> } > > Remember the caching functions. hehe - I got a little carried away in "simplifying" :-P > Also note that the caching example given above is not thread-safe. That would actually be an advantage of using a class since it can synchronize the opCall method (or whatever method name is chosen - it doesn't really matter what the name is if the delegate is used).. |
Copyright © 1999-2021 by the D Language Foundation