The thing about the cut is that it makes debugging extremely difficult because it (nearly always) completely nullifies the usual semantics of how you expect predicates to work. Stuff will seem to work and then break in mysterious ways. Also I've personally never found a valid use for them, there always seems to be a better, more logical alternative for any potential use case I've found.

It's kind of unfortunate IMO that most oldskool Prolog code out there is peppered with cuts and (->)/2 since it propagates a ton of bad habits.

Regarding the RLE problem, I posted a logical solution without cuts: https://news.ycombinator.com/item?id=35632344

I don't remember having any problems with debugging programs with cuts. But it should be said that I restrict myself to green cuts [1]. There are usual ways to avoid those, but not without making the code more complicated than it needs to be.

Debugging soft cuts is more of a problem. That's because soft cuts don't appear in the tracer and it's difficult to follow program flow when it doesn't directly correspond with the source code as-written. Or at least that's the way the tracer behaves in SWI-Prolog which I use almost exclusively these days (plus Visual Prolog, but let's not talk about that). There may be a setting to configure it. I generally don't use soft cuts, I find them a bit clutter-y anyway.

There's a run-length encoding program in the "99 Prolog problems" and it also doesn't use cuts:

https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/pro...

_______________

[1] A "green cut" is one that does not change the program's Least Herbrand Model (LHM). Or, in plain English, a green cut does not change the set of queries to the program, that succeed. A "red cut" is one that does change the program's LHM. A green cut only stops unproductive backtracking, or backtracking that diverts a proof down infinite branches. A red cut is one that cuts finite success branches. You should never use red cuts, and you should never run on a barge :P

> There's a run-length encoding program in the "99 Prolog problems" and it also doesn't use cuts

I tested them. p10, p11 and p13 all infloop when you ask what encodes to [[3,7], [2,8], {what 9 encoded to}]. p12 claims that [7,7,7,8,8,9] and [7,7,7,8,8,[9,1]] are valid encodings for [7,7,7,8,8,9] and then gives "Arguments are not sufficiently instantiated".

As I implied in my original comment, there are plenty of examples out there, none of which actually work in both directions, without metaprogramming. Using clpfd seems to work well in all directions, which is neat, but that's a solver built atop prolog, rather than prolog itself.

Right, that's interesting. Did you try tabling the looping program? That's one way to avoid (some) looping behaviour.

Note that p10 - p13 are meant to be called in mode (+,?) according to their comments, so (-,+) (or (-,?)!) is asking for trouble. I can see you were looking for a program that would run in arbitrary mode that is also non- or semi-deterministic ("gives one answer". Did you mean more like functional?) but I replied to another comment just to point to existing RLE programs, not to give examples of what you were asking.

The instantiation error is the kind of thing that you'd use a "green" cut to avoid. The cut in that case would avoid unnecessary backtracking and not change the results of the program.

I don't know about the malformed result. I'd have to pick at it a bit and I don't want to do this now. I also don't want to try and write a "pure" version, first because I don't think it satisfies any real-world need, and second because I already have a version that seems to work OK and uses cuts. I wrote it several years ago (possibly around 2010 ish). I'm copying it here keeping the idiosyncracies of my coding and commenting style at the time.

  %!   run_length_encoding(+List, -Run_length_encoding) is det.
  %
  %    Run_length_encoding is a list of all key-value pairs where each
  %    key is an element in List and value the number of consecutive
  %    repetitions of that element up to the first differing element.
  %    
  %    For example:
  %    ==
  %      ?- run_length_encoding([a,a,a,b,b,b,b,b,b,c,c,c,a,a,f], RLE).
  %    RLE = [a-3, b-6, c-3, a-2, f-1].
  %    ==
  %
  run_length_encoding([], []-0):- !.
  run_length_encoding([H|List], Run_length_encoding):-
          run_length_encoding(List, [H-1], Run_length_encoding).
  
  % Last element in input list or single-element input list.
  run_length_encoding([], [C-F|Fs], Run_length_encoding):-
          reverse([C-F|Fs], Run_length_encoding).
  % Run of N consecutive identical elements
  run_length_encoding([C|Cs],[C-F|Fs], Acc):-
          ! % Orange ish; backtracking will produce successive
          % counts of repetitions of C from different indices in the list
          % I think.
          ,F_ is F + 1
  ,run_length_encoding(Cs, [C-F_| Fs], Acc).
  % End of run of N consecutive identical elements.
  run_length_encoding([C|Cs], Fs, Acc):-
          run_length_encoding(Cs,[C-1|Fs], Acc).

