5 ms·

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

by exdsq 5y ago

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.

yldedly 5y ago
I dabble in it. FlashFill in Excel uses program synthesis, but yeah, not many applications exist yet. Have you seen DreamCoder?
- exdsq 5y ago
  I’ll check it out, thanks!
YeGoblynQueenne 5y ago
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/2017/10/program_synthesis_now.pdf 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 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 https://arxiv.org/abs/2008.07912 (Both of which ignore my own contributions. Oh well :)
- exdsq 5y ago
  Thank you!! :)
- yldedly 5y ago
  I got a lot out of this course https://people.csail.mit.edu/asolar/SynthesisCourse/ https://people.csail.mit.edu/asolar/SynthesisCourse/ from one of the authors of OP.
  - YeGoblynQueenne 5y ago
    Oh, yes! I should have added that to my links. Thanks!
    - exdsq 5y ago
      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!
      - YeGoblynQueenne 5y ago
        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 https://dbader.org/blog/writing-a-dsl-with-python

by exdsq 5y ago

yldedly 5y ago

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

exdsq 5y ago
I’ll check it out, thanks!

YeGoblynQueenne 5y ago

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/2017/10/program_synthesis_now.pdf 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 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 https://arxiv.org/abs/2008.07912 (Both of which ignore my own contributions. Oh well :)

exdsq 5y ago
Thank you!! :)
yldedly 5y ago
I got a lot out of this course https://people.csail.mit.edu/asolar/SynthesisCourse/ https://people.csail.mit.edu/asolar/SynthesisCourse/ from one of the authors of OP.
- YeGoblynQueenne 5y ago
  Oh, yes! I should have added that to my links. Thanks!
  - exdsq 5y ago
    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!
    - YeGoblynQueenne 5y ago
      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 https://dbader.org/blog/writing-a-dsl-with-python