Genetic algorithms in Forth
This work addresses program synthesis for specific algorithms in a niche language, but it is incremental as it applies existing genetic methods to a new domain.
The authors tackled the problem of automatically generating programs (bytecode) from a set of input-output tests, using genetic algorithms to find implementations of complex algorithms like sorting and factorial in a simplified Forth language.
A method for automatically finding a program (bytecode) realizing the given algorithm is developed. The algorithm is specified as a set of tests (input\_data) $ \rightarrow $ (output\_data). Genetic methods made it possible to find the implementation of relatively complex algorithms: sorting, decimal digits, GCD, LCM, factorial, prime divisors, binomial coefficients, and others. The algorithms are implemented on a highly simplified version of Forth language.