On 12/06/2015 07:50 PM, Timon Gehr wrote:
> On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>>> >The next step up the expressiveness scale would be to have a
>>> >sum-of-products representation.
>>> >
>>> >Proof of concept (disclaimer: hacked together in the middle of the
>>> >night, and not tested thoroughly):
>>> >
>>> >http://dpaste.dzfl.pl/d1512905accd
>>> >
>>> >I think this general approach is probably close to the sweet spot. ...
>>> >
>> Brilliant! ...
>
> I have noticed another thing. The comparison operator is an
> underapproximation (it sometimes returns NaN when ordering would
> actually be possible).
>
> E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m².
>
> Interesting. It would be nice if the final version had a complete
> decision procedure for ⊆.

I think it's okay to leave N^^2 + N1 and N + N1^^2 unordered. -- Andrei

On 12/07/2015 02:07 AM, Andrei Alexandrescu wrote:
> On 12/06/2015 07:50 PM, Timon Gehr wrote:
>> On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>>>> >The next step up the expressiveness scale would be to have a
>>>> >sum-of-products representation.
>>>> >
>>>> >Proof of concept (disclaimer: hacked together in the middle of the
>>>> >night, and not tested thoroughly):
>>>> >
>>>> >http://dpaste.dzfl.pl/d1512905accd
>>>> >
>>>> >I think this general approach is probably close to the sweet spot. ...
>>>> >
>>> Brilliant! ...
>>
>> I have noticed another thing. The comparison operator is an
>> underapproximation (it sometimes returns NaN when ordering would
>> actually be possible).
>>
>> E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m².
>>
>> Interesting. It would be nice if the final version had a complete
>> decision procedure for ⊆.
>
> I think it's okay to leave N^^2 + N1 and N + N1^^2 unordered. -- Andrei

Yes, certainly. By complete, I mean it orders everything that can be ordered.

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.

On 12/7/15 5:14 AM, Timon Gehr wrote:
> 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.

I fail to see how no parens after log or "^" in lieu "^^" would make a positive difference. What would be a few examples of things that won't work pleasantly enough?

I'm not sure whether the DSL argument is well applied here. Clearly using D expressions for e.g. regex or SQL syntax would be at best avoided in favor of a DSL. In this case we're defining an algebra over restricted expressions, which are a subset of the usual mathematical expressions that D's syntax already emulates.

Looks like a debate on whether to choose one standard language vs. an obscure one (in this case invented ad-hoc) is starting. This is deja vu all over again :o).

I hope you won't mind if I give your idea a slightly different angle.


Andrei

On 12/07/2015 02:46 PM, Andrei Alexandrescu wrote:
> On 12/7/15 5:14 AM, Timon Gehr wrote:
>> 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.
>
> I fail to see how no parens after log or "^" in lieu "^^" would make a
> positive difference.

Neither have I attempted to show anything like that. All arguments in this debate are obvious and boring, so no need to discuss it.

> What would be a few examples of things that won't
> work pleasantly enough?
> ...

You gave this example:
http://en.cppreference.com/w/cpp/container/forward_list/insert_after

1-2) BigO("1")
3) BigO("count")
4) BigO("distance(first,last)")
5) BigO("ilist.size()")

There's also this:
On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
> Well you'd need multiple terms if you want to say things like,
> "inserting a range into an array is O(array[].walkLength +
> r.walkLength)." When you insert a range in a binary search tree, the
> complexity would be O(log(array[].walkLength) * r.walkLength).

BigO("array[].walkLength + r.walkLength");
BigO("log(array[].walkLength) * r.walkLength");

On 12/07/2015 09:43 AM, Timon Gehr wrote:
>
> 1-2) BigO("1")
> 3) BigO("count")
> 4) BigO("distance(first,last)")
> 5) BigO("ilist.size()")
>
> There's also this:
> On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
>> Well you'd need multiple terms if you want to say things like,
>> "inserting a range into an array is O(array[].walkLength +
>> r.walkLength)." When you insert a range in a binary search tree, the
>> complexity would be O(log(array[].walkLength) * r.walkLength).
>
> BigO("array[].walkLength + r.walkLength");
> BigO("log(array[].walkLength) * r.walkLength");

These are still expressible without a DSL: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.

