length() in guards

Richard A. O'Keefe ok@REDACTED
Tue Sep 30 03:51:18 CEST 2003


I commented that
(1) while computing length(X) is O(length(X)), which is not a nice thing
    to do in a guard, *comparing* length(X) <relop> N where N is a number    
    can be done in O(min(length(X),N)) time, which is not so bad at all.
(2) an examination of a large amount of existing Erlang code showed that
    most uses were of the safe/fast kind and that other uses could be
    avoided and in avoiding them you would get faster & clearer code anyway.

Bengt Kleberg <Bengt.Kleberg@REDACTED> suggests:
	what about:
	
	is_length_equal( Var, Length )
	is_length_greater( Var, Length )
	is_length_less( Var, Length )
	
	this would make it easier to remember, imho.
	
Well, no.  First, the direct connection between length/1 and what's
happening is severed.  Second, instead of remembering one function and
8 relational operators, I would now have to remember one function and
16 relational operators, which is not good.  Third, the spelling of
"is_length_greater" is arbitrary; my Scheme code uses "length>?" which
conforms to existing Scheme naming conventions, so doesn't require any
special effort of memory.  Fourth, and most important, it's not actually
a compatible change.  Fifth, there is a substantial documentation cost
for adding these guards.
	
Here's what I had in mind.

Step 1:
    Implement if_length_<relop> instructions in BEAM.
Step 2:
    Make the compiler recognise length(X) <relop> E and
    E <relop> length(X) as special cases, and generate the
    new instructions.
Step 3:
    Make the compiler *warn* if there is a use of length/1 in a guard
    that isn't caught by step 2, *but* continue to generate the same
    code as is now generated.
Step 4:
    Encouraged by the warning, people clean up their code.
Step 5:
    You were expecting me to say "turn the warning into an error", maybe?
    No, there is no step 5.

The point is that _existing_ code can benefit from this observation
_without any change at all_.  Code which is unclear/inefficient is
pointed out when you get to step 3, but is never broken.




More information about the erlang-questions mailing list