5 ms·

This looks pretty awesome. Does anyone have good book/lecture/paper/course that deals with program synthesis and the algorithms behind them.

zaph0d 9y ago
Barliman is written in miniKanren[0], a logic/relational programming system built by Daniel Friedman[1], Will Byrd[2] & Oleg Kiselyov[3]. There are implementations of miniKanren in languages other than Scheme, one of the prominent being Clojure[4]. To oversimplify, in the miniKanren world programs are written using relational logic, wherein there are "variables" and then certain "relationships" between the variables. That is the program specification. Now we can run the specification and allow miniKanren to generate one or more variables that satisfy the relations. Thus a miniKanren program can have more than one answers. One interesting side-effect of this kind of an abstraction is that programs can also be run backwards to generate more programs that satisfy certain relations. That's pretty much what's happening with Barliman. [0] http://minikanren.org/ http://minikanren.org/ [1] https://en.wikipedia.org/wiki/Daniel_P._Friedman https://en.wikipedia.org/wiki/Daniel_P._Friedman [2] http://webyrd.net/ http://webyrd.net/ [3] http://okmij.org/ftp/ http://okmij.org/ftp/ [4] https://github.com/clojure/core.logic https://github.com/clojure/core.logic
- neoncontrails 9y ago
  Some of you might recognize Daniel Friedman as the author of The Little Schemer. If you liked that book, you might check out The Reasoned Schemer. Short, accessible, and a bit mindbending, it offers a compelling introduction to logic programming that culminates in the "invention" of a Prolog-like DSL from basic Scheme primitives. Terrific little book. https://mitpress.mit.edu/books/reasoned-schemer https://mitpress.mit.edu/books/reasoned-schemer
memebox3v 9y ago
Second that. This looks brilliant. Had no idea something like this existed :)
mycl 9y ago
The induction of logic programs in Prolog from examples was done by Ehud Shapiro's "Model Inference System" described in his PhD thesis, "Algorithmic Programming Debugging" (https://www.amazon.com/Algorithmic-Program-Debugging-Distinguished-Dissertation/dp/0262192187/ https://www.amazon.com/Algorithmic-Program-Debugging-Disting...), in 1982. This was one of the earliest inductive logic programming (https://en.wikipedia.org/wiki/Inductive_logic_programming https://en.wikipedia.org/wiki/Inductive_logic_programming) systems.
- tluyben2 9y ago
  ILP + IFP are nice subjects to read about for this kind of thing. At university a number of people believed ILP and/or neural networks and/or genetic programming would replace programmers shortly. That didn't happen (this was around 25 years ago) but it's still interesting material great to learn from.
Davidbrcz 9y ago
You could read "Syntax-Guided Synthesis" by ALUR and al. There is here (http://resources.mpi-inf.mpg.de/departments/rg1/conferences/vtsa17/slides/alur-vtsa-sygus.pdf http://resources.mpi-inf.mpg.de/departments/rg1/conferences/...) a presentation he did at a summer school last summer.

zaph0d 9y ago

Barliman is written in miniKanren[0], a logic/relational programming system built by Daniel Friedman[1], Will Byrd[2] & Oleg Kiselyov[3]. There are implementations of miniKanren in languages other than Scheme, one of the prominent being Clojure[4]. To oversimplify, in the miniKanren world programs are written using relational logic, wherein there are "variables" and then certain "relationships" between the variables. That is the program specification. Now we can run the specification and allow miniKanren to generate one or more variables that satisfy the relations. Thus a miniKanren program can have more than one answers. One interesting side-effect of this kind of an abstraction is that programs can also be run backwards to generate more programs that satisfy certain relations. That's pretty much what's happening with Barliman. [0] http://minikanren.org/ http://minikanren.org/ [1] https://en.wikipedia.org/wiki/Daniel_P._Friedman https://en.wikipedia.org/wiki/Daniel_P._Friedman [2] http://webyrd.net/ http://webyrd.net/ [3] http://okmij.org/ftp/ http://okmij.org/ftp/ [4] https://github.com/clojure/core.logic https://github.com/clojure/core.logic

neoncontrails 9y ago
Some of you might recognize Daniel Friedman as the author of The Little Schemer. If you liked that book, you might check out The Reasoned Schemer. Short, accessible, and a bit mindbending, it offers a compelling introduction to logic programming that culminates in the "invention" of a Prolog-like DSL from basic Scheme primitives. Terrific little book. https://mitpress.mit.edu/books/reasoned-schemer https://mitpress.mit.edu/books/reasoned-schemer

memebox3v 9y ago

Second that. This looks brilliant. Had no idea something like this existed :)

mycl 9y ago

The induction of logic programs in Prolog from examples was done by Ehud Shapiro's "Model Inference System" described in his PhD thesis, "Algorithmic Programming Debugging" (https://www.amazon.com/Algorithmic-Program-Debugging-Distinguished-Dissertation/dp/0262192187/ https://www.amazon.com/Algorithmic-Program-Debugging-Disting...), in 1982. This was one of the earliest inductive logic programming (https://en.wikipedia.org/wiki/Inductive_logic_programming https://en.wikipedia.org/wiki/Inductive_logic_programming) systems.

tluyben2 9y ago
ILP + IFP are nice subjects to read about for this kind of thing. At university a number of people believed ILP and/or neural networks and/or genetic programming would replace programmers shortly. That didn't happen (this was around 25 years ago) but it's still interesting material great to learn from.

Davidbrcz 9y ago

You could read "Syntax-Guided Synthesis" by ALUR and al. There is here (http://resources.mpi-inf.mpg.de/departments/rg1/conferences/vtsa17/slides/alur-vtsa-sygus.pdf http://resources.mpi-inf.mpg.de/departments/rg1/conferences/...) a presentation he did at a summer school last summer.