[RCR] New [] Semantics

[trans. (T. Onoma)]

On Thursday 07 October 2004 10:08 pm, trans. (T. Onoma) wrote:
| val <=> first >/>= 0 && val <=> last </<= 0

Technically that should be:

val <=> first >= 0 && val <=> last </<= 0
^^
T.

 

[Markus]

There are a couple of other small things that would be nice, but these are the
main important ones (IMHO) that I'm interested in solving. Brian and Markus
may have other ideas.

I have lots of other ideas. At present they are drowned out by the
seductive notion that anyone who can get a significant body of C to do
what they want (and no more) must have the patience of a saint or the
perspicacity of a seer. Or both.

That is to say, I'm still trying to get free form operators
working.

As for Ranges, I tend to favour class trees rather than (as matz
prefers) trying to make one tool serve several purposes. I would, for
example, give the Range tribe a family tree much like that of Numeric
(with Float, Bignum, Complex, etc.) where different members fill
different rolls but all work together in harmony.

As I listed before, there are at least four things being done with
ranges (Intervals, Pairs, Point_sets, Iteration_reification (including
circular/end-based indexing) and perhaps others). I would like to see
them teased apart but haven't devoted much effort to doing so myself.

Instead, since that isn't what matz wants, I am exploring my second
option; making it possible for users to flesh out their own hierarchy as
they see fit, without being sent to a syntactic ghetto. Thus my
interest in define-your-own operators. The idea first came up in the
context of Hash, where much the same discussion took place, with some
people wanting finer control over the details of Hash behaviour, while
others liked it being a single type.

My silly hope is that it may be possible to make everyone happy, by
increasing the flexibility of ruby in very specific ways (as discussed a
few weeks back); we may be able to let people play with detailed class
trees without breaking much (if any) existing code. Then, if someone
cooks up a clear winner, that can be considered for inclusion in the
core language.

-- Markus

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|Okay. In summary the problem centers around how to to define #===. When you
|think about that you realize Range is serving two purposes which are not
|perfectly compatible:
|
| 1) a discrete iterative set where .succ on first is used
| as generator and membership is defined like
|
| val <=> succ </<= last
|
| 2) an interval where membership is determined like
|
| val <=> first >= 0 && val <=> last </<= 0

You have shown the behavior. Then, what is the problem?
Please be concrete.

|Another problem is that numeric ranges, which are likely the most commonly
|used by large margin, are *very* slow to determine #member?, --but they don't
|need to be slow.

Being slow IS the problem.

matz.

 

[trans. (T. Onoma)]

On Thursday 07 October 2004 11:42 pm, Yukihiro Matsumoto wrote:
| Hi,
|
| In message "Re: Range behavior (Re: [RCR] New [] Semantics)"
|
| on Fri, 8 Oct 2004 11:08:54 +0900, "trans. (T. Onoma)"
| |Okay. In summary the problem centers around how to to define #===. When
| | you think about that you realize Range is serving two purposes which are
| | not perfectly compatible:
| |
| | 1) a discrete iterative set where .succ on first is used
| | as generator and membership is defined like
| |
| | val <=> succ </<= last
| |
| | 2) an interval where membership is determined like
| |
| | val <=> first >= 0 && val <=> last </<= 0
|
| You have shown the behavior. Then, what is the problem?
| Please be concrete.

Okay. The problem is that Range behavior is contradictory. Maybe this will
help:

def check(a)
case a
when 0..10 then
true
else
false
end
end

check(4.5) # true or false ?

So #=== and case statements have two potential meanings for Range, and both
are useful. Currently the answer is true --indicating a continuous range. But
this is counter to the definition of a Range which, being dependent on #succ,
is actually discrete. HTH.


| |Another problem is that numeric ranges, which are likely the most commonly
| |used by large margin, are *very* slow to determine #member?, --but they
| | don't need to be slow.
|
| Being slow IS the problem.

My problem? Your problem? Or Ruby's Problem?

T.

 

[trans. (T. Onoma)]

08, trans. (T. Onoma) wrote:
| > There are a couple of other small things that would be nice, but these
| > are the main important ones (IMHO) that I'm interested in solving. Brian
| > and Markus may have other ideas.
|
| I have lots of other ideas. At present they are drowned out by the
| seductive notion that anyone who can get a significant body of C to do
| what they want (and no more) must have the patience of a saint or the
| perspicacity of a seer. Or both.

He he. That's why I use Ruby!

