www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How far can CTFE go?

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
I'm experimenting with pluggable expression parser modules, and I'm
wondering if I can use CTFE to build parser tables and such. What are
the current limitations of CTFE? Are dynamic arrays of structs
supported? Associative arrays?  What about compile-time cross-module
initialization?

The idea is to have a library of modules that parse different kinds of
expressions, and depending on which subset of modules are actually
imported into the main program, the capability of the generated parser
will vary. E.g., the basic parser understands only scalar expressions;
import the vector module and it gets extended to handle vector
expressions; import another module and it understands other kinds of
expressions (matrices, etc.).  The parser will be fully specified at
compile-time (I'm not planning to support dynamically loading parsing
modules), so ideally this should be possible to handle using CTFE.

Or is this just a fool's errand?

On another level, how far are we expecting CTFE to go eventually? In my
mind, the ideal situation would be that CTFE can replace writing an
arbitrarily complex helper program that generates D code (either
functions or data, etc.) which then gets incorporated into the main
program.


T

-- 
Guns don't kill people. Bullets do.
Feb 02 2012
next sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
H. S. Teoh wrote:


 the ideal situation would be that CTFE can replace writing an
 arbitrarily complex helper program


Aebitrary complex helper programs may include viruses and other nice 
surprises. Walter does not want that adminstrators have to worry about 
a compilation step to torture the system in such a way.

Which restrictions may supress such torture seems unknown.

-manfred
Feb 02 2012
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Feb 03, 2012 at 12:51:51AM +0000, Manfred Nowak wrote:

 H. S. Teoh wrote:
 

 the ideal situation would be that CTFE can replace writing an
 arbitrarily complex helper program


 
 Aebitrary complex helper programs may include viruses and other nice 
 surprises. Walter does not want that adminstrators have to worry about 
 a compilation step to torture the system in such a way.


[...]

Well, random source code you downloaded over the internet may contain
trojans with embedded viruses, so I don't think CTFE would make this
problem any worse. You *are* running the virus either way, whether it's
compiling the helper programs first and running them (e.g., by running
the makefile or build script), or having the compiler run the virus via
CTFE.

Plus, if you're worried about CTFE being abused to cause problems with
the machine it's being compiled on, the current implementation already
suffers from the halting problem: the compiler cannot tell whether a
CTFE function will ever terminate. It could simply just keep consuming
more and more compiler resources (say, by continually appending to an
array) until memory is exhausted. And we all know the halting problem is
unsolvable. I don't think that should be grounds to get rid of CTFE,
though.


T

-- 
Кто везде - тот нигде.
Feb 02 2012
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
H. S. Teoh wrote:


 I don't think that should be grounds to get rid of CTFE,
 though.


In contrast to your remark, I do not see the benefits of reducing two 
compiling phases to one. For me CTFE ist nothing else than running the 
executables of a first compilation in order to get some values needed 
for a second compilation.

-manfred
Feb 02 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/03/2012 04:26 AM, Manfred Nowak wrote:

 H. S. Teoh wrote:


 I don't think that should be grounds to get rid of CTFE,
 though.


 In contrast to your remark, I do not see the benefits of reducing two
 compiling phases to one. For me CTFE ist nothing else than running the
 executables of a first compilation in order to get some values needed
 for a second compilation.

 -manfred


- needed for a third compilation, needed for a fourth compilation, 
needed for a fifth compilation ...

- better syntax, can do complex things without obfuscating the code

- no need to serialize and feed back the data into the compiler

- more convenient!

- faster

- very cool


You probably haven't made extensive use of the feature. For me it is the 
main reason to choose D for development.
Feb 03 2012
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Timon Gehr wrote:


 You probably haven't made extensive use of the feature.


That is correct.


 - needed for a third compilation, needed for a fourth compilation,
 needed for a fifth compilation ...


Provide an example please and I will change my opinion.


 - better syntax, can do complex things without obfuscating the
 code 


If the codes for more than one _needed_ phase are tangled into one code 
base, I call that an "obfuscated" base. 

-manfred
Feb 03 2012
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Feb 04, 2012 at 02:36:10AM +0000, Manfred Nowak wrote:
[...]

 - better syntax, can do complex things without obfuscating the
 code 


 If the codes for more than one _needed_ phase are tangled into one
 code base, I call that an "obfuscated" base. 


[...]

One major advantage of CTFE that is covered in TDPL is compile-time
validation of generated code. The example was generating a linear
congruential engine for generating random numbers. The CTFE is used not
only for generating the congruential engine code, but also to validate
that its generating parameters do not lead to poor behaviour such as a
very short period.

