diff options
| -rw-r--r-- | doc/reference/examples.verb.tex | 55 | ||||
| -rw-r--r-- | sources/scalac/symtab/Type.java | 43 | ||||
| -rw-r--r-- | sources/scalac/typechecker/RefCheck.java | 29 |
3 files changed, 86 insertions, 41 deletions
diff --git a/doc/reference/examples.verb.tex b/doc/reference/examples.verb.tex index 61afe0dab4..85b78b6af2 100644 --- a/doc/reference/examples.verb.tex +++ b/doc/reference/examples.verb.tex @@ -2196,7 +2196,7 @@ result types is very tedious. It should also be unneccessary because all such classes have exactly the same structure. In Scala, the repetition can be avoided by defining a {\em generic class}: \begin{verbatim} -case class Pair[a, b](first: a, second: b); +case class Pair[+a, +b](first: a, second: b); def divmod(x: int, y: int): Pair[int, int] = new Pair[Int, Int](x / y, x % y) \end{verbatim} @@ -2220,12 +2220,27 @@ divmod(x, y) match { case Pair(n, d) => System.out.println("quotient: " + n + ", rest: " + d); } \end{verbatim} +The type parameters in class \verb@Pair@ are each prefixed by a +\verb@+@ sign. This indicates that \verb@Pair@s are {\em +covariant}. That is, if types \verb@T$_1$@ and \verb@T$_2$@ are +subtypes of types \verb@S$_1$@ and \verb@S$_2$@, then +\verb@Pair[T$_1$, T$_2$]@ is a subtype of +\verb@Pair[S$_1$, S$_2$]@. For instance, \verb@Pair[String, int]@ is a +subtype of \verb@Pair[Object, long]@. If the \verb@+@-annotation was +missing, the type constructor would be treated as being +non-variant. That is, pairs with different element types would never +be in a subtype relation. +Besides, \verb@+@, there is also a prefix +\verb@-@ for contra-variant type constructors. +The precise rules that +for variance annotations are given in Chapter~\ref{sec:variance}. + The idea of pairs is generalized in Scala to tuples of greater arity. There is a predefined case class \verb@Tuple$_n$@ for every \verb@n@ from \verb@2@ to \verb@9@ in Scala's standard library. The definitions all follow the template \begin{verbatim} -case class Tuple$_n$[a$_1$, ..., a$_n$](_1: a$_1$, ..., _n: a$_n$); +case class Tuple$_n$[+a$_1$, ..., +a$_n$](_1: a$_1$, ..., _n: a$_n$); \end{verbatim} Class \verb@Pair@ (as well as class \verb@Triple@) are also predefined, but not as classes of their own. Instead @@ -2325,11 +2340,11 @@ def isort(xs: List[int]): List[int] = \exercise Provide an implementation of the missing function \verb@insert@. -\paragraph{List patterns.} In fact, both \verb@Nil@ and \verb@::@ are -defined as case classes in Scala's standard library. Hence, it is -possible to decompose lists by pattern matching, using patterns -composed from the \verb@Nil@ and \verb@::@ constructors. For instance, \verb@isort@ can -be written alternatively as follows. +\paragraph{List patterns.} In fact, \verb@::@ is +defined defined as a case class in Scala's standard library. Hence, it +is possible to decompose lists by pattern matching, using patterns +composed from the \verb@Nil@ and \verb@::@ constructors. For instance, +\verb@isort@ can be written alternatively as follows. \begin{verbatim} def isort(xs: List[int]): List[int] = xs match { case List() => List() @@ -2408,13 +2423,16 @@ Lists are not built in in Scala; they are defined by an abstract class In the following we present a tour through class \verb@List@. \begin{verbatim} package scala; -abstract class List[a] { +abstract class List[+a] { \end{verbatim} \verb@List@ is an abstract class, so one cannot define elements by -calling the empty \verb@List@ constructor (e.g. by \verb@new List). -The class is situated in the package \verb@scala@. This is a package -containing the most important standard classes of Scala. \verb@List@ -defines a number of methods, which are explained in the following. +calling the empty \verb@List@ constructor (e.g. by +\verb@new List). The class has a type parameter \verb@a@. It is +co-variant in this parameter, which means \verb@T <: S@ implies that +\verb@List[T] <: List[S]@. The class is situated in the package +\verb@scala@. This is a package containing the most important standard +classes of Scala. \verb@List@ defines a number of methods, which are +explained in the following. First, there are the three basic functions \verb@isEmpty@, \verb@head@, \verb@tail@. Their implementation in terms of pattern @@ -2536,10 +2554,10 @@ left-associative. E.g., \begin{verbatim} x :: y :: z = x :: (y :: z) \=$\mbox{\rm whereas}$ x + y + z = (x + y) + z \end{verbatim} -With these conventions, the definition of \verb@::@ as a method in -class \verb@List@ is straightforward: +The definition of \verb@::@ as a method in +class \verb@List@ is as follows: \begin{verbatim} -def ::(x: a): List[a] = new scala.::(x, this); +def ::[b >: a](x: a): List[a] = new scala.::(x, this); \end{verbatim} An operation similar to \verb@::@ is list concatenation, written `\verb@:::@'. The result of \verb@(xs ::: ys)@ is a list consisting of @@ -2644,6 +2662,9 @@ val intSort = msort(iless) val reverseSort = msort(x: int, y: int => x > y) \end{verbatim} +\section*{Higher-Order Methods} + + \bibliography{examples} \end{document} @@ -3486,8 +3507,8 @@ l = Branch(Leaf(1), Leaf(2)), r = Branch(Leaf(3), Leaf(4)). \end{verbatim} As another example, consider the following class \begin{verbatim} -abstract final class Option[a]; -case class None[a] extends Option[a]; +abstract final class Option[+a]; +case object None extends Option[All]; case class Some[a](item: a) extends Option[a]; \end{verbatim} ... diff --git a/sources/scalac/symtab/Type.java b/sources/scalac/symtab/Type.java index 4289498818..f98be55b21 100644 --- a/sources/scalac/symtab/Type.java +++ b/sources/scalac/symtab/Type.java @@ -1771,29 +1771,24 @@ public class Type implements Modifiers, Kinds, TypeTags { return result; } - /** Return the least upper bound of non-empty array of types `tps'. + /** remove types that are subtypes of some other type. */ - public static Type lub(Type[] tps) { - //System.out.println("lub" + ArrayApply.toString(tps));//DEBUG - - // remove types that are subtypes of some other type. + static private Type[] elimRedundant(Type[] tps, boolean elimLower) { Type.List tl = Type.List.EMPTY; int nredundant = 0; boolean[] redundant = new boolean[tps.length]; for (int i = 0; i < tps.length; i++) { - if (tps[i] == ErrorType) - return ErrorType; - else if (!tps[i].isObjectType()) { - System.out.println("not an object type"); - return Type.NoType;//todo: change + if (tps[i] == ErrorType) { + return new Type[]{ErrorType}; } else { + assert tps[i].isObjectType() : tps[i]; for (int j = 0; j < i && !redundant[i]; j++) { if (!redundant[j]) { if (tps[i].isSubType(tps[j])) { - redundant[i] = true; + redundant[elimLower ? i : j] = true; nredundant++; } else if (tps[j].isSubType(tps[i])) { - redundant[j] = true; + redundant[elimLower ? j : i] = true; nredundant++; } } @@ -1807,9 +1802,21 @@ public class Type implements Modifiers, Kinds, TypeTags { for (int i = 0; i < tps.length; i++) { if (!redundant[i]) tps1[n++] = tps[i]; } - tps = tps1; + return tps1; + } else { + return tps; } + } + + /** Return the least upper bound of non-empty array of types `tps'. + * todo: treat types with refinements + */ + public static Type lub(Type[] tps) { + //System.out.println("lub" + ArrayApply.toString(tps));//DEBUG + + // remove types that are subtypes of some other type. + tps = elimRedundant(tps, true); if (tps.length == 1) return tps[0]; // intersect closures and build frontier. @@ -1866,9 +1873,7 @@ public class Type implements Modifiers, Kinds, TypeTags { private static Type commonType(Type[] tps) { Type tp = tps[0]; if (tp.isSameAsAll(tps)) return tp; - //tp = tp.widen(); - //if (tp.isSameAsAll(widen(tps))) return tp; - return NoType; + else return NoType; } private static Symbol lub(Symbol[] syms, Type[] tps, Symbol owner) { @@ -1899,6 +1904,12 @@ public class Type implements Modifiers, Kinds, TypeTags { return lubSym; } + private static Type glb(Type[] tps) { + tps = elimRedundant(tps, false); + if (tps.length == 1) return tps[0]; + else return NoType; + } + // Erasure -------------------------------------------------------------------------- public static Map erasureMap = new MapOnlyTypes() { diff --git a/sources/scalac/typechecker/RefCheck.java b/sources/scalac/typechecker/RefCheck.java index 0d5caa78e4..9ea4f125f0 100644 --- a/sources/scalac/typechecker/RefCheck.java +++ b/sources/scalac/typechecker/RefCheck.java @@ -152,7 +152,7 @@ public class RefCheck extends Transformer implements Modifiers, Kinds { Tree vdef = gen.ValDef(mvar, gen.Ident(tree.pos, defs.NULL)); // { if (null == m$) m$ = new m$class; m$ } - Symbol eqMethod = getMemberMethod( + Symbol eqMethod = getUnaryMemberMethod( sym.type(), Names.EQEQ, defs.ANY_TYPE); Tree body = gen.Block(new Tree[]{ gen.If( @@ -185,7 +185,20 @@ public class RefCheck extends Transformer implements Modifiers, Kinds { return sym; } - private Symbol getMemberMethod(Type site, Name name, Type paramtype) { + private Symbol getNullaryMemberMethod(Type site, Name name) { + Symbol sym = getMember(site, name); + switch (sym.type()) { + case OverloadedType(Symbol[] alts, Type[] alttypes): + for (int i = 0; i < alts.length; i++) { + if (alttypes[i].firstParams().length == 0) return alts[i]; + } + } + assert sym.type().firstParams().length == 0 + : "no nullary method " + name + " among " + sym.type() + " at " + site; + return sym; + } + + private Symbol getUnaryMemberMethod(Type site, Name name, Type paramtype) { Symbol sym = getMember(site, name); switch (sym.type()) { case OverloadedType(Symbol[] alts, Type[] alttypes): @@ -306,7 +319,7 @@ public class RefCheck extends Transformer implements Modifiers, Kinds { } private Tree eqOp(Tree l, Tree r) { - Symbol eqMethod = getMemberMethod(l.type, Names.EQEQ, r.type); + Symbol eqMethod = getUnaryMemberMethod(l.type, Names.EQEQ, r.type); return gen.Apply(gen.Select(l, eqMethod), new Tree[]{r}); } @@ -316,10 +329,10 @@ public class RefCheck extends Transformer implements Modifiers, Kinds { .setInfo(defs.HASHCODE.type()); clazz.info().members().enter(hashCodeSym); Tree[] fields = caseFields(clazz); - Symbol getClassMethod = getMember(clazz.type(), Names.getClass); - Symbol addMethod = getMemberMethod( + Symbol getClassMethod = getNullaryMemberMethod(clazz.type(), Names.getClass); + Symbol addMethod = getUnaryMemberMethod( defs.INT_TYPE, Names.ADD, defs.INT_TYPE); - Symbol mulMethod = getMemberMethod( + Symbol mulMethod = getUnaryMemberMethod( defs.INT_TYPE, Names.MUL, defs.INT_TYPE); Tree body = gen.Apply( @@ -327,13 +340,13 @@ public class RefCheck extends Transformer implements Modifiers, Kinds { gen.Apply( gen.mkRef(clazz.pos, clazz.thisType(), getClassMethod), Tree.EMPTY_ARRAY), - getMember(getClassMethod.type().resultType(), Names.hashCode)), + getNullaryMemberMethod(getClassMethod.type().resultType(), Names.hashCode)), Tree.EMPTY_ARRAY); for (int i = 0; i < fields.length; i++) { Tree operand = gen.Apply( gen.Select( fields[i], - getMember(fields[i].type, Names.hashCode)), + getNullaryMemberMethod(fields[i].type, Names.hashCode)), Tree.EMPTY_ARRAY); body = gen.Apply( |