Paul: Hi, I referenced a presentation of yours in a Quora answer, I hope I’ve understood what you were saying: https://www.quora.com/What-is-the-difference-between-logic-programming-and-relational-programming

Will: Thanks! Have you seen this? http://stackoverflow.com/questions/28467011/what-are-the-main-technical-differences-between-prolog-and-minikanren-with-resp

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.

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.

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.

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.

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.