preface and lexical syntax chapter converted, other chapters

split into their own files

1 files changed, 419 insertions, 0 deletions

diff --git a/09-implicit-parameters-and-views.md b/09-implicit-parameters-and-views.md
new file mode 100644
index 0000000000..1caef761ed
--- /dev/null
+++ b/09-implicit-parameters-and-views.md
@@ -0,0 +1,419 @@
+Implicit Parameters and Views
+=============================
+
+\section{The Implicit Modifier}\label{sec:impl-defs}
+
+\syntax\begin{lstlisting}
+  LocalModifier  ::= `implicit'
+  ParamClauses   ::= {ParamClause} [nl] `(' `implicit' Params `)'
+\end{lstlisting}
+
+Template members and parameters labeled with an \code{implicit}
+modifier can be passed to implicit parameters (\sref{sec:impl-params})
+and can be used as implicit conversions called views
+(\sref{sec:views}). The \code{implicit} modifier is illegal for all
+type members, as well as for top-level (\sref{sec:packagings})
+objects.
+
+\example\label{ex:impl-monoid}
+The following code defines an abstract class of monoids and
+two concrete implementations, \code{StringMonoid} and
+\code{IntMonoid}. The two implementations are marked implicit.
+
+\begin{lstlisting}
+abstract class Monoid[A] extends SemiGroup[A] {
+  def unit: A
+  def add(x: A, y: A): A
+}
+object Monoids {
+  implicit object stringMonoid extends Monoid[String] {
+    def add(x: String, y: String): String = x.concat(y)
+    def unit: String = ""
+  }
+  implicit object intMonoid extends Monoid[Int] {
+    def add(x: Int, y: Int): Int = x + y
+    def unit: Int = 0
+  }
+}
+\end{lstlisting}
+
+\section{Implicit Parameters}\label{sec:impl-params}
+
+An implicit parameter list
+~\lstinline@(implicit $p_1$,$\ldots$,$p_n$)@~ of a method marks the parameters $p_1 \commadots p_n$ as
+implicit. A method or constructor can have only one implicit parameter
+list, and it must be the last parameter list given.
+
+A method with implicit parameters can be applied to arguments just
+like a normal method. In this case the \code{implicit} label has no
+effect. However, if such a method misses arguments for its implicit
+parameters, such arguments will be automatically provided.
+
+The actual arguments that are eligible to be passed to an implicit
+parameter of type $T$ fall into two categories. First, eligible are
+all identifiers $x$ that can be accessed at the point of the method
+call without a prefix and that denote an implicit definition
+(\sref{sec:impl-defs}) or an implicit parameter.  An eligible
+identifier may thus be a local name, or a member of an enclosing
+template, or it may be have been made accessible without a prefix
+through an import clause (\sref{sec:import}). If there are no eligible
+identifiers under this rule, then, second, eligible are also all
+\code{implicit} members of some object that belongs to the implicit
+scope of the implicit parameter's type, $T$.
+
+The {\em implicit scope} of a type $T$ consists of all companion modules
+(\sref{sec:object-defs}) of classes that are associated with the
+implicit parameter's type.  Here, we say a class $C$ is {\em
+associated} with a type $T$, if it is a base class
+(\sref{sec:linearization}) of some part of $T$.  The {\em parts} of a
+type $T$ are:
+\begin{itemize}
+\item
+if $T$ is a compound type ~\lstinline@$T_1$ with $\ldots$ with $T_n$@, the
+union of the parts of $T_1 \commadots T_n$, as well as $T$ itself,
+\item
+if $T$ is a parameterized type ~\lstinline@$S$[$T_1 \commadots T_n$]@, 
+the union of the parts of $S$ and $T_1 \commadots T_n$,
+\item
+if $T$ is a singleton type ~\lstinline@$p$.type@, the parts of the type
+of $p$,
+\item
+if $T$ is a type projection ~\lstinline@$S$#$U$@, the parts of $S$ as
+well as $T$ itself,
+\item
+in all other cases, just $T$ itself.
+\end{itemize}
+
+If there are several eligible arguments which match the implicit
+parameter's type, a most specific one will be chosen using the rules
+of static overloading resolution (\sref{sec:overloading-resolution}).
+If the parameter has a default argument and no implicit argument can
+be found the default argument is used.
+
+\example Assuming the classes from \ref{ex:impl-monoid}, here is a 
+method which computes the sum of a list of elements using the
+monoid's \code{add} and \code{unit} operations.
+\begin{lstlisting}
+def sum[A](xs: List[A])(implicit m: Monoid[A]): A = 
+  if (xs.isEmpty) m.unit
+  else m.add(xs.head, sum(xs.tail))
+\end{lstlisting}
+The monoid in question is marked as an implicit parameter, and can therefore
+be inferred based on the type of the list.
+Consider for instance the call 
+\begin{lstlisting}
+  sum(List(1, 2, 3))
+\end{lstlisting}
+in a context where \lstinline@stringMonoid@ and \lstinline@intMonoid@
+are visible.  We know that the formal type parameter \lstinline@a@ of
+\lstinline@sum@ needs to be instantiated to \lstinline@Int@. The only
+eligible object which matches the implicit formal parameter type
+\lstinline@Monoid[Int]@ is \lstinline@intMonoid@ so this object will
+be passed as implicit parameter.\bigskip
+
+This discussion also shows that implicit parameters are inferred after
+any type arguments are inferred (\sref{sec:local-type-inf}). 
+
+Implicit methods can themselves have implicit parameters. An example
+is the following method from module \code{scala.List}, which injects
+lists into the \lstinline@scala.Ordered@ class, provided the element
+type of the list is also convertible to this type.
+\begin{lstlisting}
+implicit def list2ordered[A](x: List[A])
+  (implicit elem2ordered: A => Ordered[A]): Ordered[List[A]] = 
+  ...
+\end{lstlisting}
+Assume in addition a method
+\begin{lstlisting}
+implicit def int2ordered(x: Int): Ordered[Int]
+\end{lstlisting}
+that injects integers into the \lstinline@Ordered@ class.  We can now
+define a \code{sort} method over ordered lists:
+\begin{lstlisting}
+def sort[A](xs: List[A])(implicit a2ordered: A => Ordered[A]) = ...
+\end{lstlisting}
+We can apply \code{sort} to a list of lists of integers ~\lstinline@yss: List[List[Int]]@~ 
+as follows:
+\begin{lstlisting}
+sort(yss)
+\end{lstlisting}
+The call above will be completed by passing two nested implicit arguments:
+\begin{lstlisting}
+sort(yss)(xs: List[Int] => list2ordered[Int](xs)(int2ordered)) .
+\end{lstlisting}
+The possibility of passing implicit arguments to implicit arguments
+raises the possibility of an infinite recursion.  For instance, one
+might try to define the following method, which injects {\em every} type into the \lstinline@Ordered@ class:
+\begin{lstlisting}
+implicit def magic[A](x: A)(implicit a2ordered: A => Ordered[A]): Ordered[A] = 
+  a2ordered(x)
+\end{lstlisting}
+Now, if one tried to apply
+\lstinline@sort@ to an argument \code{arg} of a type that did not have
+another injection into the \code{Ordered} class, one would obtain an infinite
+expansion:
+\begin{lstlisting}
+sort(arg)(x => magic(x)(x => magic(x)(x => ... )))
+\end{lstlisting}
+To prevent such infinite expansions, the compiler keeps track of 
+a stack of ``open implicit types'' for which implicit arguments are currently being
+searched. Whenever an implicit argument for type $T$ is searched, the
+``core type'' of $T$ is added to the stack. Here, the {\em core type}
+of $T$ is $T$ with aliases expanded, top-level type annotations (\sref{sec:annotations}) and
+refinements (\sref{sec:refinements}) removed, and occurrences
+of top-level existentially bound variables replaced by their upper
+bounds. The core type is removed from the stack once the search for
+the implicit argument either definitely fails or succeeds. Everytime a
+core type is added to the stack, it is checked that this type does not
+dominate any of the other types in the set.
+
+Here, a core type $T$ {\em dominates} a type $U$ if $T$ is equivalent (\sref{sec:type-equiv})
+to $U$, or if the top-level type constructors of $T$ and $U$ have a
+common element and $T$ is more complex than $U$.
+
+The set of {\em top-level type constructors} $\ttcs(T)$ of a type $T$ depends on the form of
+the type:
+\begin{quote}
+For a type designator, \\
+$\ttcs(p.c) ~=~ \{c\}$; \\
+For a parameterized type, \\
+$\ttcs(p.c[\targs]) ~=~ \{c\}$; \\
+For a singleton type, \\
+$\ttcs(p.type) ~=~ \ttcs(T)$, provided $p$ has type $T$;\\
+For a compound type, \\
+\lstinline@$\ttcs(T_1$ with $\ldots$ with $T_n)$@ $~=~ \ttcs(T_1) \cup \ldots \cup \ttcs(T_n)$.
+\end{quote}
+
+The {\em complexity} $\complx(T)$ of a core type is an integer which also depends on the form of
+the type:
+\begin{quote}
+For a type designator, \\
+$\complx(p.c) ~=~ 1 + \complx(p)$ \\
+For a parameterized type, \\
+$\complx(p.c[\targs]) ~=~ 1 + \Sigma \complx(\targs)$ \\
+For a singleton type denoting a package $p$, \\
+$\complx(p.type) ~=~ 0$ \\
+For any other singleton type, \\
+$\complx(p.type) ~=~ 1 + \complx(T)$, provided $p$ has type $T$;\\
+For a compound type, \\
+\lstinline@$\complx(T_1$ with $\ldots$ with $T_n)$@ $= \Sigma\complx(T_i)$
+\end{quote}
+
+\example When typing \code{sort(xs)} for some list \code{xs} of type \code{List[List[List[Int]]]}, 
+the sequence of types for 
+which implicit arguments are searched is 
+\begin{lstlisting}
+List[List[Int]] => Ordered[List[List[Int]]], 
+List[Int] => Ordered[List[Int]]
+Int => Ordered[Int]
+\end{lstlisting}
+All types share the common type constructor \code{scala.Function1}, 
+but the complexity of the each new type is lower than the complexity of the previous types. 
+Hence, the code typechecks.
+
+\example Let \code{ys} be a list of some type which cannot be converted
+to \code{Ordered}. For instance:
+\begin{lstlisting}
+val ys = List(new IllegalArgumentException, new ClassCastException, new Error)
+\end{lstlisting}
+Assume that the definition of \code{magic} above is in scope. Then the sequence
+of types for which implicit arguments are searched is 
+\begin{lstlisting}
+Throwable => Ordered[Throwable],
+Throwable => Ordered[Throwable],
+...
+\end{lstlisting}
+Since the second type in the sequence is equal to the first, the compiler
+will issue an error signalling a divergent implicit expansion.
+
+\section{Views}\label{sec:views}
+
+Implicit parameters and methods can also define implicit conversions
+called views. A {\em view} from type $S$ to type $T$ is
+defined by an implicit value which has function type
+\lstinline@$S$=>$T$@ or \lstinline@(=>$S$)=>$T$@ or by a method convertible to a value of that
+type.
+
+Views are applied in three situations.
+\begin{enumerate}
+\item
+If an expression $e$ is of type $T$, and $T$ does not conform to the
+expression's expected type $\proto$. In this case an implicit $v$ is
+searched which is applicable to $e$ and whose result type conforms to
+$\proto$.  The search proceeds as in the case of implicit parameters,
+where the implicit scope is the one of ~\lstinline@$T$ => $\proto$@. If
+such a view is found, the expression $e$ is converted to
+\lstinline@$v$($e$)@. 
+\item
+In a selection $e.m$ with $e$ of type $T$, if the selector $m$ does
+not denote a member of $T$.  In this case, a view $v$ is searched
+which is applicable to $e$ and whose result contains a member named
+$m$.  The search proceeds as in the case of implicit parameters, where
+the implicit scope is the one of $T$.  If such a view is found, the
+selection $e.m$ is converted to \lstinline@$v$($e$).$m$@.
+\item
+In a selection $e.m(\args)$ with $e$ of type $T$, if the selector
+$m$ denotes some member(s) of $T$, but none of these members is applicable to the arguments
+$\args$. In this case a view $v$ is searched which is applicable to $e$ 
+and whose result contains a method $m$ which is applicable to $\args$.
+The search proceeds as in the case of implicit parameters, where
+the implicit scope is the one of $T$.  If such a view is found, the
+selection $e.m$ is converted to \lstinline@$v$($e$).$m(\args)$@.
+\end{enumerate}
+The implicit view, if it is found, can accept is argument $e$ as a
+call-by-value or as a call-by-name parameter. However, call-by-value
+implicits take precedence over call-by-name implicits.
+
+As for implicit parameters, overloading resolution is applied
+if there are several possible candidates (of either the call-by-value
+or the call-by-name category).
+
+\example\label{ex:impl-ordered} Class \lstinline@scala.Ordered[A]@ contains a method
+\begin{lstlisting}
+  def <= [B >: A](that: B)(implicit b2ordered: B => Ordered[B]): Boolean .
+\end{lstlisting}
+Assume two lists \code{xs} and \code{ys} of type \code{List[Int]}
+and assume that the \code{list2ordered} and \code{int2ordered}
+methods defined in \sref{sec:impl-params} are in scope.
+Then the operation
+\begin{lstlisting}
+  xs <= ys
+\end{lstlisting}
+is legal, and is expanded to:
+\begin{lstlisting}
+  list2ordered(xs)(int2ordered).<=
+    (ys)
+    (xs => list2ordered(xs)(int2ordered))
+\end{lstlisting}
+The first application of \lstinline@list2ordered@ converts the list
+\code{xs} to an instance of class \code{Ordered}, whereas the second 
+occurrence is part of an implicit parameter passed to the \code{<=}
+method.
+
+\section{Context Bounds and View Bounds}\label{sec:context-bounds}
+
+\syntax\begin{lstlisting}
+  TypeParam ::= (id | `_') [TypeParamClause] [`>:' Type] [`<:'Type] 
+                {`<%' Type} {`:' Type}
+\end{lstlisting}
+
+A type parameter $A$ of a method or non-trait class may have one or more view
+bounds \lstinline@$A$ <% $T$@. In this case the type parameter may be
+instantiated to any type $S$ which is convertible by application of a 
+view to the bound $T$.
+
+A type parameter $A$ of a method or non-trait class may also have one
+or more context bounds \lstinline@$A$ : $T$@. In this case the type parameter may be
+instantiated to any type $S$ for which {\em evidence} exists at the
+instantiation point that $S$ satisfies the bound $T$. Such evidence
+consists of an implicit value with type $T[S]$.
+
+A method or class containing type parameters with view or context bounds is treated as being
+equivalent to a method with implicit parameters. Consider first the case of a
+single parameter with view and/or context bounds such as:
+\begin{lstlisting}
+def $f$[$A$ <% $T_1$ ... <% $T_m$ : $U_1$ : $U_n$]($\ps$): $R$ = ...
+\end{lstlisting}
+Then the method definition above is expanded to
+\begin{lstlisting}
+def $f$[$A$]($\ps$)(implicit $v_1$: $A$ => $T_1$, ..., $v_m$: $A$ => $T_m$,
+                       $w_1$: $U_1$[$A$], ..., $w_n$: $U_n$[$A$]): $R$ = ...
+\end{lstlisting}
+where the $v_i$ and $w_j$ are fresh names for the newly introduced implicit parameters. These
+parameters are called {\em evidence parameters}.
+
+If a class or method has several view- or context-bounded type parameters, each
+such type parameter is expanded into evidence parameters in the order
+they appear and all the resulting evidence parameters are concatenated
+in one implicit parameter section.  Since traits do not take
+constructor parameters, this translation does not work for them.
+Consequently, type-parameters in traits may not be view- or context-bounded.
+Also, a method or class with view- or context bounds may not define any
+additional implicit parameters.
+
+\example The \code{<=} method mentioned in \ref{ex:impl-ordered} can be declared
+more concisely as follows:
+\begin{lstlisting}
+  def <= [B >: A <% Ordered[B]](that: B): Boolean
+\end{lstlisting}
+
+\section{Manifests}\label{sec:manifests}
+
+\newcommand{\Mobj}{\mbox{\sl Mobj}}
+
+Manifests are type descriptors that can be automatically generated by
+the Scala compiler as arguments to implicit parameters. The Scala
+standard library contains a hierarchy of four manifest classes, 
+with \lstinline@OptManifest@
+at the top. Their signatures follow the outline below.
+\begin{lstlisting}
+trait OptManifest[+T]
+object NoManifest extends OptManifest[Nothing]
+trait ClassManifest[T] extends OptManifest[T]
+trait Manifest[T] extends ClassManifest[T]
+\end{lstlisting}
+
+If an implicit parameter of a method or constructor is of a subtype $M[T]$ of
+class \lstinline@OptManifest[T]@, {\em a manifest is determined for $M[S]$},
+according to the following rules.
+
+First if there is already an implicit argument that matches $M[T]$, this
+argument is selected.
+
+Otherwise, let $\Mobj$ be the companion object \lstinline@scala.reflect.Manifest@
+if $M$ is trait \lstinline@Manifest@, or be
+the companion object \lstinline@scala.reflect.ClassManifest@ otherwise. Let $M'$ be the trait
+\lstinline@Manifest@ if $M$ is trait \lstinline@Manifest@, or be the trait \lstinline@OptManifest@ otherwise.  
+Then the following rules apply.
+
+
+\begin{enumerate}
+\item
+If $T$ is a value class or one of the classes \lstinline@Any@, \lstinline@AnyVal@, \lstinline@Object@, 
+\lstinline@Null@, or \lstinline@Nothing@,
+a manifest for it is generated by selecting
+the corresponding manifest value \lstinline@Manifest.$T$@, which exists in the
+\lstinline@Manifest@ module.
+\item
+If $T$ is an instance of \lstinline@Array[$S$]@, a manifest is generated
+with the invocation \lstinline@$\Mobj$.arrayType[S](m)@, where $m$ is the manifest
+determined for $M[S]$.
+\item
+If $T$ is some other class type $S\#C[U_1 \commadots U_n]$ where the prefix type $S$ 
+cannot be statically determined from the class $C$, 
+a manifest is generated 
+with the invocation \lstinline@$\Mobj$.classType[T]($m_0$, classOf[T], $ms$)@
+where $m_0$ is the manifest determined for $M'[S]$ and $ms$ are the
+manifests determined for $M'[U_1] \commadots M'[U_n]$.
+\item
+If $T$ is some other class type with type arguments $U_1 \commadots U_n$, 
+a manifest is generated 
+with the invocation \lstinline@$\Mobj$.classType[T](classOf[T], $ms$)@
+where $ms$ are the
+manifests determined for $M'[U_1] \commadots M'[U_n]$.
+\item 
+If $T$ is a singleton type ~\lstinline@$p$.type@, a manifest is generated with 
+the invocation
+\lstinline@$\Mobj$.singleType[T]($p$)@ 
+\item
+If $T$ is a refined type $T' \{ R \}$, a manifest is generated for $T'$.
+(That is, refinements are never reflected in manifests).
+\item
+If $T$ is an intersection type 
+\lstinline@$T_1$ with $\commadots$ with $T_n$@ 
+where $n > 1$, the result depends on whether a full manifest is
+to be determined or not. 
+If $M$ is trait \lstinline@Manifest@, then
+a manifest is generated with the invocation
+\lstinline@Manifest.intersectionType[T]($ms$)@ where $ms$ are the manifests
+determined for $M[T_1] \commadots M[T_n]$.
+Otherwise, if $M$ is trait \lstinline@ClassManifest@, 
+then a manifest is generated for the intersection dominator
+(\sref{sec:erasure})
+of the types $T_1 \commadots T_n$.
+\item
+If $T$ is some other type, then if $M$ is trait \lstinline@OptManifest@, 
+a manifest is generated from the designator \lstinline@scala.reflect.NoManifest@.
+If $M$ is a type different from \lstinline@OptManifest@, a static error results.
+\end{enumerate}
+