8
\$\begingroup\$

This stems from JoKing's answer to Sums of Consecutive Integers, where it can be seen that the predicate always unifies Z with the correct answer first.

However, checking for all values, we see that it unifies Z with all shorter solutions after finding the longest solution: Try it online!. Can this be allowed?

\$\endgroup\$
3
  • \$\begingroup\$ Shouldn't this just be posted as an answer to Default for Code Golf: Input/Output methods for people to vote on? \$\endgroup\$
    – pxeger
    Sep 12 at 12:16
  • 3
    \$\begingroup\$ @pxeger I don't think this really counts as an input/output method, more as a language-specific functionality question. Potentially akin to "Can a Python answer exit with an error after outputting?" \$\endgroup\$ Sep 12 at 12:46
  • 1
    \$\begingroup\$ This is not an answer to the actual question, but as a Brachylog user I want to opine that when a Brachylog predicate is called as a full program, this behavior should be allowed. You give it input, it gives you the desired output. Not entirely sure how or whether that applies to Prolog, though. \$\endgroup\$
    – DLosc
    Sep 12 at 16:21

5 Answers 5

6
\$\begingroup\$

Yes

In my experience, even legitimate (i.e. not for code golf) Prolog predicates often have extraneous choice points that you don’t need. Getting rid of them is not always easy, especially if you want to keep your code "pure".

Of course you can add cuts ! after calling your predicate. A cleaner solution is to wrap your predicate call in once/1, which will make your predicate succeed at most once.

I don’t see the point in imposing such additions to answers, as they add no substance to golfing. In fact, if we were to impose discarding extraneous choice points, we might discourage alternative solutions that take shortcuts to get the right answer, at the expanse of extraneous or even "wrong" additional choice points. In my opinion we should actually encourage those approaches.

Historically accepted

I have never seen a Prolog answer’s validity be rejected based on the additional choice points it created.

Note that the same applies to Brachylog: other choice points can be queried with meta-predicates, failure loops, or Prolog’s REPL. Answers with extraneous choice points have never been debated either.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't think you are right about this being historically accepted. We have been holding ourselves to this standard for Curry answers, and loosening would make a very significant difference for Curry golfing which often has to go to extra lengths to avoid these. I also think that this loosening would make Curry golf a lot less interesting as it would make Curry a lot more like Haskell since Haskell always takes the first branch point. Curry doesn't have cut so working to prevent extraneous answers requires creativity. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 12 at 14:49
  • \$\begingroup\$ @WheatWizard But it doesn’t require creativity in Prolog since you have cut, so no one ever bothered about it. \$\endgroup\$
    – Fatalize
    Sep 13 at 7:42
6
\$\begingroup\$

Prolog isn't the only logic language

Curry, which was the language of the month back in April, is also a logic language to which any consensus here would apply.

Curry

If we look at Curry we can see that golfers are already operating under the assumption that you must return only correct answers. Here are two examples:

1, 2

While these are examples where the difference is small, this is not, in general, the case. Curry doesn't have Prolog's cut operator, so an answer that meets the relaxed standard cannot be trivially modified to meet the strict standard. Sometimes you just have to rework it.

Curry KiCS2 has a specific flag you can pass it which takes the first path. Alephalpha points to a few answers that explicitly use this flag:

1, 2

These answers clearly state the use of the flag and are marked as solutions in the language "Curry (KICS2) + :set +first". So it certainly seems like we have been operating under the assumption that answers must only return the correct answer in Curry.

And that's great for Curry, because half the time the answer that meets the relaxed standard is just the Haskell answer. Haskell is very similar to Curry in many ways, but it doesn't have non-determinism. It just follows the first path without backtracking. Often a Haskell answer will find the right answer in Curry, but have a lot of extraneous paths. Requiring cleanup is one of the things that makes Curry golf unique and sets it apart from Haskell.

In the examples where it's not the same as Haskell it is still possible to post it, but it goes in it's own special category. That seems best because really neither answer is necessarily better or more interesting. It really ought to go in it's own category.

Taking this all together it seems like the current requirements are good for Curry golf, they allow diversity and creativity in Curry golf. And it's not a surprise that Curry golfers have defaulted to this behavior.

Back to Prolog

I think Fatalize is right about how this affects Prolog. Most often getting the first answer to be the only answer just means inserting a cut in the right place to get a single solution. Which is a minor annoyance. It doesn't make a big difference.

This doesn't exactly paint a clear picture for me either way. It seems like Prolog golf will remain much the same going down either path.

As a Prolog golfer and a Curry golfer myself I can say that when looking holistically at both, it's clear that the requirement of only outputting the correct answer is worth it overall.

There are of course other logic programming languages not discussed here. I think Brachylog is the most popular one on the site. I encourage programmers and golfers in those to share how this would affect golf in their language.

\$\endgroup\$
2
  • \$\begingroup\$ In fact, I have two Curry answers (1 2) that do not meet the strict standard. In those answers, I added the :set +first flag so that only the first value is outputted, but it may still follow other paths in backtracking. \$\endgroup\$
    – alephalpha
    Sep 13 at 7:45
  • \$\begingroup\$ Brachylog's situation is basically the same as Prolog's: if you want the first solution only, you can usually just add a cut (+1 byte in Brachylog). \$\endgroup\$
    – DLosc
    Sep 13 at 16:39
3
\$\begingroup\$

It depends

After reading everyone's arguments, I think Wheat Wizard's answer makes sense. This is a concurring opinion that looks at things from a Brachylog perspective.

Predicates and unification

Like in Prolog, a Brachylog predicate typically produces output by unifying a variable with some number of values, one after another. This type of output is considered to be a "generator" in our default I/O methods. For challenges that ask for a list, I and others have written Brachylog predicates that unify a variable with the first element, then the second element, and so on.

I don't think we should try to have our cake and eat it too. If unification creates a generator, and a generator is equivalent to a list, then a generator cannot also be equivalent to a single value whenever it's convenient to treat it that way. We should either use findall when we want multiple values, or cut when we want a single value. Since there's already a consensus that unification means multiple values, let's stick with that.

To return a single value from a predicate by unification, we should make sure the predicate only returns one value and then stops. (If we think of unification as a generator, this is equivalent to returning a value in a singleton list.)

Full programs

As I said in a comment, I don't think the same rules should apply if a submission is a full program rather than just a predicate. A full program that takes input, produces output, and halts should be judged on the actual output it produces. The fact that a Brachylog program is often a single predicate, and the fact that the predicate could have produced more results if it were called multiple times, is irrelevant in this case.

However, there are some caveats:

First, in Prolog, it's possible to run a program in such a way that it produces one output and then waits for the user to indicate whether they want more or not. This should not count as producing a single output; it is analogous to the generator case. That's why I included "and halts" in my full-program description above. If there is a flag that makes the program output the first result and halt, like Curry has, then that's fine.

Second, most Brachylog solutions are not full programs. I was a bit surprised to realize this, but reading through this comprehensive answer, it makes sense. TL;DR: If you pass an input to a Brachylog program and it prints 42 to stdout, that's a full program that outputs 42. If you pass an input and a variable name X to a Brachylog program and it prints X = 42 to stdout, that's not a full program that outputs 42; it's a predicate that returns 42.

The same reasoning applies to the Prolog answer that led to this meta discussion: its input is 9+A., and its output is A = [2, 3, 4]. That's not a full program solution, it's a predicate solution. It could be made into a full program if it read input from stdin and wrote output to stdout, but of course that would cost more bytes.

Predicates and writing to stdout

Here's where it gets tricky: we allow functions to output to stdout. What should be done with a predicate that outputs to stdout? Maybe if it were called more than once, it would output more than one thing. Do we consider its output to be what it prints when it's called the first time, or what it prints when it's called until it fails? I'm not sure.

This is somewhat analogous to printing within a generator expression in a language like Python, except that in Python, you won't get any output if you return the generator untouched, whereas in Prolog and Brachylog, you'll get the first pass of output.

(Again, note that if we're talking full-program, the output should be whatever the program outputs, which is probably going to be the result of calling the predicate once.)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think it might be okay to "have our cake and eat it too". For example, Python solutions to "is the input list empty" and "what is the length of this list" can both be len, since the output can be coerced in two different ways, boolean and numeric. In Prolog, this could be seen as a generator being "coerced" to the first unified value by using once or just using it in a non-backtracking manner. \$\endgroup\$
    – Jo King Mod
    Sep 15 at 6:13
  • \$\begingroup\$ @JoKing Hmm. I could be persuaded by that argument, but my main question is consistency. Would you support other languages returning a generator that possibly yields multiple values, as long as the first value is the desired result? Or what if the desired result is the first element in a list containing multiple values? \$\endgroup\$
    – DLosc
    Sep 15 at 16:32
  • \$\begingroup\$ I wouldn't support other langs in the same way unless generators can be implicitly coerced to a single value. For example Lua has iterators that can be called to get the next value, but if the iterator just returned a value when used alone I would allow it. As a general argument, since we allow implicit type conversions in dynamic typing langs like Python and Perl, I believe this is close enough to count. \$\endgroup\$
    – Jo King Mod
    Sep 16 at 0:57
0
\$\begingroup\$

No

Despite legitimate Prolog predicates having extraneous choice points, they have more reason to leave those choice points in (generality, for example).

Prolog answers have been allowed to output variables that can assume multiple values. This is treated akin to returning a list of the required outputs. With this in mind, if a predicate unifies a variable with more than one value, and the requirement is a single, distinct value, returning all solutions like in the mentioned answer is invalid. Wrong answers should not be encouraged.

Even despite the acceptance of previous Prolog and Brachylog answers, it is wrong to allow answers to sacrifice correctness for cleverness. There can still be clever Prolog answers within this restriction, it will just need a few extra bytes for a cut or a once.

The historic acceptance of multiple choice points in cases where there should be a single answer produced is a problem, and the lack of discussion regarding it is not a point of merit toward this matter.

\$\endgroup\$
-1
\$\begingroup\$

A thought

I don't really know much about Prolog/logic languages, but this seems to me like kinda a loophole. Similar to outputting [true, false] in a and saying that "one of those is correct."

\$\endgroup\$
1
  • \$\begingroup\$ This is about outputting the correct answer first. So it wouldn't be valid to do [true, false] because true is always first, then. \$\endgroup\$
    – Steffan
    Sep 18 at 2:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .