source: http://www.msu.edu/~shawjef3/brute_big.ml
windows executable: http://www.msu.edu/~shawjef3/brute_big.exe

Compile command: ocamlopt -o brute_big nums.cmxa brute_big.ml

Inspired by a discussion at http://wiki.tcl.tk/12199, I decided to mimic Richard's brute force self-programming RPN bytecode computer in ocaml. The version I wrote behaves in roughly the same manner, but instead producing all the possible programs ahead of time, it does it as it on the fly. I also check the program for any stack problems before testing it further.

For instance, duplicating the first item on the stack when the stack is empty would produce an ocaml exception. Any programs that would do this are ignored.

The language's words are

d duplicate first element
s swap the first two elements
r remove the first element
+ add
* multiply
/ divide
- negate (not subtraction)
< left bit shift
> right bit shift
| bitwise or
& bitwise and
~ bitwise negation
q square root
m modulo

and the integers 0 to 9.

The usage for the compiled program is:

brute_big (maximum number of tests) input1 output1 input2 output2 ... inputn outputn

If (maximum number of tests) is not given, the program will test the first 10,000 programs against the io requirements. Note that the compiled program only allows for the stack to begin and end with one element. If you use the "discover" function from the ocaml toplevel you can give it more complex requirements, such as [([1;2],[2;3]);([2;3],[3;4]);([34;55],[35;56])]. This, I hope, would give you a program which would add 1 to each of the elements on a stack with size 2.

(the command to use in the toplevel would be

discover (eval littlerpn) lrpnwords [([1;2],[2;3]);([2;3],[3;4]);([34;55],[35;56])];;

or, if you wanted it to search for the first 100,000 programs,

discover ~maxnum:(Big_int.big_int_of_string "100000") (eval littlerpn) lrpnwords [([1;2],[2;3]);([2;3],[3;4]);([34;55],[35;56])];;

Note that I have not found the program to do this yet. The program is >10,000,000. I would expect it to be something like 1+s1+s.)

It comes up with some interesting things, for instance, I asked it to create a program to test if a number is even or odd (output 1 means even, 0 means odd).

brute_big 10 1 11 0 444 1 2343 0

produced "~1&". In ocaml this would be "function a -> (lnot a) land 1".

Another one I tried was seeing if it could duplicate

function a -> (a mod 3)+10

brute_big 10000000000000 0 10 1 11 2 12 3 10 4 11 5 12 6 10

I expected "3m1+9+", and (after a long wait) that's what I got! There are other possible programs that would work, such as "3m55++", but "3m1+9+" occurs first in the testing. Modifying the array lrpnwords will change the order in which programs are tested. By default it is set to

let lrpnwords = [|'d';'s';'r';'+';'*';'-';'/';'<';'>';'|';'&';'~';'q';'m';'0';'1';'2';'3';'4';'5';'6';'7';'8';'9'|]

If we were to reverse the order of the integers, the program would probably have given "3m9+1+". If the integers came before '+', then it probably would have given "3m19++".

You can try more random looking mappings to see what wild programs it will create. For example,

brute_big 10000000000000 100 10 65 15
6456014: 4|9<m

Jeff