Обзор
Программирование на уровне типов имеет много общего с традиционным программированием на уровне значений. Однако, в отличие от программирования на уровне значений, где вычисления выполняются во время выполнения, в программировании на уровне типов вычисления выполняются во время компиляции. Я попытаюсь провести параллели между программированием на уровне значений и программированием на уровне типов.
Парадигма
В программировании на уровне типов есть две основные парадигмы: «объектно-ориентированный» и «функциональный». Большинство примеров, связанных с этим, следуют объектно-ориентированной парадигме.
Хороший, довольно простой пример программирования на уровне типов в объектно-ориентированной парадигме можно найти в реализации лямбда-исчисления в 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 является подтипом BA =:= B, компилируется, только если A является подтипом B и B является подтипом AA <%< B, ("viewable as") компилируется, только если A отображается как B (то есть существует неявное преобразование из A в подтип B) - пример
- больше операторов сравнения
Преобразование между типами и значениями
Во многих примерах типы, определенные с помощью признаков, часто бывают как абстрактными, так и запечатанными, и поэтому не могут быть созданы ни напрямую, ни через анонимный подкласс. Поэтому обычно используется null в качестве значения заполнителя при выполнении вычисления уровня значения с использованием некоторого типа интереса:
- например.
val x:A = null, где A - это тип, который вам нужен
Из-за стирания типов все параметризованные типы выглядят одинаково. Кроме того, (как упоминалось выше) все значения, с которыми вы работаете, обычно равны null, и поэтому согласование с типом объекта (например, с помощью оператора match) неэффективно.
Хитрость заключается в использовании неявных функций и значений. Базовый регистр обычно является неявным значением, а рекурсивный регистр обычно является неявной функцией. Действительно, в программировании на уровне типов часто используются импликации.
Рассмотрим этот пример ( взято из metascala и apocalisp ):
sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat
Здесь у вас есть peano-кодировка натуральных чисел. То есть у вас есть тип для каждого неотрицательного целого числа: специальный тип для 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, которые вы хотите проверить, равны.Затем проверьте, что следующий компилятор:
Equal[A, B] implicitly[A =:= B]
Кроме того, вы можете преобразовать тип в значение (как показано выше) и выполнить проверку значений во время выполнения.Например, assert(toInt(a) == toInt(b)), где a относится к типу A, а b относится к типу B.
Дополнительные ресурсы
Полный набордоступные конструкции можно найти в разделе типов справочного руководства по scala (pdf) .
Adriaan Moors содержит несколько научных статей о конструкторах типов и связанных с ними темах с примерамииз scala:
Apocalisp - блог со многими примерамипрограммирования на уровне типов в Scala.
ScalaZ - очень активный проект, предоставляющий функциональность, расширяющую Scala API с использованием различныхфункции программирования на уровне типов.Это очень интересный проект с большим количеством последователей.
MetaScala - это библиотека уровня типов для Scala, включающая мета-типы для натуральных чисел, логических значений, единиц измерения, HList и т. Д.это проект Jesper Nordenberg (его блог) .
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ”несколько его”.:
Дебашиш Гош (блог) также имеет несколько соответствующих сообщений:
(Я провел некоторые исследования по этому вопросу, и вот что я узнал.Я все еще плохо знаком с этим, поэтому, пожалуйста, укажите на любые неточности в этом ответе.)