This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Fwd: what it means to contain something

34 replies
odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.

The following mail was accidentally sent to Viktor only.
I have just committed a patch that changes WithDefault.get.
I think it's the right thing and that the previous behavior can be
classified as a bug. So I would argue there are no migration issues --
since `m get k' was the same as `Some(m apply k)', nobody who depended
on that behavior would have called it. They would have called `apply'
directly. And nobody would have used a constant `contains' either.

Cheers

soc
Joined: 2010-02-07,
User offline. Last seen 34 weeks 5 days ago.
Re: Fwd: what it means to contain something

Ooops, this should have gone to the mailing list ....

--------------------------------------------

Hi Martin,

> I have just committed a patch that changes WithDefault.get.
> I think it's the right thing and that the previous behavior can be
> classified as a bug. So I would argue there are no migration issues --
> since `m get k' was the same as `Some(m apply k)', nobody who depended
> on that behavior would have called it. They would have called `apply'
> directly. And nobody would have used a constant `contains' either.

I agree, but I'm not really sure if it wouldn't be reasonable to add a
@migration
annotation to the method describing the change and saying that most
people won't be
affected by it.

Bye,

Simon

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: Fwd: what it means to contain something

Yes, I agree. Migration warning is good. Paul, can you have a look at it?

Thanks

ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: what it means to contain something
On Thu, Feb 10, 2011 at 8:27 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
So I would argue there are no migration issues -- 
since `m get k' was the same as `Some(m apply k)', nobody who depended
on that behavior would have called it. They would have called `apply'
directly. And nobody would have used a constant `contains' either.

What if you don't know what the default behavior of your map is (i.e. you want to abstract the two behaviors)?  Needing to know hidden details like whether a default is present seems like a bad idea when one is trying to write safe code.

In particular, there are various mental models of how "get" and "apply" and "contains" are related to each other.  For a normal map, we have the behavior

            contains      get       apply
key present   true     Some(value)  value
key absent    false       None     exception

from which we could infer either of the following:

  x.get(key) == (if (x contains key) x(key) else None)
  x.get(key) == try { Some(x(key)) }
                catch { case NoSuchElementException => None }
 
I'm not going to say which is wrong, but I do think that it's not unreasonable to intuit either case, since they are for all practical purposes equivalent for a map without defaults.  Now we add defaults and get

            contains      get       apply
key present   true     Some(value)  value
key absent    false       ???      default

Clearly, if there's a default then apply had better return it.  And it also seems peculiar that if the entry isn't really in the map that contains shouldn't return it.  So, what to do about get?  If you intuited the first case--get is a shorthand for testing occupancy of the map--then you will probably intuit that you will still get None.  If you intuited the second case--get is a shorthand for mapping apply failures into None--then you will probably intuit that you will get Some(default).

I would argue that the latter interpretation is the slightly more natural one, in that it is unexpected that something could be gotten with an apply but not with a get, even if on closer examination there's a good argument to be made that get really shouldn't return the default value since there is nothing really there to return, and all the other methods that query for whether something is there correctly report only those things that are truly there, not those we only asked for.

  --Rex

Donna Malayeri
Joined: 2009-10-21,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something
I agree with Rex; I find the r24253 patch to be quite unintuitive. I would personally be less surprised if "get" stayed the same (orElse some(default)), and "contains" were different for a map that has a default. It's true that changing "get" automatically changes "contains" to the reasonable semantics, but I don't think it's obvious that "get" should have different behavior than apply.
DOnna
On Feb 10, 2011, at 3:05 PM, Rex Kerr wrote:
On Thu, Feb 10, 2011 at 8:27 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
So I would argue there are no migration issues -- 
since `m get k' was the same as `Some(m apply k)', nobody who depended
on that behavior would have called it. They would have called `apply'
directly. And nobody would have used a constant `contains' either.

What if you don't know what the default behavior of your map is (i.e. you want to abstract the two behaviors)?  Needing to know hidden details like whether a default is present seems like a bad idea when one is trying to write safe code.

In particular, there are various mental models of how "get" and "apply" and "contains" are related to each other.  For a normal map, we have the behavior

            contains      get       apply
key present   true     Some(value)  value
key absent    false       None     exception

from which we could infer either of the following:

  x.get(key) == (if (x contains key) x(key) else None)
  x.get(key) == try { Some(x(key)) }
                catch { case NoSuchElementException => None }
 
I'm not going to say which is wrong, but I do think that it's not unreasonable to intuit either case, since they are for all practical purposes equivalent for a map without defaults.  Now we add defaults and get

            contains      get       apply
key present   true     Some(value)  value
key absent    false       ???      default

Clearly, if there's a default then apply had better return it.  And it also seems peculiar that if the entry isn't really in the map that contains shouldn't return it.  So, what to do about get?  If you intuited the first case--get is a shorthand for testing occupancy of the map--then you will probably intuit that you will still get None.  If you intuited the second case--get is a shorthand for mapping apply failures into None--then you will probably intuit that you will get Some(default).

I would argue that the latter interpretation is the slightly more natural one, in that it is unexpected that something could be gotten with an apply but not with a get, even if on closer examination there's a good argument to be made that get really shouldn't return the default value since there is nothing really there to return, and all the other methods that query for whether something is there correctly report only those things that are truly there, not those we only asked for.

  --Rex


Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: what it means to contain something
How about a new tri-state return type for Map#get?Presumably with an implicit conversion to Option for compatibility...
Something like:
  sealed trait GetResult  case class Contains extends GetResult   case class Default extends GetResult  case class Absent extends GetResult
It seems something that would be useful in a few other situations too.


On 10 February 2011 14:38, Donna Malayeri <lindydonna [at] gmail [dot] com> wrote:
I agree with Rex; I find the r24253 patch to be quite unintuitive. I would personally be less surprised if "get" stayed the same (orElse some(default)), and "contains" were different for a map that has a default. It's true that changing "get" automatically changes "contains" to the reasonable semantics, but I don't think it's obvious that "get" should have different behavior than apply.
DOnna
On Feb 10, 2011, at 3:05 PM, Rex Kerr wrote:
On Thu, Feb 10, 2011 at 8:27 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
So I would argue there are no migration issues -- 
since `m get k' was the same as `Some(m apply k)', nobody who depended
on that behavior would have called it. They would have called `apply'
directly. And nobody would have used a constant `contains' either.

What if you don't know what the default behavior of your map is (i.e. you want to abstract the two behaviors)?  Needing to know hidden details like whether a default is present seems like a bad idea when one is trying to write safe code.

In particular, there are various mental models of how "get" and "apply" and "contains" are related to each other.  For a normal map, we have the behavior

            contains      get       apply
key present   true     Some(value)  value
key absent    false       None     exception

from which we could infer either of the following:

  x.get(key) == (if (x contains key) x(key) else None)
  x.get(key) == try { Some(x(key)) }
                catch { case NoSuchElementException => None }
 
I'm not going to say which is wrong, but I do think that it's not unreasonable to intuit either case, since they are for all practical purposes equivalent for a map without defaults.  Now we add defaults and get

            contains      get       apply
key present   true     Some(value)  value
key absent    false       ???      default

