Hacker News Reader

Comment by exdsq | Hacker News Reader

Anyone here working on program synthesis? I did a little research project as part of an MSc in CS and found it really interesting, but when I looked at industry applications I only found one YC startup working on it in the smart contract space.

View on HN

I study Inductive Logic Programming (ILP) which is a kind of inductive program synthesis. Inductive program synthesis is learning from partial specifications, where deductive program synthesis is learning from complete specifications (compilation can be seen as a form of deductive program synthesis, for example).

ILP studies algorithms that learn logic programs from examples. "Logic programs" as in programs in a language of the Logic Programming paradigm, such as Prolog or Answer Set Programming (ASP).

If you're interested in program synthesis, this is the staple modern reference:

Program Synthesis

https://www.microsoft.com/en-us/research/wp-content/uploads/...

For ILP, see this recent review:

Inductive logic programming at 30

https://arxiv.org/abs/2102.10556

Or this longer version, here:

Inductive logic programming at 30: a new introduction

https://arxiv.org/abs/2008.07912

(Both of which ignore my own contributions. Oh well :)

Thank you!! :)

I got a lot out of this course https://people.csail.mit.edu/asolar/SynthesisCourse/ from one of the authors of OP.

Oh, yes! I should have added that to my links. Thanks!

So my little project was essentially a research survey on neural program synthesis - do you have any good sources on building program synthesis projects? I noted a lot of the literature talks about outcomes but rarely how I can go about building something small that takes some Input, Output tuples and returns some code.

Ended up dropping the MSc because of Covid and moving to the Bay Area but I'd love to eventually do a research-focused masters in the future. Which may be difficult, because I don't have a Bachelors to begin with and took a lot of effort to get onto a Masters in the first place lol!

You mean resources on creating your own program synthesis system? Hm, I don't know of anything like a program synthesis toolbox, like OpenCV for machine vision, etc. There are many freely available program synthesis systems, but most are research prototypes and they only use a particular approach anyway, while I think you 'd prefer to be able to experiment with different approaches, no?

I fear the best option is to try to roll-your-own, based on the descriptions in many different program synthesis papers. Btw, I wouldn't choose neural program synthesis for a first Project! First because neural program synthesis requires as training examples both programming tasks (usually in the form of I/O examples) _and_ programs solving the tasks, and many many of them to boot. Second because it's an uncommon enough approach, or combination of approaches, that I doubt you'll find much support for it in the standard neural net frameworks.

I think the CSAIL program synthesis course suggested above by yldedly is a good starting place though. It's graded by a program synthesis project and you might find some tools meant to help students carry out their assignment on the course pages. Or you may try asking the tutors by email even.

Other than that, the simples thing to get you started is to define a DSL, generate programs from it and test them against I/O examples of the target programs. That's the simplest, most primitive kind of thing you can do. It's not a very efficient thing to do, but it's a start. The trick is in figuring out how to define the DSL and how to search it efficiently.

Good luck, I guess! Feel free to email me if you think I can help. See profile for email.

Edit: Here's a blog post about creating a DSL in Python:

https://dbader.org/blog/writing-a-dsl-with-python

I dabble in it. FlashFill in Excel uses program synthesis, but yeah, not many applications exist yet. Have you seen DreamCoder?

I’ll check it out, thanks!

Reply on news.ycombinator.com