Newer
Older
% Type-Directed Programming
%
%
Reminder: General `sort` Operation
==================================
~~~
def sort[A](xs: List[A])(ord: Ordering[A]): List[A] = ...
~~~
Problem: passing around `Ordering` arguments is cumbersome.
~~~
sort(xs)(Ordering.Int)
sort(ys)(Ordering.Int)
sort(strings)(Ordering.String)
~~~
Sorting a `List[Int]` value always uses the same `Ordering.Int` argument,
sorting a `List[String]` value always uses the same `Ordering.String`
argument, and so on…
We can reduce the boilerplate by making `ord` an **implicit parameter**.
def sort[A](xs: List[A])(given ord: Ordering[A]): List[A] = ...
Then, calls to `sort` can omit the `ord` parameter:
~~~
sort(xs)
sort(ys)
sort(strings)
~~~
The compiler infers the argument value based on its type.
Implicit Parameters (2)
=======================
~~~
def sort[A](xs: List[A])(given ord: Ordering[A]): List[A] = ...
val xs: List[Int] = ...
~~~
->
~~~
sort(xs)
~~~
->
~~~
sort[Int](xs)
~~~
->
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
In this case, the type of `ord` is `Ordering[Int]`.
->
~~~
sort[Int](xs)(given Ordering.Int)
~~~
(assuming there exists a **given instance** of type `Ordering[Int]` named `Ordering.Int`)
Given Clauses Syntax Reference (1)
==================================
There can be several `given` parameter clauses in a definition and `given`
parameter clauses can be freely mixed with normal ones.
~~~
def sort[A](xs: List[A])(given ord: Ordering[Int]): List[A] = ...
~~~
At call site, the arguments of the given clause are usually left out, although it is
possible to explicitly pass them:
~~~
// Argument inferred by the compiler
sort(xs)
// Explicit argument
sort(xs)(given Ordering.Int.reverse)
~~~
Given Clauses Syntax Reference (2)
==================================
Multiple parameters can be in a `given` clause:
~~~
def f(x: Int)(given foo: Foo, bar: Bar) = ...
~~~
Or, there can be several `given` clauses in a row:
~~~
def f(x: Int)(given foo: Foo)(given bar: Bar) = ...
~~~
Given Clauses Syntax Reference (3)
==================================
Parameters of a given clause can be anonymous:
def sort[A](xs: List[A])(given Ordering[A]): List[A] = ...
This is useful if the body of `sort` does not mention `ord`
at all, but simply relies on the fact that there is an
available given instance of type `Ordering[A]`.
Implicit Parameters Resolution
==============================
Say, a function takes an implicit parameter of type `T`.
The compiler will search a **given instance** that:
- has a type compatible with `T`,
- is visible at the point of the function call, or is defined
in a companion object *associated* with `T`.
If there is a single (most specific) instance, it will be taken
as actual arguments for the implicit parameter.
Otherwise it’s an error.
Given Instances
===============
For the previous example to work, the `Ordering.Int` definition
must be a `given` instance:
given Int: Ordering[Int] {
def compare(x: Int, y: Int): Int = ...
}
This code defines a given instance of type `Ordering[Int]`, named `Int`.
Given Instances Syntax Reference
================================
Given instances can be anonymous. Just omit the instance name:
~~~
given Ordering[Int] { ... }
~~~
Given instances can take type parameters and implicit parameters:
~~~
given [A, B](given Ordering[A], Ordering[B]): Ordering[(A, B)] { ... }
~~~
An alias can be used to define a given instance:
~~~
given Ordering[Int] = ...
~~~
Given Instances Search Scope
============================
The search for a given instance of type `T` includes:
- all the given instances that are visible (inherited, or defined in
an enclosing scope),
- all the given instances that are imported via a “given import”,
- the *implicit scope* of type `T`, made of given instances found
in a companion object *associated* with `T`. In essence$^*$, the types
associated with a type `T` are:
- if `T` is a compound type $T_1 with T_2 ... with T_n$, the union
of the parts of $T_1$, ... $T_n$ as well as $T$ itself,
- if `T` is a parameterized type $S[T_1, T_2, ..., T_n]$, the union
of the parts of $S$ and $T_1$, ..., $T_n$,
- otherwise, just `T` itself.
In the case of the `sort(xs)` call, the compiler looks for an implicit
`Ordering[Int]` definition, which is found in the `Ordering` companion
object.
No Given Instance Found
=======================
If there is no available given instance matching the queried type,
scala> def f(given n: Int) = ()
error: no implicit argument of type Int was found for parameter n of method f
Ambiguous Given Instances
=========================
If more than one given instances are eligible, an **ambiguity** is reported:
scala> given x: Int = 0
scala> given y: Int = 1
scala> def f(given n: Int) = ()
error: ambiguous implicit arguments:
both value x and value y
match type Int of parameter n of method f
Actually, several given instances matching the same type don’t generate an
ambiguity if one is **more specific** than the other.
In essence$^{*}$, a `given a: A` definition is more specific than a
`given b: B` definition if:
- type `A` is a subtype of type `B`,
- type `A` has more “fixed” parts,
- `a` is defined in a class or object which is a subclass of the class defining `b`,
- `a` is in a closer lexical scope than `b`.
Priorities: Example (1)
=======================
Which given instance matches the `Int` implicit parameter when
given universal[A]: A = ???
given int: Int = ???
def f(given n: Int) = ()
f
~~~
Priorities: Example (2)
=======================
Which given instance matches the `Int` implicit parameter when
given y: Int = 1
def f(given n: Int) = ()
f
}
~~~
Priorities: Example (3)
=======================
Which implied instance matches the queried `Int` implicit parameter when
the `f` method is called?
~~~
given x: Int = 0
locally {
given y: Int = 1
def f(given n: Int) = ()
f
}
~~~
Context Bounds
==============
A syntactic sugar allows the omission of the given clause:
~~~
def printSorted[A: Ordering](as: List[A]): Unit = {
println(sort(as))
}
~~~
Type parameter `A` has one **context bound**: `Ordering`. There must be a
given instance of type `Ordering[A]` at the point of application.
More generally, a method definition such as:
$def f[A: U_1 ... : U_n](ps): R = ...$
Is expanded to:
$def f[A](ps)(given U_1[A], ..., U_n[A]): R = ...$
At any point in a program, one can **query** a given instance of
a specific type by calling the `summon` operation:
scala> summon[Ordering[Int]]
res0: Ordering[Int] = scala.math.Ordering$Int$@73564ab0
~~~
`summon` is not a special keyword, it is defined as a library operation:
def summon[A](given value: A): value.type = value
In this lecture we have introduced the concept of **type-directed programming**,
a language mechanism that infers **values** by using **type** information.
There has to be a **unique** given instance matching the queried type
Given instances are searched in the enclosing **lexical scope** (imports,
parameters, inherited members) as well as in the **given instances search scope**
made of given instances defined in companion objects of types associated with the