Clearly, if there's a default then apply had better return it.  And it also seems peculiar that if the entry isn't really in the map that contains shouldn't return it.  So, what to do about get?  If you intuited the first case--get is a shorthand for testing occupancy of the map--then you will probably intuit that you will still get None.  If you intuited the second case--get is a shorthand for mapping apply failures into None--then you will probably intuit that you will get Some(default).

I would argue that the latter interpretation is the slightly more natural one, in that it is unexpected that something could be gotten with an apply but not with a get, even if on closer examination there's a good argument to be made that get really shouldn't return the default value since there is nothing really there to return, and all the other methods that query for whether something is there correctly report only those things that are truly there, not those we only asked for.

  --Rex





--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

READ CAREFULLY. By reading this email, you agree, on behalf of your employer, to release me from all obligations and waivers arising from any and all NON-NEGOTIATED  agreements, licenses, terms-of-service, shrinkwrap, clickwrap, browsewrap, confidentiality, non-disclosure, non-compete and acceptable use policies ("BOGUS AGREEMENTS") that I have entered into with your employer, its partners, licensors, agents and assigns, in perpetuity, without prejudice to my ongoing rights and privileges. You further represent that you have the authority to release me from any BOGUS AGREEMENTS on behalf of your employer.
odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: what it means to contain something

On Thu, Feb 10, 2011 at 3:05 PM, Rex Kerr wrote:
> On Thu, Feb 10, 2011 at 8:27 AM, martin odersky
> wrote:
>>
>> So I would argue there are no migration issues --
>>
>> since `m get k' was the same as `Some(m apply k)', nobody who depended
>> on that behavior would have called it. They would have called `apply'
>> directly. And nobody would have used a constant `contains' either.
>
> What if you don't know what the default behavior of your map is (i.e. you
> want to abstract the two behaviors)?  Needing to know hidden details like
> whether a default is present seems like a bad idea when one is trying to
> write safe code.
>
> In particular, there are various mental models of how "get" and "apply" and
> "contains" are related to each other.  For a normal map, we have the
> behavior
>
>             contains      get       apply
> key present   true     Some(value)  value
> key absent    false       None     exception
>
> from which we could infer either of the following:
>
>   x.get(key) == (if (x contains key) x(key) else None)
>   x.get(key) == try { Some(x(key)) }
>                 catch { case NoSuchElementException => None }
>
The problem with that reasoning is that contains and apply are defined
in terms of get and default, not the other way round. And that's not
an implementation detail: get is part of the implementation interface
of a map in that it is an abstract method.

Cheers

Viktor Klang
Joined: 2008-12-17,
User offline. Last seen 1 year 27 weeks ago.
Re: what it means to contain something


On Thu, Feb 10, 2011 at 4:06 PM, Kevin Wright <kev [dot] lee [dot] wright [at] gmail [dot] com> wrote:
How about a new tri-state return type for Map#get?

Something like this?
http://scala-tools.org/mvnsites-snapshots/liftweb/lift-common/scaladocs/net/liftweb/common/Box.html

 
Presumably with an implicit conversion to Option for compatibility...
Something like:
  sealed trait GetResult  case class Contains extends GetResult   case class Default extends GetResult  case class Absent extends GetResult
It seems something that would be useful in a few other situations too.


On 10 February 2011 14:38, Donna Malayeri <lindydonna [at] gmail [dot] com> wrote:
I agree with Rex; I find the r24253 patch to be quite unintuitive. I would personally be less surprised if "get" stayed the same (orElse some(default)), and "contains" were different for a map that has a default. It's true that changing "get" automatically changes "contains" to the reasonable semantics, but I don't think it's obvious that "get" should have different behavior than apply.
DOnna
On Feb 10, 2011, at 3:05 PM, Rex Kerr wrote:
On Thu, Feb 10, 2011 at 8:27 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
So I would argue there are no migration issues -- 
since `m get k' was the same as `Some(m apply k)', nobody who depended
on that behavior would have called it. They would have called `apply'
directly. And nobody would have used a constant `contains' either.

What if you don't know what the default behavior of your map is (i.e. you want to abstract the two behaviors)?  Needing to know hidden details like whether a default is present seems like a bad idea when one is trying to write safe code.

In particular, there are various mental models of how "get" and "apply" and "contains" are related to each other.  For a normal map, we have the behavior

            contains      get       apply
key present   true     Some(value)  value
key absent    false       None     exception

from which we could infer either of the following:

  x.get(key) == (if (x contains key) x(key) else None)
  x.get(key) == try { Some(x(key)) }
                catch { case NoSuchElementException => None }
 
I'm not going to say which is wrong, but I do think that it's not unreasonable to intuit either case, since they are for all practical purposes equivalent for a map without defaults.  Now we add defaults and get

            contains      get       apply
key present   true     Some(value)  value
key absent    false       ???      default

Clearly, if there's a default then apply had better return it.  And it also seems peculiar that if the entry isn't really in the map that contains shouldn't return it.  So, what to do about get?  If you intuited the first case--get is a shorthand for testing occupancy of the map--then you will probably intuit that you will still get None.  If you intuited the second case--get is a shorthand for mapping apply failures into None--then you will probably intuit that you will get Some(default).

I would argue that the latter interpretation is the slightly more natural one, in that it is unexpected that something could be gotten with an apply but not with a get, even if on closer examination there's a good argument to be made that get really shouldn't return the default value since there is nothing really there to return, and all the other methods that query for whether something is there correctly report only those things that are truly there, not those we only asked for.

  --Rex





--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com kev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

READ CAREFULLY. By reading this email, you agree, on behalf of your employer, to release me from all obligations and waivers arising from any and all NON-NEGOTIATED  agreements, licenses, terms-of-service, shrinkwrap, clickwrap, browsewrap, confidentiality, non-disclosure, non-compete and acceptable use policies ("BOGUS AGREEMENTS") that I have entered into with your employer, its partners, licensors, agents and assigns, in perpetuity, without prejudice to my ongoing rights and privileges. You further represent that you have the authority to release me from any BOGUS AGREEMENTS on behalf of your employer.



--
Viktor Klang,
Code Connoisseur
Work:   Scalable Solutions
Code:   github.com/viktorklang
Follow: twitter.com/viktorklang
Read:   klangism.tumblr.com

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: what it means to contain something

On Thu, Feb 10, 2011 at 4:06 PM, Kevin Wright wrote:
> How about a new tri-state return type for Map#get?
> Presumably with an implicit conversion to Option for compatibility...
> Something like:
>   sealed trait GetResult
>   case class Contains extends GetResult
>   case class Default extends GetResult
>   case class Absent extends GetResult
> It seems something that would be useful in a few other situations too.
>
Please! Let's not over-design here. Besides get is part of the
implementation contract of map, we can't simply redefine it without
forcing a rewrite of implementations.

Cheers

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: what it means to contain something


On 10 February 2011 15:13, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
On Thu, Feb 10, 2011 at 4:06 PM, Kevin Wright <kev [dot] lee [dot] wright [at] gmail [dot] com> wrote:
> How about a new tri-state return type for Map#get?
> Presumably with an implicit conversion to Option for compatibility...
> Something like:
>   sealed trait GetResult
>   case class Contains extends GetResult
>   case class Default extends GetResult
>   case class Absent extends GetResult
> It seems something that would be useful in a few other situations too.
>
Please! Let's not over-design here. Besides get is part of the
implementation contract of map, we can't simply redefine it without
forcing a rewrite of implementations.

