From c2bac2fa23e1cd340e5a336821ca4a5795af98a4 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 7 May 2004 17:40:35 +0000 Subject: *** empty log message *** --- doc/reference/ReferencePart.tex | 146 +++++++++++++++++++++++++++++++++++++--- 1 file changed, 135 insertions(+), 11 deletions(-) (limited to 'doc') diff --git a/doc/reference/ReferencePart.tex b/doc/reference/ReferencePart.tex index f023a8c45f..57075bba18 100644 --- a/doc/reference/ReferencePart.tex +++ b/doc/reference/ReferencePart.tex @@ -1227,7 +1227,7 @@ As a consequence, for any two types $S$ and $T$, the type new Pair[Int, Int](1, 2) . \end{lstlisting} -\section{Type Parameters} +\section{Type Parameters}\label{sec:type-params} \syntax\begin{lstlisting} TypeParamClause ::= `[' VarTypeParam {`,' VarTypeParam} `]' @@ -3765,6 +3765,7 @@ type of all patterns is the type of the qualifier of \code{match}. In the example above, the expected type of the patterns \code{Nil} and \code{x :: xs1} would be \code{List[a]}, the type of \code{xs}. + \chapter{Views}\label{sec:views} Views are user-defined, implicit coercions that are automatically @@ -3889,8 +3890,8 @@ val x: C = B.view(new B) TypeParam ::= id [>: Type] [<% Type] \end{lstlisting} -A type parameter \code{a} may have a view bound \lstlisting@a <% T@ -instead of a regular upper bound \lstlisting@a <: T@. In that case the +A type parameter \code{a} may have a view bound \lstinline@a <% T@ +instead of a regular upper bound \lstinline@a <: T@. In that case the type parameter may be instantiated to any type \code{S} which is convertible by application of a view method to the view bound \code{T}. Here, we assume there exists an always available identity @@ -3902,6 +3903,10 @@ Hence, the type parameter \code{a} can always be instantiated to subtypes of the view bound \code{T}, just as if \code{T} was a regular upper bound. +View bounds for type parameters behave analogously to upper bounds wrt +to type conformance (\sref{sec:subtyping}), variance checking +(\sref{sec:type-params}), and overriding (\sref{sec:overriding}). + Methods or classes with view-bounded type parameters implicitly take view functions as parameters. For every view-bounded type parameter \lstinline@a <% T@ one adds an implicit value parameter @@ -3914,34 +3919,153 @@ actual argument to the corresponding view parameter. Implicit view parameters of a method or class are then taken as available view methods in its body. -\example +\example Consider the following definition of a trait +\code{Comparable} and a view from strings to that trait.. + +\begin{lstlisting} trait Comparable[a] { - def < (x: a) + def less (x: a): boolean } -def view(x: String): Comparable[String] { + +object StringsAreComparable { + def view(x: String): Comparable[String] = new Comparable[String] { + def less (y: String) = x.compareTo(y) < 0 + } } +\end{lstlisting} +Now, define a binary tree with a method \code{insert} which inserts an +element in the tree and a method \code{elements} which returns a +sorted list of all elements of the tree. The tree is defined for all +types of elements \code{a} that are viewable as \code{Comparable[a]}. +\begin{lstlisting} +trait Tree[a <% Comparable[a]] { + def insert(x: a): Tree[a] = this match { + case Empty() => new Node(x, Empty(), Empty()) + case Node(elem, l, r) => + if (x == elem) this + else if (x less elem) Node(elem, l insert x, r) + else Node(elem, l, r insert x); + } + def elements: List[a] = this match { + case Empty() => List() + case Node(elem, l, r) => + l.elements ::: List(elem) ::: r.elements + } +} +case class Empty[a <% Comparable[a]]() + extends Tree[a]; +case class Node[a <% Comparable[a]](elem: a, l: Tree[a], r: Tree[a]) + extends Tree[a]; +\end{lstlisting} +Finally, define a test program which builds a tree from all command +line argument strings and then prints out the elements as a sorted +sequence. +\begin{lstlisting} +object Test { + import StringsAreComparable.view; + def main(args: Array[String]) = { + var t: Tree[String] = Empty(); + for (val s <- args) { t = t insert s } + System.out.println(t.elements) + } +} +\end{lstlisting} +Note that the definition ~\lstinline@var t: Tree[String] = Empty();@~ +is legal because at that point a view method from \code{String} to +\code{Comparable[String]} has been imported and is therefore +accessible without a prefix. The imported view method is passed as an +implicit argument to the \code{Empty} constructor. +Here is the \code{Test} program again, this time with implicit views +made visible: +\begin{lstlisting} +object Test { + import StringsAreComparable.view; + def main(args: Array[String]) = { + var t: Tree[String] = Empty($\mbox{\bf StringsAreComparable.view}$); + for (val s <- args) { t = t insert s } + System.out.println(t.elements) + } +} +\end{lstlisting} -There is one such view function -parameter for every view bounded type parameter. +And here are the tree classes with implicit views added: +\begin{lstlisting} +trait Tree[a <% Comparable[a]]($\mbox{\bf view}$: a => Comparable[a]) { + def insert(x: a): Tree[a] = this match { + case Empty(_) => new Node(x, Empty($\mbox{\bf view}$), Empty($\mbox{\bf view}$)) + case Node(_, elem, l, r) => + if (x == elem) this + else if ($\mbox{\bf view}$(x) less elem) Node($\mbox{\bf view}$, elem, l insert x, r) + else Node($\mbox{\bf view}$, elem, l, r insert x); + } + def elements: List[a] = this match { + case Empty(_) => List() + case Node(_, elem, l, r) => + l.elements ::: List(elem) ::: r.elements + } +} +case class Empty[a <% Comparable[a]]($\mbox{\bf view}$: a => Comparable[a]) + extends Tree[a]; +case class Node[a <% Comparable[a]]($\mbox{\bf view}$: a => Comparable[a], + elem: a, l: Tree[a], r: Tree[a]) + extends Tree[a]; +\end{lstlisting} +Note that views entail a certain run-time overhead because they need +to be passed as additional arguments to view-bounded methods and +classes. Furthermore, every application of a view entails the +construction of an object which is often immediately discarded +afterwards -- see for instance with the translation of \code{(x less elem)} +in the implementation of method \code{insert} above. It is +expected that the latter cost can be absorbed largely or completely by +compiler optimizations (which are, however, not yet implemented at the +present stage). -In that case, the regular upper -bound of the +\section{Conditional Views} +View methods might themselves have view-bounded type parameters; this +allows the definition of conditional views. +\example The following view makes lists comparable, {\em provided} the +list element type is also comparable. -If $C$ is a base class of $T$ and there exists +\begin{lstlisting} +def view[a <% Comparable[a]](x: List[a]): Comparable[List[a]] = + new Comparable[List[a]] { + def less (ys: List[a]): boolean = + !ys.isEmpty + && + (xs.isEmpty || + (xs.head less ys.head) || + (xs.head == ys.head) && (xs.tail less ys.tail)) + } +\end{lstlisting} +Note that the condition \code{(xs.head less ys.head)} invokes the +\code{less} method of the list element type, which is unknown at the +point of the definition of the view method. As usual, view-bounded +type parameters are translated to implicit \code{view} arguments. In +this case, the \code{view} method over lists would receive the +\code{view} method over list elements as implicit parameter. +This opens up the risk that view methods might be passed themselves as +parameters, thus leading to an infinite instantiation. For instance, +one might try to define the following ``magic'' universal converter: +\begin{lstlisting} +def view[b, a <% b](x: a): b = x // illegal! +\end{lstlisting} +Application of this view would entail an inifinite expansion with view +parameters. To prevent this sitauation, we require that all defined +views are {\em contractive}, according to the following definition: \chapter{Top-Level Definitions} \label{sec:topdefs} -- cgit v1.2.3