www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [challenge] Limitation in D's metaprogramming

reply "Nick Sabalausky" <a a.a> writes:
I don't know if others have noticed this before, but I think I've found a 
notable limitation in D's metaprogramming potential: There doesn't appear to 
be a way to have mutable global state at compile-time.

Challange:

Create two..."things"...they can be functions, templates, variables, 
mix-n-match, whatever. One of them increments a counter, and the other can 
be used to retreive the value. But both of these must operate at 
compile-time, and they must both be callable (directly or indirectly, 
doesn't matter) from within the context of any module that imports them.

This is an example, except it operates at run-time, not compile-time:

-----------------------------------
// a.d
module a;
int value=0;
void inc()
{
    value++;
}
int get()
{
    return value;
}

void incFromA()
{
    inc();
}

//b.d
module b;
import a;
void incFromB()
{
    inc();
}

//main.d
import a;
import b;
import std.stdio;
void main()
{
    inc();
    incFromA();
    incFromB();
    writeln(get());
}
-----------------------------------

The goal of this challenge is to define a global-level manifest constant 
enum that holds a value that has been incremented from multiple modules:

enum GOAL = ????;

It can, of course, then be displayed via:
pragma(msg, std.conv.to!string(GOAL));

At this point, I'm not concerned about order-of-execution issues resulting 
in unexpected or unpredictable values. As long as a value can be incremented 
at compile-time from multiple modules and used to initialize an enum 
manifest constant, that satisfies this challenge.
Oct 18 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Nick Sabalausky:

 The goal of this challenge is to define a global-level manifest constant 
 enum that holds a value that has been incremented from multiple modules:

And I hope people will try to solve it! So if someone solves it, we can later patch that bug ;-) Bye, bearophile
Oct 18 2010
parent "Nick Sabalausky" <a a.a> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:i9inpb$15n5$1 digitalmars.com...
 Nick Sabalausky:

 The goal of this challenge is to define a global-level manifest constant
 enum that holds a value that has been incremented from multiple modules:

And I hope people will try to solve it! So if someone solves it, we can later patch that bug ;-)

