[YeGoblynQueenne]

>> If you are up for a challenge, I'd be happy to work on a Prolog version of the Scheme interpreter with you!

Oh gosh, don't do that to me :) I just finished submitting my second paper and I have to write my thesis, plus another couple of side projects already and a hell of a lot of work on my Louise ILP system. Maybe we can talk about this again after March 2022? When I should be finished with my thesis?

Note however I may not be the best person for this job. I'm serious when I say I'm "impure". I mean that I'm not very interested in declarative purity. For me it's more like an ideal goal than something I absolutely feel I need. I suppose I've become all too comfortable with Prolog's er pragrmatic hacks, that I don't feel I need them gone.

That said, it's certainly an interesting challenge :)

>> The problem isn't that relational programming in Prolog isn't possible. The problem is that it requires enough work and non-standard techniques that in practice people don't do it.

I hope I don't misunderstand what you mean by relational programming. I think you mean pure logic programming, _not_ like implemented in Prolog, but as it's described, say, in Lloyd? Then yes, I agree. It is often infinitely easier to use Prolog's impure facilities, like the dynamic db and so on, to complete a complex piece of code. I guess the quintessential example is findall/3 and friends- impossible to implement in pure Prolog, without a dynamic db (er, far as I know).

In general, I find myself resorting to using impure features when I can't find an efficient way to write a program without them. For instance, sometimes I want to use random access data structures, over linked lists (so, Prolog "terms" with setarg/3 arg/3, rather than list traversal). Othertimes it's just so much easier to bang together a findall/3 with an arg/3 counter, than write yet another recursive skeleton with 4 accumulators- and an interface predicate to hide them.

To be honest, a purely declarative language that took those impure but convenient hacks away would take me some time to get used to. I don't know that I want to give those conveniences up. They're there for a reason- a tradeoff of purity for efficiency and usability. I, personally, find that tradeoff balanced and while I'm not against going the other way (sacrificing efficiency and ease of use for purity), as a research goal, I'm not going to go out of my way to try and achieve that.

>> I'd also be delighted to write a paper about it with you! :)

I am very flatterred :) But I'm letting you down, ain't I? I'll bring up Markus Triska again, as someone I understand to be a dedicated Prolog programmer, also dedicated to declarativey purity. Maybe he'be up to it.

Thank you for the recommended reading on minikanren's search!

[will_byrd]

> Oh gosh, don't do that to me :) I just finished submitting my second paper and I have to write my thesis, plus another couple of side projects already and a hell of a lot of work on my Louise ILP system. Maybe we can talk about this again after March 2022? When I should be finished with my thesis?

Very nice! ILP is extremely interesting, especially for program synthesis.

I'd be happy to talk again after your thesis!

> I hope I don't misunderstand what you mean by relational programming. I think you mean pure logic programming, _not_ like implemented in Prolog, but as it's described, say, in Lloyd?

Correct. In particular, I mean logic programming in a system with the following properties:

1) sound unification

2) complete search

3) all predicates work in all-modes, all the time

4) [optional, but extremely useful] additional relational constraints--such as disequality constraints--that work in all modes, support limited forms of negation, and can express some otherwise infinite sets of constraints finitely

> In general, I find myself resorting to using impure features when I can't find an efficient way to write a program without them. For instance, sometimes I want to use random access data structures, over linked lists (so, Prolog "terms" with setarg/3 arg/3, rather than list traversal). Othertimes it's just so much easier to bang together a findall/3 with an arg/3 counter, than write yet another recursive skeleton with 4 accumulators- and an interface predicate to hide them.

I, too, have played in the muddy world of impure-but-convenient / not-quite-logic programming. This world is similar in spirit to almost-functional-programming, with the ocassional mutation and unconstrained effect thrown in. Mutation is powerful and useful. Unconstrained effects are powerful and useful.

On the other hand, even a single use of these features can destroy a host of program invariants that could be used for reasoning, analysis, or optimization. Or for running programs "backwards." Or for semantics-guided synthesis...

The lesson I hope Prolog programmers will take from miniKanren is that they are giving up something very powerful when using these extra-logical operators, in these operators destroy the ability to soundly run predicates in all modes, and that sophisticated all-modes relations can perform computations that would be difficult to express in other ways.

> To be honest, a purely declarative language that took those impure but convenient hacks away would take me some time to get used to. I don't know that I want to give those conveniences up.

These features are very difficult to give up, similar to the way mutation and uncontrolled effects are difficult to give up when writing programs in a lazy functional language. There is no doubt that it requires a total change in programming style, giving up convenient and powerful idioms, and often having to rethink approaches to efficiency.

