Anonymous user
User:Realazthat/Projects wishlist/LLVM/Algorithm Synthesis: Difference between revisions
User:Realazthat/Projects wishlist/LLVM/Algorithm Synthesis (view source)
Revision as of 18:13, 7 December 2010
, 13 years agono edit summary
No edit summary |
No edit summary |
||
(One intermediate revision by the same user not shown) | |||
Line 3:
Have an interpreter of language L.
So, for example, ''Interpret('''X''','''A''')'' will interpret '''X''', which is of language '''L''', and execute it with input '''A''', and return the result, '''R''', and a weight '''W''' representing the time taken to execute it.
Create a function, '''F''' in language '''L''' to accomplish a task '''T'''. So '''F''' would be executed as follows:
Line 13:
<pre>
//G is input from user
constrain( Interpret(G,T).
assert( !(Interpret(G,T).
</pre>
Line 22:
Notes:
* '''
* There should be a memory constraint as well, as a huge constant array with precomputed results will probably yeild the lowest '''w'''. The memory should probably be constrained to a constant times the size of the input, again, asymptotically.▼
* For the weight, one would probably give each instruction a weight, then sum up the weights during execution. Or, use a decidable language, and compute the complexity by counting loops etc. if possible.
▲* There should be a memory constraint as well, as a huge constant array with precomputed results will probably yeild the lowest '''
References:
* http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-15.pdf
* http://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1178&context=open_access_dissertations
|