8 ms·

Barliman – real-time program synthesis to make the programmer's life easier

accurrent 9y ago
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.
yellowapple 9y ago
I've felt for awhile that it's a matter of time before we end up with a development environment that - given a collection of tests - will automatically generate a program which passes all the tests. Barliman looks like a really cool step in that direction, even with its stated limitations.
- setr 9y ago
  isn't that called prolog
  - agumonkey 9y ago
    I wonder how far they went with prolog. I remember examples in books talking about solving a problem and outputing a plan. But it wasn't a program, not in the sense of nested/modular systems, more like a linear walk. That said, webyrd has shown kanren embedded lambda calc (evalo relation) to find which program would be reduced to some value..
  - tree_of_item 9y ago
    No, Prolog is nothing like that. Prolog is perhaps the sort of paradigm that could be used as one part of an implementation of something like that (as we see here with miniKanren), but Prolog itself isn't even close.
  - abecedarius 9y ago
    Prolog can (sometimes) "reverse execute" a specification, not generalize from examples. It's like saying "a cat has a round face and pointy ears" versus "look at these cat pictures". (Versus "draw an oval and then draw two triangles at the top...")
    - mycl 9y ago
      But generalising from examples has been a research topic in the Prolog community since at least the early 80s. The field is called inductive logic programming (https://en.wikipedia.org/wiki/Inductive_logic_programming https://en.wikipedia.org/wiki/Inductive_logic_programming).
gergoerdi 9y ago
This seems like a real-time / on-line version of MagicHaskeller: http://nautilus.cs.miyazaki-u.ac.jp/~skata/MagicHaskeller.html http://nautilus.cs.miyazaki-u.ac.jp/~skata/MagicHaskeller.ht...
- aetherspawn 9y ago
  This thing is so smart. Add a 'z' to the end of the first example and it figures out it needs to 'reverse . drop 1 . reverse' to take a character off the end. Imagine if it could learn on every open source Haskell codebase on GitHub and then learn in real time while people type.
tluyben2 9y ago
This combined with a robust type system should be nice. I thought it would be a solid direction which would've happened but didn't. One of my uni courses was ILP (long time ago indeed) and that seemed to have merit with faster computers, more advanced algorithms and heuristics. After that I saw Hoogle when I learned Haskell; seems combining these things can make something powerful. I was going to post MagicHaskeller here as well but gergoerdi did that already.
noobiemcfoob 9y ago
Attach a program that can evaluate and define test parameters... I'm looking at a core of my replacement >.<
noway421 9y ago
This is dangerous. Instead of acquiring understanding, a tool like this lets the programmer just write the code which passes tests. Without the deep understanding of algorithm you can't write sufficiently full tests which assess program's correctness. TDD wouldn't save here, because instead of being a tool of discipline it becomes a list of instructions for codegen. Would anyone want to ride in a car or fly in a plane written by set of sporadic tests? I wouldn't risk it.
- wruza 9y ago
  Fun fact: when you board on a plane, you have no idea how good its hardware, software and test suite is beyond common “it didn’t crash n-thousand times before” knowledge.
  - vbuwivbiu 9y ago
    the engineers who made and maintain it know everything about it
    - alcidesfonseca 9y ago
      Given how large those systems are, how much layers (OS) of code there are, and the turn-over in software companies, I am pretty confident that no single engineer know everything about.
      - vbuwivbiu 9y ago
        "engineers" - it's been decades since anyone on the planet could know everything about a whole system, but each engineer knows everything about their subsystem
    - coderjames 9y ago
      Which is why I won't fly on certain airlines :-). As a Software Engineer who worked at an avionics company, I know who our big customers were and what bugs are in the products they bought, so I avoid them whenever possible.
supermdguy 9y ago
This looks pretty cool! However, I think it would be annoying to have the tests automatically running as you're typing. What happens if you accidentally create an infinite loop or run something dangerous?
- etherealG 9y ago
  Stop at x time. What else is dangerous?
  - supermdguy 9y ago
    I was thinking of overwriting files or removing database items. I know it's pretty easy to minimize, it just could be a problem if it isn't.
    - etherealG 9y ago
      Fair enough, indeed I would advise to use with caution around data that needs to be kept safe from deletion. I think of this as a nice idea for experimenting forms of coding like spikes, but wouldn’t run something like this against a production database or my root file system.

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.

yellowapple 9y ago

I've felt for awhile that it's a matter of time before we end up with a development environment that - given a collection of tests - will automatically generate a program which passes all the tests. Barliman looks like a really cool step in that direction, even with its stated limitations.

setr 9y ago
isn't that called prolog
- agumonkey 9y ago
  I wonder how far they went with prolog. I remember examples in books talking about solving a problem and outputing a plan. But it wasn't a program, not in the sense of nested/modular systems, more like a linear walk. That said, webyrd has shown kanren embedded lambda calc (evalo relation) to find which program would be reduced to some value..
- tree_of_item 9y ago
  No, Prolog is nothing like that. Prolog is perhaps the sort of paradigm that could be used as one part of an implementation of something like that (as we see here with miniKanren), but Prolog itself isn't even close.
- abecedarius 9y ago
  Prolog can (sometimes) "reverse execute" a specification, not generalize from examples. It's like saying "a cat has a round face and pointy ears" versus "look at these cat pictures". (Versus "draw an oval and then draw two triangles at the top...")
  - mycl 9y ago
    But generalising from examples has been a research topic in the Prolog community since at least the early 80s. The field is called inductive logic programming (https://en.wikipedia.org/wiki/Inductive_logic_programming https://en.wikipedia.org/wiki/Inductive_logic_programming).

gergoerdi 9y ago

This seems like a real-time / on-line version of MagicHaskeller: http://nautilus.cs.miyazaki-u.ac.jp/~skata/MagicHaskeller.html http://nautilus.cs.miyazaki-u.ac.jp/~skata/MagicHaskeller.ht...

aetherspawn 9y ago
This thing is so smart. Add a 'z' to the end of the first example and it figures out it needs to 'reverse . drop 1 . reverse' to take a character off the end. Imagine if it could learn on every open source Haskell codebase on GitHub and then learn in real time while people type.

tluyben2 9y ago

This combined with a robust type system should be nice. I thought it would be a solid direction which would've happened but didn't. One of my uni courses was ILP (long time ago indeed) and that seemed to have merit with faster computers, more advanced algorithms and heuristics. After that I saw Hoogle when I learned Haskell; seems combining these things can make something powerful. I was going to post MagicHaskeller here as well but gergoerdi did that already.

noobiemcfoob 9y ago

Attach a program that can evaluate and define test parameters... I'm looking at a core of my replacement >.<

noway421 9y ago

This is dangerous. Instead of acquiring understanding, a tool like this lets the programmer just write the code which passes tests. Without the deep understanding of algorithm you can't write sufficiently full tests which assess program's correctness. TDD wouldn't save here, because instead of being a tool of discipline it becomes a list of instructions for codegen. Would anyone want to ride in a car or fly in a plane written by set of sporadic tests? I wouldn't risk it.

wruza 9y ago
Fun fact: when you board on a plane, you have no idea how good its hardware, software and test suite is beyond common “it didn’t crash n-thousand times before” knowledge.
- vbuwivbiu 9y ago
  the engineers who made and maintain it know everything about it
  - alcidesfonseca 9y ago
    Given how large those systems are, how much layers (OS) of code there are, and the turn-over in software companies, I am pretty confident that no single engineer know everything about.
    - vbuwivbiu 9y ago
      "engineers" - it's been decades since anyone on the planet could know everything about a whole system, but each engineer knows everything about their subsystem
  - coderjames 9y ago
    Which is why I won't fly on certain airlines :-). As a Software Engineer who worked at an avionics company, I know who our big customers were and what bugs are in the products they bought, so I avoid them whenever possible.

supermdguy 9y ago

This looks pretty cool! However, I think it would be annoying to have the tests automatically running as you're typing. What happens if you accidentally create an infinite loop or run something dangerous?

etherealG 9y ago
Stop at x time. What else is dangerous?
- supermdguy 9y ago
  I was thinking of overwriting files or removing database items. I know it's pretty easy to minimize, it just could be a problem if it isn't.
  - etherealG 9y ago
    Fair enough, indeed I would advise to use with caution around data that needs to be kept safe from deletion. I think of this as a nice idea for experimenting forms of coding like spikes, but wouldn’t run something like this against a production database or my root file system.