Do you know the history of D CTFE? What was the start of it, etc. Is the CTFE idea coming from the C++0x constexpr?

Bye,
bearophile

V Thu, 18 Nov 2010 20:13:40 -0500, bearophile wrote:

> Do you know the history of D CTFE? What was the start of it, etc. Is the CTFE idea coming from the C++0x constexpr?
> 
> Bye,
> bearophile

It is very! interesting to have look at the history of D, thanks to forum archives. CTFE was first introduced in DMD 1.006...see thread "Compile time function execution..." at http://www.digitalmars.com/d/archives/ digitalmars/D/index2007.html. In the previous discussion you can see this idea forming (I searched for the word "compile").

Michal Minich:

>see thread "Compile time function execution..." at http://www.digitalmars.com/d/archives/ digitalmars/D/index2007.html. In the previous discussion you can see this idea forming (I searched for the word "compile").<

Thank you, I have found and read some of those threads. It seems the idea of CTFE comes from 3-4 persons, and it has evolved progressively from finding the limits of template-based execution of regex, it was not invented in a single step by a single person. It's indeed an interesting story, worth writing a little article about. The "constexpr" has shown up in the threads only after CTFE was already in DMD, so maybe there is no direct influence of it.

After reading some of those threads I have a new question. Let's say I have a function bad() that I want to run at CT, it calls two functions, a slow CT function named aVerySlowCTFunction() and a function notCTExecutable() that can't be run at CT:


int aVerySlowCTFunction(int x) {
    int count;
    foreach(i; 0 .. x)
        foreach(j; 0 .. x)
            foreach(k; 0 .. x)
                count++;
    return count;
}

class Foo {
    int bar(int y) { return y; }
}

int notCTExecutable(int y) {
    // not currently possible in CTFE
    return (new Foo()).bar(y);
}

int bad(int x) {
    auto y = aVerySlowCTFunction(x); // good
    return notCTExecutable(y); // bad
}

enum int z = bad(120);

void main() {}


Now the compiler runs aVerySlowCTFunction() and only later it finds that notCTExecutable() can't be run at compile-time and returns an error. This isn't a tidy design for CTFE (but it probably allows a simpler implementation of it). Is this going to be a problem in programs that use CTFE a lot? It looks even worse than Python dynamic typing, this seems dynamic compilation :-)

Bye,
bearophile

bearophile wrote:
> Michal Minich:
> 
>> see thread "Compile time function execution..." at http://www.digitalmars.com/d/archives/ digitalmars/D/index2007.html. In the previous discussion you can see this idea forming (I searched for the word "compile").<
> 
> Thank you, I have found and read some of those threads. It seems the idea of CTFE comes from 3-4 persons, and it has evolved progressively from finding the limits of template-based execution of regex, it was not invented in a single step by a single person. It's indeed an interesting story, worth writing a little article about. The "constexpr" has shown up in the threads only after CTFE was already in DMD, so maybe there is no direct influence of it.

There was absolutely no influence from constexpr.

The story starts here:

http://www.digitalmars.com/d/archives/digitalmars/D/learn/1991.html

As far as I can tell, at the very beginning of D, when it was still called the "Mars programming language", the key idea of Mars was dynamic arrays and array slices. In the oldest file in the DMD source code, they are called "Jupiter arrays".

An unforseen consequence of this support for slicing was that the compiler had considerable built-in semantics for array and string processing. Many metaprogramming things just worked. In fact, so many things worked, that the gaps became obvious, and so we filled them in.
It all felt very natural.
Essentially, we followed the implications of the existing language, and ended up with CTFE.


> After reading some of those threads I have a new question. 
> Let's say I have a function bad() that I want to run at CT, it calls two functions, a slow CT function named aVerySlowCTFunction() and a function notCTExecutable() that can't be run at CT:
> int bad(int x) {
>     auto y = aVerySlowCTFunction(x); // good
>     return notCTExecutable(y); // bad
> }
> 
> enum int z = bad(120);
> 
> void main() {}
> 
> 
> Now the compiler runs aVerySlowCTFunction() and only later it finds that notCTExecutable() can't be run at compile-time and returns an error. 

> This isn't a tidy design for CTFE (but it probably allows a simpler implementation of it). 

> Is this going to be a problem in programs that use CTFE a lot? It looks even worse than Python dynamic typing, this seems dynamic compilation :-)

I think that sort of thing will be pretty rare, once CTFE is fully implemented. But tt would not be very difficult to implement a check for that.
Still, CTFE functions are always going to fail when they divide by zero, exceed array bounds, etc.

Don:

> There was absolutely no influence from constexpr.

I suspected this.


> the key idea of Mars was dynamic
> arrays and array slices. In the oldest file in the DMD source code, they
> are called "Jupiter arrays".

Wonderful. I presume no other language in Reddit threads sports that language feature. They sound even better than Judy arrays... ;-)


> Essentially, we followed the implications of the existing language, and ended up with CTFE.

I see, thank you for the info. So you have given an important starting help to the creation of the CTFE idea. There is enough material to write a not too much boring article about this five years long story.


> But tt would not be very difficult to implement a check for that.

Very good, then it may be added later, if necessary.


> Still, CTFE functions are always going to fail when they divide by zero, exceed array bounds, etc.

Compile-time exceptions may be possible. They may help a little on this.

Bye and thank you,
bearophile

bearophile <bearophileHUGS@lycos.com> wrote:

> Do you know the history of D CTFE? What was the start of it, etc. Is the CTFE idea coming from the C++0x constexpr?

If you don't mind the paranoia, might I ask if you really are bearophile?
You... feel different. Maybe it's just the lack of references to other
languages, and no bug reports mentioned in this post. :p


-- 
Simen

Simen kjaeraas:

> If you don't mind the paranoia, might I ask if you really are bearophile? You... feel different. Maybe it's just the lack of references to other languages, and no bug reports mentioned in this post. :p

You are right. Here's a bug report, in the thread Don has shown me he refers to "Fibonnacci" few times:
http://www.digitalmars.com/d/archives/digitalmars/D/learn/1991.html
But the correct surname is Fibonacci:
http://en.wikipedia.org/wiki/Fibonacci

Bye,
bearophile

Michal Minich wrote:
> It is very! interesting to have look at the history of D, thanks to forum archives. CTFE was first introduced in DMD 1.006...


Yes, that's when interpret.c appeared, which implements it.