Cheers

Paul Phillips 2
Joined: 2011-02-10,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

On 2/10/11 8:18 AM, Kevin Wright wrote:
> If we can't split Some(x) as returned from get into two distinct types,
> then how about two distinct methods? 'get' and 'getNonDefault'
> `contains` could undergo the same treatment, producing `containsNonDefault`
>
> That would preserve existing code, keep binary compatibility, not
> over-engineer a new tri-value type, and still allow Map users to
> disambiguate default values if required.

If I'm following the proposed change, you can already write a tri-state
map wrapper.

(map get key) match {
case Some(v) => NotDefault(v)
case _ =>
try DefaultValue(map(v))
catch { case _: NoSuchElementException => Absent }
}

So it throws the occasional slow exception. In a billion years, who's
going to care.

Paul Phillips 2
Joined: 2011-02-10,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

On 2/10/11 6:56 AM, martin odersky wrote:
> The problem with that reasoning is that contains and apply are defined
> in terms of get and default, not the other way round. And that's not
> an implementation detail: get is part of the implementation interface
> of a map in that it is an abstract method.

Although I fully agree that there is no obviously correct answer when
considered as a black box, I think this is the runaway reasoning winner
when we have to deal with what is. The abstract method from which all
else is derived is get. So get must communicate something meaningful
for the other pieces to fall into place. get is where this distinction
should be drawn.

I also agree with everyone about the impact: that it makes no sense to
have been relying on the behavior of get or contains in the presence of
a default, and that people will have been (unintentionally or otherwise)
anyway. So changing get and adding a migration warning looks the best
to me.

That, and polishing up and better advertising the existence of
migration. It's my fault, but for 2.8.x I think you had to be pretty
plugged in to be aware of it.

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: what it means to contain something
On Thu, Feb 10, 2011 at 15:45, Paul Phillips <paul [dot] phillips [at] gmail [dot] com> wrote:
On 2/10/11 6:56 AM, martin odersky wrote:
The problem with that reasoning is that contains and apply are defined
in terms of get and default, not the other way round. And that's not
an implementation detail: get is part of the implementation interface
of a map in that it is an abstract method.

Although I fully agree that there is no obviously correct answer when considered as a black box, I think this is the runaway reasoning winner when we have to deal with what is.  The abstract method from which all else is derived is get.  So get must communicate something meaningful for the other pieces to fall into place.  get is where this distinction should be drawn.

I also agree with everyone about the impact: that it makes no sense to have been relying on the behavior of get or contains in the presence of a default, and that people will have been (unintentionally or otherwise) anyway.  So changing get and adding a migration warning looks the best to me.

That, and polishing up and better advertising the existence of migration.  It's my fault, but for 2.8.x I think you had to be pretty plugged in to be aware of it.

I'm concerned that the most likely place for something to go wrong is maps with defaults being passed to code that expects maps. The code being called might well use get or contains, because it doesn't rely on map having a default, and the migration warning will be useless to deal with it.

I'd rather the migration warning is also put on WithDefault itself, or perhaps the withDefault/withDefaultValue methods, or wherever it can be seen by anyone using a map with default.

--
Daniel C. Sobral

I travel to the future all the time.
Paul Phillips 2
Joined: 2011-02-10,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

On 2/10/11 10:29 AM, Daniel Sobral wrote:
> I'm concerned that the most likely place for something to go wrong is
> maps with defaults being passed to code that expects maps. The code
> being called might well use get or contains, because it doesn't rely on
> map having a default, and the migration warning will be useless to deal
> with it.

Really the more I chew on it the more nervous it makes me. I feel good
that it is the right change to make, but I would like to feel a lot
better about the possible impact on existing code.

jibal
Joined: 2010-12-01,
User offline. Last seen 1 year 45 weeks ago.
Re: what it means to contain something
On Thu, Feb 10, 2011 at 10:29 AM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Thu, Feb 10, 2011 at 15:45, Paul Phillips <paul [dot] phillips [at] gmail [dot] com> wrote:
On 2/10/11 6:56 AM, martin odersky wrote:
The problem with that reasoning is that contains and apply are defined
in terms of get and default, not the other way round. And that's not
an implementation detail: get is part of the implementation interface
of a map in that it is an abstract method.

Although I fully agree that there is no obviously correct answer when considered as a black box, I think this is the runaway reasoning winner when we have to deal with what is.  The abstract method from which all else is derived is get.  So get must communicate something meaningful for the other pieces to fall into place.  get is where this distinction should be drawn.

I also agree with everyone about the impact: that it makes no sense to have been relying on the behavior of get or contains in the presence of a default, and that people will have been (unintentionally or otherwise) anyway.  So changing get and adding a migration warning looks the best to me.

That, and polishing up and better advertising the existence of migration.  It's my fault, but for 2.8.x I think you had to be pretty plugged in to be aware of it.

I'm concerned that the most likely place for something to go wrong is maps with defaults being passed to code that expects maps. The code being called might well use get or contains, because it doesn't rely on map having a default, and the migration warning will be useless to deal with it.

Indeed. And more than that: get has always been a safe apply, but now for Map withDefault you have to use apply instead to get default values. How can one write polymorphic code that handles either Map with or without withDefault? get no longer gets, it gets only non-default values, and there's no safe way to get either default or non-default values. That's untenable semantics. It seems to me that you are forced to go with something like Kevin's getNonDefault suggestion, and define apply and contains in terms of that, rather than get.

-- Jim
jibal
Joined: 2010-12-01,
User offline. Last seen 1 year 45 weeks ago.
Re: what it means to contain something
On Thu, Feb 10, 2011 at 6:26 PM, Jim Balter <Jim [at] balter [dot] name> wrote:
On Thu, Feb 10, 2011 at 10:29 AM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Thu, Feb 10, 2011 at 15:45, Paul Phillips <paul [dot] phillips [at] gmail [dot] com> wrote:
On 2/10/11 6:56 AM, martin odersky wrote:
The problem with that reasoning is that contains and apply are defined
in terms of get and default, not the other way round. And that's not
an implementation detail: get is part of the implementation interface
of a map in that it is an abstract method.

Although I fully agree that there is no obviously correct answer when considered as a black box, I think this is the runaway reasoning winner when we have to deal with what is.  The abstract method from which all else is derived is get.  So get must communicate something meaningful for the other pieces to fall into place.  get is where this distinction should be drawn.

I also agree with everyone about the impact: that it makes no sense to have been relying on the behavior of get or contains in the presence of a default, and that people will have been (unintentionally or otherwise) anyway.  So changing get and adding a migration warning looks the best to me.

That, and polishing up and better advertising the existence of migration.  It's my fault, but for 2.8.x I think you had to be pretty plugged in to be aware of it.

I'm concerned that the most likely place for something to go wrong is maps with defaults being passed to code that expects maps. The code being called might well use get or contains, because it doesn't rely on map having a default, and the migration warning will be useless to deal with it.

Indeed. And more than that: get has always been a safe apply, but now for Map withDefault you have to use apply instead to get default values. How can one write polymorphic code that handles either Map with or without withDefault? get no longer gets, it gets only non-default values, and there's no safe way to get either default or non-default values. That's untenable semantics. It seems to me that you are forced to go with something like Kevin's getNonDefault suggestion, and define apply and contains in terms of that, rather than get.

