Motivated by classic work on inferring physical laws from experimental data (39–41), we first task DreamCoder with learning equations describing 60 different physical laws and mathematical identities taken from AP and MCAT physics “cheat sheets”, based on numerical examples of data obeying each equation. The full dataset includes data generated from many well-known laws in mechanics and electromagnetism, which are naturally expressed using concepts like vectors, forces, and ratios. Rather than give DreamCoder these mathematical abstractions, we initialize the system with a much more generic basis — just a small number of recursive sequence manipulation primitives like map and fold, and arithmetic — and test whether it can learn an appropriate mathematical language of physics. Indeed, after 8 wake/sleep cycles DreamCoder learns 93% of the laws and identities in the dataset, by first learning the building blocks of vector algebra, such as inner products, vector sums, and norms (Fig. 7A). It then uses this mathematical vocabulary to construct concepts underlying multiple physical laws, such as the inverse square law schema that enables it to learn Newton’s law of gravitation and Coulomb’s law of electrostatic force, effectively undergoing a ‘change of basis’ from the initial recursive sequence processing language to a physics-style basis.
Could DreamCoder also learn this recursive sequence manipulation language? We initialized the system with a minimal subset of 1959 Lisp primitives (car, cdr, cons, . . .) and asked it to solve 20 basic programming tasks, like those used in introductory computer science classes. Crucially the initial language includes primitive recursion (the Y combinator), which in principle allows learning to express any recursive function, but no other recursive function is given to start; previously we had sequestered recursion within higher-order functions (map, fold, . . .) given to the learner as primitives. With enough compute time (roughly five days on 64 CPUs), DreamCoder learns to solve all 20 problems, and in so doing assembles a library equivalent to the modern repertoire of functional programming idioms, including map, fold, zip, length, and arithmetic operations such as building lists of natural numbers between an interval (see Fig. 7B). All these library functions are expressible in terms of the higher-order function fold and its dual unfold, which, in a precise formal manner, are the two most elemental operations over recursive data – a discovery termed “origami programming” (42). DreamCoder retraced the discovery of origami programming: first reinventing fold, then unfold, and then defining all other recursive functions in terms of folding and unfolding.
From the paper: