On Wednesday, 24 July 2013 at 01:07:15 UTC, H. S. Teoh wrote:
On Wed, Jul 24, 2013 at 01:35:23AM +0200, JS wrote:
[...]
My three points out of the post is:
1. D needs some way to make doing this stuff easier.
2. It needs to be done! ;)
3. Goto 1.
I didn't realize D could even potentially do it, and still not
sure
if it can(have to check out T's post again and work with the
code).
I think there is a lot of potential power behind such
techniques
with regard to optimization.
Suppose you are writing a matrix library. Wouldn't it be nice
to
have certain matrix computations that can be done at compile
time
actually done? (I suppose what I'm trying to do is extend the
compiler's "constant folding" to be able to deal with much more
complex cases).
[...]
Your tuple reduce seems to work! Debugging the code shows no
loops and memory debugging looks like the adjacent constants are
folded! magnificent!
As far as over optimizing, I am trying to write some library code
and want to "get it right" the first time... having it not only
optimize the best it can but also make the functions easier to
use... e.g., variargs instead of nested calls.
As far as ctfe running time issues, I believe they exist already?
In any case, the compiler at some point has to mark a variable
that is compile time evaluable as not evaluable at some
point(probably at a function call)
What we do know is arguments to ctfe's return compile time
evaluable results... So it is easy to know that a variable is
compile time evaluable but not necessarily actually be able to
compute it at compile time.... a simple time out count with
error/warning could be used... if failed it could be marked as a
run-time entity at that point and beyond(so no optimization
beyond the point where it can't be computed at compile time. Not
perfect but covers 99.99% of cases.
You're looking for expression templates. So far, nobody seems
to have
written expression templates in D yet (that I know of, anyway,
I could
be wrong). D should be more than well-equipped to handle
expression
templates, you just have to write them. (But having said that,
they
aren't exactly easy to write. :-P)
I think I'll pass, I'm still struggling just to learn D. You,
OTH, seem like someone that can pull it off rather easily!
I think the last time this topic came up, somebody mentioned
the dreaded
mythical AST macros, and the discussion got derailed. I've been
meaning
to write a D matrix library using expression templates, but I
haven't
gotten around to it yet.
The basic idea behind expression templates is that overloaded
operators
(or function calls, if operator overloading isn't good enough
for you)
don't return concrete types, but a proxy wrapper type that gets
unboxed
into a real type when assigned to a concrete variable. The
operators are
overloaded to take these wrapper types as arguments, and
basically
construct a template tree paralleling the structure of the
expression so
that when you're finally assigning the result to a concrete
variable,
the assignment operator can traverse the expression tree, fold
constants
and do whatever other optimizations you wish, then generate
optimized
code for performing the operation represented by the tree.
That's the theory anyway. In practice, expression templates are
rather
hard to write (and read!) if you're the unlucky library writer
(it *is*
really nice from the user's POV though!). They are also one of
the
sources of C++ error messages that span 15 pages per line, if
you're
ever unlucky enough to run into a problem.
Last I was told, however, that the preferred approach in D is
to use
string mixins instead. You basically write a string containing
an
arbitrary expression (of arbtrary syntax, even!) that gets
parsed by a
CTFE lexer/parser that can perform arbitrary transformations on
it,
which generates D code as a string that you can use in a mixin.
This is
significantly more powerful than expression templates, because
you're no
longer constrained by the syntax of the host language, but your
input
string can be literally *anything*, like a DSL, or a math
expression
containing real, bona fide Unicode mathematical symbols for
operators,
sets, and what-have-you. You could even write your own language
that
way. All of it eventually gets compiled down into D code as a
string
mixin.
Syntax-wise, there's the slight ugliness of having to write
"mixin(MyDSL("A ± B / C → D"))", but that's more than
outweighed by the
total freedom of syntax within the input string itself. I saw an
expression-template-based regex implementation in C++ once, and
almost
went blind. It overloaded C++ operators in rather ugly ways in
order to
work around the fact that C++ doesn't have native regex
operators. By
contrast, our own std.regex has a ctRegex function that
essentially does
the same thing while allowing you to use native regex syntax
within a
string literal. I think that's a far better approach for many
cases. :)
I was wondering if that was possible. I was using string mixins
to essentially accomplish the constant folding was thinking that
one could implement java script or some other language in the
strings and have them transformed. It could be pretty useful to
have. I've still got a lot to learn about D but it seems nearly
unbounded for what it can do compared to other languages.
Thanks for making this work! I'll spend some time studying your
code to learn how it works then try to apply it to my library
code.
Trying to do stripLeft/Right, split, join, etc... for strings.
Each function taking an arbitrary number of run-time or
compile-time char or string arguments with optimal code
generation.