Sorry, only contains needs to be defined in terms of getNonDefault; apply would still be defined in terms of get. OTOH, if get is redefined in withDefault to return None when there's no non-default value, apply must also be redefined there.
 

-- Jim

Stefan Wachter
Joined: 2009-09-18,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

Wouldn't it be possible to drop support for maps with defaults? It seems
that no really convincing solution exists that behaves consistently in
all situations.

Cheer

Stefan

On 02/10/2011 07:50 PM, Paul Phillips wrote:
> On 2/10/11 10:29 AM, Daniel Sobral wrote:
>> I'm concerned that the most likely place for something to go wrong is
>> maps with defaults being passed to code that expects maps. The code
>> being called might well use get or contains, because it doesn't rely on
>> map having a default, and the migration warning will be useless to deal
>> with it.
>
> Really the more I chew on it the more nervous it makes me. I feel
> good that it is the right change to make, but I would like to feel a
> lot better about the possible impact on existing code.
>

Donna Malayeri
Joined: 2009-10-21,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something
I strongly agree with both Paul and Daniel. I brought up the topic in Tuesday's LAMP meeting to see if any others were also concerned with the recent commit, and this was indeed the case. 

Some observations:a) The scaladoc for `MapLike.contains` says nothing about defaults and how they affect the return value of `contains`. 
b) I think that more than a few programmers would consider `get` to be a "safe" version of `apply` (i.e., one that never throws an exception), so it is somewhat non-intuitive that when `get` returns None, `apply` might still return a value. If this this intuition is false, then it is clumsy to uniformly use a map which may or may not have a default value. (Is there a way other than trying to `apply` and then catching the possible exception?)
c) The scaladoc for `get` does not mention default values. Since the implementation of `get` previously did use defaults, then there is probably some code that depends on this. d) A migration warning is insufficient!  As Daniel mentioned, a client may pass a map with a default value to library code that is supposed to be agnostic about default values. So, the migration warning would need to be extremely non-local in order to catch all cases (and afaik the current migration warning infrastructure does not even handle such analyses.)
Therefore, I propose two solutions, in order of preference:1) `contains` should stay as it is, as a constant function.     a) There could be an additional method to test containment not considering default. (I believe Paul had some pithy suggestion.)
    b) Such a method is not added.
2) `contains` returns true iff the map contains an actual binding for the key (i.e., not considering defaults). However, `get` will always return `Some` if a map has a default. One downside is that the implementation of `contains` must change. But, the interface of `contains` is currently not clear on the fact that its behavior is defined in terms of `get`--so this is not a clear interface vs. implementation issue.

I would *strongly* prefer to go back to state (1b) rather than have `get` ignore defaults and potentially break lots of code.
Donna
On Thursday, February 10, 2011 7:50:34 PM UTC+1, Paul Phillips wrote:
On 2/10/11 10:29 AM, Daniel Sobral wrote:
> I'm concerned that the most likely place for something to go wrong is
> maps with defaults being passed to code that expects maps. The code
> being called might well use get or contains, because it doesn't rely on
> map having a default, and the migration warning will be useless to deal
> with it.

Really the more I chew on it the more nervous it makes me.  I feel good
that it is the right change to make, but I would like to feel a lot
better about the possible impact on existing code.

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: what it means to contain something

I believe it's a matter of concenptual simplicity.

In my change proposal

- a map consists of a finite set of key/value pairs, plus a default
expression (which itself is by default { throw new
NoSuchElementException })

- get is the characteristic function of a map: it gives you Some(v)
where v is the value associated with a key if present, None otherwise.

- apply, contains, keySet, iterator are all defined by simple
operations over this model, which is given by get + default.

- withDefault is the same as creating a new map and overriding the
default method.

I have not seen a proposal that accounts for all of
get/apply/keySet/iterator/withDefault/override default without
complicating matters greatly.

Complicated is bad, so we should simplify.

The problem is obviously backwards compatibility. But the time window
where we had withDefault was fairly small, AFAIK it was introduced in
2.8.
So I really hope it is possible to correct now, without being caught
in the legacy tarpit.

Cheers

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: what it means to contain something
How about a slight change of my previous suggestion then.  In addition to `get` and `contains` we could add `defaultAwareGet` and `containsNotDefault`
`get` would still ignore defaults and `contains` would still recognise them.  There's then no need to change any existing methods, and we won't have to rely on exceptions as an expected return value.
keySet and iterator should also be ignorant to default values.  Given some Map[Int,T], where would such an iterator start?  The only possibility would have to be Int.MinValue, for a Map keyed on an unbounded Ref type there's no valid answer.



On 17 February 2011 15:38, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
I believe it's a matter of concenptual simplicity.

In my change proposal

 - a map consists of a finite set of key/value pairs, plus a default
expression (which itself is by default { throw new
NoSuchElementException })

 - get is the characteristic function of a map: it gives you Some(v)
where v is the value associated with a key if present, None otherwise.

 - apply, contains, keySet, iterator are all defined by simple
operations over this model, which is given by get + default.

 - withDefault is the same as creating a new map and overriding the
default method.

I have not seen a proposal that accounts for all of
get/apply/keySet/iterator/withDefault/override default without
complicating matters greatly.

Complicated is bad, so we should simplify.

The problem is obviously backwards compatibility. But the time window
where we had withDefault was fairly small, AFAIK it was introduced in
2.8.
So I really hope it is possible to correct now, without being caught
in the legacy tarpit.

Cheers

Rafael de F. Fe...
Joined: 2010-05-12,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

On Thu, Feb 17, 2011 at 11:55 AM, Donna Malayeri wrote:
> I strongly agree with both Paul and Daniel. I brought up the topic in
> Tuesday's LAMP meeting to see if any others were also concerned with the
> recent commit, and this was indeed the case.
>
> Some observations:
> a) The scaladoc for `MapLike.contains` says nothing about defaults and how
> they affect the return value of `contains`.
> b) I think that more than a few programmers would consider `get` to be a
> "safe" version of `apply` (i.e., one that never throws an exception), so it
> is somewhat non-intuitive that when `get` returns None, `apply` might still
> return a value. If this this intuition is false, then it is clumsy to
> uniformly use a map which may or may not have a default value. (Is there a
> way other than trying to `apply` and then catching the possible exception?)
> c) The scaladoc for `get` does not mention default values. Since the
> implementation of `get` previously did use defaults, then there is probably
> some code that depends on this.
> d) A migration warning is insufficient!  As Daniel mentioned, a client may
> pass a map with a default value to library code that is supposed to be
> agnostic about default values. So, the migration warning would need to be
> extremely non-local in order to catch all cases (and afaik the current
> migration warning infrastructure does not even handle such analyses.)
> Therefore, I propose two solutions, in order of preference:
> 1) `contains` should stay as it is, as a constant function.
>     a) There could be an additional method to test containment not
> considering default. (I believe Paul had some pithy suggestion.)
>     b) Such a method is not added.
> 2) `contains` returns true iff the map contains an actual binding for the
> key (i.e., not considering defaults). However, `get` will always return
> `Some` if a map has a default. One downside is that the implementation of
> `contains` must change. But, the interface of `contains` is currently not
> clear on the fact that its behavior is defined in terms of `get`--so this is
> not a clear interface vs. implementation issue.
>
> I would *strongly* prefer to go back to state (1b) rather than have `get`
> ignore defaults and potentially break lots of code.

