Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Type inference

No description
by

Svetlana Isakova

on 12 December 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Type inference

Светлана Исакова
Система типов — это гибко управляемый
синтаксический
метод доказательства
отсутствия
в программе определенных видов поведения при помощи
классификации
выражений языка по разновидностям вычисляемых ими значений.
Языки программирования
статически
типизированные
динамически
типизированные
Java
C#
Scala
Kotlin
Groovy
Python
Ruby
JavaScript
Б.Пирс
Синтаксис языка
Avoid NPE
Avoid ClassCastException
Статическая
типизация

performance
поддержка ide
безопасность
простота
больше тестов
изменение типа объекта "на лету"
MissingMethodException
Local type inference
Тип
String <: Any
Int <: Int
Int <: Any
String <: Int
Подтип
S T
S является подтипом T
Примеры:
Integer Object
ArrayList<String> List<String>
Отношение рефлексивно и транзитивно:
S <: S
S <: U U <: T => S <: T
String <:
T
List<Int> <: List<
T
>
T
= Any
Generic functions
Overloads
Default argument values:
Правила типизации
числ.константа : Integer
строковый литерал : String
переменная : ее тип
вызов метода : тип возвращаемого значения
...
Вызов функции
Type of function invocation
foo(a1, ... aN)
foo
Берем все функции "foo"
Про каждую проверяем,
можно ли ее вызвать
Выбираем
"most specific"
Динамическая
типизация

vs
Most specific function
Int <: Int
String <: Any
Int <: Any
String <: String
Int <: Any
Any <: String
Any <: Int
String <: Any
Poly expressions
тип зависит от "target" типа
Выбор функции не зависит от target типа!
Находим типы аргументов
a1 : T1
aN : TN
...
Java 7 vs Java 8
Lambdas
Lambdas
Constraints
List<E> : List<T>
Set<T> <: Set<Int>
E <: T
T <: Int
=>
=>
E <: Int
T <: Int
E = Int
T = Int
Type inference algorithm
Reduction
Incorporation
Resolution
выписываем ограничения для типов аргументов
упрощаем систему ограничений
находим подходящий результат для каждой переменной
Java 7
Java 8
error
ok
Variance
Animal
Crocodile
Alligator
Product
Bag
HermesBag
Animal
Crocodile
Alligator
Product
Bag
HermesBag
Function<Crocodile, Bag>
Animal
Crocodile
Alligator
Product
Bag
HermesBag
(Crocodile) -> Bag
(Animal) -> HermesBag
<:
Function<Animal, HermesBag>
<:
Function<Crocodile, Bag>
Function has:
- contravariant (in) type parameter P
- covariant (out) type parameter R
Covariant:
Contravariant:
Invariant:
ImmutableList<Crocodile>
ImmutableList<Animal>
<:
Function<in P, out R>
Comparator<Crocodile>
<:
Comparator<Animal>
Incompatible parameter types in lambda expression
Java: use-site variance
Declaration-site variance
Most specific function
Int <: Any
Any <: String
Any <: Int
String <: Any
Overload resolution ambiguity
Thank you!
Какая функция будет вызвана?
Incompatible types.
Required:
Found:
Collection<java.lang.Object>
Collection<java.lang.Integer>
Какая функция будет вызвана?
Ambiguous method call
ArrayStoreException
Object[ ]
<:
String[ ]
found: 'List<? extends Number>'
required 'List<? extends Number>'
List<capture#1 of ? extends Number>
Выбор функции не зависит от target типа!
не надо покрывать Unit тестами то, что может проверить компилятор
frameworks
Типы динамически
проверяются
!
Динамическая
типизация
описание множества значений
Integer, String, List<String>
Вывод типов деклараций
Вывод типов выражений
List<String> list = newArrayList(1, 2, 3);
"abc".substring("a");
List<Integer>
String
substring(int)
Типы & Классы
Foo
List<String>
List<List<Integer>>
Вызов метода
String foo(Serializable i)
foo(1)
Integer <: Serializable
String
foo("abc")
String <: Serializable
String
Вызов метода
String String
Integer
Integer String
---
Вызов метода (2)
Integer Integer
String
String Object
Тип вызова метода foo(a1, ... aN)
foo
foo
Проверяем, можно ли вызвать foo от этих аргументов
Находим типы аргументов
a1 : T1
aN : TN
...
foo
foo
Выписываем систему ограничений - проверяем, все ли выполняются
T1 P1
...
TN PN
Generic function
String
Integer T
List<T>
List<String> List<T>
Generic function (2)
Number
Integer T
Double T
Тип вызова функции foo(a1, ... aN)
foo
foo
Находим типы аргументов
a1 : T1
aN : TN
...
foo
foo
Выписываем систему ограничений - проверяем, существует ли решение системы
T1 P1
...
TN PN
T = String
Overloads
'emptyList' in Java 7
List<Object> List<String>
List<E> List<String>
E = String
Вывод типов
Выражений
Integer
Типовых аргументов
String
E = Integer
Тип - множество значений
Подтип - подмножество значений
Вывод типовых аргументов
List<Reader> readers =
Collections.singletonList(new FileReader(file));
List<Reader> readers =
Collections.<Reader>singletonList(new FileReader(file));
sigletonList
Lists vs Arrays
Reader[] readers =
new FileReader[] { new FileReader(file) };
List<Reader>
List<FileReader>
Reader[]
FileReader[]
String[] strings = new String[] { "yes", "no", "may be" };
Object[] objects = strings;
objects[0] = 42; //ArrayStoreException
List<String> strings = Lists.newArrayList("yes", "no", "may be");
List<Object> objects = (List)strings;
objects.add(42);

