Eric Normand
PodcastClojureCoursesBook

Will Byrd Clojure/conj 2016 Interview

Written by Eric Normand. Published: November 29, 2016. Updated: April 18, 2018.

Will Byrd will be giving a talk at Clojure/conj 2016. He will be speaking with Greg Rosenblatt about Barliman, an IDE that can generate code based on examples.

Follow him on Twitter, GitHub, and his homepage.

PF.tv: How did you get into relational programming?

Will Byrd: In the immortal words of Inigo Montoya, "Let me explain. No, there is too much. Let me sum up."

Dan Friedman got me involved in logic programming immediately after I started graduate school at Indiana University in 2003. He and Oleg Kiselyov had been working on a language called 'Kanren,' which was based on a language Dan had been using for teaching logic programming. My first summer at IU the three of us wrote a book, 'The Reasoned Schemer,' about logic programming in a simplified version of Kanren called 'miniKanren.'

The most important chapters in 'The Reasoned Schemer,' from my perspective, are chapter 7 and 8, which show how to implement arithmetic operators like addition and multiplication as pure relations. This approach was entirely due to Oleg, who urged us to write our programs as relations wherever possible. This was a revelation to me, and I decided I was going to write all of my programs as relations from then on!

Writing all of my programs as relations turned out to be much more difficult than I had hoped, which, as a researcher, was great news! We're still trying to make relational programming easier, more efficient, and more expressive. We've made a lot of progress over the past 13 years, though!

We owe so much to the Clojure community. David Nolen's amazing core.logic library, and the many people who use and write about the library, have given miniKanren and relational programming a giant boost. I doubt we'd still be working on relational programming without David's efforts. The countless interesting conversations Dan, Nada Amin, and I have had after our joint Conj talks have similarly been critical, as was the miniKanren miniConfo organized by Fogus as Clojure/West in 2013. And, of course, Stu Halloway's comment about quine generation pushed our work on relational interpreters to the next level, which made Barliman---and our upcoming conj talk---possible. In a very real sense the last 4 years of miniKanren research have been inspired by Stu's comment.

I'd love to describe the contributions made to miniKanren by all the people we've worked with over the years. I could write pages just on Claire Alvis's and Jason Hemann's contributions, for example. To keep things manageable, I'll mention just a few contributions most directly related to Barliman. Michael Ballantyne pointed out that we should be able to run Scheme's append, without modification, in the relational interpreter, and that append should then work as a relation. Amazingly this actually works in practice, and is the basis for Barliman. Like all great insights, it seems obvious in hindsight---we had worked on relational interpreters for years without trying this! Greg Rosenblatt, who is giving the talk with me, has sped up many synthesis queries by 6 orders of magnitude(!). He is working on other improvements that could make relational programming practical---at least for some tasks---in the near-term, rather than 15 or 30 years from now. Just as importantly, it's so much fun working with Michael and Greg! The other people I'd like to thank are, of course, Dan Friedman and Oleg Kiselyov, truly the godfathers of Barliman and our approach to relational programming---none of this would exist without them. And I'd like to specially thank Matt Might, who has been incredibly supportive of my work at the University of Utah. Thanks everyone! <3

PF.tv: What is your talk about?

WB: Greg Rosenblatt and I will be demonstrating a new interactive development environment, called Barliman, that uses relational programming under the hood. You can find Barliman on GitHub but the examples and screenshots are sadly out of date. (The age-old problem---too much hacking, not enough documenting...) The interesting examples directory contains more recent examples and screenshots.

Two interesting tasks we'll demonstrate in Barliman are example-based synthesis of simple recursive functions, and the ability to run test cases on code that is only partially defined. We'll also be showing other, more sophisticated examples of relational programming.

We'll also be talking about relational programming in miniKanren, which is the predecessor of David Nolen's core.logic library in Clojure. In particular, we'll be demonstrating improvements we've made---with the help of many talented people, including Michael Ballantyne, Jason Hemann, Claire Alvis, Eric Holk, Dan Friedman, and others---to the relational Scheme interpreter Dan Friedman and I showed at the Conj in 2011 and 2012.