I give this as an example of a simple, short program you can write in Prolog to accomplish a simple, useful task, while using the cut to make your life easier, which is what I'm arguing about here.

Note the uncertainty I had at the time about the use of the cut in the second auxiliary clause. I've left that comment in, in the interest of being honest about the difficulties in learning how to use the cut correctly. As I say, that was written many years ago. I'm not arguing that it's easy to learn to use the cut, I'm just saying that it makes your life easier once you've learned how to use it. I should probably have made that more clear in my comment.

Please let me know if my code above breaks. I haven't tested it in ages. But please respect the documented call modes and determinism :)

Edit: if you're wondering about the use of reverse/2, the goal is to simplify debugging; if you put accumulators in the head, you don't see their instantiations until recursion unrolls, so you don't know what's going on.

Edit 2: To further clarify, as documented, the program only runs in one mode, (+,-). It was an auxiliary for another program that calculates the Shannon entropy of a string (tokenised as a list of characters) so there was no need for other modes. Not every Prolog program needs to run in all possible modes. And even when one does, it's often simpler to write multiple auxiliaries for additional modes. And why not do the simpler thing, when you can? The point is to write programs that have the desired behaviour. The constant complaint about Prolog (in this discussion also) is that it makes it hard to do simple things, not that it doesn't look pretty. So we should talk about how easy it is to do simple things, not how hard it is to write pretty programs.

Yeah, my "gives one answer" was an incredibly misleading phrasing - I meant the encoding should be greedy and so [7,7,7,8,8,9] should have just the one answer of [[7,3], [8,2], [9,1]] and not also become [[7,2], [7,1], [8,2], [9,1]] or any other variant.

I feel like Prolog is sold by many as being able to solve predicates in both/many directions, with all the grandfather/ancestor/append examples, and my apparent frustration is in trying to use it that way in general and finding that doesn't work and that trying to produce working predicates that do work that way is seemingly impossible (without clpfd or cuts).

My most recent foray into Prolog was in starting with solving the Countdown numbers game (without clpfd or cuts) and then trying to use the predicates from that to answer further questions like what sets of tiles can reach all target numbers or what the highest necessary intermediate result is, or similar. I didn't just fail; I failed to learn anything useful. Getting those answers in a few imperative languages was trivial and educational.

Since then, I've reduced the goal to writing an any-mode rle that can return just correct answers and not infloop, without cuts or meta-programming. Simpler things seem easy enough. Rle seems just complex enough to make it impossible but is still logically trivial.

Your rle definition looks good to me, of course, but I'm not sure I can work out how to usefully compare it to other (+,-) answers. Certainly, I've only been checking for correctness in all modes, including a lack of infloops and a lack of extra answers.

I'd be happy to engage in offline conversation about it, but I'd likely just be yelling at clouds. I am interested in discovering which logic languages can trivially provide an any-mode rle and in working up from there to larger problems. Clearly, from this thread, prolog+clpfd is one.

Here's an implementation using Peano numbers as you mentioned which seems to work the same as the CLP(FD) one for me.

  rle2([], []).
  rle2([H],[[H, add1(zero)]]).
  rle2([H | T], [[H, CountPlus1] | More]) :-
      Count = add1(_),
      CountPlus1 = add1(Count),
      rle2(T, [[H, Count] | More]).
  rle2([H | T], [[H, add1(zero)], [Element, Count] | More]) :-
      Count = add1(_),
      dif(Element, H),
      rle2(T, [[Element, Count] | More]).

  ?- rle2([1,1,1,2,2,3],X), rle2(Y,X).
  X = [[1, add1(add1(add1(zero)))], [2, add1(add1(zero))], [3, add1(zero)]],
  Y = [1, 1, 1, 2, 2, 3] ;
  false.

It even works in the completely general case:

  ?- rle2(X,Y).
  X = Y, Y = [] ;
  X = [_A],
  Y = [[_A, add1(zero)]] ;
  X = [_A, _A],
  Y = [[_A, add1(add1(zero))]] .

As I understand it, Prolog itself is CLP(H), that is CLP over the Herbrand terms (that is, atoms and functors and stuff). CLP(FD) just extends the capability with numbers (FD = finite domains). Although I do sort of understand how you'd consider it not "pure" Prolog, I don't see it as that different especially with things like `dif/2` in Prolog which is a constraint just like any other.

