Combining top-down and bottom-up approaches for automated discovery of typed programs

Automated program discovery has been mainly approached via Genetic Programming, which represents the search space of programs implicitly by a collection of individuals. In this paper, we propose a way of representing program search space explicitly, with a top-down hierarchy of semi-constructed programs. Together with a bottom-up generation procedure, we maintain an overview of the overall search space structure, while being able to quickly get samples from the fringe. Moreover, having a type system with parametric polymorphism allows us to limit the state space size using type level programming while keeping a complete control over program sizes. Our approach can naturally be used for searching the space of programs using tree search methods. We back this claim by a simple experiment utilizing a Monte-Carlo Tree Search algorithm, though other search methods (such as A*) might be used as well.