+1

> Donna
> On Thursday, February 10, 2011 7:50:34 PM UTC+1, Paul Phillips wrote:
>>
>> On 2/10/11 10:29 AM, Daniel Sobral wrote:
>> > I'm concerned that the most likely place for something to go wrong is
>> > maps with defaults being passed to code that expects maps. The code
>> > being called might well use get or contains, because it doesn't rely on
>> > map having a default, and the migration warning will be useless to deal
>> > with it.
>>
>> Really the more I chew on it the more nervous it makes me.  I feel good
>> that it is the right change to make, but I would like to feel a lot
>> better about the possible impact on existing code.
>

Donna Malayeri
Joined: 2009-10-21,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something
Kevin, your approach seems confusing. In the current revision, `get` does not ignore defaults, nor does `contains`. In 2.8.1, `get` considered defaults, and so did `contains`. What you're suggesting is an odd mix between the two, and I don't see any advantage to this.
That said, adding one of your proposed methods might be a good option, say `getOrDefault` (i.e., your `defaultAwareGet`). This would be like a safe `apply`, which would return None if no default were set. 
Martin, I have changed my mind and I now agree with you--I had thought that withDefault had been introduced prior to 2.8. However, it would be nice to add support for defaults somewhere in the Map interface, such as by adding `getOrDefault.` (Obviously anyone can write such a method in a subclass, but having it in the interface allows all clients to use consider a map's default value if they wish to, without having to use `apply` and providing an exception handler.)
Donna
On Feb 17, 2011, at 4:58 PM, Kevin Wright wrote:
How about a slight change of my previous suggestion then.  In addition to `get` and `contains` we could add `defaultAwareGet` and `containsNotDefault`
`get` would still ignore defaults and `contains` would still recognise them.  There's then no need to change any existing methods, and we won't have to rely on exceptions as an expected return value.
keySet and iterator should also be ignorant to default values.  Given some Map[Int,T], where would such an iterator start?  The only possibility would have to be Int.MinValue, for a Map keyed on an unbounded Ref type there's no valid answer.
On 17 February 2011 15:38, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
The problem is obviously backwards compatibility. But the time window
where we had withDefault was fairly small, AFAIK it was introduced in
2.8.
So I really hope it is possible to correct now, without being caught
in the legacy tarpit.

Paul Phillips 2
Joined: 2011-02-10,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

No time to write much, but I suggest neither contains nor get should be
aware of defaults, and that the methods we can use to make everyone
happy are

withWeakDefault
withStrongDefault

If it's not obvious, a weak default doesn't register with get and other
non-applies, and a strong default does.

The reason I say neither get nor contains should be aware of defaults is
that the creator of a map is the one who should decide the semantics.
The creator is the one anyway, because if they don't like these methods
they'll just override get, contains, apply, etc.

Ruediger Keller 2
Joined: 2010-04-30,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

It seems to me that the semantics of a "default map" are confusing and
inconsistent, no matter what compromises are being discussed on the
list. That probably stems from the fact that the current
implementation changes the behavior of existing methods, instead of
only adding new methods. I think the Liskov substitution principle
applies here.

Therefore I am in favor of changing the default map trait so that it
only adds additional methods with default semantics, instead of
changing any of the preexisting methods.

Regards,
Ruediger

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: what it means to contain something


On 17 February 2011 16:12, Donna Malayeri <lindydonna [at] gmail [dot] com> wrote:
Kevin, your approach seems confusing. In the current revision, `get` does not ignore defaults, nor does `contains`. In 2.8.1, `get` considered defaults, and so did `contains`. What you're suggesting is an odd mix between the two, and I don't see any advantage to this.

I was building on Martin's proposal that `get` should be ignorant of defaults while everything else uses them. (though I believe it's an oversight to suggest that keySet and iterator could be default-aware).  Originally I suggested `getNotDefault` and `containsNotDefault` to work alongside the current 2.8.1 behaviour (where `get` does use default values).
Personally, I could live with either the current or Martin's proposed `get` behaviour, just so long as a method exists with the corresponding alternative. 
That said, adding one of your proposed methods might be a good option, say `getOrDefault` (i.e., your `defaultAwareGet`). This would be like a safe `apply`, which would return None if no default were set. 

I ruled out `getOrDefault` as a name, it sounds far too much like `getOrElse` - implying that the supplied parameter is the default value to use if get fails.  
Martin, I have changed my mind and I now agree with you--I had thought that withDefault had been introduced prior to 2.8. However, it would be nice to add support for defaults somewhere in the Map interface, such as by adding `getOrDefault.` (Obviously anyone can write such a method in a subclass, but having it in the interface allows all clients to use consider a map's default value if they wish to, without having to use `apply` and providing an exception handler.)
Donna
On Feb 17, 2011, at 4:58 PM, Kevin Wright wrote:
How about a slight change of my previous suggestion then.  In addition to `get` and `contains` we could add `defaultAwareGet` and `containsNotDefault`
`get` would still ignore defaults and `contains` would still recognise them.  There's then no need to change any existing methods, and we won't have to rely on exceptions as an expected return value.
keySet and iterator should also be ignorant to default values.  Given some Map[Int,T], where would such an iterator start?  The only possibility would have to be Int.MinValue, for a Map keyed on an unbounded Ref type there's no valid answer.
On 17 February 2011 15:38, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
The problem is obviously backwards compatibility. But the time window
where we had withDefault was fairly small, AFAIK it was introduced in
2.8.
So I really hope it is possible to correct now, without being caught
in the legacy tarpit.




--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com kev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: what it means to contain something
On Thu, Feb 17, 2011 at 10:38 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
I believe it's a matter of concenptual simplicity.

In my change proposal

 - a map consists of a finite set of key/value pairs, plus a default
expression (which itself is by default { throw new
NoSuchElementException })

 - get is the characteristic function of a map: it gives you Some(v)
where v is the value associated with a key if present, None otherwise.

 - apply, contains, keySet, iterator are all defined by simple
operations over this model, which is given by get + default.

 - withDefault is the same as creating a new map and overriding the
default method.

I have not seen a proposal that accounts for all of
get/apply/keySet/iterator/withDefault/override default without
complicating matters greatly.

Complicated is bad, so we should simplify.

I fully agree.  Unfortunately, the solution where apply(x) != get(x).get is complicated.  That, I think, is one of the more complicated things to do because it requires a new mental rule where there was previously an equivalence.  I don't think the fact that the overridable default method worked this way argues that it's any simpler.

The two invariants that are in conflict are

  forall(x) { m.get(x) === m.filter(_._1 == x).headOption }
  forall(x) { m.get(x).get === m(x) }

(where "===" is an imaginary operator that tests equality in the case of normal termination, and otherwise returns true if both sides threw an exception).

If we maintain the former, we declare that "get" is intrinsically a collectiony not an elementy type of thing to do, that defaults are elements, and that there exists no safe abstracted way within collections to deal with elements.

If we maintain the latter, we declare that "get" is intrinsically an elementy type of operation, except that it is safe, but that get and collections methods may return different answers.

So really the question is: what is the point of default?  Is its sole role to avoid throwing an exception upon a misdirected apply (that is, it's basically a type of error condition)?  If yes, this should be documented very clearly, since violating the second invariant I listed is quite a surprise.  And even then it's not so useful, because there's no trait that goes along with it, so you just have to try it and find out whether you'll be bitten or not--which is something that I would advise that people avoid as much as possible (reserve for special cases, or defensively against badly-written code that is throwing too many exceptions and thus slowing things down too much).

On Thu, Feb 17, 2011 at 11:26 AM, Paul Phillips <paul [dot] phillips [at] gmail [dot] com> wrote:
No time to write much, but I suggest neither contains nor get should be aware of defaults, and that the methods we can use to make everyone happy are

 withWeakDefault
 withStrongDefault

If it's not obvious, a weak default doesn't register with get and other non-applies, and a strong default does.

That would work, not least because it would be the best documentation possible that this issue exists and that one had better make one's assumptions explicit.  I hate to make the API larger, but if it was worth going from one to three methods to make things easier but confusing, it's worth going from three to four or five to make them clear again.

  --Rex

Aleksandar Prokopec
Joined: 2010-04-04,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

1) I would recommend against introducing two versions of withDefault.
This automatically means having to define the following 4 methods in the
base collections package: withStrongDefault, withStrongDefaultValue,
withWeakDefault, withWeakDefaultValue.
Then, it means redefining all 4 in the mutable and immutable packages,
and this seems like a lot of logic.
The second reason is the added complexity - it may be hard to pick up
the right with*Default and be aware of what it means - should we have
distinct subtypes for weak and strong defaults as well? I'm not sure
what would be the gains.

2) I agree that once a programmer creates a map with a default, he
should not call a constant `contains` or `get` for that matter. But if
converted to a plain `Map[T]` and fed to existing code which may depend
on the fact that if `contains` is `false`, `apply` will throw, it will
break things.

