www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Pre-conditions at compile-time with static arguments

reply bearophile <bearophileHUGS lycos.com> writes:
This is a possible enhancement request for DMD. I am not sure about the
consequences of this, so this is currently not in Bugzilla, I look for opinions.

DMD currently runs functions at compile time only if their call is in a context
where a compile-time value is expected, to avoid troubles. C++0X uses a keyword
to avoid those problems.

[-----------------

Little box:

Time ago I have heard that "enum" is useless and const/immutable suffice. So if
"enum" gets removed from D how do you tell apart the desire to run a function
(not a global call) at compile time from the desire to run it at run time and
assign its result to a run-time constant value?

int bar(int x) {
    return x;
}
void main() {
    enum b1 = bar(10); // runs at compile-time
    const b2 = bar(20); // doesn't run at compile-time    
}

-----------------]

DMD is able to run contracts too at compile-time, as you see in this program
(at the r1 enum):


import std.ctype: isdigit;
int foo(string text, int x)
in {
    assert(x >= 0 && x < text.length);
    foreach (c; text[0 .. x])
        assert(isdigit(c));
} body {
    return 0;
}
enum r1 = foo("123xxx", 4); // Error: assert(isdigit(cast(dchar)c)) failed
void main(string[] args) {
    auto r2 = foo(args[2], (cast(int)args.length) - 5);
    auto r3 = foo("123xxx", 4);
}


test.d(3): Error: assert(x > 0) failed
test.d(7): Error: cannot evaluate foo(-1) at compile time
test.d(7): Error: cannot evaluate foo(-1) at compile time


Given that pre-conditions are meant to run fast and to be (nearly) pure, this
is my idea: when you call a function with all arguments known at compile time
(as at the r3 variable) the compiler runs just the pre-condition of that
function at compile-time (and not its body and post-condition).

The advantage is some bugs are caught at compile-time, and the compiler is kept
simple (I'd like contracts to be verified statically in more situations, but
this requires a more complex compiler). The disadvantage is longer compilation
times, and troubles caused by pre-conditions that can't really run at
compile-time (like a precondion that uses a compiler intrinsic). A way to solve
this last problem is to not raise an error if a pre-condition can't run at
compile-time, and just ignore it, and let it later run normally at run-time.

The variable r2 is a situation where not all arguments of foo() are known at
compile-time, so here the foo pre-condition is not run.


