Страничка семинара теории типов

По концептам, типам следует читать современные статьи

Можно начинать со школы Одерского:

Статьи по теоретическим основам языка Скала

Выделю тут ряд статей, с которых, по моему мнению, следует начинать:

• Fighting Bit Rot with Types (Experience Report: Scala Collections)
• Compiling Generics Through User-Directed Type Specialization
• Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-Transform
• Modular Visitor Components: A Practical Solution to the Expression Families Problem
• Generics of a Higher Kind
• Safe Type-level Abstraction in Scala
• Translation Correctness for First-Order Object-Oriented Pattern Matching
• A Core Calculus for Scala Type Checking
• A Nominal Theory of Objects with Dependent Types

Краткий отчет о статьях

Compiling Generics Through User-Directed Type Specialization

Juliet:

Небольшая статья, 6 страниц. О технических особенностях генерации кода для шаблонов.

В двух словах речь о том, что использовать код, который генерируется для шаблона после стирания типов (где вместо типа T возникает Object) неэффективно для примитивных типов. Так как их приходится заворачивать в классы-обертки, и, соответственно, в специализированной версии возникают лишние операции boxing/unboxing.

В качестве альтернативы при описании шаблона для типа-параметра шаблона можно указать ключевое слово specialized:

def someFun[@specialized T](...

В этом случае помимо кода с Object будут сгенерированы специализации для примитивных типов.

Generics of a Higher Kind

Juliet:

16 страниц.

Насколько я понимаю, концептов в том смысле, как мы уже привыкли их воспринимать, здесь нет. Сплошные классы.

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

Далее говорится, что в статье разница между траитами и классами не так важна, так что все называется классами.

Класс может быть параметризован. А может содержать абстрактный тип-член. И они вроде бы ничем по сути не отличаются кроме области видимости.

Соль типов-параметров шаблона в том, что в качестве параметра может быть не конкретный тип, а конструктор типа.

trait Iterable[T, Container[X]] {
  def filter(p: T => Boolean): Container[T]
  ...
}

Это означает, что первый параметр — конкретный тип, а второй параметр — конструктор типа от одного параметра. И далее можем написать так:

trait List[T] extends Iterable[T, List]

На параметры шаблона можно наложить только два вида ограничений: надтипа и подтипа. Соответственно, если хочется получить несколько разносортных ограничений (то есть по-нашему — если мы хотим, чтобы тип удовлетворял нескольким концептам), надо сделать trait-наследник всех интересующих нас концептов и указать его в качестве надтипа.

Еще один интересный момент, рассматривающийся в статье — сорта типов. Из Haskell мы помним (про расширения я ничего не знаю, к сожалению), что конкретный тип имеет сорт «*», конструктор с одним параметром — «* → *», и так далее. Здесь предлагается рассматривать не просто «*», а «*(lowerBound, upperBound)». То есть сорт содержит информацию об ограничениях типовых составляющих.

Далее говорится о том, что на сортах можно ввести отношение «подсортирования». И еще есть раздел с красивым названием «kind soundness».

В общем, по-моему это крутая статья. Надо над ней подумать...

Miks:

Раз концепты есть, то как-то можно обеспечить концепт, связывающий два и более параметров шаблона. Как? Может, в статье всё-таки ничего не говорится о концептах?

Juliet:

Слова «концепты» в статье вообще нет, это правда. Есть пример моделирования классов типов Haskell.

А связать несколько параметров можно, просто trait с несколькими параметрами.

trait myTrait[S, T] {
  def convert(x: S): T
}

Miks:

Ну, это не очень - это и на C++ старом можно написать. А вот пример использования triats как концептов в новом C++ можно? В стиле

template<InputIterator Iter, typename V>
requires EqualityComparable<Iter::value_type, V>
Iter find(Iter first, Iter last, V v) { 
  while (first < last && *first != v)
    ++first;
  return first;
}

Juliet:

По идее можно, но я опять ничего не понимаю, пытаюсь написать...

Juliet:

В общем, у меня все печально. С value_type, спрятанным внутрь траита, совсем ничего не получается. Получился какой-то такой ужас:

  trait EqualityComparable[S, T] {
  	def ==(s: S, t: T): Boolean
  	def !=(s: S, t: T): Boolean = !(s == t)
  }
  
  implicit object EqIntInt extends EqualityComparable[Int, Int] {
  	def ==(a: Int, b: Int): Boolean = { a == b }
  }

  trait PInputIterator[value_type] {
  	def <(b: PInputIterator[value_type]): Boolean
  	def ++(): Unit
  	def *(): value_type
  }
  
  class IntNumber(x: Int) extends PInputIterator[Int]{
  	var n = x
  	
  	def <(b: PInputIterator[Int]): Boolean = {
  		val y = b.asInstanceOf[IntNumber];
  		n < y.n
  	}
  	def ++(): Unit = { n += 1; }
  	def *(): Int = n
  	
  	override def toString(): String = n.toString()
  }

  def pfind[X, Iter <: PInputIterator[X], V](first: Iter, last: Iter, v: V)
  		(implicit cmp: EqualityComparable[X, V]): Iter =
  {
    	while (first < last && cmp.!=(first.*(), v))
    		first.++()
  	first
  }                                               //> pfind: [X, Iter <: concepts.iterator.PInputIterator[X], V](first: Iter, las
                                                  //| t: Iter, v: V)(implicit cmp: concepts.iterator.EqualityComparable[X,V])Iter
                                                  //| 
  
  var c5 = new IntNumber(5)                //> c5  : concepts.iterator.IntNumber = 5
  var c15 = new IntNumber(15)              //> c15  : concepts.iterator.IntNumber = 15
  val d11 = pfind[Int, IntNumber, Int](c5, c15, 11)
                                                  //> d11  : concepts.iterator.IntNumber = 11

Причем не указывать параметры при вызове pfind не получается, ошибка: Type inferred type arguments [Nothing,IntNumber,Int] do not conform to method pfind's type parameter bounds [X,Iter <: PInputIterator[X],V]

Juliet:

Я снова открыла статью, про которую Артем на семинаре докладывал. Она несколько нивелировала влияние статьи «Generics of a Higher Kind». Теперь у меня вот так получилось (добраться до внутреннего типа все равно никак не получается):

trait EqualityComparable[S, T] {
	def ==(s: S, t: T): Boolean
  	def !=(s: S, t: T): Boolean = !(s == t)
}

trait InputIterator[Iter] {
	type value_type
  	
  	def <(a: Iter, b: Iter): Boolean
  	def ++(it: Iter): Unit
  	def *(it: Iter): value_type
}

trait VTInputIterator[Iter, VT] extends InputIterator[Iter] {
	type value_type = VT
}

class ArrayListIterator[T](a: ArrayList[T], i: Int) {
	val arr: ArrayList[T] = a
	var ind: Int = i
	
	def curr(): T = arr.get(ind)
	def ++(): Unit = { ind += 1 }
	
	override def toString() = "[" + ind.toString() + "]"
}

class InputIterArrList[T] extends VTInputIterator[ArrayListIterator[T], T]{	
	def <(a: ArrayListIterator[T], b: ArrayListIterator[T]) = {
	  if (a.arr == b.arr) a.ind < b.ind
	  else throw new IllegalArgumentException()
	}
	
	def ++(it: ArrayListIterator[T]): Unit = it.++()
	def *(it: ArrayListIterator[T]) = it.curr()
}

object TestInputIterator extends Application{	
  
	def find[Iter, VT, V](first: Iter, last: Iter, x: V)(implicit iterator: VTInputIterator[Iter, VT], 
	    cmp: EqualityComparable[VT, V]): Iter = 
	{
	  while (iterator.<(first, last) && cmp.!=(iterator.*(first), x))
	    iterator.++(first)
	  first
	}
	
	implicit object EqIntInt extends EqualityComparable[Int, Int] {
	  def ==(a: Int, b: Int): Boolean = { a == b }
	}
	
	implicit object inputIterArrListInt extends InputIterArrList[Int]{}
	
	val len = 10;
	var arr: ArrayList[Int] = new ArrayList(len);
	for (i: Int <- 1 to len)
	  arr.add(i)
	var arrFirst = new ArrayListIterator(arr, 0)
	var arrLast = new ArrayListIterator(arr, len)
	var r = find(arrFirst, arrLast, 7)
	println(r)
}

Juliet:

В общем, итоги на SO (http://stackoverflow.com/questions/15001138/modelling-of-c-concepts-with-scala-traits).

То есть я так понимаю, на Scala мы пишем примерно то, во что генерируются концепты у Сика. То есть явно передаем модели.

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

Ulysses:

Не «передаём», а указываем при описании функций — это полный аналог requires. Если есть implicit, то явно передавать при вызове не требуется.