4 ms·

Thanks for the post, the pull requests, and the questions! I find that it's impossible to give enough context when answering high-level questions such as these

Thanks for the post, the pull requests, and the questions! 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 http://webyrd.net/quines/quines.pdf https://github.com/webyrd/2012-scheme-workshop-quines-paper-code 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 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!

will_byrd 10y ago
> 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. 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 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." :)

will_byrd 10y ago

> 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. 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 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." :)