I pursued this question in grad school [1], leaning towards symbolic logic: Suppose we want to learn a "natural" programming language. Training data would be e

I pursued this question in grad school [1], leaning towards symbolic logic: Suppose we want to learn a "natural" programming language. Training data would be example programs that we believe should be easy to express in any language. Since each of those programs will be expressed in a particular language, we'll need a notion of program equivalence across languages. As a toy framework let "language" mean a basis of combinators in pure lambda calculus; this is convenient because we have a (Hilbert-Post-)complete theory of behavioral equivalence among programs (H*, see Barendregt's classic book), and because the combinatory basis problem has been well studied since 1950s. Applying machine learning we can try to "fit a combinatory basis to data" in the sense of finding a finite weighted set of combinators, giving more weight to language primitives with shorter spelling. Our loss function will be the Kolmogorov complexity of our training data, actually gradients will be better if we use a softmax-Kolmogorov complexity. I used gradient descent to update weights of existing language primitives, and used greedy sparse dictionary learning to propose new language primitives. Most of the work was in proving equivalence and approximating Kolmogorov complexity. It was a cute experiment, but hopelessly far from practical. [1] http://fritzo.org/thesis.pdf http://fritzo.org/thesis.pdf (2009)