5 ms·

> 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

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

YeGoblynQueenne 3y ago
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.
- ghusbands 3y ago
  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.
  - YeGoblynQueenne 3y ago
    >> 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

YeGoblynQueenne 3y ago

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.

ghusbands 3y ago
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.
- YeGoblynQueenne 3y ago
  >> 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