Ресурсы по программированию типа Scala

102

Согласно этому вопросу система типов Scala завершена по Тьюрингу . Какие ресурсы доступны, чтобы новичок мог воспользоваться преимуществами программирования на уровне типов?

Вот ресурсы, которые я нашел на данный момент:

Эти ресурсы прекрасны, но я чувствую, что мне не хватает основ, и поэтому у меня нет прочной основы, на которой можно было бы строить. Например, где есть введение в определения типов? Какие операции я могу выполнять с типами?

Есть ли хорошие вводные ресурсы?

scala types dsg
источник
Лично я считаю вполне разумным предположение, что тот, кто хочет программировать на уровне типов на Scala, уже знает, как программировать на Scala. Даже если это означает, что я не понимаю ни слова из тех статей, на которые вы ссылались :-)
Jörg W Mittag

Ответы:

140

Обзор

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

Парадигмы

В программировании на уровне типов есть две основные парадигмы: «объектно-ориентированная» и «функциональная». Большинство примеров, ссылки на которые приведены здесь, следуют объектно-ориентированной парадигме.

Хороший, довольно простой пример программирования на уровне типов в объектно-ориентированной парадигме можно найти в реализации лямбда-исчисления apocalisp , воспроизведенной здесь:

// Abstract trait
trait Lambda {
  type subst[U <: Lambda] <: Lambda
  type apply[U <: Lambda] <: Lambda
  type eval <: Lambda
}

