What is up with the cut (!)

Discussion
#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
#23

Hmmm. Am I missing something? when/2 is a coroutining predicate. Value_base64 is surely unbound as it is the first appearance. If Value is ground, the when/2 executes base64_encoded/3 immediately. Else it will delaym but that means it will immediately call atomic_list_concat/3 with an uninstantiated Value_base64, resulting in an error.

#24

Can you explain why a when clause was used here to begin with … What benefit is had?

Why should there be a Value (or Value_base64) that is uninstantiated in that call – what is the calling context?

Dan

#25

Unsure whether this question is in the right thread, but I think it’s related. Suppose I have some complicated term in a defaulty representation, e.g. a mathematical expression like a^2.

Now I want to turn this into a clean representation, say xfy(^, symbol(a), integer(2)). I can write some code with a lot of cuts and metapredicates to do this. Would this picat style be a promising alternative?

#26

It depends on the other terms you want to distinguish it from. =>/2 style matching help if the goal (input) arguments may contain variables that must be distinguished from known concrete values. So, this avoids handling variables.

 p([], ...) =>
 p([H|T], ...) =>

If you want to deal with an atom though, you get this,which I think is fine despite having a cut behind the scenes.

p(X), atom(X) => ...

Note that non-defaultly representations only make sense if you want to have code that is deterministic on given input and the same code can be used in reverse mode. If you do not want/need multi-moded code I can see no advantage on non-defaulty representations. In some Prolog systems, including SWI-Prolog you may profit from clause indexing. There is no fundamental reason why atom(X) cannot be taken into account by the clause indexing code. symbol(a) certainly needs to be created, scanned and garbage collected.

#27

This is already a huge win. Specifically because => rules do not allow a silent fall-through.

This is the closest to Erlang “guards” that I have seen so far in Prolog, and I really like it.

PS: Erlang guards have requirements on what can be in this goal between the head and the neck. My impression is that the Prolog equivalent to this would be “the goal does not further instantiate its arguments”, like any of the type checks with atom/1, ground/1, is_list/1 and so on.

If I understand the => so far, it seems that there are no restrictions on instantiation, only a “hard cut” after it, like in these examples:

foo(X), X = a => true.
foo(X), X = b => true.

bar(X), between(1, 3, X) => true.

and then:

?- foo(X).
X = a.

?- foo(a).
true.

?- foo(b).
true.

?- bar(X).
X = 1.

?- bar(4).
ERROR: No rule matches bar(4)
1 Like
#28

True. If I recall correctly the docs also claim this may not be a good idea. A general restriction “may not instantiate any of the goal arguments” would be great. This is not so easy to enforce. For the head unification we know that if some binding has been created we must fail. Prolog code for the guard may bind other variables and can still be perfectly fine. Checking that the goal arguments remain unchanged gets rather costly. An alternative could be a whitelist of allowed guards. That seems rather restricted though as libraries and extensions may provide perfectly sound guard predicates. I think I’m more in favor of future static analysis tools flagging dubious guards.

#29

I don’t remember how exactly it goes with Erlang, but my impression was that allowed guards are indeed whitelisted. Does anyone know if user-defined guards are allowed? Reading in a hurry, it seems the answer to user-defined guards is NO!

Their docs say, “evaluation of a guard expression must be guaranteed to be free of side effects”.

I guess such static analysis can eventually become a part of the compilation process, once mature enough and proven to be useful? I like this approach.

1 Like