6 ms·

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, synthes

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

will_byrd 10y ago
One more high-level comment. I'm thinking of starting a series of Google Hangouts to explain how Barliman works, and more importantly, to collaborate on making the underlying technology better and explore alternative interfaces. 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=PLO4TbomOdn2cks2n5PvifialL8kQwt0aW 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 https://groups.google.com/forum/#!forum/minikanren-uncourse or contact me directly: webyrd@gmail.com https://twitter.com/webyrd https://twitter.com/webyrd Thanks! --Will
- monorailz 10y ago
  What will the expected level of prerequisite knowledge be for participating in the hangout?
  - will_byrd 10y ago
    Good question! 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.
    - monorailz 10y ago
      Thanks for the reply. Hope I will have time to join the hangout.
adamnemecek 10y ago
I have some questions. 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?
- will_byrd 10y ago
  Good questions! I'm fading, but hope to answer these questions, and the rest that have been posted, tomorrow. :)
- will_byrd 10y ago
  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!
lopatin 10y ago
Thank you for your hard work in this area! I'm just starting to learn about relational programming, but I'm interested in it from the perspective of "computer aided thinking", i.e. a deduction assistant. 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?
- lopatin 10y ago
  Maybe I just need to learn Prolog/Aleph
  - will_byrd 10y ago
    Inductive Logic Programming is really interesting. I'd really like to explore similarities between ILP and the synthesis used in Barliman--I suspect Barliman's example-based synthesis could get a real boost from ILP. 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.
    - YeGoblynQueenne 10y ago
      A good resource for relational learning in general including ILP is this: http://www.springer.com/gp/book/9783540200406 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/ 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/ 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.
chrismonsanto 10y ago
How does this compare to Solar-Lezama et al's "Sketching Stencils" approach to program synthesis?
- will_byrd 10y ago
  Sorry for the slow reply. 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/ http://groups.csail.mit.edu/cap/ I'm looking forward to trying to incorporate their techniques into Barliman!

will_byrd 10y ago

One more high-level comment. I'm thinking of starting a series of Google Hangouts to explain how Barliman works, and more importantly, to collaborate on making the underlying technology better and explore alternative interfaces. 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=PLO4TbomOdn2cks2n5PvifialL8kQwt0aW 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 https://groups.google.com/forum/#!forum/minikanren-uncourse or contact me directly: webyrd@gmail.com https://twitter.com/webyrd https://twitter.com/webyrd Thanks! --Will

monorailz 10y ago
What will the expected level of prerequisite knowledge be for participating in the hangout?
- will_byrd 10y ago
  Good question! 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.
  - monorailz 10y ago
    Thanks for the reply. Hope I will have time to join the hangout.

adamnemecek 10y ago

I have some questions. 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?

will_byrd 10y ago
Good questions! I'm fading, but hope to answer these questions, and the rest that have been posted, tomorrow. :)
will_byrd 10y ago
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!

lopatin 10y ago

Thank you for your hard work in this area! I'm just starting to learn about relational programming, but I'm interested in it from the perspective of "computer aided thinking", i.e. a deduction assistant. 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?

lopatin 10y ago
Maybe I just need to learn Prolog/Aleph
- will_byrd 10y ago
  Inductive Logic Programming is really interesting. I'd really like to explore similarities between ILP and the synthesis used in Barliman--I suspect Barliman's example-based synthesis could get a real boost from ILP. 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.
  - YeGoblynQueenne 10y ago
    A good resource for relational learning in general including ILP is this: http://www.springer.com/gp/book/9783540200406 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/ 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/ 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.

chrismonsanto 10y ago

How does this compare to Solar-Lezama et al's "Sketching Stencils" approach to program synthesis?

will_byrd 10y ago
Sorry for the slow reply. 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/ http://groups.csail.mit.edu/cap/ I'm looking forward to trying to incorporate their techniques into Barliman!