FWIW, The original motivation for this was that I was reading the recent "Improving version(...)" thread and thought "isVersion" was a notable improvement, but still didn't solve the problem that version identifiers don't have to be pre-defined and are therefore subject to bugs from typos. I wondered if an acceptable library-based solution could be done and started tinkering with it, but quickly realized it would most likely need mutable global compile-time state which D doesn't have a direct mechanism for. The only way to trigger CTFE seems to be by creating a value that's immutable even at compile-time (ex: enum x = ctfeFunc()). And trying to do it with template or mixin trickery leads to seemingly insurmountable scope-related problems.
Oct 18 2010
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 19 Oct 2010 04:07:16 +0400, Nick Sabalausky <a a.a> wrote:

 I don't know if others have noticed this before, but I think I've found a
 notable limitation in D's metaprogramming potential: There doesn't  
 appear to
 be a way to have mutable global state at compile-time.

 Challange:

 Create two..."things"...they can be functions, templates, variables,
 mix-n-match, whatever. One of them increments a counter, and the other  
 can
 be used to retreive the value. But both of these must operate at
 compile-time, and they must both be callable (directly or indirectly,
 doesn't matter) from within the context of any module that imports them.

 This is an example, except it operates at run-time, not compile-time:

 -----------------------------------
 // a.d
 module a;
 int value=0;
 void inc()
 {
     value++;
 }
 int get()
 {
     return value;
 }

 void incFromA()
 {
     inc();
 }

 //b.d
 module b;
 import a;
 void incFromB()
 {
     inc();
 }

 //main.d
 import a;
 import b;
 import std.stdio;
 void main()
 {
     inc();
     incFromA();
     incFromB();
     writeln(get());
 }
 -----------------------------------

 The goal of this challenge is to define a global-level manifest constant
 enum that holds a value that has been incremented from multiple modules:

 enum GOAL = ????;

 It can, of course, then be displayed via:
 pragma(msg, std.conv.to!string(GOAL));

 At this point, I'm not concerned about order-of-execution issues  
 resulting
 in unexpected or unpredictable values. As long as a value can be  
 incremented
 at compile-time from multiple modules and used to initialize an enum
 manifest constant, that satisfies this challenge.

I hope that's not a limitation but rather a deliberate design decision. CTFE needs to be pure, otherwise an order of evaluation would have an impact.
Oct 18 2010
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, October 18, 2010 17:07:16 Nick Sabalausky wrote:
 I don't know if others have noticed this before, but I think I've found a
 notable limitation in D's metaprogramming potential: There doesn't appear
 to be a way to have mutable global state at compile-time.
 
 Challange:
 
 Create two..."things"...they can be functions, templates, variables,
 mix-n-match, whatever. One of them increments a counter, and the other can
 be used to retreive the value. But both of these must operate at
 compile-time, and they must both be callable (directly or indirectly,
 doesn't matter) from within the context of any module that imports them.
 
 This is an example, except it operates at run-time, not compile-time:
 
 -----------------------------------
 // a.d
 module a;
 int value=0;
 void inc()
 {
     value++;
 }
 int get()
 {
     return value;
 }
 
 void incFromA()
 {
     inc();
 }
 
 //b.d
 module b;
 import a;
 void incFromB()
 {
     inc();
 }
 
 //main.d
 import a;
 import b;
 import std.stdio;
 void main()
 {
     inc();
     incFromA();
     incFromB();
     writeln(get());
 }
 -----------------------------------
 
 The goal of this challenge is to define a global-level manifest constant
 enum that holds a value that has been incremented from multiple modules:
 
 enum GOAL = ????;
 
 It can, of course, then be displayed via:
 pragma(msg, std.conv.to!string(GOAL));
 
 At this point, I'm not concerned about order-of-execution issues resulting
 in unexpected or unpredictable values. As long as a value can be
 incremented at compile-time from multiple modules and used to initialize
 an enum manifest constant, that satisfies this challenge.

One word: monads. Now, to get monads to work, you're going to have to be fairly organized about it, but that would be the classic solution to not being able to have or alter global state and yet still be able to effectively have global state. - Jonathan M Davis
Oct 18 2010
parent reply "Nick Sabalausky" <a a.a> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote in message 
news:mailman.715.1287449256.858.digitalmars-d puremagic.com...
 One word: monads.

 Now, to get monads to work, you're going to have to be fairly organized 
 about
 it, but that would be the classic solution to not being able to have or 
 alter
 global state and yet still be able to effectively have global state.

Oh yea, I've heard about them but don't have any real experience with them. Any FP experts know whether or not monads are known to be constructible from purely-FP building blocks? I always assumed "no", and that monads really just came from a deliberate compiler-provided hole in the whole purity thing, but maybe I'm wrong? (That would be quite interesting: constructing impurity from purity.)
Oct 18 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

 You can think of a monad as an extra parameter which is passed to each
function 
 and holds the global state. It isn't a hole in purity at all. For instance,
it's 
 how Haskell manages to have I/O and yet be functionally pure. You don't need
the 
 compiler's help to do monads - it's just easier if you have it.

Yet, sooner or later the compiler has to help you giving you a hole to let the contents of those I/O monads pass though to/from the outside world, otherwise you will not see any program input/output unless you use something like a post-mortem debugger :-) So I think the Haskell compiler has to manage your I/O monads in a special way anyway. Purity can't be absolute. Bye, bearophile
Oct 18 2010
parent Michael Stone <mstone xx.xxx> writes:
bearophile Wrote:

 Jonathan M Davis:
 
 You can think of a monad as an extra parameter which is passed to each
function 
 and holds the global state. It isn't a hole in purity at all. For instance,
it's 
 how Haskell manages to have I/O and yet be functionally pure. You don't need
the 
 compiler's help to do monads - it's just easier if you have it.

Yet, sooner or later the compiler has to help you giving you a hole to let the contents of those I/O monads pass though to/from the outside world, otherwise you will not see any program input/output unless you use something like a post-mortem debugger :-) So I think the Haskell compiler has to manage your I/O monads in a special way anyway. Purity can't be absolute.

The stdin/(stdout/stderr) streams/pipes form a pure system with eager evaluation of the application in my opinion. You can use monads to propagate the state through the application naturally in this way. The arguments about real world are silly in this context. Even the operating system, the compiler and the processes are all abstactions. The real world operates with resistances, capacitances, voltages etc.
Oct 18 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, October 18, 2010 17:54:50 Nick Sabalausky wrote:
 "Jonathan M Davis" <jmdavisProg gmx.com> wrote in message
 news:mailman.715.1287449256.858.digitalmars-d puremagic.com...
 
 One word: monads.
 
 Now, to get monads to work, you're going to have to be fairly organized
 about
 it, but that would be the classic solution to not being able to have or
 alter
 global state and yet still be able to effectively have global state.

Oh yea, I've heard about them but don't have any real experience with them. Any FP experts know whether or not monads are known to be constructible from purely-FP building blocks? I always assumed "no", and that monads really just came from a deliberate compiler-provided hole in the whole purity thing, but maybe I'm wrong? (That would be quite interesting: constructing impurity from purity.)

You can think of a monad as an extra parameter which is passed to each function and holds the global state. It isn't a hole in purity at all. For instance, it's how Haskell manages to have I/O and yet be functionally pure. You don't need the compiler's help to do monads - it's just easier if you have it. - Jonathan M Davis
Oct 18 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 18 October 2010 18:49:41 bearophile wrote:
 Jonathan M Davis:
 You can think of a monad as an extra parameter which is passed to each
 function and holds the global state. It isn't a hole in purity at all.
 For instance, it's how Haskell manages to have I/O and yet be
 functionally pure. You don't need the compiler's help to do monads -
 it's just easier if you have it.

Yet, sooner or later the compiler has to help you giving you a hole to let the contents of those I/O monads pass though to/from the outside world, otherwise you will not see any program input/output unless you use something like a post-mortem debugger :-) So I think the Haskell compiler has to manage your I/O monads in a special way anyway. Purity can't be absolute. Bye, bearophile

I've been dealing primarily with D in my free time these days instead of Haskell, so I don't remember all of the details, but the side effects are essentially removed by making the IO part of the output at the end. If there _is_ a hole of some kind in the functional purity of the language it's confined to one point and it does not affect your program overall at all. It would only be when the monad was finally consumed. And many other types of monads don't have anything do to with I/O and _definitely_ don't need any kind of hole in the functional purity of the system. Haskell wouldn't work if it weren't functionally pure (thanks to the fact that it's lazy). Monads were an ingenious solution to the problem of how to deal with stuff like I/O that needs side effects and/or global state without actually allowing either. Monads _do_ end up being a rather viral in that once you have one, pretty much everything in the call chain after that has to pass it along too, but it does allow for functional purity and still allow global state and side effects. Regardless, you can implement basic monads in D just fine without any language support whatsoever. What you basically end up doing is passing around the global state to every function. It's returned as part of the result of the function. Think of passing the global state to every function and having those functions return a tuple of their actual return value and the global state. The caller takes out the actual return value to do whatever it does and passes on the global state variable to the next function that it calls and finally returning it in a tuple along with its own return value. Tuple!(Retval, GlobalState) func(GlobalState gs, otherparams...) { //.... return tuple(retval, gs); } Monads can be a bit hard to wrap your mind around, but they're ingenious. Haskell couldn't really exist without them. - Jonathan M Davis
Oct 18 2010
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 18 Oct 2010 20:07:16 -0400, Nick Sabalausky <a a.a> wrote:
 I don't know if others have noticed this before, but I think I've found a
 notable limitation in D's metaprogramming potential: There doesn't  
 appear to
 be a way to have mutable global state at compile-time.

 Challange:

 Create two..."things"...they can be functions, templates, variables,
 mix-n-match, whatever. One of them increments a counter, and the other  
 can
 be used to retreive the value. But both of these must operate at
 compile-time, and they must both be callable (directly or indirectly,
 doesn't matter) from within the context of any module that imports them.

 This is an example, except it operates at run-time, not compile-time:

 -----------------------------------
 // a.d
 module a;
 int value=0;
 void inc()
 {
     value++;
 }
 int get()
 {
     return value;
 }

 void incFromA()
 {
     inc();
 }

 //b.d
 module b;
 import a;
 void incFromB()
 {
     inc();
 }

 //main.d
 import a;
 import b;
 import std.stdio;
 void main()
 {
     inc();
     incFromA();
     incFromB();
     writeln(get());
 }
 -----------------------------------

 The goal of this challenge is to define a global-level manifest constant
 enum that holds a value that has been incremented from multiple modules:

 enum GOAL = ????;

 It can, of course, then be displayed via:
 pragma(msg, std.conv.to!string(GOAL));

 At this point, I'm not concerned about order-of-execution issues  
 resulting
 in unexpected or unpredictable values. As long as a value can be  
 incremented
 at compile-time from multiple modules and used to initialize an enum
 manifest constant, that satisfies this challenge.

This isn't exactly what you're looking for, but you can abuse conditional compilation + D's symbol table to create a scoped counter: string nthLabel(int n) { return "__Global_"~ to!string(n); } string incGlobal() { return `mixin("alias int "~nthLabel( getGlobal!(__FILE__, __LINE__) )~";");`; } template getGlobal(string file = __FILE__, int line = __LINE__, int N = 0) { static if( !__traits(compiles, mixin(nthLabel(N)) ) ) enum getGlobal = N; else enum getGlobal = getGlobal!(file,line, N+1 ); } enum Foo = getGlobal!(__FILE__, __LINE__) ; mixin( incGlobal() ); enum Bar = getGlobal!(__FILE__, __LINE__); mixin( incGlobal() ); enum FooBar = getGlobal!(__FILE__, __LINE__); void main(string[] args) { // 0 1 2 writeln(Foo,'\t',Bar,'\t',FooBar); return; }
Oct 18 2010
prev sibling next sibling parent Graham Fawcett <fawcett uwindsor.ca> writes:
Hi Jonathan,

On Mon, 18 Oct 2010 18:02:58 -0700, Jonathan M Davis wrote:

 On Monday, October 18, 2010 17:54:50 Nick Sabalausky wrote:
 "Jonathan M Davis" <jmdavisProg gmx.com> wrote in message
 news:mailman.715.1287449256.858.digitalmars-d puremagic.com...
 
 One word: monads.
 
 Now, to get monads to work, you're going to have to be fairly
 organized about it, but that would be the classic solution to not
 being able to have or alter global state and yet still be able to
 effectively have global state.

Oh yea, I've heard about them but don't have any real experience with them. Any FP experts know whether or not monads are known to be constructible from purely-FP building blocks? I always assumed "no", and that monads really just came from a deliberate compiler-provided hole in the whole purity thing, but maybe I'm wrong? (That would be quite interesting: constructing impurity from purity.)

You can think of a monad as an extra parameter which is passed to each function and holds the global state. It isn't a hole in purity at all. For instance, it's how Haskell manages to have I/O and yet be functionally pure. You don't need the compiler's help to do monads - it's just easier if you have it.

I don't see how monads will help here. Monads are useful for threading state through pure computations, and are an enabler for I/O in Haskell by threading the "real world" through a computation as a series of computational states. Something has to initiate the thread, and tie it up at the end: there's an implicit scope here, and I think here's where the hard questions start to crop up in the context of CTFE. Without permitting I/O, you could use a state-carrying monad to implement a kind of dynamically-scoped namespace during CTFE; the dynamically-scoped, mutable values would be global from the internal perspective of the CTFE computations, but they would not leak out of the monad into "truly global" state; and the overall effect would be pure. So, you can achieve an implicit, dynamic scope using monads. But if all CTFE expansions are done within a single such scope, it would be indistinguishable from running all CTFE expansions with access to globally shared state (though not I/O). So then, why not just use global state? Therefore, the monads could only practically be used as an isolation technique, to isolate dynamically scoped values during different CTFE expansions -- for example, at a compilation-unit level -- without sacrificing purity. But then, it seems you would lose the very thing you need to implement the challenge on the table: two modules would want access to the same counter during expansion, not two isolated copies of the counter. So again, you're back at global state, or mimicking it using a state-carrying monad, with no significant benefits accomplished by using a monad. Just my two cents, Graham
Oct 19 2010
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday 19 October 2010 12:13:19 Graham Fawcett wrote:
 Hi Jonathan,
 
 On Mon, 18 Oct 2010 18:02:58 -0700, Jonathan M Davis wrote:
 On Monday, October 18, 2010 17:54:50 Nick Sabalausky wrote:
 "Jonathan M Davis" <jmdavisProg gmx.com> wrote in message
 news:mailman.715.1287449256.858.digitalmars-d puremagic.com...
 
 One word: monads.
 
 Now, to get monads to work, you're going to have to be fairly
 organized about it, but that would be the classic solution to not
 being able to have or alter global state and yet still be able to
 effectively have global state.

Oh yea, I've heard about them but don't have any real experience with them. Any FP experts know whether or not monads are known to be constructible from purely-FP building blocks? I always assumed "no", and that monads really just came from a deliberate compiler-provided hole in the whole purity thing, but maybe I'm wrong? (That would be quite interesting: constructing impurity from purity.)

You can think of a monad as an extra parameter which is passed to each function and holds the global state. It isn't a hole in purity at all. For instance, it's how Haskell manages to have I/O and yet be functionally pure. You don't need the compiler's help to do monads - it's just easier if you have it.

I don't see how monads will help here. Monads are useful for threading state through pure computations, and are an enabler for I/O in Haskell by threading the "real world" through a computation as a series of computational states. Something has to initiate the thread, and tie it up at the end: there's an implicit scope here, and I think here's where the hard questions start to crop up in the context of CTFE. Without permitting I/O, you could use a state-carrying monad to implement a kind of dynamically-scoped namespace during CTFE; the dynamically-scoped, mutable values would be global from the internal perspective of the CTFE computations, but they would not leak out of the monad into "truly global" state; and the overall effect would be pure. So, you can achieve an implicit, dynamic scope using monads. But if all CTFE expansions are done within a single such scope, it would be indistinguishable from running all CTFE expansions with access to globally shared state (though not I/O). So then, why not just use global state? Therefore, the monads could only practically be used as an isolation technique, to isolate dynamically scoped values during different CTFE expansions -- for example, at a compilation-unit level -- without sacrificing purity. But then, it seems you would lose the very thing you need to implement the challenge on the table: two modules would want access to the same counter during expansion, not two isolated copies of the counter. So again, you're back at global state, or mimicking it using a state-carrying monad, with no significant benefits accomplished by using a monad. Just my two cents, Graham

I haven't really looked in detail at how you'd solve the problem in question, but I believe that you'd pretty much have to chain all of the initializations so that there is a clear one which is initialized first and that each successive initialization relies on the previous one, with the monad being passed along through each. I believe that that would work between modules as well, though I'm not 100% certain. Regardless, the solution is rather messy because you have to have the monad specifically passed along everywhere and have a fairly explicit ordering to the instantiation (though you might be able to decouple it a bit if all you care about was the final count and some of the initializations depended on multiple other instantations and combined their monads), so it's not a particularly pretty solution even if it works. However, if you're trying to have state in an effectively stateless environment, that's pretty much the only way that I know to go about doing it. What you really need is some sort of global state for CTFE, but static initialization is specifically designed so that it doesn't have global state (if nothing else to avoid order issues screwing with initializations), so I don't really see that happening any time soon, if ever. - Jonathan M Davis
Oct 19 2010