Nice!

>> As I understand it, Prolog itself is CLP(H), that is CLP over the Herbrand terms (that is, atoms and functors and stuff).

That's an interesting way to see it. Quite an unorthodox one, mind. I learned recently that it was Alain Colmerauer, co-creator of Prolog, who also came up with the idea of Constraint Logic Programming, specifically to address Prolog's er difficulties with numbers and arithmetic. See:

https://youtu.be/74Ig_QKndvE?t=1046

I was recently asked a question about the use of Peano notation in some stuff I was working on. I didn't think of it that way at the time, but one big advantage of Peano notation compared to is/2 is that it is... well, in a nutshell it's declarative integer arithmetic, just like CLP(FD). Boy I hate saying jargon-y things like that. But Peano numbers as Prolog terms in predicate's heads can be backtracked-over, and unwound when recursion unwinds, just like you do in your rle2/2 above. The downside is that they get hard to read once they get too big.

Then again, you can easily do this sort of thing:

  %!      peano(?Arabic,?Peano) is nondet.
  %
  %       Convert between Arabic and Peano number notations.
  %
  %       Use this program to quickly convert between Peano notation and
  %       Arabic notation.
  %
  %       Accepted modes are (+,-) and (-,+). In mode (?,?) this predicate
  %       returns only 0 deterministically.
  %
  %       Examples:
  %       ==
  %       ?- peano(1,P).
  %       P = s(0).
  %
  %       ?- peano(I,s(0)).
  %       I = 1.
  %
  %       ?- peano(N,P).
  %       N = P, P = 0.
  %       ==
  %
  peano(N,P):-
          peano(P,0,N).
  
  peano(0,N,N):-
          !.
  peano(s(P),N,Acc):-
          succ(N,N_)
          ,peano(P,N_,Acc).

Expects Peano numbers with the functor "s"!

Runs both ways :P

I see your points - I'll certainly use clpfd more, in future.

Also, I was mistaken - my peano-ish solution worked in both directions, though it had probable performance issues (perhaps because I didn't know `dif/2` was more flexible than `\=`) and then had trouble when I tried to map back from peano to naturals. I used a fun and perhaps misleading form to try for brevity:

  rle([], []).
  rle([X], [[1, X]]).
  rle([X,X|XS], [[N+1,X]|ZS]) :- rle([X|XS], [[N,X]|ZS]).
  rle([X,Y|XS], [[1,X]|ZS]) :- rle([Y|XS], ZS), X\=Y.

And so:

  ?- rle([7,7,7,8,8,9], Y).
  Y = [[1+1+1, 7], [1+1, 8], [1, 9]];
  false.
  ?- rle(X, [[1+1+1, 7], [1+1, 8], [1, 9]]).
  X = [7, 7, 7, 8, 8, 9];
  false.

Edit: If one cared for safety/compatibility, each [1, X] would be [0+1, X].

>> I feel like Prolog is sold by many as being able to solve predicates in both/many directions, with all the grandfather/ancestor/append examples, and my apparent frustration is in trying to use it that way in general and finding that doesn't work and that trying to produce working predicates that do work that way is seemingly impossible (without clpfd or cuts).

You're not wrong about that and it's not your fault, or any misunderstanding. Certainly Prolog has been "sold" this way, by some. I can't name those "some" because I'm not sure who they are exactly (although I have a few specific people in mind). I don't think it's something that's made a big issue of in the usually recommended textbooks (Clocksin and Mellish, Sterling and Shapiro, O'Keefe, Bratko) but I can't be sure.

Obviously, you can run some programs in multiple modes, in Prolog. You can't always write every program to be all-modes. Pretending that it's possible to do so is overselling the language. What's more it's trying to sell a nice feature, as a defining feature. The idea I think is that First-Order Logic predicates are relations and so should not have "inputs" and "outputs". But Prolog predicates are not FOL predicates. If they were, they'd be simultaneously capable of being run in all modes, and less expressive than they are now (because Prolog is higher-order, as I say in other comments, trying not to sound like a dangerous loon).

I think this is the age-old debate about purity and formal rigour in Prolog, that has never done the language any good. There has always been a part of the Prolog community who wanted Prolog to be some kind of pure and perfect jewel, that should remain untouched from the real world. There's always been another part, who wanted to treat Prolog as a programming language to do real work with. I get the feeling that the latter, more practically-minded, folks have slowly weeded themselves out and now the majority of those who remain are of the "purist" camp. Entirely coincidentally, the number of people picking up Prolog has also constantly dwindled.

