7 ms·

Just try writing (without hacks/cuts) a run-length encoder that produces only one answer ([9,9,9,8,8,7] -> [[9,3], [8,2], [7,1]]) and works forwards and backwar

Just try writing (without hacks/cuts) a run-length encoder that produces only one answer ([9,9,9,8,8,7] -> [[9,3], [8,2], [7,1]]) and works forwards and backwards and then tell me the execution model is not a limitation. It's the sort of thing where people produce versions that seem to work, but fall into infinite loops or inconsistent extra outputs if you go past the first answer. I'm not sure it's actually possible without meta-programming.

convolvatron 4y ago
I think aggregates help here by allowing you to take one answer, or take the best. But in general absolutely
YeGoblynQueenne 4y ago
>> Just try writing (without hacks/cuts) a run-length encoder that produces only one answer ([9,9,9,8,8,7] -> [[9,3], [8,2], [7,1]]) and works forwards and backwards and then tell me the execution model is not a limitation. But, why not use the cut? It's a feature of the language and it's there exactly so you don't have to bust your head trying to find a way to do things the hard way. I honestly don't understand what's the fuss with the poor cut. If you want an efficient language that runs on a computer then you have to be pragmatic and recognise that concessions have to be made to accommodate the limitations of the hardware. If you want something pure and ideal, then you should probably not be trying to do that on a computer. You should probably not be trying to do it at all. There are no pure formal systems, or if there are, we can't explain or understand them because they can't communicate with the external world (hey, no side effects, OK?). See Haskell, for instance. The article above says something really strange about Haskell, that it: >> ... finally broke through the wall of pure-functional programs being seen as ivory-tower languages that were impractical, or at least really awkward, for any system that needed to do I/O or interact with users Which to me is insane. I think it's talking about monads. Monads, as an escape from the ivory tower, impractical, or at least awkward formalisms of... what, LISP? I mean for the love of dogs. Prolog is a balanced language. People complain about it because it's not unbalanced, that's the problem. If it were 100% declarative and nobody could program anything in it, it would have legions of dotting admirers praising it for its perfection, and whining because they have to do all their work in languages that are hardly 10% declarative, like Rust, or Python or Ruby (and I'm being generous). People have to get their head around this: our computer science is primitive and it is full of holes, dark pits of despair and undecidability, intractability, and terminal inefficiency. To be practical, a language has to give up a little part of its true, pure self, that it could achieve in a perfect world. So Prolog has the cut, and you can use it to control its backtracking, which you need because it's implemented as a depth-first search, because that's efficient and convenient. So use the cut, it's a feature.
- superdisk 4y ago
  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 https://news.ycombinator.com/item?id=35632344
  - YeGoblynQueenne 4y ago
    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/prolog/problemas/ 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
    - ghusbands 4y ago
      > 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.
superdisk 4y ago
:- use_module(library(clpfd)). rle([], []). rle([H],[[H, 1]]). rle([H | T], [[H, CountPlus1] | More]) :- Count #> 0, CountPlus1 #= Count+1, rle(T, [[H, Count] | More]). rle([H | T], [[H, 1], [Element, Count] | More]) :- Count #> 0, dif(Element, H), rle(T, [[Element, Count] | More]). Even though I'm the one who was making the execution model complaint, this implementation seems to work for me. ?- rle([1,1,1,2,3,1,1],X), rle(Y, X). X = [[1, 3], [2, 1], [3, 1], [1, 2]], Y = [1, 1, 1, 2, 3, 1, 1] ; false.
- falsissime 4y ago
  There is a minor impurity in this code: `N = 1+1, rle([a,a],[[a,N]]).` succeeds, yet `rle([a,a],[[a,N]]), N = 1+1` fails. Add `:- op(150, fx, #).` and use it like `#CountPlus1 #= #Count+1` etc.
- ghusbands 4y ago
  I was lumping clpfd under metaprogramming, since it acts like an extra runtime or dsl and you can't use the prolog debugger to make sense of it. I'll readily admit that prolog+clpfd is very powerful; any goalpost-moving on my part is unintentional. I found that using peano numbers got a bit further in plain prolog, but it still eventually infloops in at least one of the directions.

convolvatron 4y ago

I think aggregates help here by allowing you to take one answer, or take the best. But in general absolutely

YeGoblynQueenne 4y ago

>> Just try writing (without hacks/cuts) a run-length encoder that produces only one answer ([9,9,9,8,8,7] -> [[9,3], [8,2], [7,1]]) and works forwards and backwards and then tell me the execution model is not a limitation. But, why not use the cut? It's a feature of the language and it's there exactly so you don't have to bust your head trying to find a way to do things the hard way. I honestly don't understand what's the fuss with the poor cut. If you want an efficient language that runs on a computer then you have to be pragmatic and recognise that concessions have to be made to accommodate the limitations of the hardware. If you want something pure and ideal, then you should probably not be trying to do that on a computer. You should probably not be trying to do it at all. There are no pure formal systems, or if there are, we can't explain or understand them because they can't communicate with the external world (hey, no side effects, OK?). See Haskell, for instance. The article above says something really strange about Haskell, that it: >> ... finally broke through the wall of pure-functional programs being seen as ivory-tower languages that were impractical, or at least really awkward, for any system that needed to do I/O or interact with users Which to me is insane. I think it's talking about monads. Monads, as an escape from the ivory tower, impractical, or at least awkward formalisms of... what, LISP? I mean for the love of dogs. Prolog is a balanced language. People complain about it because it's not unbalanced, that's the problem. If it were 100% declarative and nobody could program anything in it, it would have legions of dotting admirers praising it for its perfection, and whining because they have to do all their work in languages that are hardly 10% declarative, like Rust, or Python or Ruby (and I'm being generous). People have to get their head around this: our computer science is primitive and it is full of holes, dark pits of despair and undecidability, intractability, and terminal inefficiency. To be practical, a language has to give up a little part of its true, pure self, that it could achieve in a perfect world. So Prolog has the cut, and you can use it to control its backtracking, which you need because it's implemented as a depth-first search, because that's efficient and convenient. So use the cut, it's a feature.

superdisk 4y ago
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 https://news.ycombinator.com/item?id=35632344
- YeGoblynQueenne 4y ago
  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/prolog/problemas/ 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
  - ghusbands 4y ago
    > 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.

superdisk 4y ago

:- use_module(library(clpfd)). rle([], []). rle([H],[[H, 1]]). rle([H | T], [[H, CountPlus1] | More]) :- Count #> 0, CountPlus1 #= Count+1, rle(T, [[H, Count] | More]). rle([H | T], [[H, 1], [Element, Count] | More]) :- Count #> 0, dif(Element, H), rle(T, [[Element, Count] | More]). Even though I'm the one who was making the execution model complaint, this implementation seems to work for me. ?- rle([1,1,1,2,3,1,1],X), rle(Y, X). X = [[1, 3], [2, 1], [3, 1], [1, 2]], Y = [1, 1, 1, 2, 3, 1, 1] ; false.

falsissime 4y ago
There is a minor impurity in this code: `N = 1+1, rle([a,a],[[a,N]]).` succeeds, yet `rle([a,a],[[a,N]]), N = 1+1` fails. Add `:- op(150, fx, #).` and use it like `#CountPlus1 #= #Count+1` etc.
ghusbands 4y ago
I was lumping clpfd under metaprogramming, since it acts like an extra runtime or dsl and you can't use the prolog debugger to make sense of it. I'll readily admit that prolog+clpfd is very powerful; any goalpost-moving on my part is unintentional. I found that using peano numbers got a bit further in plain prolog, but it still eventually infloops in at least one of the directions.