logoalt Hacker News

doorhammer • today at 4:07 AM • 1 reply • view on HN

> Red cuts change the set of answers found by a query, green cuts don't.

Ohhh, interesting. So a green cut is basically what I described as cutting branches you know are a waste of time, and red cuts are the ones where you're wrong and cut real solutions?

> At first, don't use the cut, until you know what you're doing, is I think the best advice to give to beginner Prolog programmers. And to advanced ones sometimes. I've seen things...

Yeah, I'm wondering how much of this is almost social or use-case in nature?

E.g., I'm experimenting with Prolog strictly as a logic language and I experiment with (at a really novice level) things like program synthesis or model-to-model transformations to emulate macro systems that flow kind of how JetBrains MPS handles similar things. I'm basically just trying to bend and flex bidirectional pure relations (I'm probably conflating fp terms here) because it's just sort of fun to me, yeah?

So cut _feels_ like something I'd only use if I were optimizing and largely just as something I'd never use because for my specific goals, it'd be kind of antithetical--and also I'm not an expert so it scares me. Basically I'm using it strictly because of the logic angle, and cut doesn't feel like a bad thing, but it feels like something I wouldn't use unless I created a situation where I needed it to get solutions faster or something--again, naively anyway.

Whereas if I were using Prolog as a daily GP language to actually get stuff done, which I know it's capable of, it makes a lot of sense to me to see cut and `break` as similar constructs for breaking out of a branch of computation that you know doesn't actually go anywhere?

I'm mostly spit-balling here and could be off base. Very much appreciate the response, either way.

Replies

YeGoblynQueenne • today at 2:00 PM

>> So a green cut is basically what I described as cutting branches you know are a waste of time, and red cuts are the ones where you're wrong and cut real solutions?

Basically, yes, except it's not necessarily "wrong", just dangerous because it's tempting to use it when you don't really understand what answers you're cutting. So you may end up cutting answers you'd like to see after all. The "red" is supposed to signify danger. Think of it as red stripes, like.

Which make stuff go faster too (well, a little bit). So, yeah, cuts in general help the compiler/interpreter optimise code execution. I however use it much more for its ability to help me control my program. Prolog makes many concessions to efficiency and usability, and the upshot of this is you need to be aware of its idiosyncrasies, the cut being just one of them.

>> Whereas if I were using Prolog as a daily GP language to actually get stuff done, which I know it's capable of, it makes a lot of sense to me to see cut and `break` as similar constructs for breaking out of a branch of computation that you know doesn't actually go anywhere?

Cuts work like breaks sometimes, but not always. To give a clear example of where I always use cuts, there's a skeleton you use when you want to process the elements of a list that looks like this:

  list_processing([], Bind, Bind):-
    !. % <-- Easiest way to not backtrack once the list is empty.

  list_processing([X|Xs], ..., Acc, Bind, ... ):-
     condition(X)
     ,! % Easiest way to not fall over to the last clause.
     ,process_a(X,Y)
    ,list_processing(Xs, ..., [Y|Acc], Bind, ... ).

  list_processing([X|Xs], ..., Acc, Bind, ... ):-
     process_b(X,Y)
    ,list_processing(Xs, ..., [Y|Acc], Bind, ... ).
So, the first cut is a green cut because it doesn't change the set of answers your program will find, because once the list in the first argument is empty, it's empty, there's no more to process. However, Prolog will leave two choice points behind, for each of the other two clauses, because it can't know what you're trying to do, so it can't just stop because it found an empty list.

The second cut is technically a red cut: you'd get more answers if you allowed both process_a and process_b to modify your list's elements, but the point is you don't want that, so you cut as soon as you know you only want process_a. So this is forcing a path down one branch of search, not quite like a break (nor a continue).

You could also get the same behaviour without a cut, by e.g. having a negated condition(X) check in the last clause and also checking that the list is not empty in every other clause (most compilers are smart enough to know that means no more choice points are needed), but, why? All you gain this way is theoretical purity, and more verbose code. I prefer to just cut there and get it done. Others of course disagree.