[erlang-questions] erlang:max/2 and erlang:min/2

117 views
Skip to first unread message

Richard O'Keefe

unread,
Sep 9, 2010, 12:33:56 AM9/9/10
to Erlang Questions
I see that max/2 and min/2 are now in Erlang.
You would expect them to satisfy
[min(X,Y),max(X,Y)] is a permutation of [X,Y]
max(X,Y) is max(Y,X)
min(X,Y) is min(Y,X)
amongst other things.

When X and Y are distinct terms that are equal as numbers,
max(X,Y) and min(X,Y) both return X.

sort3([A,B,C]) ->
[U,V] = sort2([A,B]),
[W,Z] = sort2([V,C]),
[X,Y] = sort2([U,W]),
[X,Y,Z].

sort2([A,B]) ->
[min(A,B),max(A,B)].

You'd expect this to sort. But it doesn't:
> sort3:sort3([0,0.0,-0.0]).
[0,0,0]

It really is very confusing for it to make a difference
whether you write max(X, 0) or max(0, X), but in R14A it does.

The *really* big problem here is that max/2 and min/2 are
(otherwise) based on *term* comparison, and there *can't* be
two identical but distinguishable terms.

In order to get a total order on numbers, it seems necessary
to rule that
-0.0 < 0 < 0.0
and this extends to a general rule that
if X and Y are numbers that are numerically equal
but of different types, the floating point one is
smaller if its sign bit is set, otherwise the
floating point one is bigger.

The root of the problem is trying to make one ordering
serve as both a numeric ordering and a term ordering.

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questio...@erlang.org

Nicholas Frechette

unread,
Sep 10, 2010, 7:53:02 PM9/10/10
to Richard O'Keefe, Erlang Questions
This is fairly standard as far as I know in languages without strong typing
in function arguments (when that is the case, usually coercion happens which
hides this behavior from you).
For example in ruby:
>> [1, 1.0].min
=> 1
>> [1.0, 1].min
=> 1.0
>>

And again in python:
>>> min([1, 1.0])
1
>>> min([1.0, 1])
1.0
>>>

For these languages (and erlang), order DOES matter.

This isn't unlike a naive implementation of min/max in C++:
#define max(A, B) A >= B ? A : B

However, even using c++0x:
auto SomeResult = max(1, 1.0); // what happens here? what is the type of
SomeResult? (float) See note below
auto SomeResult = max(1.0, 1); // what happens here? what is the type of
SomeResult? (float) See note below

*** Note below (really a side note, you can skip this) ***
The 'ternary' operator is special (in C/C++). In the case above, both A and
B can't be of different types. The type will be coerced to a common base
type only if possible, otherwise compilation will fail.
See for details:
http://msdn.microsoft.com/en-us/library/e4213hs1%28VS.71%29.aspx (applies to
other compilers as well)
The ternary operator can also be used as an l-value (for fun and profit) :)
((A >= B) ? A : B) = 123; // Don't do this.. otherwise your coworkers will
want to kill me for teaching you
***

In C++ at least, both types will be converted to a common base type with the
ternary operator or you'll traditionally write functions which will coerce
the arguments for you in order to use hardware specific instructions to do
the selection:
max(A,B) becomes 2 instructions for floats/doubles (on powerpc, same for
min): C = A - B, C >= 0 ? B : A (powerpc has an instruction to compare a
float against zero and select the result (fsel))
For integers, you can go either with a branch or branch-free version.
Mixing types will always go to the float/double impl for obvious reasons.

As far as I know, in a loosely type language like erlang, you have to know
your data... if you sort/compare mixed types (integers/floats/otherwise),
you have to handle that case and be aware of the (potential) consequences.
I for one disagree with the global/total ordering imposed on mixed types.
But then again, I mainly come from strongly typed languages and I am not
aware of the original logic behind it, perhaps it makes perfect sense.
This thread should perhaps be merged with the 'strictly less then' thread
since it voices a similar issue regarding term comparison and ordering.

Nicholas

Tony Rogvall

unread,
Sep 11, 2010, 9:10:16 AM9/11/10
to Nicholas Frechette, Richard O'Keefe, Erlang Questions
>
> The ternary operator can also be used as an l-value (for fun and profit) :)
> ((A >= B) ? A : B) = 123; // Don't do this.. otherwise your coworkers will
> want to kill me for teaching you

