Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tag: svn-import
Fetching contributors…

Cannot retrieve contributors at this time

199 lines (142 sloc) 6.672 kB
EEP: 30
Title: Maximum and Minimum
Version: $Revision$
Last-Modified: $Date$
Author: Richard A. O'Keefe <ok@cs.otago.ac.nz>
Status: Draft
Type: Standards Track
Erlang-Version: R12B-4
Content-Type: text/plain
Created: 10-Jul-2008
Post-History:
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.
References
http://mathworld.wolfram.com/Lattice.html
Copyright
This document has been placed in the public domain.
Local Variables:
mode: indented-text
indent-tabs-mode: nil
sentence-end-double-space: t
fill-column: 70
coding: utf-8
End:
Jump to Line
Something went wrong with that request. Please try again.