Entirely coincidentally.

You can probably tell which camp I'm on. Actually, I'm not. I got a foot in each. I serve two masters and all that. I just want to know that things work, that's my schtick. Sometimes you need formal rigor, sometimes you just need to bodge some codes together. And use the cut :P

>> I'd be happy to engage in offline conversation about it, but I'd likely just be yelling at clouds. I am interested in discovering which logic languages can trivially provide an any-mode rle and in working up from there to larger problems. Clearly, from this thread, prolog+clpfd is one.

You're welcome to get in touch:

  eIA!patsantzis17CTHULHUimperialIA!acIA!uk

But first open vim and praise Cthulhu:

  s/IA!/./g
  s/CTHULHU/@/g

If you're not trying to make your programs as close to logic as possible (that is, support as many modes as possible and make it so you can model your program as a logical expression) then what's even the point of using Prolog? Settling for having to reimplement the same logic in multiple directions completely defeats the purpose, you're just writing imperative code at that point.

I think "pragmatic therefore non-logical" versus "ivory tower therefore useless" is a false dichotomy. In my experience it's nearly impossible to make green cuts, and once you know a few tricks and rules of thumb, you can get pretty far writing logical code.

Support of as many modes as possible is an aim that is often too ambitious. Instead, unsupported modes should be indicated with an instantiation error or (much rarer) an uninstantiation_error. In this manner the logic remains intact as long as no error occurs and the program does not loop. And yes, this may come at the expense of its usefulness, think of (is)/2.

YeGoblynQueenne omitted what the mode +,- actually means. And the program does not check it. Does it mean that the first argument must be ground or is it OK, to leave some variables inside? Think of `[a,f(X),b]`. Also the - has sometimes the meaning of being descriptive (that is a completely steadfast argument) or prescriptive (meaning that the program may be incorrect if the argument is not an unaliased variable). Would errors be used for the unintended cases things would be much clearer.

Good points and I have to hang my head in shame. Prolog doesn't enforce mode declarations in documentation and I don't either, most of the time, in my code. I also use modes imprecisely and never define them, before I use them, in my documentation, which if anyone ever looks at my code and tries to run it, would create confusion.

For instance, I use "-" to indicate both a term that's an unbound variable on entry and one that can be partially instantiated on entry. Obviously that will cover different behaviour in different programs. That's not very nice of me. At least, since I've been bitten many times myself by this I try to document the structure of arguments and to give an example or two of calling in different modes, when that is not too hard to do.

