automatic programming / algorithm discovery

[gusl]

This entry has been wikified. See it here.

Comments

[amoken.livejournal.com]

Let me know if you come up with something that will automate memory optimization...even if it decreases speed efficiency by a little bit. Analysts are willing to wait for big answers to big problems, but they don't like it whe the program errs, stalls or crashes because there isn't enough memory!

[gustavolacerda.livejournal.com]

Oh, I see. Memory optimization is what we do when we streamline a program that keeps redundant data around... maybe it uses some non-optimal representation, like using a matrix for representing a graph with sparse connectivity: a list of edges is much better.

I can imagine lots of useful applications of algorithm discovery / data-structure discovery to indexing problems. When should you use an array vs. (multiply) linked list vs. hash table, etc?

Of course, we would need to give the program more info:
* our estimate of typical input parameters (e.g. size of matrix, connectivity, etc)
* our preferences in the space vs. time trade-off, etc. (+ vs. bandwidth in networked apps)

Can you give me concrete examples of this memory optimization work?

I think it's feasible for us to start a very specific automatic optimizer by looking at narrow cases: what is the programmer doing, etc.

[gustavolacerda.livejournal.com]

also: time to add vs. retrieval time, etc.

[chipuni.livejournal.com]

I'm convinced that this can best be performed in a functional language (like Lisp) or something like logical languages (Prolog). I know that there have been uses of Lisp to do program proving (proof that a program accomplishes a certain task), but I'm not aware of uses of it for generating faster -- but provably the same -- code.

I would examine compiler theory closely, though. They use similar things to rewrite procedural code: removing unnecessary statements, moving statements outside loops, unrolling loops, and the like.

Sounds interesting, though!