Paul Bone

Conversation with William Byrd

Today I had an interesting chat with William Byrd about logic programming, relational programming and parallelism. William Byrd is a co-creator of miniKanren (with Dan Friedman and Oleg Kiselyov), miniKanren is the subject of his PhD research, he’s been working on it for over 10 years. Byrd is an author of The Reasoned Schemer However how our conversation begun is not very interesting but provides some context, please bare with me while I set this up.

About a week ago I came across a Quora question asking about the difference between logic and relational programming. Initially I choose not to answer, as I assume this is the same difference between predicate logic and relational algebra but my maths knowledge is not strong enough to answer this. After phoning a friend, Bartosz Witkowski, I was pointed to William Byrd on Logic and Relational Programming, miniKanren. Byrd gives a different answer, not based on the theory, and so I finally answered the Quora question and contacted Byrd on twitter to inform him and clarify my understanding of his talk.

I’ve extracted our conversation from twitter as best I can. I’ve made some minor corrections, added some links and things may appear in a slightly different order compared to our actual conversation. Hopefully these changes make it easier to follow.

Paul: Hi, I referenced a presentation of yours in a Quora answer, I hope I’ve understood what you were saying:

Paul: No, reading now. Cheers.

Will: My definition of relational in this context is that you can place variables representing unknown values anywhere. In any argument to a predicate. From a Mercury/Prolog standpoint, you could say that all arguments can be any mode. This includes partially-ground terms as arguments.

Paul: Not really true for Mercury. Mercury doesn’t support some things properly like partial instantiation or aliasing of two free vars.

Will: Yes. I’d love a Mercury-like lang that handled partial instantiation and aliasing, which are used in our interesting mk queries. The reason that allowing variables anywhere is important is that many problems (program inversion, synthesis, etc.) are identical. Just change where the variables are in the query to get different behavior. Of course, there is a disadvantage to this generality.

Paul: Yeah, that makes sense, when it’s more or less free to run something "in reverse".

Will: Yes. And not just in reverse. For example, for generating quines both the expression and the value are fresh logic variables.

Paul: So would you say that Prolog does/supports relational programming?

Will: Certainly you can write relational programs in Prolog. I do think the defaults of Prolog, and the style, inhibits relationality.

Paul: By defaults, do you mean the resolution strategy?

Will: Depth-first search, no occurs check, that sort of thing. For example, for all of our interesting miniKanren examples, a complete search is necessary. And we need the occur check. And we can’t use cut in many cases. And we use some special constraints. It’s not that it’s impossible to do these things in Prolog, but it is awkward, and far from the default behavior.

Paul: This makes sense, but opens a whole new can of how to express problems in languages for me. Our experience with Mercury (coming from Prolog also) is that logic programming is so awkward we tend to avoid nondet code.

Will: One of the goals of miniKanren is to make nondet code nicer to write/reason about.

The conversation forked several times, this fork of the conversation talked more about avoiding the extra-logical operators common in Prolog.

Will: Can be harder to take advantage of special cases. We are looking into static analysis for miniKanren programs for this reason. Also, Greg Rosenblatt has been working on specializing miniKanren queries, inspired by Mercury.

Paul: A specialisation makes sense. You probably already know about Ciao Prolog, they’ve probably got some work on this.

Will: Ciao is super interesting! Yes, they’ve done neat work on analyses.

Paul: Mercury’s mode analysis may also be interesting, but probably not what you want since it is strong/static. Mercury also allows mode specific clauses, which provides a nice way to specialise code manually, like using var/1 in Prolog.

Will: Greg has been hand-compiling code to act like Mercury. He is reading Mercury papers to understand the optimizations.

Paul: Greg is welcome to contact us if he wants. The mailing lists are the best option. miniKanren sounds like a very cool project!

Will: Thanks! We’re also playing around with probabilistic inference, partly to improve synthesis. Is there probabilistic Mercury?

Paul: No nothing like that.

Will: Also, does Mercury support CHR?