// Implementations
trait App[S <: Lambda, T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = App[S#subst[U], T#subst[U]]
  type apply[U] = Nothing
  type eval = S#eval#apply[T]
}

trait Lam[T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = Lam[T]
  type apply[U <: Lambda] = T#subst[U]#eval
  type eval = Lam[T]
}

trait X extends Lambda {
  type subst[U <: Lambda] = U
  type apply[U] = Lambda
  type eval = X
}

Как видно из примера, объектно-ориентированная парадигма для программирования на уровне типов действует следующим образом:

  • Во-первых: определите абстрактную черту с различными полями абстрактного типа (см. Ниже, что такое абстрактное поле). Это шаблон для гарантии того, что определенные поля типов существуют во всех реализациях, без принуждения к реализации. В примере лямбда - исчислении это соответствует , trait Lambdaчто гарантирует , что следующие типы существуют: subst, applyиeval .
  • Далее: определите вычитаемые признаки, которые расширяют абстрактную черту и реализуют различные поля абстрактного типа
    • Часто эти субтитры параметризуются аргументами. В примере лямбда-исчисления это подтипы, trait App extends Lambdaкоторые параметризованы двумя типами ( Sи Tоба должны быть подтипами Lambda), trait Lam extends Lambdaпараметризованы одним типом ( T) иtrait X extends Lambda (который не параметризован).
    • поля типа часто реализуются путем обращения к параметрам типа вычитаемой характеристики, а иногда и ссылки на их поля типа с помощью оператора хеширования: #(который очень похож на оператор точки: .для значений). В черте Appпримера лямбда - исчисления, тип evalреализуется следующим образом : type eval = S#eval#apply[T]. По сути, это вызов evalтипа параметра признака Sи вызов applyс параметром Tрезультата. Обратите внимание S: гарантированно будет evalтип, потому что параметр указывает, что он является подтипом Lambda. Точно так же результат evalдолжен иметь applyтип, поскольку он указан как подтип Lambda, как указано в абстрактной характеристике Lambda.

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

Сравнение программирования на уровне значений и программирования на уровне типов

  • абстрактный класс
    • ценностный уровень: abstract class C { val x }
    • уровень типа: trait C { type X }
  • зависящие от пути типы
    • C.x (ссылка на значение поля / функцию x в объекте C)
    • C#x (ссылка на тип поля x в трейте C)
  • подпись функции (без реализации)
    • ценностный уровень: def f(x:X) : Y
    • уровень типа: type f[x <: X] <: Y(это называется «конструктором типа» и обычно встречается в абстрактной характеристике)
  • реализация функции
    • ценностный уровень: def f(x:X) : Y = x
    • уровень типа: type f[x <: X] = x
  • условные
  • проверка равенства
    • ценностный уровень: a:A == b:B
    • уровень типа: implicitly[A =:= B]
    • уровень значений: происходит в JVM через модульный тест во время выполнения (т.е. без ошибок времени выполнения):
      • в сущности это утверждение: assert(a == b)
    • уровень типа: Происходит в компиляторе через проверку типов (т.е. без ошибок компилятора):
      • по сути, это сравнение типов: например implicitly[A =:= B]
      • A <:< B, компилируется, только если Aявляется подтипомB
      • A =:= B, компилируется, только если Aявляется подтипом Bи Bявляется подтипомA
      • A <%< B, ("viewable as") компилируется только в том случае, если Aон доступен для просмотра B(т. е. существует неявное преобразование из Aв подтип B)
      • пример
      • больше операторов сравнения

Преобразование между типами и значениями

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

    • например val x:A = null, где Aтип, о котором вы заботитесь

  • Из-за стирания типа все параметризованные типы выглядят одинаково. Более того, (как упоминалось выше) все значения, с которыми вы работаете, обычно nullсовпадают, поэтому обусловливание типа объекта (например, посредством оператора соответствия) неэффективно.

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

Рассмотрим этот пример ( взятый из metascala и apocalisp ):

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

Здесь у вас есть пано-кодирование натуральных чисел. То есть у вас есть тип для каждого неотрицательного целого числа: специальный тип для 0, а именно _0; и каждое целое число больше нуля имеет тип формы Succ[A], где A- тип, представляющий меньшее целое число. Например, тип, представляющий 2, будет:Succ[Succ[_0]] (преемник применяется дважды к типу, представляющему ноль).

Мы можем использовать псевдонимы для различных натуральных чисел для более удобного использования. Пример:

type _3 = Succ[Succ[Succ[_0]]]

(Это очень похоже на определение val как результата функции.)

Теперь предположим, что мы хотим определить функцию уровня значения, def toInt[T <: Nat](v : T)которая принимает значение аргумента v, которое соответствует Natи возвращает целое число, представляющее натуральное число, закодированное в vтипе. Например, если у нас есть значение val x:_3 = null( nullтипа Succ[Succ[Succ[_0]]]), мы хотели toInt(x)бы вернуть3 .

Для реализации toIntмы собираемся использовать следующий класс:

class TypeToValue[T, VT](value : VT) { def getValue() = value }

Как мы увидим ниже, будет объект, созданный из класса TypeToValueдля каждого Natот _0до (например) _3, и каждый будет хранить представление значения соответствующего типа (т.е. TypeToValue[_0, Int]будет хранить значение 0,TypeToValue[Succ[_0], Int] будет хранить значение 1и т. Д.). Обратите внимание, TypeToValueпараметризуется двумя типами: Tи VT. Tсоответствует типу, которому мы пытаемся присвоить значения (в нашем примере Nat), и VTсоответствует типу значения, которое мы ему присваиваем (в нашем примере,Int ).

Теперь мы сделаем следующие два неявных определения:

implicit val _0ToInt = new TypeToValue[_0, Int](0)
implicit def succToInt[P <: Nat](implicit v : TypeToValue[P, Int]) = 
     new TypeToValue[Succ[P], Int](1 + v.getValue())

И реализуем toIntтак:

def toInt[T <: Nat](v : T)(implicit ttv : TypeToValue[T, Int]) : Int = ttv.getValue()

Чтобы понять, как toIntработает, давайте рассмотрим, что он делает на паре входов:

val z:_0 = null
val y:Succ[_0] = null

Когда мы вызываем toInt(z), компилятор ищет неявный аргумент ttvтипа TypeToValue[_0, Int](посколькуz имеет тип _0). Он находит объект _0ToInt, вызывает getValueметод этого объекта и возвращает0 . Важно отметить, что мы не указали программе, какой объект использовать, компилятор нашел его неявно.

А теперь рассмотрим toInt(y). На этот раз компилятор ищет неявный аргумент ttvтипа TypeToValue[Succ[_0], Int](поскольку yимеет тип Succ[_0]). Он находит функцию succToInt, которая может возвращать объект соответствующего типа ( TypeToValue[Succ[_0], Int]), и оценивает ее. Эта функция сама принимает неявный аргумент ( v) типа TypeToValue[_0, Int](то есть, TypeToValueгде параметр первого типа имеет на один меньше Succ[_]). Компилятор предоставляет _0ToInt(как это было сделано при оценкеtoInt(z) выше) и succToIntсоздает новый TypeToValueобъект со значением 1. Опять же, важно отметить, что компилятор предоставляет все эти значения неявно, поскольку у нас нет доступа к ним явно.

Проверка вашей работы

Есть несколько способов проверить, что ваши вычисления на уровне типов делают то, что вы ожидаете. Вот несколько подходов. Сделайте два типа Aи B, которые вы хотите проверить, равны. Затем проверьте, что следующая компиляция:

В качестве альтернативы вы можете преобразовать тип в значение (как показано выше) и выполнить проверку значений во время выполнения. Например assert(toInt(a) == toInt(b)), где aесть типа, Aа где b- типа B.

Дополнительные ресурсы

Полный набор доступных конструкций можно найти в разделе типов справочного руководства по scala (pdf) .

У Адриана Мурса есть несколько научных статей о конструкторах типов и связанных темах с примерами из scala:

Apocalisp - это блог с множеством примеров программирования на уровне типов в scala.

ScalaZ - очень активный проект, который предоставляет функциональные возможности, расширяющие Scala API с помощью различных функций программирования на уровне типов. Это очень интересный проект, у которого много поклонников.

MetaScala - это библиотека уровня типов для Scala, включая метатипы для натуральных чисел, логических значений, единиц измерения, HList и т. Д. Это проект Джеспера Норденберга (его блог) .

В Michid (блоге) есть несколько потрясающих примеров программирования на уровне типов в Scala (из другого ответа):

У Дебасиша Гоша (блог) также есть несколько соответствующих сообщений:

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

dsg
источник
12

В дополнение к другим ссылкам здесь есть также мои сообщения в блоге о метапрограммировании на уровне типов в Scala:

михид
источник
Просто хотел сказать спасибо за интересный блог; Я слежу за ним некоторое время, и особенно последний пост, упомянутый выше, обострил мое понимание важных свойств, которые должна иметь система типов для объектно-ориентированного языка. Так что спасибо!
Зак Сноу,
4

Scalaz имеет исходный код, вики и примеры.

Василь Ременюк
источник