Author: Richard A. O'Keefe <ok(at)cs(dot)otago(dot)ac(dot)nz>
Status: Final/R13A/R14A Proposal is implemented in OTP release R13A and R14A 
Type: Standards Track
Erlang-Version: R12B-4
Created: 10-Jul-2008
Post-History:

EEP 30: Maximum and Minimum

Abstract

Add maximum and minimum core functions.

Specification

Currently the Erlang language has no built-in support for the maximum and minimum operations. So we add new functions

erlang:min(E1, E2) with the same effects and value as

(T1 = E1, T2 = E2, if T1 > T2 -> T2 ; true -> T1 end)

erlang:max(E1, E2) with the same effects and value as

(T1 = E1, T2 = E2, if T1 > T2 -> T1 ; true -> T2 end)

except that we expect them to be implemented using single VM instructions, and we expect HiPE to use conditional moves on machines that have them.

The erlang: module prefix on max/2 (respectively min/2) can be omitted if and only if there is no locally defind max/2 (respectively min/2).

Motivation

Maximum and minimum are extremely useful operations. The fact that there is no standard way to express them in Erlang has had the predictable result: there are definitions of max/2 in tool_utils, tv_pg_gridfcns, tv_pb, tv_comm_func, ssh_connection_handler, bssh_connection_handler, ssh_cli, hipe_arm, hipe_schedule, hipe_ultra_prio, hipe_ppc_frame, ?HIPE_X86_FRAME (presumably one each for 32- and 64-bit PCs), hipe_sparc_frame, erl_recomment, erl_syntax_lib, appmon_info, oh, the list goes on and on. There are dozens of copies. There are nearly as many copies of min/2. And that's leaving aside possible copies with different names.

Not only are the operations useful, they can be implemented more efficiently by the compiler than by the programmer. If X < Y can be a VM instruction, so can min and max. Here's a first draft implementation:

OpCase(i_minimum): {
    r(0) = CMP_GT(tmp_arg1, tmp_arg2)) ? tmp_arg1 : tmp_arg2;
    Next(1);
}
OpCase(i_maximum): {
    r(0) = CMP_GT(tmp_arg1, tmp_arg2)) ? tmp_arg2 : tmp_arg1;
    Next(1);
}

Beware: untested code! Amongst other things, I don't know all the places that need to be updated, or how, when new instructions are added. These instructions are intended to be preceded by an i_fetch instruction the way < and its other friends are.

This is much cheaper than an Erlang function call, and it's much easier for HiPE to recognise when a maximum or minimum of two floating point numbers is involved and can be turned into a compare and a conditional move.

The most important thing is the barrier to thought that is removed. When I'm writing Fortran, I know that max and min have been there for decades, and I use those operations freely. When I'm writing C, I know that those operations are not there, and that there are problems with the conventional macros, so I avoid them. As an experiment, I added max() and min() functions to the version of AWK that I maintain. It was easy, and the result is that I now have a lot of AWK code that can't be run by anything else, because the operations are so handy. Erlang has no documented maximum or minimum functions other than those in the lists module, and writing lists:max([X,Y]) is sufficiently painful to deter all but the most determined.

Rationale

Function or operator?

I believe that there are excellent reasons to use the standard /\ and \/ symbols from lattice theory. However, discussion in the EEPs mailing list showed that the community was divided into

  • people who were familiar with the operators
  • people who insisted that they were only Boolean operators
  • people who didn't get them at all because they weren't C.

The ready availability of the operations as a standard part of the language is much more important than what they are called, so the second draft of this EEP switched to built in functions in order to increase acceptance.

The argument which finally settled it for me was the internationalisation one: Japanese programmers may be using keyboards where \ means or screens where \ displays as Yen, so /\ and \/ just won't work for them.

We cannot use max and min as operators because the compiler will not let you use a symbol as both an operator and a function name, and there are lots and lots of uses of max and min as function names. That's precisely the problem we're trying to address here. So they have to be function names.

There is no great difficulty in adding new functions to the erlang: module.

I don't want to write the erlang: prefix here. There is nothing new in making the erlang: prefix for some functions optional either.

What we want is for existing modules with their own definitions of max/2 and/or min/2 to remain legal, and then to be upgraded simply by removing the redundant definitions.

Imagine that you want to find the bounding box for a set of 2D points. (This is adapted from code in Wings3D.)

bounding_box([{X0,Y0}|Pts]) ->
    bounding_box(Pts, X0,X0, Y0,Y0).

bounding_box([{X,Y}|Pts], Xlo,Xhi, Ylo,Yhi) ->
    if X < Xlo -> Xlo1 = X,   Xhi1 = Xhi
     ; X > Xhi -> Xlo1 = Xlo, Xhi1 = X
     ; true    -> Xlo1 = Xlo, Xhi1 = Xhi
    end,
    if Y < Ylo -> Ylo1 = Y,   Yhi1 = Yhi
     ; Y > Yhi -> Ylo1 = Ylo, Yhi1 = Y
     ; true    -> Ylo1 = Ylo, Yhi1 = Yhi
    end,
    bounding_box(Pts, Xlo1,Xhi1, Ylo1,Yhi1);
bounding_box([], Xlo,Xhi, Ylo,Yhi) ->
    {{Xlo,Ylo}, {Xhi,Yhi}}.

With maximum and minimum operators, this becomes

bounding_box([{X,Y}|Pts], Xlo,Xhi, Ylo,Yhi) ->
    bounding_box(Pts, min(X,Xlo), max(X,Xhi),
              min(Y,Ylo), max(Y,Yhi));
bounding_box([], Xlo,Xhi, Ylo,Yhi) ->
    {{Xlo,Ylo}, {Xhi,Yhi}}.

Backwards Compatibility

No issues. Where a module already has max/2 or min/2, the erlang: prefix is required to get the new function.

Reference Implementation

I don't understand BEAM or the compiler well enough to provide one, but the instruction definitions above are offered as evidence that it should not be hard for those who do. If this EEP is accepted I will be happy to write the documentation for these operators.

Copyright

This document has been placed in the public domain.

Powered by Erlang Web