February 15, 2007
BCS wrote:

>>> 6) when the whole program is const foldable, e.i. no runtime inputs, like with some scientific software.
>>>
>> That's interesting. What kind of program has no runtime inputs?
>>
>> And why would it be a problem if the whole program is reduced to printing constants to the output? It would certainly be small and fast.
> 
> I have a program that calculates the number of N length sequences whose sum is less than M. M and N are consts so it has no inputs. Runtime speed is of no more importance than compile time speed because I only need to run it once for each time I compile it. I'd rather let the CPU do the crunching rather than the DMD. It takes about 15min to run as is, so that would be about 1500+ min under DMD.

Ah, now I understand the fuss. :) Walter is using an interpreter for the compile time execution.

All this time I was assuming multiple compilation stages. First compile the compile-time functions and let the processor run them at compile time.

-- 
Michiel
February 15, 2007
Michiel kirjoitti:
> BCS wrote:
> 
>> 6) when the whole program is const foldable, e.i. no runtime inputs, like with some scientific software.
> 
> And why would it be a problem if the whole program is reduced to printing constants to the output? It would certainly be small and fast.

If the compiler generates a new instance of the algorithm whenever it is needed (i.e. function is partially evaluated), it can actually produce longer code than when simply calling the same function over and over. It's almost like inlining functions whenever possible.
February 15, 2007
Jari-Matti Mäkelä wrote:

>>> 6) when the whole program is const foldable, e.i. no runtime inputs, like with some scientific software.
>>
>> And why would it be a problem if the whole program is reduced to printing constants to the output? It would certainly be small and fast.
> 
> If the compiler generates a new instance of the algorithm whenever it is needed (i.e. function is partially evaluated), it can actually produce longer code than when simply calling the same function over and over. It's almost like inlining functions whenever possible.

That's actually not the idea. Basically, the idea is that the compiler runs the algorithm and replaces every call to it with the answer. It's possible (though unlikely), that the executable would be a bit larger, but the executable would be much faster. And memory we have. In most cases it's speed that's the problem.

-- 
Michiel
February 16, 2007
Michiel wrote:
> Walter Bright wrote:
> 
>>>> Many functions could be executed at compile time, but should not be.
>>> When should they not be?
>> 1) Another poster mentioned a function that decompressed a built-in
>> string - the whole point of having it compressed was to reduce the exe
>> file size. Decompressing it at compile time defeats the purpose.
> 
> Yes, that one was mentioned by Bill Baxter. But I think this is the
> exception rather than the rule. The programmer could explicitly tell the
> compiler to not execute that piece of code at runtime.

The programmer *already* has explicit control over whether it is folded or not.
February 16, 2007
Walter Bright wrote:
> Bill Baxter wrote:
>> Walter Bright wrote:
>>> ... is now in DMD 1.006. For example:
>>>
>>
>> Very nice!
>>
>> A few questions:
>> 1) You say recursion is allowed -- does it do proper tail recursion?
> 
> Tail recursion is a performance optimization, it has no effect on semantics, so it's not an issue for compile time execution.
> 
>> 2) Can't you just ignore 'synchronized' at compile time?
> 
> Pure functions (the kind that can be compile time executed) don't need to be synchronized anyway.
> 
>> 3) Would it be possible to add some sort of a version(CompileTime)? This would make it possible for those who want to be *sure* the function is only used at compile time to simply have it not exist as a runtime call.  It could also be used to make slight modifications to functions that one would like to use as both compile-time and run-time.  For example if you want to have synchronized/try/catch/throw/writefln type things in the runtime version.
> 
> Once more, there is never a situation where a function *might* or *might not* get executed at compile time. A function is *always* executed at runtime unless it is in a situation where it *must* be executed at compile time, such as in an initializer for a global.

Right.  But if I understand correctly, the same code can get called either at runtime or compile time depending on the situation.

But what if I want the runtime version to print out a message.  Or add to a global counter variable for some simple home-brew profiling stats. 
 It would be handy then if I could do:

int square(int x) {
   version(compiletime) {}else{
     writefln("trace: square");
     G_CallsToSquare++;
   }
   return (x*x);
}

I think I'm getting at the same kind of thing Andrei is talking about. I don't want to have to limit what I do in the runtime version in order to make it acceptable for compile time.  He's saying I should be able to have two versions of the function, one for compile time and one for run time.  I think that's useful too.  But for simpler cases like the above, it would be nice I think if one could just version-out the bad parts.

And in this case:

int calculationIShouldOnlyDoAtCompileTime(int x)
{
   // * whatever it is *
}

int K = calculationIShouldOnlyDoAtCompileTime(4);

Whoops!  Silly programmer, looks like I forgot the 'const' on K.  Would be nice if I could get the compiler to remind me when I'm silly like that.  That could be arranged if there were a version(CompileTime).

I think one holy grail of this stuff (and one Lisp apparently attained in the 60's or 70's) is to just be able to treat everything as either compile-time or run-time depending on how much information you have.

For instance, it's not uncommon to make a fixed length vector class using templates.  Vec!(N) kind of thing.  But it would really be nice if the majority of that code could remain even when N is not constant. That means both on the user side and on the implementation side.  I don't know how realistic that is, but I often find myself sitting on the fence trying to decide -- do I make this a compile-time parameter, thereby cutting off all opportunity for runtime creation of a particular instance, or do I make it runtime, thereby cutting my and the compiler's opportunity to make several obvious optimizations.

--bb
February 16, 2007
Walter Bright wrote:

>>>>> Many functions could be executed at compile time, but should not be.
>>>> When should they not be?
>>> 1) Another poster mentioned a function that decompressed a built-in string - the whole point of having it compressed was to reduce the exe file size. Decompressing it at compile time defeats the purpose.
>>
>> Yes, that one was mentioned by Bill Baxter. But I think this is the exception rather than the rule. The programmer could explicitly tell the compiler to not execute that piece of code at runtime.
> 
> The programmer *already* has explicit control over whether it is folded or not.

Correction, I meant to say: "The programmer could explicitly tell the compiler to not execute that piece of code at *compile time*."

And yes, the programmer already has explicit control. But not the way I mean. Right now, in places where a call could potentially be either a runtime- or compiletime- execution:

* the compiler defaults to runtime execution. And like I said, that behavior isn't wanted in most cases (when compiling for release). I would suggest defaulting to compile time execution and using a special keyword to avoid that. The programmer will use this keyword if he's compressed some data and wants it to be decompressed at runtime.

* the syntax for functions to be executed at compile time isn't the nice-and-simple D syntax, but the template-syntax. And in another thread you yourself have mentioned why that's not optimal. I agree.

-- 
Michiel
February 16, 2007
Walter Bright wrote:
> Bill Baxter wrote:
>> Walter Bright wrote:
>>> ... is now in DMD 1.006. For example:
>>>
>>
>> Very nice!
>>
>> A few questions:
>> 1) You say recursion is allowed -- does it do proper tail recursion?
> 
> Tail recursion is a performance optimization, it has no effect on semantics, so it's not an issue for compile time execution.

Yeh, it's not a big deal.  I was more just curious since you recently added it back to DMD.  And since it does affect the /effective/ semantics if you have a very deep recursion that overflows the stack. Or is the stack for compile-time execution is actually on the heap?

Either way, it might actually be /better/ to have the compile-time implementation have a limited stack so that infinite recursion errors result in stack overflows rather than just the compiler hanging.

--bb
February 16, 2007
Ary Manzana wrote:
> A question: is there anyway the compiler can tell the user if a certain function can be executed at compile time? Those six rules may be hard to memorize and while coding sensitive code it would be great to ask the compiler "Is the function I'm writing can be executed at compile time?". Otherwise it's just a guess.

Walter pointed out, faster than I, that an eval!() template does this.

But here's my question: How do we have a compile-time switch which controls what to compile-time evaluate and what not?  Somebody mentioned, elsewhere, that you would not want to do compile-time evaluation in a debug build but you would in a release build.  How would one achieve that, other than wrapping every use with a version switch?
February 16, 2007
Michiel wrote:
> BCS wrote:
> 
>> 6) when the whole program is const foldable, e.i. no runtime inputs,
>> like with some scientific software.
> 
> That's interesting. What kind of program has no runtime inputs?
> 
> And why would it be a problem if the whole program is reduced to
> printing constants to the output? It would certainly be small and fast.

How about:

import std.stdio;
void main() {
  writefln("%d\n", CalculateTheAnswerToLifeUniverseEverything());
}

if it took 7.5 million years to run on a supercomputer, how long is it going to take to run on your compiler?
February 16, 2007
Walter Bright wrote:
> ... is now in DMD 1.006. For example:
> 
>> -------------------------------------------
>> import std.stdio;
>>
>> real sqrt(real x)
>> {
>>    real root = x / 2;
>>    for (int ntries = 0; ntries < 5; ntries++)
>>    {
>>        if (root * root - x == 0)
>>            break;
>>        root = (root + x / root) / 2;
>>    }
>>    return root;
>> }
>>
>> void main()
>> {
>>    static x = sqrt(10);   // woo-hoo! set to 3.16228 at compile time!
>>    writefln("%s, %s", x, sqrt(10));  // this sqrt(10) runs at run time
>> }
>> ------------------------------------------
> 
> This should obsolete using templates to compute values at compile time.

This doesn't seem to work either -- should it?


char[] UpToSpace(char[] x)
{
    int i=0;
    while (i<x.length && x[i] != ' ') {
        i++;
    }
    return x[0..i];
}

void main()
{
    const y = UpToSpace("first space was after first");
    writefln(y);
}

It prints out the whole string rather than just "first".

If you change it to return 'i' it does correctly evaluate to 5.
If you change it to just 'return x[0..5];'  it also works correctly.

--bb
1 2 3 4 5 6 7 8 9 10 11 12 13 14