Introduction To Program Synthesis (2018)

Ask him about Sid in Lawrence Rawschberger's class for good old anecdotes! :)

> which are pretty much always mathematically uninteresting), then...absolutely! SAT/SMT are at the core of constraint-based synthesis.

Wow this is super cool to know!

> http://www.pathsensitive.com/2021/03/why-programmers-shouldn...

This would definitely help to kickstart my journey in program synthesis:)

> "egg: Fast and Flexible Equality Saturation"... It uses code trees, which I read about a few months earlier in the Handbook of Automated Reasoning > http://cubix-framework.com/ > https://egraphs-good.github.io/ > https://people.csail.mit.edu/asolar/ > https://github.com/microsoft/prose

These stuff are super cool! Really appreaciate it!

My intuition is the same as yours: US institutions don't really take notice of what's going on in Europe. It's a little strange in this day and age were we don't have to wait for correspondence to be delivered by wind clipper, say, but oh well, it's the way it is.

ILP is a small field with hubs in Europe and in Japan, and those also tend to be the hubs for logic programming (for obvious reasons). The overlap with a slightly arcane programming paradigm that, like you say, is more well-known in Programming Language circles is not really helping ILP's popularity, I guess.

>> I came in prepared to dismiss the field's relevance to synthesis, but decided to do a bunch of reading first so that I could do so from an informed perspective

Well, respect!

Regarding Mukund Raghothaman's work that you linked. First of all, thanks for making me aware of yet another interesting approach to learning datalog programs that I had missed because I myself don't keep as watchful an eye on the wider program synthesis literature as I wish others kept on ILP. Guilty! Second, I so disagree with the characterisation of the work in Muggleton et al. 2015 :) I guess that's typical, Stephen (Muggleton) is my thesis advisor and my work is a few steps down the path from the 2015 work so obviously I have a different perspective. Still, by January 2020 there were more recent results to cite and more advanced systems to compare against. Exciting things are happening in ILP right now, long-term thorny problems (predicate invention, learning recursion, learning in languages other than Prolog, efficiency) are falling one by one and it's a bit of a shame that it's all being missed by everyone outside our tiny little field.

Regarding what techniques belong to what field, I think you're probably right, ILP is traditionally based on search, specifically searching the space of logic programs that are sets of clauses constructible from examples and background knowledge (both also logic programs) and some kind of typically extra-logical language bias. The big problem has always been the size of the resulting hypothesis spaces. Of course I would think so because my work has been mainly about this big problem. Anyway as far as I know, wider program synthesis approaches also work essentially the same way, by searching a program space, and so have the same problems wih searching large spaces so definitely there will be much overlap. The difference is in the perspective: like you say, ILP sometimes has a bit of a strongly theoretical flavour because many of the experts in the field have a deep background in logic programming and expect the same from published papers. Btw, while there's few of us, the main venues for ILP work still include IJCAI and AAAI and special issues of the MLJ, and you can even find work in the machine learning conferences (although usually it's the Statistical Relational Learning branch that publishes there).

>> I knew ILP to be "constructing a classifier from a conjunction of literals," which is very much not synthesis.

Yes, I know this interpretation of ILP. The idea is that examples in ILP are typically labelled positive/negative so you can see a correct program that accepts positives and rejects negatives as a discriminator. Another way to see it is that examples are logical atoms assigned true/false values by a logical interpretation (literally an assignment of truth values to atoms) so again correctly recognising true from false can be seen as a classification.

This notion of "classification" has come from inside the field, I think as part of an effort to make ILP more approachable to the mainstream of machine learning. I know the people it came from and the goal was of course noble, but I think the result is that it sells short what is a much more interesting discipline. I mean, sure, the task of recognising _and generating_ sorted/unsorted lists can be shoehorned into a classification problem but that's missing the point that the task is to learn a program that has some kind of expected behaviour. Which is the essence of program synthesis of course.

For me the magical thing about ILP considered as program synthesis from incomplete specifications is that the specifications are logic programs, so learning a program that explains the examples with respect to the background knowledg is essentially completing a specification. And while the specicification is a program, a program-learning approach can learn its own specifications: what is called "predicate invention" in the literature.