scala - Skolemization of existentially typed expressions -

in scala, following expression raises type error:

val pair: (a => string, a) forsome { type } = ( { a: int => a.tostring }, 19 ) pair._1(pair._2) 

as mentioned in si-9899 , answer, correct according spec:

i think working designed per sls 6.1: "the following skolemization rule applied universally every expression: if type of expression existential type t, type of expression assumed instead skolemization of t."

however, not understand this. @ point rule applied? apply in first line (i.e., type of pair different 1 given type annotation), or in second line (but applying rule second line whole not lead type error)?

let's assume sls 6.1 applies first line. supposed skolemize existential types. can make in first line non-existential type putting existential inside type parameter:

case class wrap[t](x:t) val wrap = wrap(( { a: int => a.tostring }, 19 ) : (a => string, a) forsome { type }) wrap.x._1(wrap.x._2) 

it works! (no type error.) means, existential type got "lost" when defined pair? no:

val wrap2 = wrap(pair) wrap2.x._1(wrap2.x._2) 

this type checks! if have been "fault" of assignment pair, should not work. thus, reason why not work lies in second line. if that's case, what's difference between wrap , pair example?

to wrap up, here 1 more pair of examples:

val wrap((a2,b2)) = wrap a2(b2)  val (a3,b3) = pair a3(b3) 

both don't work, analogy fact wrap.x._1(wrap.x._2) did typecheck, have thought a2(b2) might typecheck, too.

i believe figured out of process how expressions above typed.

first, mean:

the following skolemization rule applied universally every expression: if type of expression existential type t, type of expression assumed instead skolemization of t. [sls 6.1]

it means whenever expression or subexpression determined have type t[a] forsome {type a}, fresh type name a1 chosen, , expression given type t[a1]. makes sense since t[a] forsome {type a} intuitively means there type a such expression has type t[a]. (what name chosen depends on compiler implementation. use a1 distinguish bound type variable a)

we @ first line of code:

val pair: (a => string, a) forsome { type } = ({ a: int => a.tostring }, 19) 

here skolemization rule not yet used. ({ a: int => a.tostring }, 19) has type (int=>string, int). subtype of (a => string, a) forsome { type } since there exists a (namely int) such rhs of type (a=>string,a).

the value pair has type (a => string, a) forsome { type }.

the next line

pair._1(pair._2) 

now typer assigns types subexpressions inside out. first, first occurrence of pair given type. recall pair had type (a => string, a) forsome { type }. since skolemization rule applies every subexpression, apply first pair. pick fresh type name a1, , type pair (a1 => string, a1). assign type second occurrence of pair. again skolemization rule applies, pick fresh type name a2, , second occurrence of pair types (a2=>string,a2).

then pair._1 has type a1=>string , pair._2 has type a2, pair._1(pair._2) not well-typed.

note not skolemization rule's "fault" typing fails. if not have skolemization rule, pair._1 type (a=>string) forsome {type a} , pair._2 type a forsome {type a} same any. , pair._1(pair._2) still not well-typed. (the skolemization rule helpful in making things type, see below.)