Somewhat independently of DSL or not: At this point I'm unclear whether supporting free variables with arbitrary names is a good thing. The key to unleashing the power of BigO is to compute it when combining functions, and the names seem to be specific to the function and therefore not easy to combine.


Andrei

On 12/07/2015 05:15 PM, Andrei Alexandrescu wrote:
> On 12/07/2015 09:43 AM, Timon Gehr wrote:
>>
>> 1-2) BigO("1")
>> 3) BigO("count")
>> 4) BigO("distance(first,last)")
>> 5) BigO("ilist.size()")
>>
>> There's also this:
>> On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
>>> Well you'd need multiple terms if you want to say things like,
>>> "inserting a range into an array is O(array[].walkLength +
>>> r.walkLength)." When you insert a range in a binary search tree, the
>>> complexity would be O(log(array[].walkLength) * r.walkLength).
>>
>> BigO("array[].walkLength + r.walkLength");
>> BigO("log(array[].walkLength) * r.walkLength");
>
> These are still expressible without a DSL:
> BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.
> ...

This just goes from one string to two strings and adds some noise on top of it. Also, now, what is D and what is in a string is arbitrary.

BigO(Var.array[].walkLength + Var.r.walkLength);

> Somewhat independently of DSL or not:

Yes, notation does not matter at this stage.

> At this point I'm unclear whether
> supporting free variables with arbitrary names is a good thing.

Restricting the set of names to 8 predefined ones does not simplify anything. It just means that a mapping of predefined names to real names has to be carefully managed manually and clashes have to be avoided, all while limiting the value of BigO as documentation.

> The key
> to unleashing the power of BigO is to compute it when combining
> functions, and the names seem to be specific to the function and
> therefore not easy to combine.
> ...

Just substitute something else for those names to get rid of them. That is how passing of parameters is handled. Probably we should get some actual examples where combination should work to see what could be done.

If you have:

void foo(int n,int m) @BigO("n*m^2"){ ... }

Something like this is easy to implement:

// compute runtime bound from bounds on parameters:
// first expression passed is O(x^3) and second expression passed
// is O(log(y)^(1/2)).
enum bound = getRuntimeBound!foo(BigO("x^3"),BigO("log(y)^(1/2)"));
static assert(bound == BigO("x^3*log(y)"));

Note how the end user does not need to worry much about names.

On Monday, 7 December 2015 at 16:15:46 UTC, Andrei Alexandrescu wrote:
>
> These are still expressible without a DSL: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.
>

We can remove the use of strings if we tag walkLength with BigO:

// this:
BigO(Atom("array[].walkLength") + Atom("r.walkLength"))

//become this:
@(complexity!(array[].walkLength) + complexity!(r.walkLength))

Or if we rename complexity to bigO:

@(bigO!(array[].walkLength) + bigO!(r.walkLength))

On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
> Consider the collections universe. So we have an imperative primitive like:
>
> c.insertAfter(r, x)
>
> where c is a collection, r is a range previously extracted from c, and x is a value convertible to collection's element type. The expression imperatively inserts x in the collection right after r.
>
> Now this primitive may have three complexities:
>
> * linear in the length of r (e.g. c is a singly-linked list)
>
> * linear in the number of elements after r in the collection (e.g. c is an array)
>
> * constant (c is a doubly-linked list)
>
> These complexities must be reflected in the name of the primitives. Or perhaps it's okay to conflate a couple of them. I know names are something we're awfully good at discussing :o). Destroy!
>
>
> Andrei

Why not create the capability to get the complexity by the user:

writeln(c.insertAfter(r, null).complexity);

If all algorithms implemented such a feature, one could have a compile time argument to display the complexity of the algorithms along with profiling.

Complexity is not important except when profiling. It's also generally static depending on the types rather than the values of the types.

On Monday, 7 December 2015 at 16:15:46 UTC, Andrei Alexandrescu wrote:
> On 12/07/2015 09:43 AM, Timon Gehr wrote:
>>
>> 1-2) BigO("1")
>> 3) BigO("count")
>> 4) BigO("distance(first,last)")
>> 5) BigO("ilist.size()")
>>
>> There's also this:
>> On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
>>> Well you'd need multiple terms if you want to say things like,
>>> "inserting a range into an array is O(array[].walkLength +
>>> r.walkLength)." When you insert a range in a binary search tree, the
>>> complexity would be O(log(array[].walkLength) * r.walkLength).
>>
>> BigO("array[].walkLength + r.walkLength");
>> BigO("log(array[].walkLength) * r.walkLength");
>
> These are still expressible without a DSL: BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.
>
> Somewhat independently of DSL or not: At this point I'm unclear whether supporting free variables with arbitrary names is a good thing. The key to unleashing the power of BigO is to compute it when combining functions, and the names seem to be specific to the function and therefore not easy to combine.
>
>
> Andrei

