www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - CTFE history

reply bearophile <bearophileHUGS lycos.com> writes:
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
Nov 18 2010
next sibling parent reply Michal Minich <michal.minich gmail.com> writes:
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").
Nov 19 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Nov 19 2010
parent reply Don <nospam nospam.com> writes:
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.
Nov 19 2010
parent bearophile <bearophileHUGS lycos.com> writes:
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
Nov 19 2010
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Nov 22 2010
prev sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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
Nov 19 2010
parent bearophile <bearophileHUGS lycos.com> writes:
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
Nov 19 2010