I remember the first time I heard about functional programming. After programming for 20 years, I had to re-learn the notion of 'variable'. (Just like I had to re-learn the notion of 'variable' when I learned logic programming.)

This is the main reason I think Prolog isn't suitable for relational (pure logic) programming. The language design, compilers, libraries, the WAM, books and tutorials, research papers, publicly available code, etc., assume non-relationality by default. If you want to program purely in Prolog, you have to know which parts of the language to avoid (almost everything!) and which libraries to avoid (most of them, as far as I can tell), in addition to knowing exactly which combination of optional features to use to enable relational programming. You won't find this described in any Prolog book or tutorial that I have seen, beyond the famous append` example, so you are on your own to develop a style of programming that is at odds with the ecosystem in which you work. It's the same feeling I get whenever I try to write purely functional code in a language in which mutation is the default, and in which almost all libraries use mutation.

Relational programming requires a different point of view, which is usually at odds with standard Prolog practice.

> They're there for a reason- a tradeoff of purity for efficiency and usability. I, personally, find that tradeoff balanced and while I'm not against going the other way (sacrificing efficiency and ease of use for purity), as a research goal, I'm not going to go out of my way to try and achieve that.

I agree--it's all tradeoffs! And I agree that it is such a different way of programming, with a totally different set of idioms, advantages and disadvantages, performance issues, etc., that you would have to go far out of your way to program in the purely relational style. And, of course, programming relationally may provide little or no benefit for what you want to accomplish.

[YeGoblynQueenne]

>> 3) all predicates work in all-modes, all the time

I think this is the feature that is the most sorely missed in Prolog programming and as you say it is possible to have it, but only if one is prepared to jump through no end of hoops. Sometimes it's just not possbile with any reasonable amount of effort and any sensible amount of coding. This feature is also the one most characteristic of relations, rather than functions, or the demi-functions that Prolog predicate definitions end up as (i.e. with more or less standard inputs and outputs, a.k.a. modes).

I think I detect a hint of frustration in your comment, perhaps after one too many encounter with recalcitrant Prolog programmers, unwilling to give up their convenient hacks :)

Well, these days I can wear another hat, that of the ILP researcher, and there is an interesting use of modes in ILP: they are often used to reduce the size of the hypothesis search space. Because, of course, the hypothesis space for the program append(+,+,-) is much smaller than the hypothesis space for the program append(?,?,?)! Aleph, probably the best-known ILP system of all time (and its ancestor, Progol) has a special syntax of "mode declarations" to determine input and output modes, for this reason.

Interestingly, the more recent approach (attention: I'm about to talk about my PhD work :) of Meta-Interpretive Learning (MIL), does away with specific modes and Aleph and Progol's (and many other systems') mode declarations. Instead, MIL encodes inductive bias by means of second-order datalog clauses, the "metarules" (e.g. ∃P,Q,R,X ∀x,y,z: P(x,y) ← Q(x,z), R(z,y,X) is a metarule with second-order variables P,Q,R existentially quantified over the set of predicates, first-order variable X existentially quantified over the set of constants and first-order variables x,y,z universally quantified over constants). Metarules do not specify input and output modes -they are, after all, datalog. This would normally blow up the hypothesis space to unsearchable proportions, but this is managed in various ways- and an actual search of the hypothesis space (i.e. the set of sets of clauses) can be avoided alltogether, for a polynomial time learning approach.

But I digress. What I mean to say is that this theoretically mode-free learning has so far only been implementedin Prolog [1][2][3] or ASP [4]. ASP is purely declarative, but incomplete in its own way (because the Herbrand base must be fully ground, which is impossible to do for infinite Herbrand bases) and Prolog has- the mode problem we discussed. So while we have a powerful learning approach, with a nice theoretical basis, in practice we implement it in a less than satisfying manner, always. And, I dare say I've seen the result in annoying "edge cases". So, after our discussion, I wonder if a minikanren implementation of MIL would overcome the limitations of the Prolog and ASP implementations - even at the cost of expensive occurs-checks etc. I mean, at least if one gives up efficiency, there should be an equally important reward, and an in-practice realisation of the in-principle soundness and completeness of the approach would probably be that. In my opinion anyway. At the very least it's a more compelling reason to re-implement a system in a new language than "well, it's an implementation in a new language".

Food for thought, post-thesis :)

____________

[1] Metagol:

https://github.com/metagol/metagol

(Try to ignore the scary header)

[2] Thelma:

https://github.com/stassa/thelma

[3] Louise:

https://github.com/stassa/louise

[4] Hexmil:

https://arxiv.org/abs/1805.00068