Stack-based Genetic Programming benchmarked as slower than tree-based or random search for polymorphic code synthesis

The benchmark compares three Genetic Programming (GP) representations, tree-based, grammatical evolution, and stack-based, against random search for synthesizing programs in a language with high-order functions and polymorphism. The results indicate that stack-based GP is significantly slower, failing to outperform even random search in most cases. This challenges the assumption that stack-based approaches are inherently efficient for general-purpose program synthesis.

Tree-based GP and random search demonstrated nearly identical performance, suggesting that the evolutionary mechanisms in GP may not provide a meaningful advantage for tasks involving polymorphic types. This aligns with prior observations that GP excels in constrained domains like symbolic regression but struggles with broader program synthesis challenges. The findings imply that the overhead of stack-based representations may outweigh their theoretical benefits in complex language contexts.

The benchmark was conducted using 30 executions per representation, with the stack-based approach consistently lagging behind. While stack-based GP is conceptually appealing for its simplicity in encoding operations, its practical limitations become apparent in languages requiring type flexibility. Engineers evaluating GP for automated code generation should weigh these trade-offs, particularly if their use case involves polymorphic or high-order functions.