Ultra cool.
This is perfect for obscure programming. I will integrate this in the standard workflow here at the office!

Sadly gcc complains a bit about this!
tassign.c:12: warning: target of assignment not really an lvalue; this will be a hard error in the future

with the option -fno-non-lvalue-assign
This will generate error:

tassign.c:12: error: lvalue required as left operand of assignment

Unfortunately I could not find any option to turn off the irritating warning.

Thanks ;-)

/Tony

Richard O'Keefe

unread,
Sep 12, 2010, 10:43:55 PM9/12/10
to Nicholas Frechette, Erlang Questions

On Sep 11, 2010, at 11:53 AM, Nicholas Frechette wrote:

> This is fairly standard as far as I know in languages without strong typing in function arguments (when that is the case, usually coercion happens which hides this behavior from you).
> For example in ruby:
> >> [1, 1.0].min
> => 1
> >> [1.0, 1].min
> => 1.0

The traditional retort to this is "And if all your friends jumped off
a cliff, would you copy that too?"


>
> For these languages (and erlang), order DOES matter.

And all that means is that they are buggy too.

>
> This isn't unlike a naive implementation of min/max in C++:
> #define max(A, B) A >= B ? A : B

Er, that is a couple of steps of beginnerness _below_ "naive".
#define max(A, B) ((A) >= (B) ? (A) : (B))
is normally required, and of course the preferred method in C++
is
template <typename T>
T max(T a, T b) {
return a >= b ? a : b;
}
for obvious reasons.


>
> However, even using c++0x:
> auto SomeResult = max(1, 1.0); // what happens here? what is the type of SomeResult? (float) See note below
> auto SomeResult = max(1.0, 1); // what happens here? what is the type of SomeResult? (float) See note below

What happens here is quite irrelevant to dynamically typed languages.
The if-then-else operator has to return a result of *some* definite type,
so there really are only two choices for it.
Either it demands that both choices be the same type,
or else it has to convert at least one of them.

This has no significance whatever for a language that *doesn't* require
all arms of an if to have the same type and *doesn't* have to convert.


>
> *** Note below (really a side note, you can skip this) ***
> The 'ternary' operator is special (in C/C++). In the case above, both A and B can't be of different types.

I think "can't" was meant to be "can".

> The type will be coerced to a common base type only if possible, otherwise compilation will fail.
> See for details: http://msdn.microsoft.com/en-us/library/e4213hs1%28VS.71%29.aspx (applies to other compilers as well)
> The ternary operator can also be used as an l-value (for fun and profit) :)

NOT IN STANDARD C OR C++ IT CANNOT!

> ((A >= B) ? A : B) = 123; // Don't do this.. otherwise your coworkers will want to kill me for teaching you
> ***

One reason they will be displeased with you is that most compilers reject this.
A typical error message:
"foo.c", line 2: warning: conditional expression is not a valid lvalue


>
> In C++ at least, both types will be converted to a common base type with the ternary operator or you'll traditionally write functions which will coerce the arguments for you in order to use hardware specific instructions to do the selection:
> max(A,B) becomes 2 instructions for floats/doubles (on powerpc, same for min): C = A - B, C >= 0 ? B : A (powerpc has an instruction to compare a float against zero and select the result (fsel))

On a SPARC or a Pentium or an ARM, it would be
[assume A is in register x]
[assume B is in register y]
[assume result is wanted in register x]
compare x with y one compare instruction
move y to x if x < y one conditional move

It is not clear to me how this is supposed to be relevant to Erlang,
which has to deal with mixed integer/float comparisons, or to the
question of how you implement max/2 and min/2 so that they satisfy
the laws that a programmer *ought* to be able to take for granted.

C and C++ can get away with (user-provided) definitions that convert
basically because they can't have arrays whose elements are of varying
types, so if you do
auto x = a[0];
for (int i = 1; i < n; i++) x = max(x, a[i]);
there _can't_ be any problems introduced by conversion, because
all the a[i] must be the *same* type.

But in Erlang, the elements of a list CAN be of different types.

