progfun2-4-2.md

% 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…

Implicit Parameters
===================

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)
~~~

->

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:

~~~
object Ordering {

  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,
an error is reported:

~~~
scala> def f(given n: Int) = ()
scala> f
       ^
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) = ()
scala> f
       ^
error: ambiguous implicit arguments:
 both value x and value y
 match type Int of parameter n of method f
~~~

Priorities
==========

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
the `f` method is called?

~~~
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
the `f` method is called?

~~~
trait A {
  given x: Int = 0
}
trait B extends A {
  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 = ...$

Implicit Query
==============

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
~~~

Summary
=======

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
for it to be used by the compiler.

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
queried type.