Algorithms, term rewriting and compile time reflection

[via Digitalmars-d]

Generic programming without high level analytical capabilities 
are problematic since you cannot optimize everything on a low 
level.

For instance, some algorithms run better if the input is sorted, 
and although you can cover one property with typing (e.g. sorted 
range) the combinatorial explosion is too big and the code 
becomes very messy.

The better approach is to let the compiler deduce properties of 
the input/output based on stronger assertions than 
postconditions. And it should work for FFI as well as for D. That 
way D can obtain meta-information about C functions.

Let's call it input-output-assumptions and take a look at:

y = f(x)

After calling f on x, f could provide propositions about y such 
as:

- y is null iff x is null
- length(y) == length(x) if x is not null
- y is sorted for all x if x is not null
- y contains the same elements as x
- y is alias free (copy by value)

It should also state whether the semantic side effects has been 
completely described.

Then you need statments for f that says something about how 
functions affects the properties of input like. E.g.:

z = g( f(x) )

For g we could say that it preserves:
- element order
- element values
- z is an alias free copy of the input

Thus we cannot assume length(z) == length(x), but we can assume 
that it is sorted and that z is a subset of x. That means the 
compiler can optimize expressions. E.g.:

y = f(x);
z = g(y);

inline_sort(z);  ==>  ;

x = union(z,y); ==> ;

canFind(y,v) || canFind(z,v) ==> canFind(y,v);

linear_find(x,v)  =>  binary_search(y,v)

With term rewriting and compile time reflection we can now 
perform optimizations by querying properties of expressions, 
looking up dependent results of an expression, and doing a search 
over various ways of ordering expressions.

f(sort(g(x))) can be optimized into f(g(x)) if the knowledge of 
the effects of sort() is complete and if the total effects of f,g 
and x completely covers what sort() do.

These kinds of optimizations are very difficult to achieve in a 
low level backend, but you really need them in order to do 
generic programming properly.

A simple start would be to not provide term rewriting as a 
language feature, but rather define a vocabulary that is useful 
for phobos and hardcode term rewriting for that vocabulary.

I think this is feasible.