Thank you for the interest in Barliman!
I'll try to answer all of the questions this afternoon.
Also, I'm very much open to collaboration on Barliman, synthesis, relational interpreters/type inferencers, constraint logic programming, etc.! :)
I'll try to answer all of the questions this afternoon.
Also, I'm very much open to collaboration on Barliman, synthesis, relational interpreters/type inferencers, constraint logic programming, etc.! :)
This would build upon 40 hours of hangouts I did on miniKanren and relational interpreters in 2014 and 2015:
https://www.youtube.com/playlist?list=PLO4TbomOdn2cks2n5Pvif...
The new hangouts would be more focused on research and development, trying to make Barliman more practical, and would hopefully lead to academic publications. In addition to my interest in logic programming, I'm very interested in how to work with people online to do research and writing.
If this sounds interesting to you, please sign up to the miniKanren uncourse mailing list:
https://groups.google.com/forum/#!forum/minikanren-uncourse
or contact me directly:
webyrd@gmail.com
Thanks!
--Will
Since I imagine hangouts based on improving/exploring/experimenting with Barliman, or other similar tools, knowledge of interface design, GUI programming, parallel programming, EC2, etc., should be just as useful as knowledge of logic programming, interpreters, type systems, etc.
I think interest, creativity, and a willingness to learn is the only real prerequisite. For more technical aspects of synthesis using relational interpreters, or whatever, I'll probably do a recap of the core areas of the previous hangout series. I'm sure those 40 hours could be boiled down to something much, much shorter.
a.) What do you think about the current/future state of logic programming?
b.) Do you think that logic programming can at some point be 'mainstream'? If so, what steps need to happen for this to occur.
c.) Is there a particular area of problems that would really benefit from being solved with logic programming? E.g. I was surprised to learn that Windows used to have an embedded prolog interpreter for network configuration and I realized that there must be more areas that could benefit from using logic programming.
d.) Are there some areas where logic programming should never be used?
e.) What is the thing/insight that sparked your interest in this particular research area?
I find that it's impossible to give enough context when answering high-level questions such as these, so some of my answers will probably seem more provocative or critical than I intend. Please ask me for more details/context for any answers that seem especially ridiculous/stupid. I'm not promising, though, that the answers aren't ridiculous/stupid! :)
I'll answer these questions in reverse order.
> e.) What is the thing/insight that sparked your interest in this particular research area?
I had zero interest in logic programming until I saw two programs.
The first was a relational type inferencer written in the original Kanren language, capable of type inhabitation--that is, of synthesizing expressions of a given type. Dan Friedman showed me this program in his B521 graduate programming languages course at Indiana University in Fall 2003. He and Oleg Kiselyov had been playing with these relational type inferencers; this made me want to write an interpreter for Scheme in the same fashion, to generate Scheme expressions that evaluate to a given value. It took us a long time to figure out how to do this is a semi-reasonable way! Our first interesting relational interpreter is described in this paper:
William E. Byrd, Eric Holk, and Daniel P. Friedman. miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl). Proceedings of the 2012 Workshop on Scheme and Functional Programming, Copenhagen, Denmark, 2012.
http://webyrd.net/quines/quines.pdf
https://github.com/webyrd/2012-scheme-workshop-quines-paper-...
This interpreter the single most interesting and enjoyable program I've worked on, and is the basis for Barliman's synthesis. I intend to keep improving this program for the rest of my life.
The second program was the relational arithmetic system that Oleg Kiselyov created, and which appears in chapters 7 and 8 of 'The Reasoned Schemer'. This is the system that convinced me that non-trivial programs can be expressed as true relations, allowing logic variables to be placed in arbitrary positions, and that such programs could be efficient enough to produce interesting answers in practice. A Prolog version of the arithmetic system can be found in this paper:
Oleg Kiselyov, William E. Byrd, Daniel P. Friedman and Chung-chieh Shan. Pure, declarative, and constructive arithmetic relations (declarative pearl). In Proceedings of the 9th International Symposium on Functional and Logic Programming, ed. Jacques Garrigue and Manuel Hermenegildo, pp. 64-80. LNCS vol. 4989, Springer, 2008.
http://webyrd.net/arithm/arithm.pdf
> d.) Are there some areas where logic programming should never be used?
"Never" is a very serious word! :) I don't think we know enough about any form of programming to use words like "always" and "never." I agree with Gerry Sussman and Alan Kay that we really don't have any idea of how to program. That is doubly true for the kinds of relational programs we're exploring with miniKanren.
Also, I don't really do logic programming, as it's commonly understood. (As in Prolog programming, for example.) I'm interested in writing non-trivial programs as relations, in which variables representing unknown sub-terms can be placed anywhere, within any argument. Relational programming overlaps with traditional logic programming in many ways, but really has a different feel, different goals, and requires different techniques, and different features from the underlying language.
In the short term I would say that relational programming should be used for everything, and nothing. 'Nothing,' since it is so difficult to write efficient relational programs, or even to write queries that are guaranteed to terminate. 'Everything,' since writing programs as relations is often shocking, infuriating, and delightful, all at the same time.
For example, when we were working on the relational Scheme interpreter, we had no idea that it could generate quines from their mathematical definition, until Stu Halloway pointed this out to me and Dan Friedman at Clojure/conj. Talk about a bolt from the blue! And later Michael Ballantyne showed that we could treat the Scheme definition of `append` as a relation by running it inside the relational Scheme interpreter, instead of writing a special `appendo` relation directly in miniKanren. This is the technique used by Barliman! I didn't realize either of these insights, even after many years of writing relational interpreters. I love writing these short programs that can surprise its creator in such deep ways, even after many years!
I suppose the standard answer is: rule-based systems that have to perform some type of logical inference. For example, UBS bank apparently wrote a rule-based system in core.logic (David Nolen's Clojure library, originally based on miniKanren, but which now has many extensions). My understanding is that the UBS system was some sort of expert system, determining when certain financial operations should occur. This is a very Prology application.
Like I said above, I'm much more interested in relational programming than in logic programming. I'm not sure which problems benefit most from relational programming, which is one reason I created the Barliman prototype. Nehal Patel thinks that the generality/efficiency tradeoff inherent in the relational interpreter approach to program synthesis makes it most useful for extremely difficult or extremely general problems that cannot be readily expressed using other techniques. This would be similar in spirit to techniques like Markov Chain Monte Carlo--a very general, but potentially slow, technique that should never be be used (here's the "never" word!) if a faster, more specific technique is applicable, but which can be used to express all manner of messy computation.
> b.) Do you think that logic programming can at some point be 'mainstream'? If so, what steps need to happen for this to occur.
In the 1980s logic programming was mainstream, at least in Japan! (https://en.wikipedia.org/wiki/Fifth_generation_computer) LISP, Common Lisp, and Lisp machines, and all that, was also semi-mainstream, in that companies and organizations were willing to spend real money on custom hardware and programmers to develop expert systems.
LISP and Prolog were closely connected to good ol' fashioned symbolic AI. During (that season of) the AI winter, the bottom fell out from under LISP and Prolog.
LISP hasn't really become mainstream, although Clojure is fairly popular. But functional programming, and especially ideas from functional programming, has become much more mainstream in the past 10 years. Garbage collection, closures, and even (semi-)hygienic macros are now standard features--or at least standard extensions--in am increasing number of popular or semi-popular languages.
There are at least some uses of logic programming that have started to become popular again. Datalog is being used for static analysis, LogicBlox is selling Datalog-based products to major corporations, Clojure's Datomic is (or contains) a Datalog, and I know of at least one startup writing a custom Datalog. So at least Datalog, which is closely related to Prolog, seems to be gaining in popularity.
What hasn't taken off again is a full, general purpose logic programming language, like Prolog. Maybe functional programming has to become more firmly entrenched in industry before general purpose logic programming can become popular, since logic programming is even higher-level, more abstract, and further from the hardware than functional programming. Trying to understand how the search and constraint solving works, seems much more difficult for most programmers than understanding how Lisp's `cons` works, for example. Understanding monads seems closer in difficulty to understanding basic logic programming--the proliferation of tutorials on the basic ideas of miniKanren and core.logic reminds me a little of the multitude of monad tutorials.
There is also the applicability and performance issue. There is increasing interest in using functional programming, or at least functional techniques, in AAA video games, and there have been a few success stories. Still, using Haskell to write Call of Duty 17 doesn't seem feasible right now. Similarly, it's not clear how to write such a game using a general-purpose logic language. I think what's clear, though, is that parts of these games can be a good match for functional or logic languages or DSLs.
> a.) What do you think about the current/future state of logic programming?
I'm disappointed by the extent to which Prolog is still dominant in the logic programming community, especially for research. I have nothing against Prolog. Having a mono-culture, though, stifles lots of ideas. (Thought experiment--imagine what the state of programming languages research would be in all research was done in...FORTRAN, LISP, Haskell, or any other single language, no matter how great that language is.)
Curry, Mercury, Mozart/Oz, and miniKanren, of course, each have a different take on logic programming than does Prolog, and the logic programming community has never been entirely a mono-culture. But compared to functional programing, for example, there are far fewer logic programming languages that are at all popular, or that are used in research or industry.
I suspect that the dominance of Prolog is one reason that logic programming isn't currently more popular. Haskell, Scheme, Common Lisp, Scala, Clojure, F#, OCaml, Racket, etc., are active enough, and have vibrant enough communities, that someone interested in functional programming can pick from a wide variety of languages, with different philosophies, syntax, type systems, tooling, etc. In the logic programming world it's still either Prolog...or some essentially marginal language (in terms of popularity, not quality!) with a tiny community.
I do think that many people are interested in the ideas of logic programming, especially now that functional programming ideas have become mainstream, having infected even Java and C++. People are starting to look for the next higher level of abstraction after traditional functional programming, be it dependent types, proof assistants, logic programming, or whatever. And I find the interest in Datalog, and the interest in miniKanren, promising.
Unless some language/killer-application combination appears out of the blue (think Ruby/Rails), I suspect that for the foreseeable future it will be the ideas of logic programming, and perhaps a few logic programming DSLs, that influence the broader programming community, and only for the early adopters.
Using multiple DSLs to express different paradigms within the same program seems entirely reasonable to me. This is a very Lispy/Schemely/Rackety notion. There is lots of interest in DSLs these days, and more languages are supporting macro systems, even hygienic macro systems (at least for limited notions of "hygienic"). I wouldn't be surprised if logic programming ideas slip into programmers' toolkits through DSLs like miniKanren or embedded Prologs. Something like an O'Reilly book on using logic programming DSLs to solve common problems would go a long way towards making these techniques more widely known.
As far as the future of relational programming, as opposed to logic programming, I think we haven't even scratched the surface of what is possible. I'm inspired by Alan Kay's saying that "the best way to predict the future is to invent it." :)
> Thanks for the post, the pull requests, and the questions!
You are very welcome, lol. There might be more coming as time permits. I'll keep an eye out on the progress.
> I'm not promising, though, that the answers aren't ridiculous/stupid! :-)
I've always felt like people are too afraid about not sharing their ridiculous ideas anyway :-).
> I suppose the standard answer is: rule-based systems that have to perform some type of logical inference.
I think that my question was a bit too ambiguous. I think that I meant like an area where logic programming isn't currently commonly used (to me, the network configuration tool seems very out of place for example) but it would be a match made in heaven. I'm aware of expert systems :-).
> In the 1980s logic programming was mainstream, at least in Japan!
I'm actually aware but for some reason it's not mainstream now.
> What hasn't taken off again is a full, general purpose logic programming language, like Prolog.
That's what I was asking about. E.g. would it make sense to e.g. write an OS in a logic/relational language? What sort of CPU support would be required to make this a serious effort? I think what I'm getting at is that I feel like e.g. Prolog isn't truly general purpose. I get that it's turing complete but large portion of programs are much slower in prolog (as you say yourself). Is this something that's "inherent" to logic languages (like even if HW support were better, will it always (i know i know, no absolutes but you get the gist) be MUCH slower or could it be just slightly slower)?
Like I realize that they are slower because they are fundamentally doing a search but I'm wondering if e.g (and I'm really just trowing ideas on the wall here) it's possible to leverage type systems and hw support to considerably reduce the runtime search space and do most of it on compile time. Are you familiar with liquid types (you mention dependent types, so I'm guessing yes?)?
In your work, you seem to be gravitating towards dynamically typed languages. Wouldn't a lot of work be easier in like Haskell or some other type language? I'm sure you have good reasons for not having switched and I'm interested in hearing those. Why are Lisps better for your work?
> "Never" is a very serious word! :-) I don't think we know enough about any form of programming to use words like "always" and "never."
I was actually thinking about wording it slightly less absolutely but I was interested if there were any problems where logic programming would be a bad idea no matter what so it would be basically "never".
> Unless some language/killer-application combination appears out of the blue (think Ruby/Rails),
I think that's part of what I was asking. What would be a "killer" app for logic programming? Are there any problems out there that aren't currently being solved with logical programming but would really benefit from them?
Btw can you recommend some literature on the intersection of logic/constraint/relational programming and music? I've ordered this book https://amazon.com/dp/1848212887/
I'll check out the links you posted. I'm actually working full-time on this music composition app (logic/relational programming isn't the main contribution of the application but I'm just trying to see if there's some low hanging fruit I could do easily and blow minds). If you have any sort of input into that I'm be interested. I saw on your CV that you supervised some undergrad research in this area so I'm guessing that you might not be unfamiliar with that intersection.
I did see like the top google links when I searched for the combination of those keywords (e.g. https://vimeo.com/55677313) so I think I'm interested in some sort of meta analysis.
Sure. I'll take a crack at these followup questions first, though!
> I think that my question was a bit too ambiguous. I think that I meant like an area where logic programming isn't currently commonly used (to me, the network configuration tool seems very out of place for example) but it would be a match made in heaven. I'm aware of expert systems :-).
It doesn't surprise me to see Prolog in a configuration system, since configuration is a standard use of expert systems--for example, Xcon (https://en.wikipedia.org/wiki/Xcon). Getting a manager at Microsoft to allow the use of Prolog is the surprising thing to me! :)
> That's what I was asking about. E.g. would it make sense to e.g. write an OS in a logic/relational language? What sort of CPU support would be required to make this a serious effort? I think what I'm getting at is that I feel like e.g. Prolog isn't truly general purpose. I get that it's turing complete but large portion of programs are much slower in prolog (as you say yourself). Is this something that's "inherent" to logic languages (like even if HW support were better, will it always (i know i know, no absolutes but you get the gist) be MUCH slower or could it be just slightly slower)?
You can play all sorts of "extra-logical" tricks in Prolog to improve performance, at the cost of giving up declarativeness. Still, Prolog is not the language I'd reach for first when writing system software, as you point out.
Have you looked at Mercury? Mercury is a logic programming language that borrows heavily from Haskell. One cool thing about Mercury is that you define high-level relations, specifying types and other annotations for each relation. The Mercury compiler then compiles the high-level declarative relations into lower level, more efficient functional definitions. One high-level relation might be compiled to many functions, which are dispatched to at run-time based on the groundness of the arguments passed to the relation. Mercury is specifically designed for system programming, and also has support for parallelism.
I should point out that Mercury relations aren't really full relations, like they are in miniKanren. Mercury compiles away unifications for efficiency, which means that Mercury can't handle more sophisticated uses of logic variables. For example, the quine-generating query would be impossible to specify in Mercury. But the resulting code is much more efficient.
Greg Rosenblatt has applied a few of the Mercury compiler techniques to the relational interpreter used by Barliman, which has sped up some synthesis queries by orders of magnitude. He suspects there are more gains to be made from borrowing Mercury optimizations.
> Like I realize that they are slower because they are fundamentally doing a search but I'm wondering if e.g (and I'm really just trowing ideas on the wall here) it's possible to leverage type systems and hw support to considerably reduce the runtime search space and do most of it on compile time. Are you familiar with liquid types (you mention dependent types, so I'm guessing yes?)?
I'm not sure what you mean by hardware support, exactly. Are you talking about using accelerators like GPUs or FPGAs? If so, as far as I can tell miniKanren doesn't map well onto these accelerators, although the Intel Phi might be a decent match.
I suspect that running synthesis tasks on a beefy server, or even on a cluster, would result in a significant improvement to performance. Static analysis and compiler optimizations would probably make a much bigger difference, though.
I'm slightly familiar with liquid types. There may be ways for dependent types to prune parts of the search space statically, although I'm not sure. I'd like to explore combining miniKanren and Idris, to see where that leads.
> In your work, you seem to be gravitating towards dynamically typed languages. Wouldn't a lot of work be easier in like Haskell or some other type language? I'm sure you have good reasons for not having switched and I'm interested in hearing those. Why are Lisps better for your work?
I like Scheme because it has very powerful meta-programming capabilities, it is easy to write meta-circular interpreters, it is trivial to write DSLs (without having to write parsers or whatever), and the abstract syntax and concrete syntax are essentially the same. Being able to just call 'read' to parse an expression, and being able to redefine built-in binding forms, for example, can be extremely handy.
Haskell is a language chock full of interesting ideas. I don't love it, though. The syntax, lack of macros, all the extensions in GHC, etc., make for a language that is powerful but complex. I like languages that are powerful but small, containing only a few concepts. miniKanren itself only has three core operators; the relational interpreter uses an extended version of miniKanren with six operators, but we hope to get that down to five.
In short, Scheme fits my programming style better. I'm not averse to using other languages, though. And miniKanren has been ported to dozens of host languages, including multiple Haskell implementations.
As far as the types making things easier, I'm not sure this is true. Many ML and Haskell programmers have looked at miniKanren and said, "this would be so much better with types!" After playing around with the implementation for a while, they usually say, "taking advantage of the types without losing the flavor of miniKanren is much harder than I thought." As far as I can tell, the only interesting embedding of miniKanren in a typed language is Dmitry Boulytchev's OCanren (https://github.com/dboulytchev/OCanren). Dmitry had to hack the OCaml type system at a low (and potentially unsafe) level to make the embedding possible. I would be interested in exploring OCanren for writing relational interpreters. I'm not exactly sure what it would buy us, though.
There are lots of interesting connections between dependent types and logic programming. I'd like to explore combining Idris and ideas from miniKanren, for example. To me, combining Idris and miniKanren seems more interesting and promising than combining Haskell and miniKanren, which has been done many times without apparent benefit.
Now, in contrast to the host language used for the embedding of miniKanren, implementing a typed language in the relational interpreter definitely makes synthesis easier. In other words, implementing a relational interpreter for an ML-like language, using miniKanren embedded in Scheme, is probably far better for synthesis than implementing a relational interpreter for Scheme, using miniKanren embedded in Haskell.
I definitely plan to investigate relational interpreters for typed languages (Michael Ballantyne has already done some work in this area, and showed great improvements in synthesis). I'm also open to exploring miniKanren's embedded in typed languages. This seems like a much trickier problem than you might think, though. OCanren looks like a promising start, and I look forward to playing with it more.
> I was actually thinking about wording it slightly less absolutely but I was interested if there were any problems where logic programming would be a bad idea no matter what so it would be basically "never".
I think this largely depends on what you consider "logic programming". Mercury seems applicable to systems programming problems that aren't an ideal match for traditional Prolog, for example. And Curry allows functional programming and logic programming to be blended in interesting ways that blur the lines between the paradigms.
There are also approaches like Answer Set Programming, and even Answer Set Programming Modulo Theories, that use powerful solvers to solve problems that would be hopelessly inefficient with naive Prolog (or miniKanren) search.
So I'll stick with my original answer, and say it's far too soon to tell. :) We do need new langauges and approaches, though!
> I think that's part of what I was asking. What would be a "killer" app for logic programming? Are there any problems out there that aren't currently being solved with logical programming but would really benefit from them?
Such a tiny percentage of programmers have even heard about Answer Set Programming; it's possible there are killer apps for ASP laying around, just waiting for someone to connect the ideas.
I suspect killer apps will be found for probabilistic logic programming, as the languages and implementations improve, and as more people become comfortable with probabilistic programming.
And, of course, I'm hoping program synthesis using logic programming will be a killer app! :)
> Btw can you recommend some literature on the intersection of logic/constraint/relational programming and music? I've ordered this book https://amazon.com/dp/1848212887/ > I'll check out the links you posted. I'm actually working full-time on this music composition app (logic/relational programming isn't the main contribution of the application but I'm just trying to see if there's some low hanging fruit I could do easily and blow minds). If you have any sort of input into that I'm be interested. I saw on your CV that you supervised some undergrad research in this area so I'm guessing that you might not be unfamiliar with that intersection. > I did see like the top google links when I searched for the combination of those keywords (e.g. https://vimeo.com/55677313) so I think I'm interested in some sort of meta analysis.
I'd be happy to talk to you about this in more depth, maybe via hangouts. I think it depends very much on what you want to do. For example, synthesis of music that pleases humans is still an open problem. But other problems seem more tractable.
When I'm learning a new system, especially in an unfamiliar domain, it sometimes takes a while for that "click" to happen in my brain. Before the click, I'm just building mental projections of the system internals, adding primitives and new relations on the fly based on whatever reading material I have at my disposal. After the click, I have a solid understanding of the core of the system and all other knowledge fits neatly on top of it.
This is especially important for me when designing new systems from my mental projections, as opposed to deducing systems that I know already exist. Sometimes there are inconsistencies hidden behind several layers of indirection. Hard to spot when you're not an expert in the domain, because the domain keeps changing as you're brainstorming.
I've been experimenting with JetBrains MPS for this exact purpose. It's good, but it doesn't "guide you" if that makes sense. Providing autocompletion for custom concepts is as far as it goes AFAIK. Barliman looks very useful for this kind of guided approach.
I'd love to hear any thoughts you may have on the topic! Do you think about things in a similar manner? Is there anything that I should check out?
One book I highly recommend, and which I've found very accessible, is Ivan Bratko's 'Prolog Programming for Artificial Intelligence'. The 4th edition has a section on ILP.
If you are interested in ILP and also in Barliman, maybe this is a topic we could explore together.
http://www.springer.com/gp/book/9783540200406
And this is a good introduction to the statistical side of things, a.k.a. statistical relational learning:
http://www.cs.umd.edu/srl-book/
Also, if you're considering adding stochastic search this might be a good pointer:
https://dtai.cs.kuleuven.be/problog/
Problog is a probabilistic Prolog. Above is the implementation in Python but there's a few Prolog versions floating around, unfortunately the ones I tried did not seem to work out of the box.
I really enjoyed the Statistical Relational Learning book.
Rob Zinkov and I have worked on two prototypes of probKanren (https://github.com/webyrd/probKanren), a probabilistic version of miniKanren inspired partly by the Hakaru language (http://indiana.edu/~ppaml/HakaruTutorial.html, https://github.com/hakaru-dev/hakaru). We learned a lot from our two prototypes of probKanren, but neither version is ready for real use (and neither version is documented!).
Rob and I have taken a step back, and are now working with Evan Donahue on just adding stochastic search to miniKanren. If you are interested in joining us, please let me know! :)
I've heard of MPS but I don't know much about it. I need to watch the demos/screencasts!
I'm very much interested in "tools for thought," which could include deduction assistants, but also other tools to augment human intellect. Barliman is the first program I've worked on with this tools-for-though mindset, which I've found very stimulating. I've been influenced by Englebart, Vannevar Bush, Licklider, Alan Kay, Alan Borning, Brett Victor, Alex Warth, Michael Nielsen, among others. I can point you to lots of resources on this topic, if you are interested.
Michael Ballantyne and I started a mailing list/set of Google Hangouts called "As We May Thunk" to explore some of these ideas. You might find some of the hangouts interesting:
https://groups.google.com/forum/#!forum/as-we-may-thunk
I'm not sure I fully understand your question though. It sounds like you may have a specific tool or feature in mind. Can you elaborate a little more?
I'm always up for email or a hangout if this isn't the best venue.
As I understand it, Solar-Lezama's approach is based on CEGIS (counter-example guided inductive synthesis), using a model checker or similar tool to generate counter examples from a specification. Barliman currently doesn't use anything like CEGIS, although I hope to add something similar in the near futures, perhaps using optional properties (as in Quickcheck) or contacts as partial specifications.
The sketching approach seems to require more structure than does Barliman in terms of what the programmer must specify, to make synthesis more efficient. The versions of Sketch that I've seen don't have anything like an interactive editor--the interactivity is really the key part Barliman is meant to explore.
Solar-Lezama's group is doing lots of interesting work in addition to Sketch:
http://groups.csail.mit.edu/cap/
I'm looking forward to trying to incorporate their techniques into Barliman!