Обобщения (параметрический полиморфизм)

Текущее состояние

Libretto ограниченно поддерживает обобщения (вид параметрического полиморфизма).

Пользователь может определять только трейты и структуры с переменными типа. Но ограничения на переменные типа не описываются (можно подставлять любые типы).

Нельзя определять обобщения объединений. (todo)

Использовать переменные типа в определениях методов или функций нельзя на уровне пользовательского программирования, но в стандартном окружении Libretto есть встроенные (библиотечные) методы, которые используют переменные типа. В будущем, возможно, появится и соответствующая пользовательская возможность.

Зачем нужны обобщения

Например, нужно определить структуру для хранения пар значений (кортеж из двух элементов). Если сделать обычным способом, то придётся указывать наиболее общий тип Any:

struct Pair(a: Any, b: Any)

Но это неудобно для работы при статической типизации. Придётся делать преобразования типов при получении элементов.

Можно определять структуру для каждого случая:

struct PairIntInt(a: Int, b: Int)
struct PairIntString(a: Int, b: String)
struct PairValueTree(a: Value, b: Tree)
// и так далее

Но это очень громоздко. Поэтому и нужен параметрический полиморфизм - возможность использования переменных типа (в данном случае переменные типа структуры).

В Libretto частично реализован простой вариант параметрического полиморфизма - “обобщения” (generics). В будущем, возможно, будут добавлены ограничения на параметры типов (ограниченная квантификация).

Например, в Libretto можно сделать обобщенное определение пары:

struct Pair[A, B](a: A, b: B)

Здесь A и B в квадратных скобках [] - это переменные типа Pair, которые превратят Pair в конкретный тип структуры при подстановке значений типов.

Это означает, что можно использовать Pair с указание конкретных типов для подстановки в A и B тоже при помощи квадратных скобок [].

Pair[Int, Int]
Pair[Int, String]
Pair[Value, Tree]

Обобщения в Libretto можно использовать для трейтов и структур. В будущем, возможно, будет реализовано обобщение для объединений и пользовательских методов.

Важно, что обобщения в Libretto используются для работы с отображениями (мэпами) при помощи обобщенного трейта Map[K, V] и обобщенного метода map[K, V]. Это позволило не делать отображения конструкцией языка, а реализовать на уровне библиотеки (пакета libretto).

Имя и квадратные скобки []

В текущей реализации считается, что квадратные [] скобки, которые служат для указания имен (при определении) и значений (при использовании) переменных типа, всегда располагаются после имени и синтаксически считаются его неотъемлемой частью.

Например, метод upcast с подстановкой типа SomeUnion имеет имя upcast[SomeUnion], которое используется целиком в таком виде:

• upcast[SomeUnion](value) - обычный синтаксис вызова
• value.*upcast[SomeUnit] - вызов через .*
• upcast[SomeUnit]: value - вызов через :

Аналогично и с именами трейтов и структур.

Обобщения трейтов

Можно использовать переменные типа в квадратных скобках для определения обобщения трейта.

trait Test[A, B] {
  def work(a: A): B
}

Это означает, что при использовании (подстановке значений переменных типа) будет автоматически создан трейт с уточнёнными типами методов.

Число имён переменных типа от 1 и далее.

Имена переменных типа должны быть уникальные, рекомендуется начинать с заглавной буквы. Обычно применяют просто заглавные буквы, но могут быть и другие варианты.

При разрешении имен типов в определениях методов трейта имя переменных типа приоритетно перед именами типов.

// пример плохого стиля
trait Test[Int] {
  def result: Int // Int - это имя переменной типа, а не `Int` из `libretto`
}

def main = {
  fix t: Test[String] = new Test[String] {
    def result = "abc"
  }
  println: t.result
}

Выдаёт:

abc

В этом примере Int в определении Test обозначает имя переменной типа (которое будет String в этом примере), а не тип Int из пакета libretto. Чтобы избегать сложностей понимания, лучше не использовать имена переменных типа, которые могут быть восприняты как имена каких-то известных типов. Отсюда и обычное использование заглавных букв, которые больше подходят для имен переменных типа, а не для имени конкретного типа.

В определении методов трейта имена переменных типов используются всегда без указания кардинальности. Тип переменной типа (в том числе с опциональной кардинальностью) будет подставлен при использовании трейта:

Test[Int, String?] - в определении вместо A будет использован Int, а вместо B - String?, т.е. условно можно записать так:

// пример условный, не компилируется
trait Test[Int, String?] {
  def work(a: Int): String?
}

Возможно, что в будущем будет добавлено управление переменными типа при помощи обобщенных псевдотрейтов. (todo)

Одну и ту же переменную типа можно использовать несколько раз в определениях метода:

trait Calc[A] {
  def startValue: A
  def calc(a: A): A
}

def main = {
  fix calc = new Calc[Int*] {
    def startValue = 1..3
    def calc(a) = a.{ -$ }
  }
  println: calc.calc(calc.startValue)
}

Выдаёт:

(-1,-2,-3)

Если трейт определен с переменными типа, то использовать его можно только с подстановкой типов в квадратных скобках [].

// пример не компилируется
trait Test[A]

def main = {
  fix test: Test? = () // ошибка: неизвестный Test
}

И, наоборот, если трейт определен без переменных типа, то нельзя его использовать с подстановкой типов в квадратных скобках [].

// пример не компилируется
trait Test

def main = {
  fix test: Test[Int]? = () // ошибка: неизвестный Test
}

Для пользовательских трейтов с параметрами типов не допускается множественное определение с одним именем, даже если изменено число параметров типов:

// пример не компилируется
trait Test[A]
trait Test[A, B] // ошибка: уже есть Test