3) I would recommend against the 3-state return type or using the
exception mechanism to distinguish between the cases. This seems like a
lot of magic. I believe things should be kept simple, but that's just me.

My concerns are - breaking existing code. Places where that could happen
include default maps. The question is how often default maps were used.
I would say not that often, but I don't really know for sure. It might
be safe to make the change with a migration warning.

After reading it carefully, I agree with Martin's proposal. I think it
makes sense, as it could only break the use of default maps in existing
code.

So, I propose the following:

a) deprecate default maps altogether, and define a new type of default
maps, say `DefaultedMap` (or whatever name is appropriate) which are
implemented according to the latest changes which change the semantics
of `get` and `contains`. Then add `withDefaulted*` methods to create
such maps.
[optionally] b) Add a marker method to distinguish a map which has a
default value.
c) Finally, clearly document the contract for the new `DefaultedMap`s,
and use them forever after.

Effects: existing code involving `withDefault` will still work but get a
deprecation warning.
Any new code will use `withDefaulted` (or whatever the name) and rely on
the new contract.
[optionally] And users of maps can programatically check what they're
dealing with.

The only problem may still, however, be with the "legacy" code mentioned
above in 2), which deals with the `Map` interface and may not be
written with awareness of the new well documented connection between
`contains`, `apply` and `get`.
But, we such code would need to be changed anyway.

Cheers,
Alex

P.S. Martin, what did you mean by iterators being defined in terms of
"get+default"? Did you mean that they iterate over the pairs with keys
for which get does not return a `None` (and the same for `keySet`)? This
was my understanding.

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: what it means to contain something

On Thu, Feb 17, 2011 at 6:22 PM, Rex Kerr wrote:
> On Thu, Feb 17, 2011 at 10:38 AM, martin odersky
> wrote:
>>
>> I believe it's a matter of concenptual simplicity.
>>
>> In my change proposal
>>
>>  - a map consists of a finite set of key/value pairs, plus a default
>> expression (which itself is by default { throw new
>> NoSuchElementException })
>>
>>  - get is the characteristic function of a map: it gives you Some(v)
>> where v is the value associated with a key if present, None otherwise.
>>
>>  - apply, contains, keySet, iterator are all defined by simple
>> operations over this model, which is given by get + default.
>>
>>  - withDefault is the same as creating a new map and overriding the
>> default method.
>>
>> I have not seen a proposal that accounts for all of
>> get/apply/keySet/iterator/withDefault/override default without
>> complicating matters greatly.
>>
>> Complicated is bad, so we should simplify.
>
> I fully agree.  Unfortunately, the solution where apply(x) != get(x).get is
> complicated.  That, I think, is one of the more complicated things to do
> because it requires a new mental rule where there was previously an
> equivalence.  I don't think the fact that the overridable default method
> worked this way argues that it's any simpler.
>

Just to clarify:

> The two invariants that are in conflict are
>
>   forall(x) { m.get(x) === m.filter(_._1 == x).headOption }

That one does not hold in 2.8.1, but would hold in my proposal.
Another equality like this which does not hold now but would hold in
my proposal is:

m.keySet contains x === m.iterator map (_._1) contains x

>   forall(x) { m.get(x).get === m(x) }
>
That one does not hold (either now or in the past), because you can
override default.

> So really the question is: what is the point of default?  Is its sole role
> to avoid throwing an exception upon a misdirected apply (that is, it's
> basically a type of error condition)?  If yes, this should be documented
> very clearly, since violating the second invariant I listed is quite a
> surprise.  And even then it's not so useful, because there's no trait that
> goes along with it, so you just have to try it and find out whether you'll
> be bitten or not--which is something that I would advise that people avoid
> as much as possible (reserve for special cases, or defensively against
> badly-written code that is throwing too many exceptions and thus slowing
> things down too much).

I use default a lot, and think it's very useful. It's precisely if you
do not want to deal with the boilerplate of dealing with missing
elements because keys you
know a good default value. An example is any map of keys to sets of
values. It makes perfect sense to associate the empty set with every
missing key. Dealing with such a much is much smoother than having to
deal with missing keys explicitly.

Cheers

Seth Tisue
Joined: 2008-12-16,
User offline. Last seen 34 weeks 3 days ago.
Re: what it means to contain something

>>>>> "martin" == martin odersky writes:

martin> The problem is obviously backwards compatibility. But the time
martin> window where we had withDefault was fairly small, AFAIK it was
martin> introduced in 2.8.

2.7 didn't have withDefault, but it did have withDefaultValue:

Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).
scala> Map(1 -> 2).withDefaultValue(5).apply(3)
res0: Int = 5
scala> Map(1 -> 2).withDefaultValue(5).contains(3)
res2: Boolean = false
scala> Map(1 -> 2).withDefaultValue(5).get(3)
res1: Option[Int] = None

On 2.8 the last answer is instead Some(3).

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: what it means to contain something
On Thu, Feb 17, 2011 at 15:59, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
>   forall(x) { m.get(x).get === m(x) }
>

That one does not hold (either now or in the past), because you can
override default.

Well, get is defined like this:

def get(key: A) = underlying.get(key) orElse Some(default(key))

So I don't see how overriding default would change that equation.

In any case, I have two main concerns:

1. There must be a "safe apply" method on Map which can be fed a Map.WithDefault, otherwise the usefulness of Map decreases a lot.

To me, "contains" and "get", as they are today, are just right. That an iterable will not contain all keys is unfortunate, but I'd rather solve this in some other fashion (ie, introducing methods that ignore defaults). Still, if a safe-get and defaulted-contains gets introduced in Map, I can live with that.