If this was code generated by an external utility, you cannot easily
validate the resulting code. Worse yet, the external utility generates
correct code (e.g. a linear congruential generator with a maximal
period) but the user goes and edits one of the parameters, it turns into
a generator with a bad period. There's no easy way to prevent this.
With CTFE, all generated linear congruential generators are *guaranteed*
to have maximal periods, because the CTFE simply refuses to generate
something with bad parameters.

Also, functions used in CTFE can *also* be used at runtime. If you were
forced to generate code by an external utility, there may not be a nice
way of reusing code in this way, and there's the possibility that you
will accidentally end up using two different versions of the function,
leading to subtle hard-to-find bugs. With CTFE, it is guaranteed that
the function used to generate the compile-time data is exactly the same
as the one that is used at runtime to generate other data.


T

-- 
There are 10 kinds of people in the world: those who can count in binary, and
those who can't.
Feb 03 2012
parent Manfred Nowak <svv1999 hotmail.com> writes:
H. S. Teoh wrote:


 If this was code generated by an external utility


I wasn't argumenting for using external utilities, but against the 
argument, that separating code for separatable phases would obfuscate 
the code.


 for more than one _needed_ phase


 compile-time validation of generated code


The proof for more than one needed phase is missing and I doubt that 
there is one, because validation is part of checking contracts, which 
are not included in the `-release' compilation by definition. 

-manfred
Feb 04 2012
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/03/2012 12:22 AM, H. S. Teoh wrote:

 I'm experimenting with pluggable expression parser modules, and I'm
 wondering if I can use CTFE to build parser tables and such. What are
 the current limitations of CTFE? Are dynamic arrays of structs
 supported? Associative arrays?  What about compile-time cross-module
 initialization?

 The idea is to have a library of modules that parse different kinds of
 expressions, and depending on which subset of modules are actually
 imported into the main program, the capability of the generated parser
 will vary. E.g., the basic parser understands only scalar expressions;
 import the vector module and it gets extended to handle vector
 expressions; import another module and it understands other kinds of
 expressions (matrices, etc.).  The parser will be fully specified at
 compile-time (I'm not planning to support dynamically loading parsing
 modules), so ideally this should be possible to handle using CTFE.

 Or is this just a fool's errand?


This should work just fine. There is at least one compile-time parser 
generator for D around, but I cannot find it.


 On another level, how far are we expecting CTFE to go eventually? In my
 mind, the ideal situation would be that CTFE can replace writing an
 arbitrarily complex helper program that generates D code (either
 functions or data, etc.) which then gets incorporated into the main
 program.


 T


It can already do that!

mixin(arbitrarily_complex_helper_function());
Feb 03 2012
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Feb 04, 2012 at 01:54:55AM +0100, Timon Gehr wrote:
[...]

On another level, how far are we expecting CTFE to go eventually? In
my mind, the ideal situation would be that CTFE can replace writing
an arbitrarily complex helper program that generates D code (either
functions or data, etc.) which then gets incorporated into the main
program.




[...]

 
 It can already do that!
 
 mixin(arbitrarily_complex_helper_function());


[...]

Yes, but how complete is the support for this? Last I checked, I
couldn't call floating-point functions in the helper function 'cos
std.math apparently uses asm to implement some of the math functions,
and gdc refuses to evaluate that at compile-time.

And IIRC, TDPL does mention that certain language constructs can't be
used due to compiler limitations. (I'll have to look that up again when
I get home.)

But my original question pertains to cross-module initialization. Can
the following can be achieved?:

- The parser module (or parser generator module as the case may be)
  needs to collect info for all modules to be included in the final
  parser so that it can generate tables used by the parsing engine.

- Ideally, the act of compiling one of these pluggable modules should
  automatically include itself into the parsing tables.

- The tables should ideally be fully computed at compile-time.

The main challenge is, how to have the pluggable module inform the
parser module of its presence *at compile time*? Ideally, the parser
module shouldn't need to keep a big list of potential modules; it should
be the modules that register themselves with the parser. This is easily
done with a static init method, obviously, but the challenge is how to
achieve this at compile time.

One way I can think of is for the module that contains main() decide
which modules it wants to include, and call the parser module's setup
function via CTFE with the list of modules it should lookup. So then the
question becomes, given a list of modules represented as strings, is it
possible for CTFE to do symbol lookups of that module at compile-time?

This seems as far as I can go, at least from what I know. It would be
nice if the main module doesn't even need to pass a list of modules to
the parser generator, just link the relevant modules, and have the
parser generator automatically detect what modules are present. But I
suspect that won't work 'cos by the time we get to the linker it's too
late to know which modules were included.


T

-- 
Don't throw out the baby with the bathwater. Use your hands...
Feb 03 2012