On 12/07/2015 02:05 AM, Andrei Alexandrescu wrote:
On 12/06/2015 06:21 PM, Timon Gehr wrote:
The implementation of power on BigO given does not actually work in
general (there should have been an enforcement that makes sure there is
only one summand). I'll think about whether and how it can be made to
work for multiple summands.
No matter, you may always use runtime assertions - after all it's all
during compilation. That's the beauty of it!
...
Even better: I was wrong when I claimed it does not work.
For 0<=x, it actually works as-is:
O((f+g)^x) = O(max(f,g)^x) = O(max(f^x,g^x)) = O(f^x+g^x).
Define global constants K, N, and N1 through N7. K is constant
complexity
all others are free variables.
Then complexities are regular D expressions e.g BigO(N^2 * log(N)).
On a the phone sry typos.
I generally tend to avoid DSLs based solely on operator overloading, as
they don't always work and hence are awkward to evolve. Here, the
biggest current nuisance is that the variable names are not very
descriptive.
The bright side is you get to standardize names. If you limit names to
K, N, and N1 through N7 then you can always impose to APIs the meaning
of these.
...
Well, how?
Another bright side is people don't need to learn a new, juuust slightly
different grammar for complexity expressions - just use D. For example
the grammar you defined allows log n without parens - what's the
priority of log compared to power etc?
There is no priority. The parser explicitly rejects log n^x. :-)
Why is power ^ in this notation and ^^ in D?
Because ^ is taken for bitwise xor in D due to backwards-compatibility
constraints.
All these differences without a distinction are gratuitous.
Just use D.
...
D does not allow overloading of syntax to the extent necessary to make
similar things really pleasant in the long run, and it has been
repeatedly argued that this is a good thing; that custom parsing should
be used instead. It is easy to align the parser with D syntax. Anyway,
syntax is not the problem here, and the implementation can be downgraded
to not support parsing and/or proper names at any point.
