A weekend replication of STOKE, a stochastic superoptimiser A super optimizer is a type of compiler that takes a program and finds the optimal sequence of inst

A weekend replication of STOKE, a stochastic superoptimiser A super optimizer is a type of compiler that takes a program and finds the optimal sequence of instructions that perform the same task as the original program. A stochastic thing X is a thing X that uses randomness. STOKE is a superoptimizer that finds optimal instruction sequences to perform a particular task by using numerical techniques which rely on randomness (markov-chain-monte-carlo/MCMC) to explore the space of "all possible programs". Here, we re-implement STOKE for a tiny stack machine language whose instruction set is Push, Add, Mul, and And. Sample output * original: (nparams: 0 | [IPush 2,IPush 3,IAdd])* [IPush 5] | score: 2.5 // constant folding: 2 + 3 -> 5 * original: (nparams: 1 | [IPush 2,IMul])* [IDup,IAdd] | score: 2.25 // strength reduction: 2 * x -> x + x * original: (nparams: 1 | progInsts = [IDup,IAnd])* [] | score: 3.0 // strength folding: x & x == x That is, we automatically disover those program transformations by randomly trying different programs (in a somewhat smart way).