2. As the change currently stands, not everyone who needs them will get the migration warnings. For example:

val m: Map[Int, Int] = Map(1 -> 2).withDefault(_+1)
m.get(0)

On the other hand, the same change _already_ happened from 2.7 to 2.8, as Seth Tisue just pointed out, and neither of these two points (in reverse) were addressed then.

--
Daniel C. Sobral

I travel to the future all the time.
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: what it means to contain something
On Thu, Feb 17, 2011 at 16:09, Seth Tisue <seth [at] tisue [dot] net> wrote:
>>>>> "martin" == martin odersky <martin [dot] odersky [at] epfl [dot] ch> writes:

 martin> The problem is obviously backwards compatibility. But the time
 martin> window where we had withDefault was fairly small, AFAIK it was
 martin> introduced in 2.8.

2.7 didn't have withDefault, but it did have withDefaultValue:

Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).
scala> Map(1 -> 2).withDefaultValue(5).apply(3)
res0: Int = 5
scala> Map(1 -> 2).withDefaultValue(5).contains(3)
res2: Boolean = false
scala> Map(1 -> 2).withDefaultValue(5).get(3)
res1: Option[Int] = None

On 2.8 the last answer is instead Some(3).

And the second is true:

Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_22).
Type in expressions to have them evaluated.
Type :help for more information.

scala> Map(1 -> 2).withDefaultValue(5).apply(3)
res3: Int = 5

scala> Map(1 -> 2).withDefaultValue(5).contains(3)
res4: Boolean = true

scala> Map(1 -> 2).withDefaultValue(5).get(3)
res5: Option[Int] = Some(5)
 
--
Daniel C. Sobral

I travel to the future all the time.
Johannes Rudolph 2
Joined: 2010-02-12,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

Perhaps we should think about what a Map is on a higher level first.

Looking at the ScalaDocs of MapLike a Map is both:
1. something which associates keys with values (manifested by
inheriting PartialFunction[A, B])
2. a list of (key, value) bindings (manifested by inheriting
IterableLike[(A, B)])

Classifying the methods in questions two one of those two traits of a
Map by their current Scaladoc descriptions:

apply => 1 "Retrieves the value which is associated with the given
key." (Function1)
get => 1 "Optionally returns the value associated with a key" (MapLike)
contains => 2 "Tests whether this map contains a binding for a key." (MapLike)
isDefinedAt => 2 "Tests whether this map contains a binding for a key.
This method [...] is equivalent to contains" (PartialFunction)
filter => 2 "Selects all elements of this map which satisfy a predicate"
keySet => 2 "Collects all keys of this map in a set."

Just by looking at this list, you can see one possible conflict in the
definition of apply and isDefinedAt, which are both methods of
PartialFunction and which only work correctly if the relation between
Traits A and B is fixed, so that there exists a binding for each
possible association. IMO, implicitly, that's a promise which the
trait MapLike makes (and as I understood Martin, which should be kept
by refering to MapLike being defined in terms of `get`).

Obviously, a map with default values can't fulfill this promise and as
such shouldn't inherit from MapLike in its current form.

I have no constructive suggestion yet, but I don't think this problem
is solvable solely by focusing on fixing singular points which may
fail without thinking generally about the things that can fail when
one uses a Map as one of the things it represents by inheritance. IMO
multiple inheritance gone wrong is at the heart of this issue.

Johannes

On Thu, Feb 17, 2011 at 7:22 PM, Daniel Sobral wrote:
> On Thu, Feb 17, 2011 at 16:09, Seth Tisue wrote:
>>
>> >>>>> "martin" == martin odersky writes:
>>
>>  martin> The problem is obviously backwards compatibility. But the time
>>  martin> window where we had withDefault was fairly small, AFAIK it was
>>  martin> introduced in 2.8.
>>
>> 2.7 didn't have withDefault, but it did have withDefaultValue:
>>
>> Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM,
>> Java 1.6.0_22).
>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>> res0: Int = 5
>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>> res2: Boolean = false
>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>> res1: Option[Int] = None
>>
>> On 2.8 the last answer is instead Some(3).
>
> And the second is true:
>
> Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM,
> Java 1.6.0_22).
> Type in expressions to have them evaluated.
> Type :help for more information.
>
> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
> res3: Int = 5
>
> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
> res4: Boolean = true
>
> scala> Map(1 -> 2).withDefaultValue(5).get(3)
> res5: Option[Int] = Some(5)
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>

John Nilsson
Joined: 2008-12-20,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

I've also had this line of thinking.

First of all. The fact that this thread hasn't reached an obvious
conclusion yet is evidence that a map with default doesn't really make
sense.

Lets say that the difference between Map and a Function is the
cardinality of the underlying sets. As Martin said: a Map is a
_finite_ Set. A Map with default puts the map in infinite territory so
it can't really be a Map.

If we turn it around and instead focus on the default we get a
Function (infinite set) with a finite set of overrides (the Map).

I would guess that the usefulness of a Map, compared to a Function,
comes from the fact that it's definition can be inspected (iterated
even).

So maybe the solution is to create a notion of FunctionWithOverrides
from which the overrides can be inspected?

But then again. I can imagine that the original use case for a Map
with default actually had nothing to do with the infinite properties
of the default function. I assume that the actual use case was
concerned with a very limited (finite) subset of keys that just hadn't
been defined yet.

I can imagine few other approaches to this problem, (than to define a
default value on the Map as such).
a) Extract all relevant keys from the problem and make the initial
state of the map complete.
b) Don't read values from a map at all. Collect the update operations
per key, and reduce them using a fold in a second step.
c) Optimize b whit a combined map and reduce step.

So maybe the fix to this problem is to just remove the default thing
from map, and instead focus on the surrounding API to supply other
building blocks for the problem to be solved.

BR,
John