Единственное исключение - это псевдоним Func (из пакета libretto), который автоматически компилятором отображается в Func0, Func1 и т.д. (в зависимости от числа значений параметров типа). Его поддержка сделана на уровне компилятора. Возможно, что будущем это будет разрешено и для пользовательских определений.

Ещё одно ограничение в том, что нельзя одновременно определять трейт с параметрами типов и одноименный трейт вообще без параметров типа:

// пример не компилируется
trait Test[A]
trait Test // ошибка: уже есть Test

Определение трейта с переменными типа допускает рекурсию:

trait Entry[A] {
  def value: A
  def entries: Entry[A]*
  def string: String
}

def main = {
  def entry(entryValue: String, entryEntries: Entry[String]*) = {
    new Entry[String] {
      def value = entryValue
      def entries = entryEntries
      def string = "[" + this.value.string + 
        ", " + this.entries.string.*join(",") + "]"
    }
  }
  fix root = entry("root", (entry("a", ()), entry("b", entry("c", ()))))
  println: root
}

Выдаёт:

[root, [a, ],[b, [c, ]]]

Допускается использование и других обобщенных трейтов и структур, в том числе с типизацией переменными типа (todo Map, new трейт):

trait Base[A] {
  def value: A
}

trait Test[A, B] {
  def map(b: Base[A]): Base[B]
}

def main = {
  def intBase(v: Int) = new Base[Int] {
    def value = v
  }
  def stringBase(v: String) = new Base[String] {
    def value = v
  }
  fix t = new Test[Int, String] {
    def map(b) = {
      stringBase: (b.value + 777).string
    }
  }
  println: t.map(intBase(123)).value
}

Выдаёт:

900

В текущей реализации нельзя указать какие-либо ограничения на переменные типа пользовательских трейтов. При их использовании допускается подстановка любых типов в качестве значений переменных типа.

Обобщения структур

todo типизация с разными значениями переменных типа и без типа

Обобщения объединений

Обобщение объединений пока ещё не поддерживается, но, возможно, будет реализовано в будущих версиях Libretto.

Обобщения методов

Пользователь не может определить свои методы с параметрами типа. Но есть предопределенный (с поддержкой на уровне компилятора) набор методов, которые принимают значения для параметров типов.

Из пакета libretto:

• upcast[A] - безопасное гарантированное преобразование в тип A
• cast[A] - динамическое преобразование в тип A с исключением
• dyn[A] - динамическое преобразование в тип A с указанием поведения
• force[A] - принудительное преобразование в тип A (только для специфического использования)
• map[K, V] - создание отображения (мэпа) с ключами типа K и значениями типа V
• buffer[A] - создание буфера с элементами типа A

Из пакета libretto/num:

• array[A] - преобразование в массив элементов типа A
• newArray[A] - создание массива элементов типа A

Из пакета libretto/mem/q:

• queue[A] - создание блокирующей очереди элементов типа A

И ещё методы из пакета libretto/jvm (см. соответствующий раздел).

Ковариантность, контравариантность, инвариантность

Ковариантность и контравариантность характеризует возможность подстановки контейнеров типов в зависимости от возможности подстановки самих типов. Например, подтипом списка элементов типа A является список элементов типа B, когда B является подтипом A, а реализация не допускает изменения состава списка (неизменяемый список). Иначе будет нарушение принципа подстановки (Б.Лисков). Это пример ковариантности.

В Libretto нет прямого наследования трейтов, а иерархия трейтов определяется возможностью использования одного трейта вместо другого. Поэтому проблема ковариантности и контравариантности решается автоматически (и естественно для программиста) в зависимости от места использования параметра типа: только в параметре методов (контравариантность), только в результате методов (ковариантность). В случае инвариантности будет невозможность преобразования.

trait Test[A] {
  def value: A // только тип результата
}

def main = {
  fix test: Test[Any] = new Test[Int] {
    def value = 123
  }
  println: test.value
}

Выдаёт:

123

Переменная типа (A) используется только как тип результата метода, поэтому вместо Test[Any] можно подать значение Test[Int] (при помощи неявного преобразования трейта).

trait Test[A] {
  def out(v: A): () // только тип параметра
}

def main = {
  fix test: Test[Int] = new Test[Any] {
    def out(v) = { println(v); () }
  }
  test.out(123)
}

Выдаёт:

123

В этом примере, наоборот, переменная типа (A) используется как тип параметра метода, поэтому вместо Test[Int] можно подать Test[Any] (при помощи неявного преобразования трейта).

Пример определения обобщенного List

Пример классического связного списка в обобщённом варианте при помощи трейта (можно сделать и при помощи структуры):

use libretto/util

struct Nil

def Nil string = "Nil"

trait Cons[A] {
  def head: A
  def tail: (Cons[A] | Nil)
  def string: String
}

def intList(seq: Int*) = {
  var ret: (Cons[Int] | Nil) = Nil()
  seq.*util/reverse as v.${
    fix t = ret // текущее значение для замыкания
    ret = new Cons[Int] {
      def head = v
      def tail = t 
      def string = this.head.string + " :: " + 
        this.tail.string
    }
  }
  ret
}

def main = {
  println: intList: ()
  println: intList: (1)
  println: intList: (1, 2)
  println: intList: (1, 2, 3)
}

Выдаёт:

Nil
1 :: Nil
1 :: 2 :: Nil
1 :: 2 :: 3 :: Nil

Пока Libretto не поддерживает обобщение объединения, но теоретически можно было бы добавить определение union List[A] = Cons[A] | Nil.

Обратите внимание, что fix t = ret используется для получения текущего значения ret для замыкания (см. про проблемы замыкания с var).

todo: Поскольку список неизменяемый, то можно подавать список Int вместо, например, списка Int | String: