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 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
next sibling 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
next sibling 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 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 parent reply 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
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
prev 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