so, why scala refuse understand 2 instances of pair of type (a=>string,a) the same a? not know reason in case of val pair, example if have var pair of same type, compiler must not skolemize several occurrences of same a1. why? imagine within expression, content of pair changes. first contains (int=>string, int), , towards end of evaluation of expression, contains (bool=>string,bool). ok if type of pair (a=>string,a) forsome {type a}. if computer give both occurrences of pair same skolemized type (a1=>string,a1), typing not correct. similarly, if pair def pair, return different results on different invocations, , must not skolemized same a1. val pair, argument not hold (since val pair cannot change), assume type system complicated if try treat val pair different var pair. (also, there situations val can change content, namely unitialized initialized. don't know whether can lead problems in context.)

however, can use skolemization rule make pair._1(pair._2) well-typed. first try be:

val pair2 = pair pair2._1(pair2._2) 

why should work? pair types (a=>string,a) forsome {type a}. it's type becomes (a3=>string,a3) fresh a3. new val pair2 should given type (a3=>string,a3) (the type of rhs). , if pair2 has type (a3=>string,a3), pair2._1(pair2._2) well-typed. (no existentials involved more.)

unfortunately, not work, because of rule in spec:

if value definition not recursive, type t may omitted, in case packed type of expression e assumed. [sls 4.1]

the packed type opposite of skolemization. means, fresh variables have been introduced inside expression due skolemization rule transformed existential types. is, t[a1] becomes t[a] forsome {type a}.

thus, in

val pair2 = pair 

pair2 given type (a=>string,a) forsome {type a} though rhs given type (a3=>string,a3). pair2._1(pair2._2) not type, explained above.

but can use trick achieve desired result:

pair match { case pair2 =>   pair2._1(pair2._2) } 

at first glance, pointless pattern match, since pair2 assigned pair, why not use pair? reason rule sls 4.1 applied vals , vars. variable patterns (like pair2 here) not affected. pair typed (a4=>string,a4) , pair2 given same type (not packed type). pair2._1 typed a4=>string , pair2._2 typed a4 , well-typed.

so code fragment of form x match { case x2 => can used "upgrade" x new "pseudo-value" x2 can make expressions well-typed not well-typed using x. (i don't know why spec not allow same thing happen when write val x2 = x. nicer read since not level of indentation.)

after excursion, let go through typing of remaining expressions question:

val wrap = wrap(({ a: int => a.tostring }, 19) : (a => string, a) forsome { type }) 

here expression ({ a: int => a.tostring }, 19) types (int=>string,int). type case makes expression of type (a => string, a) forsome { type }). skolemization rule applied, expression (the argument of wrap, is) gets type (a5=>string,a5) fresh a5. apply wrap it, , rhs has type wrap[(a5=>string,a5)]. type of wrap, need apply rule sls 4.1 again: compute packed type of wrap[(a5=>string,a5)] wrap[(a=>string,a)] forsome {type a}. wrap has type wrap[(a=>string,a)] forsome {type a} (and not wrap[(a=>string,a) forsome {type a}] 1 might expect @ first glance!) note can confirm wrap has type running compiler option -xprint:typer.

we type

wrap.x._1(wrap.x._2) 

here skolemization rule applies both occurrences of wrap, , typed wrap[(a6=>string,a6)] , wrap[(a7=>string,a7)], respectively. wrap.x._1 has type a6=>string, , wrap.x._2 has type a7. wrap.x._1(wrap.x._2) not well-typed.

but compiler disagrees , accepts wrap.x._1(wrap.x._2)! not know why. either there additional rule in scala type system don't know about, or compiler bug. running compiler -xprint:typer not give insight, either, since not annotate subexpressions in wrap.x._1(wrap.x._2).

next is:

val wrap2 = wrap(pair) 

here pair has type (a=>string,a) forsome {type a} , skolemizes (a8=>string,a8). wrap(pair) has type wrap[(a8=>string,a8)] , wrap2 gets packed type wrap[(a=>string,a)] forsome {type a}. i.e., wrap2 has same type wrap.

wrap2.x._1(wrap2.x._2) 

as wrap.x._1(wrap.x._2), should not type does.

val wrap((a2,b2)) = wrap 

here see new rule: [sls 4.1] (not part quoted above) explains such pattern match val statement expanded to:

val tmp = wrap match { case wrap((a2,b2)) => (a2,b2) } val a2 = tmp._1 val b2 = tmp._2 

now can see (a2,b2) gets type (a9=>string,a9) fresh a9, tmp gets type (a=>string,a) forsome a due packed type rule. tmp._1 gets type a10=>string using skolemization rule, , val a2 gets type (a=>string) forsome {type a} packed type rule. , tmp._2 gets type a11 using skolemization rule, , val b2 gets type a forsome {type a} packed type rule (this same any).

thus

a2(b2) 

is not well-typed, because a2 gets type a12=>string , b2 gets type a13=>string skolemization rule.

similarly,

val (a3,b3) = pair 

expands to

val tmp2 = pair match { case (a3,b3) => (a3,b3) } val a3 = tmp2._1 val b3 = tmp2._2 

then tmp2 gets type (a=>string,a) forsome {type a} packed type rule, , val a3 , val b3 type (a=>string) forsome {type a} , a forsome {type a} (a.k.a. any), respectively.

then

a3(b3) 

is not well-typed same reasons a2(b2) wasn't.