| That is to say, I'm still trying to get free form operators
| working.

All power to you! If it can be done, I think it is a very excellent thing for
Ruby to have.

| As for Ranges, I tend to favour class trees rather than (as matz
| prefers) trying to make one tool serve several purposes. I would, for
| example, give the Range tribe a family tree much like that of Numeric
| (with Float, Bignum, Complex, etc.) where different members fill
| different rolls but all work together in harmony.

I think Einstein put is best (parapharsed): make things simple, but not too
simple. In otherwords, its good to have something be multi-purpose, but not
if it interferes with function. [1]

| As I listed before, there are at least four things being done with
| ranges (Intervals, Pairs, Point_sets, Iteration_reification (including
| circular/end-based indexing) and perhaps others). I would like to see
| them teased apart but haven't devoted much effort to doing so myself.

I would tend toward a balance. I think Discrete vs. Continuous is probably is
kludge combined, but I think others can work fine for joint purposes.

| Instead, since that isn't what matz wants, I am exploring my second
| option; making it possible for users to flesh out their own hierarchy as
| they see fit, without being sent to a syntactic ghetto. Thus my
| interest in define-your-own operators. The idea first came up in the
| context of Hash, where much the same discussion took place, with some
| people wanting finer control over the details of Hash behaviour, while
| others liked it being a single type.

I've always wanted some extra operators!

| My silly hope is that it may be possible to make everyone happy, by
| increasing the flexibility of ruby in very specific ways (as discussed a
| few weeks back); we may be able to let people play with detailed class
| trees without breaking much (if any) existing code. Then, if someone
| cooks up a clear winner, that can be considered for inclusion in the
| core language.

Sounds good.

T.

Footnotes:
[1] In fact, I tend to think even Class and Module could be one thing.

---

P.S. Two other (not very important) oddities about Range:

Although as you point out this is at least quite comprehensible, it might
still strike one as odd:

q = 0..3.5
=> 0..3.5
q.member?(3.5)
=> false

I am not sure what causes this:

q = 'a'..200
=> "a"..200
q.member?(100)
NoMethodError: undefined method `>' for false:FalseClass
from (irb):6:in `member?'
from (irb):6

Though it seems a dumb thing to do anyway.

 

[Markus]

| That is to say, I'm still trying to get free form operators
| working.

All power to you! If it can be done, I think it is a very excellent thing for
Ruby to have.

I've fixed the one bug I found in the pre-alpha version. I want to
do some more test cases (and probably put it up on a web page w. the
test cases rather than sending the patch to the list again--though I
never quite know the etiquette). Should have something in about 12
hours, & will post the URL.