There are many "operations" that can be carried out on methods.

Many are composable and decomposable in the exact same way and can be generalized as an algorithm:

let f,f1,f2, etc be functions,

if f = f1 + f2
then L(f) = L(f1) + L(f2)


Hence if L is a linear operator, this always holds. Addition(+) is linear, BigO is linear. Composing linear operators is linear(but it doesn't have an inverse like addition).


If D supported some generic way to handle such linear operators acting on methods, with calls to other methods as decomposing the method, one could do many cool things quite easily in D. BigO would just be one.


e.g.,

void foo()
{
    bar1();
    bar2();
    for(auto i = 1; i < 100; i++)
       for(auto j = 1; j < 100; j++)
           bar3();
}

then we can see L(foo) = L(bar1) + L(bar2) + X(n^2)*L(bar3)

(Here, X(n^2) is because we have a double nested for loop which multiples the complexity by n^2 for big notation. To be more precise, we should refactor all code inside the function in such a way to make things precise, i.e.,

void foo()
{
    bar1();
    bar2();
}

void fooTemp()
{
    for(auto i = 1; i < 100; i++)
       for(auto j = 1; j < 100; j++)
           bar3();
}

which then gives the more precise decomposition as

L(foo) = L(bar1) + L(bar2) + L(fooTemp)


The main point of all this, is that L can be many things. If one has the complete hierarchical call stack(with root = Main) then L can be scene as recursively working on the tree.

In this case, addition would rather be "insertion into tree". We could easily check relations such as if foo is called, calls, or disjoint from bar.


We can, as already stated, implement complexity analysis automatically:

BigO - The sup of the complexity of a function assuming all unknowns(loops, user input, unknown sub-function calls) have maximal complexity.
bigO - The sup of the complexity of all functions assuming all unknowns have 0 complexity.
LittleO - The inf of complexity....
litleO - ...


The point, by simply implementing a decomposable structure on the "call hierarchy", one can implement all kinds of cool stuff. If it is exposed to D at run time, then even more amazing things can happen.

e.g., one could implement a real time profiler. L would be an "operator" that simply sends the current ticks when first called and when returning. The "addition" is really just code that does the computations on the differences it is getting.

Imagine hitting some hot key and your current app showing a tree(something like a fractal tree) where each node is a function call and sub nodes are functions that are the functions that the function calls("uses").

Color the tree based on the use rate(count how many times the function is called, or even accumulate hierarchically) or the execution time, or even BigO. You'll then see a visual of where the program is active the most. It might sort of look like the heat distribution map of the earth.

I realize it is more complex to implement than I'm making it out, but it's basically tree traversal and hooks stuff.

Once you start allowing meta coding, the power becomes magnified:

e.g. (psuedo-code)

// Define generic meta code function composer(the + in the algorithm) for BigO
@function!composer!BigO(functions)
{
    let f1, ..., fn = functions
    return function!composer!BigO(f1) + ... + function!composer!BigO(f2)

    // Would need to separate parse f1 in such a way that it is composed of only calls to functions or none calls(the loop stuff I mentioned above)
}

// The Linear operator BigO that returns the complexity of a function f
@function!composer!BigO(f)
{
   return complexity(f);
}


// Explicitly specify complexity for foo
void foo()
[function!composer!BigO() { return 0; }
{
    ...
}


------------------------------------

The above represents a mock way to allow the programmer to "hook" into the compilers call hierarchy structure. Obviously it would require some work for actual implementation. But once such a feature is implemented, the programmer can do all sorts of things. Implement "attributes"(not needed, of course), real time profiling, BigO, Code replacement/Self Modifying Programs(essentially change how a function behaves), etc...

Of course, maybe we are starting to get into AI here? ;) (e.g., one could use multiple similar functions in a program for performance enhancements, but implement a few lines of code to have those functions reconfigure themselves to use the most optimal one for performance reasons)


Also, why stop at functions? what about all sub-structures in the program? We could work on classes, structs, etc...