PF.tv: What do you hope people will take away from the talk?

WB: Inspiration, questions, and ideas, and---ideally---a desire to work on much more advanced editors and IDEs than currently exist (regardless of whether those IDEs are related to Barliman or relational programming). And, of course, a basic understanding of relational programming, and hopefully an interest in learning more about it. (Core.logic is a great place to start!)

For anyone interested in contributing to Barliman, better understanding how Barliman works, porting Barliman to Clojure, or whatever, Greg, Michael Ballantyne, and I will be starting a new Google Hangout series on relational programming, focused on Barliman. Anyone interested can sign up on the Barliman Google Group.

PF.tv: What question is Barliman an answer to?

WB: Barliman isn't an answer---rather, it is an attempt to identify interesting questions. What might a real-time, interactive editor, with deep semantic understanding of the underlying programming language, along with (currently modest) synthesis abilities, look and feel like? What is the space of interesting and useful interaction design? How far might this approach be pushed? How could the IDE be made conversational, in a useful way? How might it interact with test-driven development, property-based testing, and contracts? (Think core.spec here!) We've only touched on a few of these questions. The questions have become far more interesting now that Greg has sped up some features of the tool by many orders of magnitude!

PF.tv: What concepts do you recommend people be familiar with to maximize their experience with the talk?

WB: I think the Clojure audience will be able to follow along, since everyone is already familiar with S-expressions, recursion, and functional programming! I think the most important thing is to come to the talk with an open mind and a sense of imagination and curiosity.

It would also be useful to think before hand about the question, "What might an advanced interactive development environment look like 30 years from now?" Greg and I will be showing one possible vision for an advanced IDE, but there are many alternative visions. I'm extremely curious which ideas others in the Clojure community have, or will have!

PF.tv: What resources are available for people who want to study up before the talk?

WB: Of course there is the Barliman website.

The main page is woefully out of date---more recent and more advanced examples and screenshots can be found in the interesting examples directory.

Anyone who wants to study before the talk could look at core.logic, which is the Clojure equivalent of the miniKanren language that underlies the Barliman editor.

minikanren.org contains lots of information on miniKanren, including how the language differs from Prolog.

Two very interesting projects to read up on are the 'Programmer's Apprentice' project from MIT:

and the 'Wise Computing' project from the Weizmann Institute.

How might tools like Barliman relate to these visions of intelligent, conversational development environments? Something to think about before, during, and after the talk! :)

PF.tv: Where can people follow you online?

WB: I'm on Twitter at [@webyrd]twitter and GitHub.

My YouTube channel has videos from past Google Hangouts on miniKanren (including a 40-hour miniKanren "uncourse") and other programming topics:

Greg Rosenblatt, Michael Ballantyne, and I will be starting a new Google Hangout series on Barliman, relational interpreters, and program synthesis right after the conj! Anyone interested should sign up for the new Barliman Google Group.

PF.tv: How can people help out with Barliman?