for (String s : strings) {} //ClassCastException
Covariant ImmutableList<T>
безопасно
ImmutableList<Object>
ImmutableList<String>
Predicate<Crocodile>
Lambdas
List<? extends Number> List<T>
List<? extends Number> List<T>
T = capture#1 of ? extends Number
T = capture#2 of ? extends Number
Captured types
List<? extends Number> List<T>
T = capture#1 of ? extends Number
Вывод типов из control flow
smart casts
checker framework (?)
Global type inference
-- id :: Int -> Int
id x = x
mysum :: Int -> (Int -> Int)
mysum x y = x + y
d = (mysum 2) 2

callMe f x = f x
fac 0 = 1
fac n = n*fac (n-1)

callMeSquared :: (Num a) => (a -> t) -> a -> t
callMeSquared f x = f x*x

-- problem = callMeSquared show 42
'emptyList' in Java 8
Находим тип аргумента с точностью до неизвестных типовых переменных
List<E> List<T>
Set<T> Set<String>
E = T
T = String
=>
=>
E = String
T = String
Система ограничений
Animal
Crocodile
Predicate<Crocodile>
Predicate<Animal>
безопасно
Predicate<in T>
Predicate<? super Crocodile>
Animal
Crocodile
List<Student> students = persons.stream() // Stream<Person>
.filter(p -> p.getAge() > 18) // Stream<Person>
//Person
.map(p -> new Student()) // Stream<Student>
//Function<Person, Student>
.collect(Collectors.toList()); // List<Student>

Lambdas (2)
List<Student> students = stream.collect(Collectors.toList());
//Stream<Student> //Collector<T, List<T>>

interface Stream<E> {
<R> R collect(Collector<E, R> collector);
}

<R, A> R collect(Collector<Student, R> collector)
Collector<T, List<T>> <: Collector<Student, R>
T = Student
R = List<T>
R = List<Student>
*
на самом деле все чуть сложнее
Lambdas (3)
List<Student> students = stream.collect(Collectors.toList());
//Stream<Student> //Collector<T, ?, List<T>>

interface Stream<E> {
<R, A> R collect(Collector<? super E, A, R> collector);
}

<R, A> R collect(Collector<? super Student, A, R> collector)
Collector<T, ?, List<T>> <: Collector<? super Student, A, R>
T >: Student
R = List<T>
R = List<Student>
1
T = Integer
Почему не T >: String?..
Java 1.4
Java 1.5
List<T>
kotlin.List (ReadOnly)
List<Object>
List<String>
безопасно
'emptyList'
List<E> List<String>
E = String
E = Object
List<Object>
Generic function (3)
T String
Integer T
Double T
Находим тип аргумента, не учитывая "target" тип
List<E> <: List<? extends Number>
E <: Number
public void foo(List<? extends Number>)
foo(Collections.emptyList())
E = Number
List<? extends Number>
Спасибо!
Примеры:
Lambdas
// проверяем ограничение
// выводим тип аргумента
Lambdas (2)
выводим тип s (аргумента лямбды),
анализируем лямбду,
добавляются новые ограничения
Простыми словами
про вывод типов

String String
"Stronger typing with less typing" - No casts!
J.Bloch
Integer String
Классификация выражений языка
Integer:
String:
List<String>:
Отсутствие в программе определенных ошибок
ClassNotFoundException
NoSuchMethodError
NoSuchFieldException
IllegalAccessException


NullPointerException
ClassCastException
ArrayStoreException
how to fix groovy.lang.MissingMethodException
...because you are passing three arguments to a four arguments method
Haskell
Java
Groovy, Ruby, Python...
борьба с компилятором
борьба с ошибками (покрытие тестами)
Строгость системы типов
Kotlin
Integer
foo
1
foo
1
foo
2
foo
3
foo
2
foo
3
=>
T = Number
ClassCastException
Captured types (2)
List<capture#2 of ? extends Number>
Crocodile <: Crocodile
(Animal) -> Boolean
Predicate<? super Crocodile>
Predicate<Animal>
Predicate<? super Crocodile>
possible
ClassCastException
incompatible parameter types in lambda expression
*
Full transcript