Can/do you compile from source? The last version was shaky, but
it's getting better as I pound on it. If possible, I'd like you (or
anyone else who's interested) to test it out. Specifically, I'm
interested in finding any:

* Bug/crashes--I'm aiming for none, of course

* Incompatibility with existing code--I'd like this to break
absolutely nothing. Anything that worked in unpatched ruby
should work the same way with the patch

* Shortfalls in addressing the extensibility goals (i.e., does
this just get us to the next roadblock, or would it be possible
to implement something like Neo_range or Uber_hash with all of
the properties of the built-in classes? I suspect that we're
not there yet, but I'm not sure where the next hurdle is.
Compile-time constructors, probably, but what else?

* Timing/speed issues--in theory my code should be slightly slower
than the original, but I'm not seeing it. It could be that C
programmers just habitually write for speed rather than clarity,
but it is as or more likely I'm missing something.

-- Markus

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|Okay. The problem is that Range behavior is contradictory. Maybe this will
|help:
|
| def check(a)
| case a
| when 0..10 then
| true
| else
| false
| end
| end
|
| check(4.5) # true or false ?
|
|So #=== and case statements have two potential meanings for Range, and both
|are useful. Currently the answer is true --indicating a continuous range. But
|this is counter to the definition of a Range which, being dependent on #succ,
|is actually discrete. HTH.

I don't agree with the word "contradictory". The above function
returning true would have no problem, wouldn't it?

Here's my possible plans:

planA - leave member? and include? as they are; they are very easy
to distinguish, and to remember. why bother?

planB - making member? as alias to include?; they behave same. no
confusion, no problem. who wants membership for ranges?

The planB solves your second problem (slowness) as well.

matz.

 

[Brian Candler]

planA - leave member? and include? as they are; they are very easy
to distinguish, and to remember. why bother?

In this case, also change the documentation of Enumeration to state that
whilst Enumeration#include? and Enumeration#member? do the same thing, that
they are intended for different purposes (and in particular, that
Range#include? is different from Range#member?)

That for me is the biggest problem - confusion caused by the fact that I
expected them to be the same, because Enumerable says they are aliases.

planB - making member? as alias to include?; they behave same. no
confusion, no problem. who wants membership for ranges?

Hmm, actually that's a pretty good idea IMO. Does anyone care to keep
(0..3).member?(2.5) # => false

? I doubt it. There's almost always a direct (non-interative) way to test
that anyway with a Range; nobody wants to iterate for hours to discover
(0..100000000).member?(2.5) # => false

Remember the problem which triggered all this off, was testing ranges with
infinite bounds...

OK, I think that gets my vote.

Cheers,

Brian.

 

[James Edward Gray II]

planA - leave member? and include? as they are; they are very easy
to distinguish, and to remember. why bother?

My opinion is that the only reason people complain about this is the
fact that Enumerable documents them as alias. I believe this to be a
documentation issue, not a language issue.

For what it's worth, I like the current behavior, but I won't lose too
much sleep if it gets changed.

James Edward Gray II

 

[trans. (T. Onoma)]

On Friday 08 October 2004 04:31 am, Yukihiro Matsumoto wrote:
| I don't agree with the word "contradictory". The above function
| returning true would have no problem, wouldn't it?
|
| Here's my possible plans:
|
| planA - leave member? and include? as they are; they are very easy
| to distinguish, and to remember. why bother?
|
| planB - making member? as alias to include?; they behave same. no
| confusion, no problem. who wants membership for ranges?
|
| The planB solves your second problem (slowness) as well.

Okay, planB is good. You are going the other way toward Range being
continuous. That's fine, but really that should be called an Interval:

http://mathworld.wolfram.com/Interval.html

Range really means something else.

T.

 

[Markus]

On Friday 08 October 2004 04:31 am, Yukihiro Matsumoto wrote:
| I don't agree with the word "contradictory". The above function
| returning true would have no problem, wouldn't it?
|
| Here's my possible plans:
|
| planA - leave member? and include? as they are; they are very easy
| to distinguish, and to remember. why bother?
|
| planB - making member? as alias to include?; they behave same. no
| confusion, no problem. who wants membership for ranges?
|
| The planB solves your second problem (slowness) as well.

Okay, planB is good. You are going the other way toward Range being
continuous. That's fine, but really that should be called an Interval:

http://mathworld.wolfram.com/Interval.html

Range really means something else.

Yes, the problem is that it means several something elses (see

http://mathworld.wolfram.com/Range.html

for example). I think the one you are thinking of is "statistical
range" whereas the "image" definition is pretty close to
"interval"--though I do see your point that it need not be continuous,
it also need not be limited to integers or even reals. "integer powers
of Pi less than a thousand" is a range in that sense as well.

-- Markus

 

[trans. (T. Onoma)]

On Friday 08 October 2004 09:43 am, trans. (T. Onoma) wrote:
| Okay, planB is good. You are going the other way toward Range being
| continuous. That's fine, but really that should be called an Interval:
|
| http://mathworld.wolfram.com/Interval.html
|
| Range really means something else.

Following this to logical conclusion. (IMHO) Elegant design would be along
these lines:

class Interval
# not Enumerable
def to_rng
Range[self]
end
def each
# coerce to Range, then each
to_rng.each
end
end

(0..5).class #=> Interval

class Range < Interval
alias :enclose? :include?
include Enumerable
def self.[](*args)
if args[0].kind_of?(Range)
# ...
end
def initialize(start, length)
# ...
end
def each
# based on start#succ
end
end

So a Range is a "temporal" Array, in contrast to an Array which is "spacal"
--if you know what I mean. Also, coercing Interval to Range in #each deals
with most, if not all, compatibility issues (I think). The only thing the
above appears to need is how to handle the disconnect between Interval#end
and Range#length. There's no perfect "congruence", as we have already
discussed, but it shouldn't be difficult to determine this, i.e. I see no
reason Range can't also support termination proc.

T.

 

[trans. (T. Onoma)]

On Friday 08 October 2004 12:41 pm, trans. (T. Onoma) wrote:
| Also, coercing Interval to Range in #each deals
| with most, if not all, compatibility issues (I think).

(well, except for when you compare class)

T.

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|| planA - leave member? and include? as they are; they are very easy
|| to distinguish, and to remember. why bother?
||
|| planB - making member? as alias to include?; they behave same. no
|| confusion, no problem. who wants membership for ranges?

|Okay, planB is good. You are going the other way toward Range being
|continuous.

OK. I will consider taking planB in the future. Would somebody
volunteer to update the RDoc in range.c if I change?

matz.

 

[Randy W. Sims]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|| planA - leave member? and include? as they are; they are very easy
|| to distinguish, and to remember. why bother?
||
|| planB - making member? as alias to include?; they behave same. no
|| confusion, no problem. who wants membership for ranges?

|Okay, planB is good. You are going the other way toward Range being
|continuous.

OK. I will consider taking planB in the future.

FWIW, I respectfully disagree.

irb(main):001:0> (1..5).each {|i| puts i}
1
2
3
4
5
=> 1..5

The range 1..5 above is an ordered Set that contains 5 elements.

The behavior of:

irb(main):002:0> (1..5).include?( 2.5 )
=> true

was a complete suprise to me. It goes against the expectations created
by the first example above.

Thanks for your consideration. I will now sit down and shutup.
Randy.

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|The behavior of:
|
|irb(main):002:0> (1..5).include?( 2.5 )
|=> true
|
|was a complete suprise to me. It goes against the expectations created
|by the first example above.

The point is whether your expectation is

* important enough to keep, even after you've been explained
* worthy for the cost of iteration, such that

(0..1000000000).member?(999999999)

takes seven minutes.

matz.

 

[Randy W. Sims]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|The behavior of:
|
|irb(main):002:0> (1..5).include?( 2.5 )
|=> true
|
|was a complete suprise to me. It goes against the expectations created
|by the first example above.

The point is whether your expectation is

* important enough to keep, even after you've been explained
* worthy for the cost of iteration, such that

(0..1000000000).member?(999999999)

takes seven minutes.

Hmm, I guess I expected Range to be implemented as an ordered set, an
array. Thus Range#member? would be a quick binary search...

Randy.

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|Hmm, I guess I expected Range to be implemented as an ordered set, an
|array. Thus Range#member? would be a quick binary search...

No. It just hold upper and lower bounds, plus a flag for exclusion of
the last element.

matz.

 

[Randy W. Sims]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|Hmm, I guess I expected Range to be implemented as an ordered set, an
|array. Thus Range#member? would be a quick binary search...

No. It just hold upper and lower bounds, plus a flag for exclusion of
the last element.

Ahh, ok. I didn't realize set was implemented in this way. I can see why
you did it: it allows ranges for all types of objects. Very nice.

Even with this, It would still be nice if membership could be tested...
efficiently. Or at least efficient for the common cases. Range could be
special cased for Integers so that a member could be found by
calculating elements for a "binary search" (if (((end - start) / 2) >
target))...

Or better. Some classes could implement an optional method (a mixin
interface?), say find_in_range, so that if the method exists for the
type of objects in the range it is called for an efficient lookup. If
the object does not support the method, it can be done the old way using
obj#succ. This is not as kludgy as I've made it sound. There is
precedent for this type of implementation in many libraries, including
the C++ standard library. This also sort of corresponds to having
different iterator types in C++ where some iterators are more
powerful/functional than others.

Randy.

 

[Brian Candler]

Ahh, ok. I didn't realize set
Range

was implemented in this way. I can see why
you did it: it allows ranges for all types of objects. Very nice.

Range#include? just uses the <=> operator to test for the bottom and top of
the range (in other words, it's intended for objects which are Comparable
rather than Enumberable)

Even with this, It would still be nice if membership could be tested...
efficiently. Or at least efficient for the common cases. Range could be
special cased for Integers so that a member could be found by
calculating elements for a "binary search" (if (((end - start) / 2) >
target))...

You can't do a binary search over an Enumberable, because it just gives you
the elements one at a time in order; it doesn't support "fetch Nth item".
You'd have to first enumerate everything into an Array, which brings you
back to the current situation anyway.

Also, if you really want that sort of membership test with integers, then
there's no need for a binary search anyway:

myrange.include?(x) and x.to_i == x

ISTM that in Ruby, a range is *primarily* a continuous range with lower and
upper bounds. If the lower bound happens to be an object which responds to
'succ' to generate the next object in a sequence, and <=> to match the upper
bound, then magically it also becomes Enumerable.

Regards,

Brian.