On Fri, Feb 18, 2011 at 11:29 AM, Johannes Rudolph
wrote:
> Perhaps we should think about what a Map is on a higher level first.
>
> Looking at the ScalaDocs of MapLike a Map is both:
>  1. something which associates keys with values (manifested by
> inheriting PartialFunction[A, B])
>  2. a list of (key, value) bindings (manifested by inheriting
> IterableLike[(A, B)])
>
> Classifying the methods in questions two one of those two traits of a
> Map by their current Scaladoc descriptions:
>
> apply => 1 "Retrieves the value which is associated with the given
> key." (Function1)
> get => 1 "Optionally returns the value associated with a key" (MapLike)
> contains => 2 "Tests whether this map contains a binding for a key." (MapLike)
> isDefinedAt => 2 "Tests whether this map contains a binding for a key.
> This method [...] is equivalent to contains" (PartialFunction)
> filter => 2 "Selects all elements of this map which satisfy a predicate"
> keySet => 2 "Collects all keys of this map in a set."
>
> Just by looking at this list, you can see one possible conflict in the
> definition of apply and isDefinedAt, which are both methods of
> PartialFunction and which only work correctly if the relation between
> Traits A and B is fixed, so that there exists a binding for each
> possible association. IMO, implicitly, that's a promise which the
> trait MapLike makes (and as I understood Martin, which should be kept
> by refering to MapLike being defined in terms of `get`).
>
> Obviously, a map with default values can't fulfill this promise and as
> such shouldn't inherit from MapLike in its current form.
>
> I have no constructive suggestion yet, but I don't think this problem
> is solvable solely by focusing on fixing singular points which may
> fail without thinking generally about the things that can fail when
> one uses a Map as one of the things it represents by inheritance. IMO
> multiple inheritance gone wrong is at the heart of this issue.
>
> Johannes
>
> On Thu, Feb 17, 2011 at 7:22 PM, Daniel Sobral wrote:
>> On Thu, Feb 17, 2011 at 16:09, Seth Tisue wrote:
>>>
>>> >>>>> "martin" == martin odersky writes:
>>>
>>>  martin> The problem is obviously backwards compatibility. But the time
>>>  martin> window where we had withDefault was fairly small, AFAIK it was
>>>  martin> introduced in 2.8.
>>>
>>> 2.7 didn't have withDefault, but it did have withDefaultValue:
>>>
>>> Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM,
>>> Java 1.6.0_22).
>>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>>> res0: Int = 5
>>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>>> res2: Boolean = false
>>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>>> res1: Option[Int] = None
>>>
>>> On 2.8 the last answer is instead Some(3).
>>
>> And the second is true:
>>
>> Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM,
>> Java 1.6.0_22).
>> Type in expressions to have them evaluated.
>> Type :help for more information.
>>
>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>> res3: Int = 5
>>
>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>> res4: Boolean = true
>>
>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>> res5: Option[Int] = Some(5)
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>>
>
>
>
> --
> Johannes
>
> -----------------------------------------------
> Johannes Rudolph
> http://virtual-void.net
>

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: what it means to contain something
This is non-sensical. The goal of a map is not to represent some abstract mathematical concept, but to enable efficient operations on arbitrary relationships between two values -- a Map is an API for dictionary implementations. A map with default is a way to abstract away initialization of not previously defined relationships as well as remove the need to handle relationship-not-present exceptions in certain algorithms.
The fact that this thread hasn't reach an obvious conclusion is evidence that API changes have practical consequences and that people have different needs for maps, as evidenced by two common objections: it is hard to put sensible migration warnings for this change (practical consequence), and changing both "get" and "contains" remove Map's safe lookup (different needs).
On Sat, Feb 19, 2011 at 16:18, John Nilsson <john [at] milsson [dot] nu> wrote:
I've also had this line of thinking.

First of all. The fact that this thread hasn't reached an obvious
conclusion yet is evidence that a map with default doesn't really make
sense.

Lets say that the difference between Map and a Function is the
cardinality of the underlying sets. As Martin said: a Map is a
_finite_ Set. A Map with default puts the map in infinite territory so
it can't really be a Map.

If we turn it around and instead focus on the default we get a
Function (infinite set) with a finite set of overrides (the Map).

I would guess that the usefulness of a Map, compared to a Function,
comes from the fact that it's definition can be inspected (iterated
even).

So maybe the solution is to create a notion of FunctionWithOverrides
from which the overrides can be inspected?


But then again. I can imagine that the original use case for a Map
with default actually had nothing to do with the infinite properties
of the default function. I assume that the actual use case was
concerned with a very limited (finite) subset of keys that just hadn't
been defined yet.

I can imagine few other approaches to this problem, (than to define a
default value on the Map as such).
a) Extract all relevant keys from the problem and make the initial
state of the map complete.
b) Don't read values from a map at all. Collect the update operations
per key, and reduce them using a fold in a second step.
c) Optimize b whit a combined map and reduce step.

So maybe the fix to this problem is to just remove the default thing
from map, and instead focus on the surrounding API to supply other
building blocks for the problem to be solved.

BR,
John

On Fri, Feb 18, 2011 at 11:29 AM, Johannes Rudolph
<johannes [dot] rudolph [at] googlemail [dot] com> wrote:
> Perhaps we should think about what a Map is on a higher level first.
>
> Looking at the ScalaDocs of MapLike a Map is both:
>  1. something which associates keys with values (manifested by
> inheriting PartialFunction[A, B])
>  2. a list of (key, value) bindings (manifested by inheriting
> IterableLike[(A, B)])
>
> Classifying the methods in questions two one of those two traits of a
> Map by their current Scaladoc descriptions:
>
> apply => 1 "Retrieves the value which is associated with the given
> key." (Function1)
> get => 1 "Optionally returns the value associated with a key" (MapLike)
> contains => 2 "Tests whether this map contains a binding for a key." (MapLike)
> isDefinedAt => 2 "Tests whether this map contains a binding for a key.
> This method [...] is equivalent to contains" (PartialFunction)
> filter => 2 "Selects all elements of this map which satisfy a predicate"
> keySet => 2 "Collects all keys of this map in a set."
>
> Just by looking at this list, you can see one possible conflict in the
> definition of apply and isDefinedAt, which are both methods of
> PartialFunction and which only work correctly if the relation between
> Traits A and B is fixed, so that there exists a binding for each
> possible association. IMO, implicitly, that's a promise which the
> trait MapLike makes (and as I understood Martin, which should be kept
> by refering to MapLike being defined in terms of `get`).
>
> Obviously, a map with default values can't fulfill this promise and as
> such shouldn't inherit from MapLike in its current form.
>
> I have no constructive suggestion yet, but I don't think this problem
> is solvable solely by focusing on fixing singular points which may
> fail without thinking generally about the things that can fail when
> one uses a Map as one of the things it represents by inheritance. IMO
> multiple inheritance gone wrong is at the heart of this issue.
>
> Johannes
>
> On Thu, Feb 17, 2011 at 7:22 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
>> On Thu, Feb 17, 2011 at 16:09, Seth Tisue <seth [at] tisue [dot] net> wrote:
>>>
>>> >>>>> "martin" == martin odersky <martin [dot] odersky [at] epfl [dot] ch> writes:
>>>
>>>  martin> The problem is obviously backwards compatibility. But the time
>>>  martin> window where we had withDefault was fairly small, AFAIK it was
>>>  martin> introduced in 2.8.
>>>
>>> 2.7 didn't have withDefault, but it did have withDefaultValue:
>>>
>>> Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM,
>>> Java 1.6.0_22).
>>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>>> res0: Int = 5
>>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>>> res2: Boolean = false
>>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>>> res1: Option[Int] = None
>>>
>>> On 2.8 the last answer is instead Some(3).
>>
>> And the second is true:
>>
>> Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM,
>> Java 1.6.0_22).
>> Type in expressions to have them evaluated.
>> Type :help for more information.
>>
>> scala> Map(1 -> 2).withDefaultValue(5).apply(3)
>> res3: Int = 5
>>
>> scala> Map(1 -> 2).withDefaultValue(5).contains(3)
>> res4: Boolean = true
>>
>> scala> Map(1 -> 2).withDefaultValue(5).get(3)
>> res5: Option[Int] = Some(5)
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>>
>
>
>
> --
> Johannes
>
> -----------------------------------------------
> Johannes Rudolph
> http://virtual-void.net
>



--
Daniel C. Sobral

I travel to the future all the time.
John Nilsson
Joined: 2008-12-20,
User offline. Last seen 42 years 45 weeks ago.
Re: what it means to contain something

On Sat, Feb 19, 2011 at 10:23 PM, Daniel Sobral wrote:
> A map with default is a way to abstract away initialization
> of not previously defined relationships as well as remove the need to handle
> relationship-not-present exceptions in certain algorithms.
Which is also what the other half of the mail you responded too concluded.

BR,
John

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland