What is up with the cut (!)

Discussion
1

The message by Dan earlier today pushed me down a line of thinking I have visited many times before; this time I got further than ever. Please bear with me.

Hypothesis: the cut (!) was a hack that was so successful that it locked Prolog programmers into a local optimum. It is worth trying to find a Prolog subset or extension that doesn’t need cuts, ever (or at least 99.5% of the time).

Background: Things are better without cuts, everyone agrees, but we keep on using them. They are confusing. “Learn Prolog Now!” decided that the exclamation mark in the title is all they can afford, and do not discuss cuts at all. Both “The Art of Prolog” and “The Craft of Prolog” use a lot of emphasis when trying to explain what the cut does. Well-meaning people on Stackoverflow go into all kinds of acrobatics to avoid the cut or at least hide it very well. There is too much code floating around the internet where cuts lower the perceived subjective quality of the program. Finally, I suspect that once a programmer gets used to using cuts (and understands them well enough) they don’t have the motivation to find a better solution.

NB: by “a better solution” I mean something that is at least as readable, succinct, and efficient as the same code with the explicit cuts.

State-of-the-art: Depending on the situation, we already have a multitude of tools and techniques. In arbitrary order, certainly incomplete, and not properly classified:

  • once/1
  • the conditional ->/2 and the soft cut *->/2
  • in some cases, coroutining as in dif/2
  • (better and consistently improving) clause indexing
  • in some cases, constraint logic programming
  • using “non-defaulty” representation
  • …

Question: If I were to systematically evaluate a large enough code base (Prolog’s standard library?) and classify the uses of cuts inside of it; could that serve as a starting point for figuring out whether a cut-free (99.5%-cut-free, that is) Prolog is possible or desirable?

Any comments are welcome. I am a bit ashamed of starting such a hollow topic, but I guess you can ignore me and no further harm is done :slight_smile:

PS: One of the last places where I personally need a cut is when defining a predicate that need to check its arguments then cut, or continue with the next clause. Sometimes a cut is cleaner than if-then, for example (:<)/2. I did not fully understand yet the “Picat style matching” suggestion; does that apply in such cases?

3 Likes
2

Hi Boris,

Thank you for your thoughtful posting.

Here is the case I am handing – perhaps you can make sense out of it with your suggested classification of “cut” cases …

Essentially, I have a set of resources from a pool of resources. Some predicates p/2 need a resource, so they request one like so: get_resource(Pool, Resource).

When, p/2 subsequent computation with the obtained resource fails, then it does not mean that a different resource needs to be requested upon backtracking, but that the whole predicate should fail as well.

Now, i could wrap get_resource/2 into a once/1, ensuring that upon backtracking no other resource is requested.

However, that was exactly the point in the Craft book – instead of letting the caller wrap with a cut or a once/1, make get_resource/2 determined by ending it with a cut internally.

From the outside, for p/2, get_resource will not have additional internal choice points (another resource – although, they are in principle available), but fail – since the semantics of the get_resource/2 asks for such a failure.

I.e. you can only request a resource once (once/1) during forward execution of code, but you can not request another resource during backwards execution – as part of trying out another solution path – obtaining another resource won’t solve the problem – so backtrack some more and search elsewhere.

Dan

3

Some quick comments. Richard’s explanation of when and where to use cuts is probably the best there is. It leads to these remarks:

It typically an indication that it is the client committing some predicate. Though it makes the cut invisible, is IMO more indication of something dubious. I very rarely use once/1.

->/2 is often good in “procedural” code. *->/2 is a strange beast that is better avoided until you really know what you are doing.

In what sense is this a replacement for the cut? Surely, dif/2 (and constraints in general) are incompatible with cuts.

Yes. This is more or less the same argument as using “non-defaulty” representation. The problem is that Prolog doesn’t make many guarantees.

Note that this also relates to my RFC Picat style matching

4

Is there a good posting about defaulty representation – what it is and how to use it (or not use it). Couldn’t find one via search.

5

Hi!

If you want a cut-free Prolog, then check out Mercury. It’s an advanced, pure, logic-functional language. No cuts, no side effects, pure logical IO, static type system and more.

There are also Curry and Oz, but I don’t know much about them.

Cheers
Volker

1 Like
6

I guess, in Mercury, instead of a cut, you use a function – “forcing” to have one result, per call.

I am surely simplifying all this way too much :slight_smile:

7

You’re using determinism categories in order to ensure you predicate has only one result.

8

This reminded of a post a while back in which I rewrote the JavaScript switch example at switch - JavaScript | MDN in Prolog like so:

fruit('Oranges') :- !,
    format("Oranges are $0.59 a pound.~n", []).

fruit(Fruit) :-
    member(Fruit, ['Mangoes', 'Papayas']), !,
    format("~w are $2.79 a pound.~n", [Fruit]).

fruit(Fruit) :-
   format("Sorry, we are out of ~w.~n", [Fruit]).

Prolog has a similar bug/feature as JavaScript’s fall-through cases in that the default case will always be matched if something equivalent to JavaScript’s break or return isn’t called by an earlier matching case.

A difference between JavaScript’s break and Prolog’s ! is it’s good style in Prolog to cut as soon possible (whereas break or return are usually at the end of case blocks in JavaScript), so Prolog’s cuts are akin to guards as described by Edsger Dijkstra in this famous paper.

As in any programming language, one often needs conditionals with some default action in Prolog, and using cuts is the easy way to achieve that.

9

See e.g. Prolog Data Structures. Its easy to find, just stop Google from correcting it to default.

10

I think the original idea of looking at and evaluating the cause of cuts in real code is a good one. It would surely help to understand how and why we are using cut in practice.

Some of it is clearly because of the people using the language being steeped in procedural or even functional programming languages - in which determinism is the norm. I suffer badly from the functionalitis.

Some of it is to have a committed choice when you have a number of potential examples but only want one - and the first will do. This happens to me quite a lot with I/O (for instance HTTP handlers).

The use of defaulty representations is a big problem as well, but getting rid of defaulty representations takes a bit of practice and thought. It is actually very similar to specifying a data-type with case-coverage. This fact has always made me think that greater “gradual typing” would greatly improve prolog. The task of doing this in an acceptably prology way however is a bit tricky in practice and requires really tight integration with the development environment making portability a bit tricky as well.

I’d like to support Boris’ contention that diff/2 and in general co-routining does reduce cuts in code. The reason is that implementing relations which work in multiple modes often requires meta-logical nonsense with cuts. i.e.

p(X, Y) :- var(X), !, do_something_to_obtain_x_from_y(X,Y).  
p(X, Y) :- do_something_to_obtain_y_from_x(Y,X).

I find this code deeply offensive, and yet routinely engage in such evil in order to hide the implementation details from the caller. Unfortunately it is also error prone as the reversibility of the relation must be ensured carefully by hand. Co-routining tends to yield reversibility more reliably and with far fewer cuts.

But in some cases it should be possible to obtain the same by simply reordering clauses with a “mode specialising compiler” given that the compiler was:

  • aware of the acceptable modes
  • allowed to reorder clauses

Both of those things seem like they would be beneficial if they could be achieved but it is no short order. The reordering of clauses is impossible to do logically unless we know that the predicate is pure - i.e. no effects including exceptions and that means being able to know such things.

I think a good mode and type system which allows the types to be a type assertion is probably the first step towards a lot of more clever ways of avoiding cut and would have other benefits as well. I just wish I had the time to put more effort into solving it.

2 Likes
11

It’s also true as mentioned above that better indexing would surely help. I have loads of cuts that are caused by dictionaries not being sufficiently indexable.

And if you have a Picat-style solution you get to say that lack of determinism is an error due to a coverage failure. Otherwise you need to have cuts if you’re going to try to track coverage yourself, or stick it in a wrapper predicate that checks determinism of the outcome.

13

In my simple example above, if one was to query fruit(X), X would only be ‘Oranges’. So there is the snag that if you wanted all possible results, the cut would break a general query.

So care is needed with using ! that you are not breaking multiple choices.

14

With the new “Picat style matching”, we can write if_then_else as:

if_then_else(Test, Then, _Else), Test => Then.
if_then_else(_Test, _Then, Else) => Else.

(untested code, no warranty, etc. etc.)

Here’s an example of max_member_/3, rewritten with => style:

max_member_([], Max0, Max) =>
    Max = Max0.
max_member_([H|T], Max0, Max), H @=< Max0 =>
    max_member_(T, Max0, Max).
max_m_([H|T], _Max0, Max) =>
    max_member_(T, H, Max).

The original code (using if-then-else) was:

max_member_([], Max, Max).
max_member_([H|T], Max0, Max) :-
    (   H @=< Max0
    ->  max_member_(T, Max0, Max)
    ;   max_member_(T, H, Max)
    ).

There’s a bit more discussion at How to write max_member/2 with => (but ignore the digression about “lazy lists”).

1 Like
16

I’m not so sure about this any longer. Sure, if you want to write a multi-moded pure predicate this is the way to go as it results in deterministic and fully indexed code when the arguments are sufficiently instantiated and the clause indexing is smart enough. I also agree this is what Prolog is meant for :slight_smile:

Given all the stuff that is not multi-moded though (e.g. max_member/2 as we have seen), relying on clause indexing to achieve deterministic behavior has the flaw that insufficiently instantiated calls typically lead to an unintended (though often logically correct) result and an open choice point. E.g, sum_list(L,S) leads to L= and S=0, a choice point and an exception on backtracking. That makes little sense.

2 Likes
17

Well I’m super happy with deterministic guarded clauses to construct well defined functions or help with any other restricted modalities. Especially if they get rid of cuts which feel quite extra-logical.

But I’d still like to retain as much of the relational part as possible. Bidirectionality / multidirectionality is really incredibly useful when you can get it.

I’m not sure how often I’ve done it in practice but I want to say “a lot”, and increasingly I’ve been trying to do it with coroutining as this seems to be more robust and less error prone.

3 Likes
18

Hi Gavin,

Could you give some (educational) examples … for example, related to co-routines and/or otherwise.

Dan

19

An example in the wild:

There is still a cut there but it could be removed by checking the form of Key in the second branch. That might be better actually…

1 Like
20

Thank you.

Funny, to find another world domination plan – as I sharpen mine :slight_smile:

Dan

test(parse_upload_metadata_backwards, []) :-
    Struct = [filename-"world_domination_plan.pdf",is_confidential],
    parse_upload_metadata(String, Struct),
    String = 'filename d29ybGRfZG9taW5hdGlvbl9wbGFuLnBkZg==,is_confidential'.
2 Likes
21

Pinky and the Brain fan here!

The bulk of every episode involves one of Brain’s plans for world domination with Pinky’s assistance and the ultimate failure of that plan, with some exceptions.

1 Like
22

with failure …

"In each episode, Brain devises a new plan to take over the world which ultimately ends in failure

:slight_smile:

1 Like