(Note: the variable r2 is a situation where one argument of foo is known at
run-time, and in this case the pre-condition contains a part
(assert(x>=0&&x<text.length)) that's able to use this information to catch a
bug. This is a possible improvement of the idea is to perform this partial
test. This looks less easy to implement, so it's not important).

Bye,
bearophile
Apr 25 2011
next sibling parent reply so <so so.so> writes:
On Mon, 25 Apr 2011 22:44:07 +0300, bearophile <bearophileHUGS lycos.com>  
wrote:

 This is a possible enhancement request for DMD. I am not sure about the  
 consequences of this, so this is currently not in Bugzilla, I look for  
 opinions.

 DMD currently runs functions at compile time only if their call is in a  
 context where a compile-time value is expected, to avoid troubles. C++0X  
 uses a keyword to avoid those problems.
constexpr double pi = 3; // C++ enum double pi = 3; // D constexpr double fun() { return 3; } // C++ double fun() { return 3; } // D For variable declaration, exact same thing. For functions, i am not exactly sure the need for a keyword and i think the D way is simply beautiful and truly generic. One reason i could think of is for library development, you sometimes want to be sure that a function "could be" executed at compile-time. In C++ there is no such thing i am aware of, in D we got unittesting.
 [-----------------

 Little box:

 Time ago I have heard that "enum" is useless and const/immutable  
 suffice. So if "enum" gets removed from D how do you tell apart the  
 desire to run a function (not a global call) at compile time from the  
 desire to run it at run time and assign its result to a run-time  
 constant value?

 int bar(int x) {
     return x;
 }
 void main() {
     enum b1 = bar(10); // runs at compile-time
     const b2 = bar(20); // doesn't run at compile-time
 }
Another question is why would the left hand side of "=" even matter? What is wrong with executing the function(constant) pair always at compile-time (if it could be executed that is)? Only reason using "enum, static, immutable" over "auto" should be "making sure" it runs at compile-time (again, if it can). Obviously we know the reasons for the desire for compile-time execution, is there any reason at all for runtime?
Apr 25 2011
next sibling parent so <so so.so> writes:
 Only reason using "enum, static, immutable" over "auto" should be  
 "making sure" it runs at compile-time (again, if it can).
Besides the obvious reason, making it immutable :)
Apr 25 2011
prev sibling parent so <so so.so> writes:
 Time ago I have heard that "enum" is useless and const/immutable  
 suffice.
AFAIK it wasn't clear, it was said that we adopted this usage of "enum" just because of some bugs in "const/immutable" but we also know "enum" and "immutable" have difference(s), especially related to this issue. We can't replace "enum" with "immutable". Answering my own question on another reply, for arguably same reasons function(constant) pair is not expected to run at compile-time unless it was labeled with "enum" or "static".
Apr 25 2011
prev sibling next sibling parent KennyTM~ <kennytm gmail.com> writes:
On Apr 26, 11 03:44, bearophile wrote:
 [-----------------

 Little box:

 Time ago I have heard that "enum" is useless and const/immutable suffice. So
if "enum" gets removed from D how do you tell apart the desire to run a
function (not a global call) at compile time from the desire to run it at run
time and assign its result to a run-time constant value?

 int bar(int x) {
      return x;
 }
 void main() {
      enum b1 = bar(10); // runs at compile-time
      const b2 = bar(20); // doesn't run at compile-time
 }

 -----------------]
static b1 = bar(20);
Apr 25 2011
prev sibling next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Apr 26, 11 03:44, bearophile wrote:
 Given that pre-conditions are meant to run fast and to be (nearly) pure, this
is my idea: when you call a function with all arguments known at compile time
(as at the r3 variable) the compiler runs just the pre-condition of that
function at compile-time (and not its body and post-condition).

 The advantage is some bugs are caught at compile-time, and the compiler is
kept simple (I'd like contracts to be verified statically in more situations,
but this requires a more complex compiler). The disadvantage is longer
compilation times, and troubles caused by pre-conditions that can't really run
at compile-time (like a precondion that uses a compiler intrinsic). A way to
solve this last problem is to not raise an error if a pre-condition can't run
at compile-time, and just ignore it, and let it later run normally at run-time.

 The variable r2 is a situation where not all arguments of foo() are known at
compile-time, so here the foo pre-condition is not run.


 (Note: the variable r2 is a situation where one argument of foo is known at
run-time, and in this case the pre-condition contains a part
(assert(x>=0&&x<text.length)) that's able to use this information to catch a
bug. This is a possible improvement of the idea is to perform this partial
test. This looks less easy to implement, so it's not important).

 Bye,
 bearophile
I feel this isn't right. The input or the precondition is very often not compile-time evaluable, thus it just won't run. An example grabbed from my code near by: foreach (key; keys) // <-- keys is usually not known at compile time assert(key !in _map); // <-- 'in' is not CTFE-able (yet). Also, if the precondition were complaining, and you change some bit of the code and find it can be compiled -- that won't mean anything, as it is likely the change just make the precondition non-CTFE-able. The benefit doesn't worth the cost. (And this is yet another kind of 0% false-positive-rate, non-zero false-negative-rate feature. I bet you'll get a "false sense of security" response. Personally I'd rather have the compiler to catch 50% of compile-time detectable errors than leaving 100% of them to run time.) I also don't believe this still keeps the compiler simple, as now there are 2 kinds of CTFE error the compiler needs to distinguish: assert errors and non-assert errors. I don't know much about the compiler intrinsic, and actually the D front-end is already very complicated :), so this doesn't matter.
Apr 25 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
KennyTM~:

 Also, if the precondition were complaining, and you change some bit of 
 the code and find it can be compiled -- that won't mean anything, as it 
 is likely the change just make the precondition non-CTFE-able.
You are right, this is bad. But the compile-time interpreter is getting able to run a larger percentage of D code, so that problem becomes smaller, and this idea doesn't give false positives.
 I also don't believe this still keeps the compiler simple,
It's _way_ simpler than solutions like one in Sing#. Here you don't need a powerful symbolic constraint solver inside the compiler :-) All the needed tools are already present. Bye, bearophile
Apr 25 2011
parent KennyTM~ <kennytm gmail.com> writes:
On Apr 26, 11 07:25, bearophile wrote:
 KennyTM~:

 Also, if the precondition were complaining, and you change some bit of
 the code and find it can be compiled -- that won't mean anything, as it
 is likely the change just make the precondition non-CTFE-able.
You are right, this is bad. But the compile-time interpreter is getting able to run a larger percentage of D code, so that problem becomes smaller, and this idea doesn't give false positives.
 I also don't believe this still keeps the compiler simple,
It's _way_ simpler than solutions like one in Sing#. Here you don't need a powerful symbolic constraint solver inside the compiler :-) All the needed tools are already present. Bye, bearophile
I see. I was comparing to the current situation where such feature does _not_ exist.
Apr 25 2011
prev sibling next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
bearophile wrote:
 Given that pre-conditions are meant to run fast and to be (nearly)
 pure, this is my idea: when you call a function with all arguments
 known at compile time (as at the r3 variable) the compiler runs just
 the pre-condition of that function at compile-time (and not its body
 and post-condition).
 
 The advantage is some bugs are caught at compile-time, and the
 compiler is kept simple (I'd like contracts to be verified statically
 in more situations, but this requires a more complex compiler). The
 disadvantage is longer compilation times, and troubles caused by
 pre-conditions that can't really run at compile-time (like a
 precondion that uses a compiler intrinsic). A way to solve this last
 problem is to not raise an error if a pre-condition can't run at
 compile-time, and just ignore it, and let it later run normally at
 run-time.
