Why did Prolog lose steam? (2010)

Re:Why did Prolog lose steam? (2010) by superdisk on Friday April 21, 2023 @05:12PM (#35660251)

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.

[ Parent | on HN ]

Re:Why did Prolog lose steam? (2010) by YeGoblynQueenne on Saturday April 22, 2023 @05:25AM (#35664752)

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

[ Parent | on HN ]

Re:Why did Prolog lose steam? (2010) by ghusbands on Saturday April 22, 2023 @08:43AM (#35666056)

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].

[ Parent | on HN ]