420chan now has a web-based IRC client available, right here
Leave these fields empty (spam trap):
Name
You can leave this blank to post anonymously, or you can create a Tripcode by using the float Name#Password
Comment
[*]Italic Text[/*]
[**]Bold Text[/**]
[~]Taimapedia Article[/~]
[%]Spoiler Text[/%]
>Highlight/Quote Text
[pre]Preformatted & Monospace text[/pre]
1. Numbered lists become ordered lists
* Bulleted lists become unordered lists
File

Sandwich

penis pump

Community Updates

420chan now supports HTTPS! If you find any issues, you may report them in this thread
Brute Force Compiler by Fanny Grandford - Sun, 19 Mar 2017 14:35:03 EST ID:8Wkw9vVF No.36625 Ignore Report Quick Reply
File: 1489948503186.jpg -(118472B / 115.70KB, 500x716) Thumbnail displayed, click image for full size. 118472
I've just made what I call a brute force compiler. How does it work? Well it occurred to me that since a program is simply a sequence of bytes we can actually enumerate all the possible programs. So it does that, and runs each one in an emulator until the tests all pass.

One test is that the program should not have written to, read from, or branched to any byte in memory that it hasn't explicitly been given read write execute access to. Just to prove the idea, I put a second test in and that' passes if some memory location, which was initialised to 0, contains some non-zero value after the program has run. Sure enough, the compiler produced the following code (in 6502 assembly):
dec $7F
(that decrements the memory location I specified, so since it was initialised to zero now it'll obviously contain a non-zero value). And this is the shortest program that passes this test, and dec is the first opcode numerically which modifies a memory location in the necessary way.

My idea is that if we have enough tests, then we can use this to generate a program which matches some specification. (And since the programs are tested in a certain order, we also know that it's the shortest possible program that matches the specification).

So the next thing is: How can we get these necessary tests? Maybe I can automatically generate them from running an equivalent program. Maybe I can generate them from source code. Any ideas about that? Or any ideas about how useful this whole contrafibulation might be?
>>
Fuck Sigglekork - Sun, 19 Mar 2017 15:43:37 EST ID:S3TDz6jS No.36626 Ignore Report Quick Reply
What you have is logic programming and not-quite-genetic programming. I think the first problem you'll run into is that constraints are really hard to think about, often harder than solving the problem yourself. The second is that even far more sophisticated approaches are very slow in practice. These are the reasons Prolog isn't popular.
>>
Martha Wudgeridge - Sun, 19 Mar 2017 17:42:47 EST ID:9QSfnS0r No.36627 Ignore Report Quick Reply
There is current research on a topic like that.
The researchers have created a neural network capable of generating source code for a program that produces a required output scheme.

In a sense it's the only currently somewhat plausible way to do that.
https://techcrunch.com/2017/02/23/deepcoder-builds-programs-using-code-it-finds-lying-around/
https://openreview.net/pdf?id=ByldLrqlx
>>
Archie Bottinglack - Mon, 20 Mar 2017 03:50:28 EST ID:P6PS9CBz No.36628 Ignore Report Quick Reply
>>36625
This sounds like the principle applied to superoptimizers:
https://en.wikipedia.org/wiki/Superoptimization

The problem (both with your idea and with superoptimizers) is that with larger programs your search-space expands too quickly for it to be feasible to search all possible sequences of program bytecode. If you query:
Find me the fastest program that does this thing in less than 4 bytes, you're searching through 2^32 possible (though not necessarily valid) program sequences, but if you expand the search to 8 bytes then you're already at a size too large to search on a single computer in a human lifetime at 2^64 program sequences.

If you restrict your search to only valid programs, then the possibility-space is reduced, but only linearly so you're still stuck with the exponential-search issue only now you have fewer possible programs to enumerate.
>>
Phoebe Fanlock - Wed, 22 Mar 2017 16:57:02 EST ID:8Wkw9vVF No.36631 Ignore Report Quick Reply
Thanks for all your thoughts and input thus far.


>>36626
>constraints are really hard to think about
So maybe this thing would have a hard time with functions that have side effects and other unknowns and things which are hard to reason about (luckily those things are rare in good programs). But maybe this thing would work okay on a function which returns a value or set of values given an input. Something like a keyboard matrix decoder or a mathematical function. The constraint would be as simple as "You can use this region of memory for your own purposes. You can read from these locations. Put the return value here. Here is how the inputs map to the return value, including the don't-cares."
Of course, that might still be hard to compute...

>>36627
I haven't had time yet to read that paper properly yet, but the skim has been interesting. Neural nets are another interest of mine

>>36628
One application that has a (relatively) small search-space: automatically finding the transformations for a peep-hole optimizer. A peephole optimizer might look at four bytes at a time, seeing if a four-byte sequence may be replaced by shorter sequence.


Report Post
Reason
Note
Please be descriptive with report notes,
this helps staff resolve issues quicker.