WB: We have a ton of open problems to work on with Barliman. How do we create a conversational interface that will interact with the user in a rich and helpful manner? (The Programmer's Apprentice project at MIT worked on this problem for over a decade, but using a different approach---it would be great to borrow some of their ideas!) More generally, what sort of interaction design makes sense for a tool like Barliman? How should programmers write their code to get the most benefit from such a tool? How might optional types, properties, and contracts be best integrated into Barliman? What would Barliman for Clojure or JavaScript (for example) feel like? There are countless other open problems.

If any of this excites you, drop me a line at webyrd@gmail.com or post to the new Barliman Google Group!

And of course, I hope people will join us for the new Google Hangouts series on Barliman and relational programming, focused on improving Barliman, after the Conj ends. Just sign up for the Barliman Google Group!

PF.tv: Are there any other projects you'd like people to be aware of?

WB: There are always a variety of relational programming projects ongoing or in the planning stages. For example, I'm working with Greg Rosenblatt on improving Barliman, with Michael Ballantyne on improving the relational interpreter, with Nick Labich and Tom Gilray on static analysis of miniKanren programs, with Chris Brooks on partial evaluation of miniKanren, and with Evan Donahue and Rob Zinkov on probabilistic search for miniKanren. There are many other projects that I would like to work on, including improved constraint solving, synthesis of JavaScript programs, a conversational interface for Barliman, deep learning to guide miniKanren search, and advanced test generation. Anyone interested in working on any of these projects, or other projects related to miniKanren, relational programming, program synthesis, or advanced IDEs, should definitely contact me at webyrd@gmail.com!

As a personal project, I've been working with biochemists at Stanford and Harvard, providing pro bono software engineering help for their research on glycobiology, which I hope will eventually help my friends and their son (also here). I've learned that many labs doing biomedical research---even at prestigious universities---are in desperate need of even basic software engineering expertise. I suspect other programmers and researchers may be interested in sharing their skills to quicken the pace of biomedical research. I'd like to figure out how to organize this expertise. If this interests you, please contact me! And if you are going to Clojure/conj, come to the "unsession" I'm organizing on "Software engineering support for scientists"!

I love big ideas, transformative technology, long-term thinking, and the willingness to take goofy-sounding ideas (like relational programming!) seriously. Four areas of transformative technology I'm fascinated with are artificial intelligence, nanotechnology, molecular and synthetic biology, and space travel. I'd like to always be involved with at least one project---even a hobbyist project---in each of these areas. Program synthesis is often considered a branch of artificial intelligence, and we are looking to integrate machine learning and probabilistic programming into miniKanren, so that area is covered. I'm very interested in nanotechnology, and was fascinated to learn that it is possible to build a low-cost scanning tunneling microscope (STM) that can resolve individual atoms! My father, my friend Tom Gilray, and I are each building our own low-cost STM, based on an awesome design by Dan Berard. Not only can this STM resolve individual atoms, it looks like the design can be upgraded to allow for moving individual atoms around, similar to how the famous "A boy and his atom" movie was made by IBM. If this interests you, please join the unsession I'm organizing at the conj on DIY Nanotechnology! Or, email me! I'd love to start a "building your own STM" hangout series with other interested people! :)

I also have projects related to synthetic biology and space travel, but I'll leave those for another time.

PF.tv: Where do you see the state of relational programming in 10 years?

WB: In 10 years I see relational programming as being more expressive, more declarative, more principled, more efficient, more practical, more surprising, and even more fun. Relational programming is so terribly fun---we need to make sure we don't lose the fun, even as the paradigm becomes practical.

Greg Rosenblatt sped up some of our program synthesis queries by a factor of a million (!) over four months, and is now working on a more declarative approach to synthesis. I hope in the next decade we can steal a page (or an encyclopedia) from the program synthesis community, and get another factor of million speedup. And then another factor of a million. I think this is possible, since program synthesis is an inherently exponential problem, so being clever can lead to huge speedups, and since the synthesis community has a very large bag of tricks. A 10^18 speedup over naive synthesis would be a nice start!

I suspect we'll have a very cool, unusual, and practical approach to test generation in the near future.

I also suspect we'll be able to combine machine learning and statistical techniques with relational programming in the medium term.

Our constraint solving will become more sophisticated, and we'll call out to external solvers for help in some domains.

We'll be able to handle languages that don't look like Scheme with our relational interpreter approach. JavaScript and Python, for example, or at least interesting and useful subsets of those languages.

I have a 30---50 year plan in my head for relational programming. I don't know how far the paradigm can be pushed, but I suspect we've barely scratched the surface. If Greg keeps giving us million-fold speedups every four months, my 50 year plan will only take another year, and I'll have to retire to play StarCraft and build space e levators in my apartment instead!

PF.tv: If relational programming were a superhero, what superpower would it have?

WB: The ability to run in a circle, forever, while remaining invisible (at least to most people!).