I've been complimented many times about the good documentation of my projects, but I feel so embarrassed when people do that. My documentation sucks. It's worse to have half-done documentation than to have no documentation at all :(

Explicit checking of the appropriate instantiations is something for more or less official interfaces, not for every internal predicate. For those official checking via must_be/2, can_be/2 and the library(si) (all in Scryer) is often all you need. (The SWI-version conflates must_be/2 and can_be/2).

But you could save your beloved cut with minimal effort by using dif_si/2 (voir https://stackoverflow.com/a/20238931/772868) just before the cut. In this manner you would get instantiation errors for exactly the cases you cannot handle.

>> Explicit checking of the appropriate instantiations is something for more or less official interfaces, not for every internal predicate.

But there's no formal concept of "interface" in Prolog, and the module system sucks (or doesn't exist, depending on implementation) and many programs don't ever use it anyway, so instantiations errors are a possible issue at every level of a program. For me at least it's a constant headache knowning how a predicate must be called (hence my practice of documenting the structure of inputs and outputs carefully).

I really don't like the ad-hoc "type" checking in Prolog (as in integer/1 etc). Prolog doesn't have types, because pre-Church logic doesn't have types (and post-Church logic is a mess; typed mess, but still a mess). And yet Prolog terms (in the sense of a functor followed by comma-separated terms in parentheses) are implicitly typed, under unification: T is the type of all terms that unify with T. So making sure that terms are correctly instantiated is the most prudent thing to do when checking the "type" of a term. Unfortunately that adds too much clutter and I personally resent havng to do it. I have seen various attempts to solve that conundrum over the years, for example there's a package for SWI-Prolog that adds Hindley-Milner type checking (brrr). I don't like any of them.

It's a bit weird how that is the kind of thing that Prolog gets wrong that I rarely hear as an actual criticism, as opposed to complaints about the cut, or the imperfect declarative-ness.

I guess all this would be solved in practice by the addition of a static type system, checked at compile time, which would completely change the language of course. Incidentally, I'm currently working on an ancient (30 years old) Visual Prolog project; Visual Prolog is exactly that, a compiled Prolog with a static type system. I feel that while it sure helps catch some errors, it contrives to suck all the energy and life out of Prolog. Prolog is like parcour: it lets you fly around town, jumping and rolling like Spiderman. So sometimes you get a lamppost en plein dans la figure. So what. Who needs type safety anyway?

(She says while changing yet another bloody bandage)

>> But you could save your beloved cut with minimal effort by using dif_si/2 (voir https://stackoverflow.com/a/20238931/772868) just before the cut. In this manner you would get instantiation errors for exactly the cases you cannot handle.

Thanks for the pointer. I had a quick look. I think there's something similar in SWI-Prolog's Picat-style matching with the "=>" operator that is an alternative to ":-". I'm not sure exactly what it does (something about "steadfastness", that you also mentioned, and that is a new term for me) but I prefer to not use libraries that significantly change standard Prolog syntax, for fear of backwards compatibility.

> But there's no formal concept of "interface" in Prolog

Any predicate you write for someone else has an interface. Someone else includes you in a couple of weeks. All predicates that are not truly auxiliary ones which are more like basic blocks of command oriented programming languages - COPLs.

> instantiations errors are a possible issue at every level of a program

That is not the worst that can happen. Nor is non-termination the worst. The worst is if an unexpected failure or success happens that looks like a legitimate answer. However, for many, non-termination is seen as being worse than such real errors. The reason is that there are only very few Prolog systems that reliably catch resource errors or have reliable timeouts. Well, to be true, there is one system. And the others most often abort.

> (hence my practice of documenting the structure of inputs and outputs carefully).

> I really don't like the ad-hoc "type" checking in Prolog (as in integer/1 etc).

integer/1 is one of the orignal sins of DEC10 which remplaced the errors of Prolog I by silent failure. And everybody then followed suit. Mindlessly. There is library(si) that offers integer_si/1 to make things much cleaner.

As for your remarks on type systems for Prolog, one feature they do not provide is a dynamic conversion between regular Prolog and the typed part. There was an attempt some time ago but unfortunately the individual left for FP.

> Who needs type safety anyway?

It seems there are two different objectives: type safety and instantiation safety. Both are often confounded.

> SWI-Prolog's Picat-style matching with the "=>" operator that is an > alternative to ":-".

This approach does not distinguish between instantiation and type errors. Take the sum_list/2 from https://www.swi-prolog.org/pldoc/man?section=ssu

   ?- sum_list(1, N).
      existence_error(matching_rule, sum_list(1, 0, _A)).
   ?- sum_list(L, N).
      existence_error(matching_rule, sum_list(_A, 0, _B)).

And then when adding the suggested catchall rule, both fail. Both. This throws us back by almost half a century. So now DEC10-style errors get into the 21st century. Prolog 0 and Prolog I were better.

   ?- sum_list(1, N).
      false.
   ?- sum_list(L, N).
      false, unexpected.

> "steadfastness", that you also mentioned, and that is a new term for me

Since 1987-09-29 in common use, see the Prolog Digest of that date, posting by Richard O'Keefe. Here is my definition: an argument Ai is steadfast w.r.t. a goal g(A1,..Ai,..AN), when executing this goal is equivalent (complete operationally) to, g(A1,..CAi,..AN), CAi = Ai with CAi a fresh new variable. And more generally an argument Ai is steadfast, if this property holds for all goals.

A good example of a steadfast argument is the second argument of append/3. You can replace any goal append(Xs, Ys, Zs) by append(Xs, CYs, Zs), CYs = Ys without observable effect (except efficiency, resource consumption and the like). But even non-termination is preserved! Another one is the 3rd argument of phrase/3.

Or take your run_length_encoding/2/3, where the second argument is steadfast. You (presumably on purpose) accumulated in the second argument all the elements only to reverse them finally in a highly lispeling manner. At least no destructive nreverse.

>> That is not the worst that can happen. Nor is non-termination the worst. The worst is if an unexpected failure or success happens that looks like a legitimate answer. However, for many, non-termination is seen as being worse than such real errors. The reason is that there are only very few Prolog systems that reliably catch resource errors or have reliable timeouts. Well, to be true, there is one system. And the others most often abort.

Yes, those "right for the wrong reasons" results are a bad problem, too.

Which system are you referring to? I mainly use SWI-Prolog and in my experience it does exit with error when the stack size limit is exceeded, and it will even give you a message about possible unbounded recursion. Although on my Windows machine it then often crashes immediately after because it's left with no memory to recover from the error. I normally don't try-catch such errors because they're most of the time a sign of programming error (a well-written program should go into an infinite recursion without blowing the stack).

I've had more mixed experience with SWI-Prolog's resource-limited call/1 variants, like call_with_time_limit/2 and call_with_depth_limit/3 and call_with_inference_limit/3. The first one seems to work OK. The other two are a bit hit-and-miss, although there's warnings about that in the documentation if I remember correctly.

>> Or take your run_length_encoding/2/3, where the second argument is steadfast. You (presumably on purpose) accumulated in the second argument all the elements only to reverse them finally in a highly lispeling manner. At least no destructive nreverse.

Oh, is that lisp-y style? I had no idea. I use it because it makes tracing the program easier. There's a bit of overhead, but I feel it's made up for in spades by the ability to debug errors. If you put an accumulator variable in the head of the goal, it is only bound when the recursion terminates and the stack "unrolls", so you don't get to see the bindings of the accumulator and it's harder to verify the logic of the program. I normally trace with the "unify" port non-leashed but I don't think that changes anything.

>> A good example of a steadfast argument is the second argument of append/3. You can replace any goal append(Xs, Ys, Zs) by append(Xs, CYs, Zs), CYs = Ys without observable effect (except efficiency, resource consumption and the like). But even non-termination is preserved! Another one is the 3rd argument of phrase/3.

Thanks, this is a clear explanation. To be honest, I don't stay up-to-date with discussions about Prolog programming, as I did in the past. Even in the discussions that I've followed there's a lot that turns around principles that don't mean anything to me (as I said in another comment, I really can't be bothered about declarative, vs non-declarative programming, for example) and so I'm a bit suspicious of jargon that seems to be pointing to such principles. Maybe steadfastness is a more practical consideration. I'll have to think about it.

> Which system are you referring to?

SICStus. The best for catching resource errors (that is with catch/3) and continues thereafter happily. SWI does catch many situations, but as you observe it is much less reliable. SICStus is also best for timeouts. I have not tested SWI recently, only noted that the compatibility library(timeout) has been updated. The call_with_inference_limit/3 might be interesting. The others you mention have just bad interfaces. But what both systems lack is a reproducible notion of time on a lower level. Walltime is not useful, as it is load dependent, CPU-time depends on TLBs, caches and all that. Think of number of (completed) CPU-instructions. PAPI-wise. While there is some JIT-tering in both systems this is still the best. Anyway, I start daydreaming...

> they're most of the time a sign of programming error

Often yes, but then you need to explain such errors which incurs a lot of attempts to execute fragments of the looping program. Like with a failure-slice https://stackoverflow.com/tags/failure-slice

And then, there is another kind of programs that effectively do not terminate but are still useful. Those that try to find counterexamples (posh expression for bugs).

> Oh, is that lisp-y style?

Recursive functions a la (cons x (recursive ...)) are not tail recursive (or at least have been not in the 1970s), whereas the corresponding code in Prolog is. So they were often transformed with an auxiliary argument that collected all conses in the wrong direction and were nreverse-d thereafter since (ideally) noone else referred to that list. I believe this has been solved in the meantime.

And yes, with a step-by-step tracer, this style makes things easier to watch. OTOH, you could use purer methods for debugging (for the pure part of your programs). At least, when you are into constraints, the tracers are of no use any longer and you have to switch.

>> I think "pragmatic therefore non-logical" versus "ivory tower therefore useless" is a false dichotomy. In my experience it's nearly impossible to make green cuts, and once you know a few tricks and rules of thumb, you can get pretty far writing logical code.

I don't agree that it's hard to make green cuts. The standard ones are, in recursive programs, one in the terminating condition of a recursive program and one in every recursive clause after the last. Ideally those should be placed immediately after the goal in the relevant clause acting as a "test" to select the clause, as advised by Covington et al (https://www.covingtoninnovations.com/mc/plcoding.pdf; much sensible advise on using the cut there, too).

Those cuts are "green" as a rule (there will be exceptions) in that they avoid unnecessary backtracking after a condition is met for selecting the clause. But of course those cuts can be misused to hide a programming error. That is something the programmer must learn to avoid, but I really don't see that as an insurmountable obstacle. To come back to Covington et al:

5.5 Never add a cut to correct an unknown problem

A common type of Prolog programing error is manifested in a predicate that yields the right result on the first try but goes wrong upon backtracking. Rather than add a cut to eliminate the backtracking, investigate what went wrong with the logic. There is a real risk that if the problem is cured by adding the cut, the cut will be far away from the actual error (even in a different predicate), which will remain present to cause other problems later.

And btw, "pragmatic" doesn't have to be "non-logical". I'm not arguing about that. I'm claiming that the purity of FOL is unreachable in the real world and concessions have to be made. At the end of the day, sloppy coding is sloppy coding, whether it's pragmatic, or pure, or declarative, or whatever and I'm definitely not advocating for writing code in any old way.

What's the point of using Prolog? I like it.

I mean, I don't have any rational reasons. I could try to find some but I'd just be rationalising. The things that most people consider advantages or disadvantages, I couldn't care less about. Take declarativeness for example- writing declarative code is just not something I care deeply about. Nor is being able to run code both ways. I don't care about that stuff. I just like writing my code in Prolog [1].

Of course, if you do care about being able to code declaratively, or logically, then Prolog is your best chance. Prolog is maybe 90% purely declarative. You can write your programs so they run in all modes easily maybe 60% of the time. Try getting anywhere close to either of that in any other language. The reason people oversell Prolog with "you can run your code backwards" is that you can do that at all in Prolog, but not in other languages.

As to "make your programs as close to logic as possible" - well, you can't. Logic is not a programming paradigm. Logic programming is. FOL says nothing about programs. Logic programming does. FOL doesn't even say anything about proofs. That's how logic works: you have your clean and tidy syntax rules and everything else is semantics.

Now, Logic Programming, that's a semantics for FOL on computers. Like I say in another comment, logic programming begins and ends with Robinson's Resolution principle [2]. That's the theory of logic programming, or in any case Resolution-based logic programming (hi ASP folks!). Prolog is an implementation of Resolution. The implementation is not perfect, but I'm fine with that, as long as I know I can count on the theory to be well-formed. If the theory is good, the implementation can do whatever it likes. At some point, if there is a real need, someone will come up with a better one. So far, I don't see anyone making a better Resolution implementation than Prolog. So I don't think it's needed. I think Prolog is just fine the way it is.

_________

[1] Not just Prolog, of course. Then again, last time I had to write a substantial bit of Python I found, to my horror, that I have turned to the proverbial FORTRAN programmer who can write FORTRAN in any language; except s/FORTRAN/Prolog/g. By which I mean my Python code looked just like my Prolog code. I may have lost the ability to write anything but Prolog, after writing almost all my stuff in Prolog for the last five years or so. Well at least it didn't happen with R...

[2] I know that is a disservice to all the people who worked on automated theorem proving and logic programming before and after Robinson, but I'm going through a bit of a phase where I am in awe of what Robinson achieved, and I think of him as the god of logic programming, more or less. I'll get over it.

For one, the second argument should be (upon success at least) a list. But in your program it isn't a list for `[]`.

Are you talking about this?

  run_length_encoding([], []-0):- !.

Yeah, well spotted, that looks stupid. Who knows what I was thinking...

(It takes some time here, before the reply link appears)

While I do not know what you were thinking either, I do know that you insisted on a mode +,- and thus refrained from using the most general query to test your program just in case. Prolog would have shown you the problem right in the first answer!

    ?- run_length_encoding(L,E).
       L = [], E = []-0, unexpected
    ;  ... .

While the most general query often leads to an unfair enumeration of answers/solutions, it is still a useful and effortless way to test a program, just in case.

>> (It takes some time here, before the reply link appears)

Yes, I think that happens when threads exceed a certain size, perhaps also when replies come at a certain rate. I believe it's a measure put in place to cool down hot heads revving up to a flame war, or something like that.

Or maybe it's just a measure put in place to avoid people kicking a programmer for an error she made in decades-old code >:P

(Thanks for the advice though, it's good advice and useful for programmers at any stage of their evolution).

P.S. I kept thinking of what you said that Kowalski said regarding Colmerauer's knowledge of meta-interpreters. I'm really curious to know and there's a couple other questions I have he might be interested in answering so I plan to write him an email and point him to your comment (https://news.ycombinator.com/item?id=34243808).

(It seems one needs to go into a post directly to be able to reply more rapidly. The delay seems to be reserved for the thread-mode.)

Before sending an e-mail, check https://www.softwarepreservation.org/projects/prolog/ there are so many original sources now online that help to reconsider some perceptions. In particular, the Prolog I manual is there, but in a very bad shape (bad scan from a used up chain printer, probably a 3203, all caps, no accents ...).

>> (It seems one needs to go into a post directly to be able to reply more rapidly. The delay seems to be reserved for the thread-mode.)

Oh, right, good catch!

That's an amazing resource you linked me to. Thanks!

On the other hand, it's such an awful feeling some times that all the activity of the early years of logic programming has died out, that I've come to it too late, and that so many of the people who created the field are now retired or gone.

> ... all the activity of the early years of logic programming has died out, ...

Of course, now there is activity of the current years! What else could we have now? If you look back, there was not only progress but also quite a lot of regress. Like, dif/2 in Prolog 0, then to stay submerged for so long, resurfacing in Prolog II and Mu etc. Errors in Prolog I, then abolished in DEC10 at the expense of incorrectness, only to resurface later on, but still not entirely recovered...

Btw, the reason I want to write to Kowalski is not just the history of meta-interpreters. There's a question that only he may be able to answer. The question is about the Subsumption Theorem in Inductive Logic Programming (ILP).

Briefly stated, the Subsumption Theorem, as it's known today, is that a clause D is entailed by a logic program S if there exists a clause C that can be derived from S and such that C subsumes D.

Similar statements are also found in the logic programming literature, for example in Lloyd's Foundations of Logic Programming.

There's a bit of a mystery about the origins of the Theorem.

A series of similar papers by Ninenhuys-Cheng and de Wolf point out different definitions and apparent rediscoveries of the Theorem, and proofs of it, some of them mistaken, in the ILP literature. The paper I use as my reference is titled The Subsumption Theorem in Inductive Logic Programming: Facts and Fallacies. (http://homepages.cwi.nl/~rdewolf/publ/ilp/ilp95.pdf found in Ronald de Wold's webpage, here: https://homepages.cwi.nl/~rdewolf/).

That paper claims that the Theorem was probably first stated by R. C. T. Lee, in his 1967 doctoral thesis. It seems this information comes from Kowalski, in a paper that I can't access fully (cited in the Nienhuys-Cheng and de Wolf paper). However, the earliest statement, and proof, of a Subsumption Theorem that I could find is from Robinson's resolution paper, published in 1965, where subsumption is also defined. The Subsumption Theorem in Robinson's paper is slightly different than the one found in the ILP literature, in fact it looks to me like the modern version of the Subsumption Theorem is a corrolary of Robinson's one.

If I were to rephrase Robinson's Subsumption Theorem in more modern terms, what it says it as follows:

[Restated Subsumption Theorem] Let S be a finite set of clauses and C ≠ D be two clauses that are not in S and such that C ≼ D (C subsumes D). Then, S ∪ {C,D} is satisfiable if and only if S ∪ {C} is satisfiable.

So this statement is missing the explicit requirement for derivation of C from S, but if S ∪ {C} is satisfiable then C should be derivable from S by Resolution.

Now, R. C. T. Lee's thesis is not available anymore, it seems, and it wasn't available to Nienhuys-Cheng and de Wolf, either, so there's a lot of uncertainty around what, exactly, Lee stated and proved, and how it is similar or different to Robinson's Subsumption Theorem, and to subsequent statements of the Subsumption Theorem in ILP. Kowalski may be able to clarify the confusion.

I'm posting this in the very slim chance that you might have some intuition about all this, in which case I'd be grateful to hear it.

The sibling comment has a good general answer. In this particular case, if you use cut, it seems like it works, but then you try to solve rle([9,9,A,B,8,7], [[9,X], [8,Y], [7,1]]) or other bidirectional things and you find the cuts prevent you from finding some answers. Generally, I find that cuts (and implication and such) are prone to only work in the specific cases the programmer considered and to cause missed solutions, elsewhere.

Like I say above, that's the difference between using a green cut vs. a red cut. See also my link to the RLE version in "99 Prolog Problems". So far it's been my experience that it's very hard to find a Prolog program that can't be written without a cut.