4
\$\begingroup\$

There are some questions requiring distinct and consistent output. It's obvious what they mean for submissions printing to stdout. But how does that apply to the return values of functions?

For example, in Python, if a function always returns 1 for one case and "a" for another, we could say they are distinct and consistent. But what if it returned lambda:1? The problem is, (lambda:1) == (lambda:1) is false. And their string representations could change if run again.

If that shouldn't be acceptable, it would be difficult to justify how non-constant, non-static C strings are consistent, as they are technically pointers which may have different values even if the strings are the same.

If that should be acceptable, how should it be defined exactly? Someone could think it's a good idea to create two instances of a class to represent two different results. But in other cases, someone may prefer generating even the classes on the fly.

Should we have a standard for all cases or make it flexible? And what would be acceptable exactly?

If we use the simple approach to allow writing their own comparison functions, it would leave a loophole that they simply return the input and do everything in the comparison function.

\$\endgroup\$

2 Answers 2

9
\$\begingroup\$

Outputs are consistent if they are equal in the sanest and most obvious way of comparing them. For example, if you have two char * strings in C or C++, and you try

a == b

you will get a falsy value even if the strings are equal. But every half-decent C programmer knows that you don't compare strings with ==. That's the reason this SO question has almost 50,000 views at the time I'm writing this answer. Your python example is similar. For example:

(lambda: 1) == (lambda: 1)

is false. And comparing lambda functions by their string representation is completely nonsensical.

But it's still perfectly obvious that the two values are conceptually the same. They're both unnamed functions that return one. In fact, there's even a sane way to compare them. For example:

(lambda: 1)() == (lambda: 1)()

Now to be fair, this is a pretty flexible/laissez faire approach. It's pretty close to an "I know it when I see it" policy. But that's because this is mostly an edge case. I'm not aware of any cases where this little detail happens to matter, and I can barely think of any hypothetical cases where it would.

But if this wasn't accepted by default that you can choose the most obvious way of comparing return values, I can imagine pointless arguing like:

Well sure, a and b happen to have the same values in them. But so what? They're not in the same location!

(&a) == (&b)

is false, so technically you failed all of the test-cases.

which is clearly ridiculous.

\$\endgroup\$
11
  • \$\begingroup\$ Why would str(lambda: 1) == str(lambda: 1) be false? \$\endgroup\$
    – Dennis
    Dec 12, 2016 at 6:38
  • \$\begingroup\$ @Dennis That's weird. str(lambda: 1) == str(lambda: 1) is true but a=lambda:1; b=lambda:1; a==b is false. \$\endgroup\$
    – jimmy23013
    Dec 12, 2016 at 6:42
  • \$\begingroup\$ @Dennis My guess is, the addresses of freed variables could be reused, and they are very likely to be reused. When the first str(lambda: 1) is evaluated, the lambda function in it isn't necessary anymore, so it is freed. \$\endgroup\$
    – jimmy23013
    Dec 12, 2016 at 6:45
  • \$\begingroup\$ @jimmy23013 That seems to be the case. tio.run/nexus/python2#@19QlJlXolBcUqSRk5iblJJopWCoyYVN8P9/AA One point in favor of the lambdas being equal. \$\endgroup\$
    – Dennis
    Dec 12, 2016 at 6:50
  • \$\begingroup\$ @jimmy23013 When you bind the lambda expression to references, they reside in two different memory locations, and a == b is false because id(a) == id(b) is false (which compares memory locations). Without binding them to references, there is only one copy of the lambda liteal in memory (the interpreter is smart), and so str(lambda:1)==str(lambda:1) is true (since the string representation of a lambda expression contains its memory location). \$\endgroup\$
    – user45941
    Dec 12, 2016 at 6:50
  • \$\begingroup\$ @jimmy23013 Can't reproduce. tio.run/nexus/python2#@59om5OYm5SSaGXIlYRgFhRl5pVoJNraJmn@/w8A prints False. \$\endgroup\$
    – Dennis
    Dec 12, 2016 at 7:01
  • \$\begingroup\$ @Dennis My bad, I forgot to remove str(). \$\endgroup\$
    – jimmy23013
    Dec 12, 2016 at 7:03
  • \$\begingroup\$ @Mego That could be easily falsified. But let's not go into too much details as I don't think this is a defined and consistent behavior anyway. \$\endgroup\$
    – jimmy23013
    Dec 12, 2016 at 7:12
  • \$\begingroup\$ @jimmy23013 This is what I meant. \$\endgroup\$
    – user45941
    Dec 12, 2016 at 7:12
  • \$\begingroup\$ @Mego Oh, I may have misunderstood you but still don't think that's the answer. What do you mean by "binding to references"? Even if there isn't such a thing, address reuse clearly happens and make that true in both of our examples anyway. And... \$\endgroup\$
    – jimmy23013
    Dec 12, 2016 at 7:22
  • \$\begingroup\$ @jimmy23013 What I mean is, if you assign the same lambda function to two different variables, they will not compare equal, even though they are the same function, because they will reside at two different memory locations, and thus id(a) == id(b) will be false. In fact, you don't even have to assign them to variables to see this behavior - the same lambda object won't be reused when comparing the lambdas directly, so (lambda:1) != (lambda:1). \$\endgroup\$
    – user45941
    Dec 12, 2016 at 8:11