Intuitions based on experience with strongly typed languages
(Ada, Clean, Haskell) would tell you that mixed-mode arithmetic
should simply be banned. Any time it is intentional, an explicit
coercion can be provided by the programmer.

Intuitions based on experience with weakly typed languages
(C, C++, Java, C#) would mislead you into thinking that operations
that don't actually obey the mathematical laws they are supposed
to are OK because thanks to the all-elements-of-an-array-are-the-
same-type setup, uses of < and max DO obey the laws in question.
(Sorting a floating-point array is unproblematic in C
*IF* (1) there is at most one -infinity
(2) there is at most one +infinity
(3) there are no NaNs
(4) either you don't care about the order of -0 and +0
or they don't both occur.
Sorting a mixed integer/float array just can't happen.)

Nicholas Frechette

unread,
Sep 13, 2010, 10:41:00 AM9/13/10
to Richard O'Keefe, Erlang Questions
Yes precisely, I was arguing mixed mode arithmetic should be banned or have
no defined behavior to force programmers to think and be sure to know what
they are doing.
I agree with your claim that the behavior is currently unintuitive and prone
to error. I simply meant to illustrate erlang isn't alone in that respect
and that when one programs in a language, one has to know the potential
pitfalls associated with it...
I wouldn't be surprised if at this point they were unwilling to correct this
situation considering it is of fairly high impact. Although perhaps it could
be done with compiler/erl switches to turn on/off the old/new behavior.

The bit about the ternary operator is to show that for most of these
languages, a similar construct is likely used which causes order to matter.
In erlang, it could have been done as follow (wild guess as it is probably a
nif but likely of a similar nature given the observed result):
max(A, B) when A >= B -> A;
max(_, B) -> B.

A more correct implementation could have been (not actually compiled to test
but you get the idea):
%% Integer/integer
max(A, B) when is_integer(A) and is_integer(B) and A >= B -> A;
max(A, B) when is_integer(A) and is_integer(B) -> B;
%% Float/float
max(A, B) when is_float(A) and is_float(B) and A >= B -> A;
max(A, B) when is_float(A) and is_float(B) -> B;
%% Mixed integer/float coerced result as float but could be made to raise an
exception/exit process
max(A, B) when is_integer(A) and is_float(B) and float(A) >= B -> float(A);
%% Not sure if float() can be used in a guard?
max(A, B) when is_integer(A) and is_float(B) -> B;
max(A, B) when is_float(A) and is_integer(B) and A >= float(B) -> A;
max(A, B) when is_float(A) and is_integer(B) -> float(B);
%% General case of other types, would it make sense though?
max(A, B) when A >= B -> A;
max(_, B) -> B.

Unfortunately, the above doesn't extend to tuples/lists/other types.

*** Side note ***
Also, while it is true the ternary operator can't always be used as an
l-value, some compilers still allow it as it must have been once part of the
standard.
For example, wikipedia still mentions it at:
http://en.wikipedia.org/wiki/%3F:
The link I included (which you may not have read) also says: "The type of
the result is the common type, and it is an l-value if both the second and
third operands are of the same type and both are l-values."
Unfortunately I can't find a copy of the C++ standard laying around but here
are some results on the compilers I currently have on hand:
In VS2008, the below compiles for win32, for the xbox360 (somewhat expected
since they are both Microsoft compilers) and perhaps surprisingly on sony's
compiler for the PS3 (PPU) (which is oftentimes more strict than GCC but
obviously not for this special case) :
void* A;
void* B;
((someCondition) ? A : B) = NULL;
Alas, I digress.
Nicholas

Toby Thain

unread,
Sep 14, 2010, 12:48:04 AM9/14/10
to Nicholas Frechette, Richard O'Keefe, Erlang Questions

On 13-Sep-10, at 10:41 AM, Nicholas Frechette wrote:

> ...


> *** Side note ***
> Also, while it is true the ternary operator can't always be used as an
> l-value, some compilers still allow it as it must have been once
> part of the
> standard.

While I haven't internalised the relevant standards the way ROK has,
there's no reason to assume this was EVER 'standardised' behaviour.
Vendors will make arbitrary and/or egregious divergences from
standards. That's the problem.

--T

> ...snipped anecdotes...

> Alas, I digress.
> Nicholas

Reply all
Reply to author
Forward
0 new messages