We thought about this approach and deliberately did not do it. It is not predictable at compile time whether a function can be executed at compile time or not (the halting problem). Therefore, you'll wind up with cases that silently fail at compile time, and so are put off until runtime. The user cannot tell (without looking at assembly dumps) if it happened at compile time or not. Instead, we opted for a design that either must run at compile time, or must run at run time. Not one that decides one way or the other in an arbitrary, silent, and ever-changing manner. The user must make an explicit choice if code is to be run at compile time or run time. D has had this in operation for several years, and it's been a big success. I don't think we should tamper with the formula without very compelling evidence.
Apr 25 2011
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
I was distracted and with a unfocused mind, sorry for the late reply.

Walter:

 We thought about this approach and deliberately did not do it.
Thank you for your answer. Sometimes it doesn't harm to think again a bit about a topic.
 It is not predictable at compile time whether a function can be executed
 at compile time or not (the halting problem). Therefore, you'll wind up
 with cases that silently fail at compile time, and so are put off until
 runtime. The user cannot tell (without looking at assembly dumps) if it
 happened at compile time or not.
 
 Instead, we opted for a design that either must run at compile time, or
 must run at run time. Not one that decides one way or the other in an
 arbitrary, silent, and ever-changing manner.
In this discussion I was talking about running just the pre-conditions, and not the whole function, and not its post-condition. This is different because: - Pre-conditions are usually small or smaller than function bodies; - Pre-conditions are usually meant to be fast (and not slower than the function body), so they are probably not too much heavy to run. pre-conditions, unlike debug{} code are meant to run often; - Pre-conditions are often pure (mine). If the "feature" I am talking about gets introduced, D programmers will be encouraged to write more pure preconditions (this probably explains why most other Contract-based systems I've seen don't use free code in contracts as D does, but use a specific expression language. This forces them to be pure and simpler, more fit for analysis!). Even if a function is not marked as "pure", what matters in this discussion is to its pre-condition to be CTFE-pure. The problem you list is of course important for the normally run CT functions, and I agree with the decision. But it's much less important for my idea, because I've seen that finding bug in code is essentially never a deterministic process, it's very probabilistic. People find only some bugs (people today find new bugs even in 10+ years old very-high-quality C code used by everyone (Zlib)), lint tools (including the static analysis flag of Clang I've shown recently) find only some other bugs, and different lints find different bugs. One important factor for those tools is to reduce false positives as much as possible (even if this increases false negatives a little), and this idea of mine produced zero false alarms (if the pre-conditions are written correctly). This feature is useful because when in your code you have struct literals like: Foo f1 = Foo(10, -20); The compiler is able at compile-time to tell you that line of code is wrong because -20 is not acceptable :-) This is useful in many situations. This feature works only if the arguments are known at compile-time, this is a strong limitation, but I think it's better to have it anyway. Even if this feature sometimes gets disabled by turning a CTFE-pure function pre-condition into not CTFE-pure code as you say, the programmer doesn't need to care a lot about this, because even if this change doesn't allow to catch a bug in the code, other bugs too are not found by the compiler. All static analysis tools do the same, they sometimes find a bug, but if you change the code in a way they don't fully understand, they don't find the bug any more. This is why I think your argument doesn't hold. The feature I have proposed is not a language feature, it's a compiler feature (the only change is in user code, that's encouraged to create CTFE-pure pre-conditions). This means that even if DMD doesn't want this idea, future D compilers will be free to adopt it. And from the direction of the tide (as Clang adds better and better analysis for C and C++ code) I think this will be seen as a cheap but useful compiler feature to add (a "low-hanging fruit" because the only needed compiler change I see needed is to not stop the compilation if a pre-condition of a function with statically known arguments turns out to be not runnable). Bye, bearophile
Apr 26 2011