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