Paul: No, but people have talked off and on about adding a CHR library. It’s something I’d like to see, it’d be a good fit.

Then we started talking about parallelism in logic languages.

Will: Oh yeah—​I’m also very interested in a parallel miniKanren…​i

Paul: Parallel nondet code is very difficult. In Mercury we restrict ourselves to dependant AND parallelism, as it’s the most plentiful. If you’re interested in this my thesis is the latest/most complete resource.

Will: Thanks! I’ll take a look. miniKanren’s implementation is purely functional—​no mutation or backtracking. Does this make parallelization of nondet easier?

Paul: Probably, The remaining thing is how much different things depend on each-others results. also profiling data.

Will: All disjunctions in miniKanren can be thought of as separate processes running in different address spaces.

Paul: In Prolog they often had to communicate regarding variable bindings. If you don’t have that then OR-parallelism is a good way to go!

Will: Yep, our disjuncts never communicate! Conjunction is trickier, though. How much harder is dependent AND parallelism over independent AND parallelism?

Paul: Since things are pure it’s pretty easy, Each shared variable is transformed into a future. P. Wang and Z. Somogyi: Minimizing the overheads of dependent AND-parallelism Pro: there are a lot more dependent conjunctions. Con: Most dependent conjunctions are very dependent - not enough parallelism. Finding which conjunctions offer profitable parallelism was the most significant contribution that I made (ch 4 in my thesis).

Will: Are you doing a static analysis to find these conjuncts?

Paul: A profile-feedback analysis.

Will: Is there any point in parallelizing unification, maybe on an accelerator? Or is that too fine-grained?

Paul: Too fine grained IMHO. Plus in Mercury it’s very cheap, at worst it allocates a memory cell and fills it in.

Will: Is there a killer app for parallel Mercury yet?

Paul: I’m afraid not. IMHO the next challenge is specialising different "patterns" like loops, foldl-shaped, divide and conquer etc.

Our thread about AND-parallelism continued separately to cover a clarification.

Will: Thanks! Does Mercury have any issues with divergence vs. failure when reordering conjuncts?

Paul: I’m not sure what that is.

Will: In Prolog and miniKanren, reordering code can cause queries that terminate with a finite set of answers to diverge.

Paul: Okay, I’m pretty sure our mode system prevents that.

Following our discussion of parallelism, we started talking about Plasma.

Paul: But I’ve also shifted my focus from parallelism in Mercury to Plasma. Mercury still pays the bills though.

Will: How does Plasma differ from Mercury or Prolog?

Paul: Plasma isn’t a logic language. It’s a pure functional language that "looks" imperative, has a few imperative features.

Will: How does it compare to Curry?

Paul: Quite different from Curry also. As it’s not very much like Haskell.

Will: Sounds interesting! Can you write things like append as a relation?

Paul: No, it’s not multi-moded. Functions have clear inputs and outputs. Like Haskell/ML etc. But there can be more than one output:

x, y = foo(a, b)

Will: Is there a particular point of view for the language design?

Paul: If I understand the question: Trying to find a compromise between declarative and imperative programming. And when in doubt, choosing more "familiar" syntax styles, like curly braces. A fair amount of inspiration comes from SISAL too.

Will: Interesting. Are you familiar with Gödel, BTW? Another take on trying to make LP more relational.

Paul: I’ve heard of it, but haven’t read much. Same as miniKanren.

And so a hesitant answer on Quora led to a very interesting discussion. I had been hearing about miniKanren lately but hadn’t looked into it myself. Without learning the specifics I now understand the projects goals, including the very interesting goal of making what I would call non-deterministic code easier to write correctly. This is interesting since we’ve both found that non-deterministic code in Prolog can be awkward. Mercury attempts to this easier to handle by having less non-determinism and while miniKanren (and perhaps Gödel) attempt to make non-determinism easier to work with. Certainly my interest in Plasma moves me even further from logic/relational programming, however I salute people like William Byrd who are working to make this very powerful programming model easier to use.