|
This would ultimately have to go to a SIP, but I don't know enough to write it and just wanted to bounce some ideas about the motivation.
The goal is partial type inference - to distinguish parts of a type that you want inferred from parts that you want to specify. This email uses '?' as a special mark, but something else would work just as well. The mark indicates a portion of a type that you want inferred. I'll give a few examples below. In the cases I present, having ? significantly lowers the amount of typing that's necessary. Sometimes you want a more general type than can be inferred, e.g. with ADTs and default implementations: trait Foo { def optionalParameters:Option[?] = Some(Map("a"->7, "b"->8)) // infers optionalParameter:Option[Map[String, Int]] - trait implementers are then free to override with None } OO practice says code to the interface import java.util.{Map => JMap, HashMap => JHashMap} def buildMap = { val map:JMap[?,?] = new JHashMap[Int,String] map.add(2, "bar") map.add(42, "baz") map } // infers val map:JMap[Int,String], thus def buildMap:JMap[Int,String] and users are now ignorant of the use of the more specialized JHashMap While more general types are one important driver, my main use case is as an aid where some type parameters can be inferred but some just can't def cps[A,R](f: => A) = {k:(A=>R) => k(f)} val x = cps[?,Unit](List("a", "b", "c", "d")) // infers val x:(List[String] => Unit) => Unit = cps[List[String],Unit](List("a", "b", "c", "d")) In the above code there's no way to locally infer the Unit type in the call to the cps function, but everything else is inferrable once that is specified. Currently there's no alternative but to write 'cps[List[String],Unit](List("a","b","c","d"))' Finally, a general rule val x : ? = "hello" and val x = "hello" would mean exactly the same thing. This proposal wouldn't remove the later form, it would just make it sugar for the x : ? form. Thoughts? 1) The current type inference behavior seems un(der)documented, so I have no idea how to extend the specification to say when ? would work and when it wouldn't. 2) I don't know much about Scala's inference algorithm, so I can't say for certain that this doesn't create a monster. Intuitively it would seem a reasonable extension. 3) How would/should ? play with higher kinds, existentials, view bounds, and structural types? Does it change anything on those fronts at all? Please keep comments on whether ? is the right symbol to less than 3% of the volume :-) |
|
On Wed, Sep 10, 2008 at 4:46 AM, James Iry <[hidden email]> wrote:
> Thoughts? > 1) The current type inference behavior seems un(der)documented, so I have no > idea how to extend the specification to say when ? would work and when it > wouldn't. I believe this algorithm is used largely without modification at the moment http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.8225 |
Can this be verified by the Scala Team? I would really like to delve into these matters some day, so a research reference to match the current workings of scalac would be invaluable. Needles to say, I would love to see such pointers in the Scala Web Site :-) -- __~O -\ <, Christos KK Loverdos (*)/ (*) http://ckkloverdos.com |
|
On Wed, Sep 10, 2008 at 12:20 PM, Christos KK Loverdos
<[hidden email]> wrote: > >> >> I believe this algorithm is used largely without modification at the >> moment http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.8225 > The type inference is based on these algorthms, but there are several refinements. The most important one is discussed in Inferred Type Instantiation for GJ, Martin Odersky, Januaey 2002. available at: http://lampwww.epfl.ch/~odersky/papers/#Types Cheers --Martin |
|
Thanx! :-)
Christos On Wed, Sep 10, 2008 at 3:47 PM, martin odersky <[hidden email]> wrote:
-- __~O -\ <, Christos KK Loverdos (*)/ (*) http://ckkloverdos.com |
|
In reply to this post by Martin Odersky
Thanks guys. Both papers indicate that internally the algorithm works with partially inferred types under some circumstances. So it appears what I'm talking about is just a modification where the engine might start with partial types before inference starts.
On Wed, Sep 10, 2008 at 5:47 AM, martin odersky <[hidden email]> wrote:
|
|
In reply to this post by James Iry-2
I haven't heard much feedback on the idea. In IM Ricky Clarkson and David MacIver said they think it's a good idea. Greg Meredith had an interesting question which I'll address in my next email.
In IM Ricky Clarkson pointed out that C# replaces parameters to be inferred with nothing at all. That's kinda nice because it unifies the notation for complete type inference and with the notation for partial type inference. It also doesn't use up a precious symbol like ?. My examples rewritten would look like trait Foo { def optionalParameters:Option[ ] = Some(Map("a"->7, "b"->8)) } import java.util.{Map => JMap, HashMap => JHashMap} def buildMap = { val map:JMap[ , ] = new JHashMap[Int,String] map.add(2, "bar") map.add(42, "baz") map } def cps[A,R](f: => A) = {k:(A=>R) => k(f)} val x = cps[ ,Unit](List("a", "b", "c", "d")) As one more example def arrayOfOptionalInts : [Option[ ]] = Array(Some(7), Some(8)) It's not clear whether the following should be valid val string : = "hello" On Tue, Sep 9, 2008 at 8:46 PM, James Iry <[hidden email]> wrote:
|
|
I should note that in C# it's not actually for parameters that should
be inferred but for uninstantiated types, e.g., List<> is the List type without a type parameter set yet (is this called a type constructor or a higher-kinded type or something?). C# needs that because you can overload on number of type parameters. E.g., in one namespace there is Action, Action<>, Action<,>, Action<,,> and Action<,,,>. HList for President. 2008/9/11 James Iry <[hidden email]>: > I haven't heard much feedback on the idea. In IM Ricky Clarkson and David > MacIver said they think it's a good idea. Greg Meredith had an interesting > question which I'll address in my next email. > > In IM Ricky Clarkson pointed out that C# replaces parameters to be inferred > with nothing at all. That's kinda nice because it unifies the notation for > complete type inference and with the notation for partial type inference. > It also doesn't use up a precious symbol like ?. My examples rewritten would > look like > > trait Foo { > def optionalParameters:Option[ ] = Some(Map("a"->7, "b"->8)) > } > > import java.util.{Map => JMap, HashMap => JHashMap} > def buildMap = { > val map:JMap[ , ] = new JHashMap[Int,String] > map.add(2, "bar") > map.add(42, "baz") > map > } > > def cps[A,R](f: => A) = {k:(A=>R) => k(f)} > val x = cps[ ,Unit](List("a", "b", "c", "d")) > > > As one more example > > def arrayOfOptionalInts : [Option[ ]] = Array(Some(7), Some(8)) > > It's not clear whether the following should be valid > > val string : = "hello" > > > On Tue, Sep 9, 2008 at 8:46 PM, James Iry <[hidden email]> wrote: >> >> This would ultimately have to go to a SIP, but I don't know enough to >> write it and just wanted to bounce some ideas about the motivation. >> >> The goal is partial type inference - to distinguish parts of a type that >> you want inferred from parts that you want to specify. This email uses '?' >> as a special mark, but something else would work just as well. The mark >> indicates a portion of a type that you want inferred. I'll give a few >> examples below. In the cases I present, having ? significantly lowers the >> amount of typing that's necessary. >> > > |
|
In reply to this post by James Iry-2
The question raised by Greg Meredith is how this notion plays with partial type application. I'll use another symbol to illustrate what partial type application does
type MapS = Map[String, *] type Map SI = MapS[Int] // the above would be the same as type MapSI = Map[String,Int] You can encode partial type application in Scala now, but it's awkard - I'll add it at the bottom of this email. Anyway, Greg wondered if partial type inference and partial type application could be the same thing. I'm not sure it can. In my cps example, leaving both parameters to be inferred should result in exactly what scala does now def cps[A,R](f: => A) = {k:(A=>R) => k(f)} // current scala val x = cps(42) // x : (Int => Nothing) => Nothing // proposal would consider the following exactly the same val x = cps[,](42) // x: (Int => Nothing) => Nothing //Whereas if it were the same as partial type application, I would expect val x = cps[Int,](42) // x[R]: (Int => R) => R In other words, x would be polymorphic and that's a whole different kettle of fish. That would be nice, but I'm concerned that the value restriction on polymorphism is due to an important soundness property like it is in many languages in the ML family. He asked what "type MapS = Map[String,]" would mean under my proposal. The only reasonable answer is that it would mean "type MapS=Map[String,Nothing]" - that being the most specific type compatible with the constraints. But, of course, that's not a very useful type. Thoughts? Anyway, the awkard way to encode partial function application has been mentioned here before type Partial[T[_,_], A] = { type Apply[B] = T[A,B] } type MapS = Partial[Map, String] type MapSI = MapS#Apply[Int] On Tue, Sep 9, 2008 at 8:46 PM, James Iry <[hidden email]> wrote:
|
|
In reply to this post by Ricky Clarkson
Sorry, my misunderstanding. I still like the notation.
On Thu, Sep 11, 2008 at 5:41 AM, Ricky Clarkson <[hidden email]> wrote: I should note that in C# it's not actually for parameters that should |
|
In reply to this post by James Iry-2
Hi James,
On Thu, Sep 11, 2008 at 3:47 PM, James Iry <[hidden email]> wrote:
I am afraid I cannot follow your argument above. Could you explain a bit?
(modulo the explanation I need, as requested above :-) ) Couldn't you use ? for situations where you actually ASK scala to infer and use nothing when you want to get partial type application ala Greg? BR Christos. -- __~O -\ <, Christos KK Loverdos (*)/ (*) http://ckkloverdos.com |
|
On Thu, Sep 11, 2008 at 5:57 AM, Christos KK Loverdos <[hidden email]> wrote: Sure, the two different things could have two different notations. The question is can they be unified in some way? Is the value restriction a red herring?
Basically you can make a def polymorphic but not a val. Here's a pretty good explanation for FSharp, although F# uses different syntax to indicate the difference. http://www.strangelights.com/fsharp/wiki/default.aspx/FSharpWiki/ValueRestriction.html (modulo the explanation I need, as requested above :-) ) Couldn't you use ? for situations where you actually ASK scala to infer and use nothing when you want to get partial type application ala Greg? |
|
Why did I write FSharp and F# in the same email? how confusing. Replace one with the other. :-)
On Thu, Sep 11, 2008 at 6:14 AM, James Iry <[hidden email]> wrote:
|
|
On Thu, Sep 11, 2008 at 4:15 PM, James Iry <[hidden email]> wrote:
Not only in the same email, but also in the same sentence, separated by just a comma and another word :-) Anyway, thanx for the pointer. Under the new light of value restriction (value polymorphism), I tried a few known things in the interpreter. scala> def ident[A](x: A) = x ident: [A](A)A scala> val ident1 = ident _ ident1: (Nothing) => Nothing = <function> scala> val ident2 = ident[Int] _ ident2: (Int) => Int = <function> and voila! The value ident1 is not polymorphic (not to mention that it is useless) and value ident2 is (on purpose) restricted to Int. And if I use a var and reassign, scala> var ident2 = ident[Int] _ ident2: (Int) => Int = <function> scala> ident2 = ident _ ident2: (Int) => Int = <function> the previously infered type Int is used in the fragment ident _. Are these things I am trying and witnessing related to value restriction really, or have I misunderstood the concept? And if the last one is the case, what would be "good" exposition of the case in Scala? (I am learning here... :-) ) BR Christos -- __~O -\ <, Christos KK Loverdos (*)/ (*) http://ckkloverdos.com |
|
In reply to this post by James Iry-2
James, et al,
Just to refine the feedback i was giving on your proposal. My concern is this: there are some contexts where Map[?,??] seems to mean one thing and other contexts where it means another. Specifically, in this context from your original post import java.util.{Map => JMap, HashMap => JHashMap} def buildMap = { val map:JMap[?,?] = new JHashMap[Int,String] map.add(2, "bar") map.add(42, "baz") map } it has a different meaning than in this context type Phred = JMap[?,?] Whenever that sort of contextual dependence happens it starts to smell of a non-compositional feature and that's the primrose path. i've really not had the time to think about this deeply; so, it could be that the proposal as it stands is just fine and there is a rational, compositional interpretation to the idea. These are just early warning signs i notice from extremely painful experience. Best wishes, --greg On Thu, Sep 11, 2008 at 5:47 AM, James Iry <[hidden email]> wrote:
-- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com |
|
They should have the same meaning in both contexts - the question marks (or blanks in the later version of the proposal) specify types that need to be inferred based on the standard type inference algorithm.
In the former case, there's a constraint placed that the type on the left, Jmap[?,?], must be a supertype of type on the right, JHashMap[Int,String]. There are many types that meet the criteria (e.g. JMap[Any,String]) but JMap[Int,String] is the most specific type that meets the contstraints. In the second case you haven't placed any constraints other than that it must be a JMap[?,?]. Again, there are many types that meet that constraint, but JMap[Nothing,Nothing] is the most specific type that meets the constraint. Context does influence the inference, but hey, that's inference for you. On Thu, Sep 11, 2008 at 10:25 PM, Meredith Gregory <[hidden email]> wrote:
|
|
James,
Cool. Then compositional semantics would demand that the following two programs are the same. import java.util.{Map => JMap, HashMap => JHashMap} def buildMap = { val map:JMap[?,?] = new JHashMap[Int,String] map.add(2, "bar") map.add(42, "baz") map } import java.util.{Map => JMap, HashMap => JHashMap} type Pred = JMap[?,?]; def buildMap = { val map:Phred = new JHashMap[Int,String] map.add(2, "bar") map.add(42, "baz") map } Does that line up with your intention? Best wishes, --greg On Fri, Sep 12, 2008 at 7:46 PM, James Iry <[hidden email]> wrote:
-- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com |
|
Sure, I'd love that to work. But what you're asking for is type inference based on a broader context than we have now. Before your more complicated example could work, the following simple one would also have to work.
def foo = { def id[A](x:A) = x val myId : ? = id[?] _ myId(42) } which, recall, is exactly the same as the following code def foo = { def id[A](x:A) = x val myId = id _ myId(42) } When you try to compile that right now you get a type mismatch error because the type of myId is inferred without reference to its use later in foo found : Int(42) required: Nothing myId(42) If you have a suggestion for the Scala team on how to make that work then what you're asking for below might start entering the realm of possibility. On Fri, Sep 12, 2008 at 10:29 PM, Meredith Gregory <[hidden email]> wrote:
import java.util.{Map => JMap, HashMap => JHashMap} def buildMap = { import java.util.{Map => JMap, HashMap => JHashMap} type Pred = JMap[?,?]; Best wishes, --greg |
|
James,
This conversation has been really stimulating and for that i thank you! In doing some background research to find ways to think about this, i noticed that polarization and focusing are showing up on the types list in connection with some of these issues. Dale Miller and his gang seem to be having way too much fun working on some hard problems in this area. For example, this paper by Noam Zeilberger seems to touch on the issues at hand. Best wishes, --greg On Sat, Sep 13, 2008 at 4:10 AM, James Iry <[hidden email]> wrote:
-- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com |
| Powered by Nabble | Edit this page |