2
\$\begingroup\$

For a result to be consistent, it must belong to a type that's comparable

Integers are possible to compare consistently. Strings are possible to compare consistently (you can do it character by character). In general, anything that can be represented as a simple recursive data structure (think a Lisp list) can be compared simply via iterating over it recursively. These are known as comparable types; languages with particularly advanced type systems often have an interface, typeclass, or equivalent that marks the type as possible to compare. For example, Haskell has Eq. (Note that the comparison is typically not done with == or the equivalent, but rather requires a function to compare; in Java, strings (and every other reference type, for that matter) are compared with .equals().)

Although the majority of types are comparable (PPCG problems normally use strings, integers, and lists of other types that are used), there are some types that inherently aren't. Most notably, functions are mathematically impossible to compare, at least in a Turing-complete language. Languages with strong enough type systems are aware of this. Here's what happens if I try the example in the OP in Haskell:

Prelude> (\() -> 1 :: Integer) == (\() -> 1 :: Integer)

<interactive>:8:23:
    No instance for (Eq (() -> Integer))
      (maybe you haven't applied enough arguments to a function?)
      arising from a use of ‘==’
    In the expression: (\ () -> 1 :: Integer) == (\ () -> 1 :: Integer)
    In an equation for ‘it’:
        it = (\ () -> 1 :: Integer) == (\ () -> 1 :: Integer)

So, if an answer belongs to a comparable type, we can determine if it's consistent by comparing all the output values to see if they're equal. If it doesn't, I suspect it can't be consistent by definition.

Note that in some cases, an output may be consistent in a less powerful language even though it's inconsistent in a more powerful language; for example, a language in which all functions are deterministic and always terminate, and in which all base types had finitely many values, would make it possible to compare first-order functions by verifying that they had the same behaviour for all possible arguments (something that can't be done in general because you can't compare the nontermination behaviour of functions due to the halting problem).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ The last paragraph needs a slight qualification: it's only possible to compare first-order functions if their argument ranges are finite and enumerable. E.g. it's easy to compare terminating functions which take an 8-bit input, but not to compare functions which take a bigint input. \$\endgroup\$ Dec 13, 2016 at 8:49
  • \$\begingroup\$ There is a misconception. Comparing functions is as impossible as to know the correctness of the answers on our site. It's impossible to cover every case (thus the type is incomparable), but it's possible to compare a subset of all possible functions, and know the correctness of a subset of all possible answers. We don't need to know exactly whether each of all the possible answers is correct. Being unable to prove correctness with some basic assumptions should be enough to reject an answer. \$\endgroup\$
    – jimmy23013
    Dec 13, 2016 at 17:38
  • \$\begingroup\$ The same could be applied to comparing functions. Sometimes it's obvious whether the functions actually used in an answer are equivalent or not. But if it's not obvious and the poster cannot prove it, we could simply reject that answer and not others. \$\endgroup\$
    – jimmy23013
    Dec 13, 2016 at 17:39
  • \$\begingroup\$ Fun fact: In Mathematica, functions are just nested lists of symbols, so (1 &) == (1 &) returns True (but (1 + 1 &) == (2 &) stays unevaluated.) \$\endgroup\$ Dec 23, 2016 at 14:04

You must log in to answer this question.

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