Scala 类型编程资源

Scala type programming resources

提问by dsg

According to this question, Scala's type system is Turing complete. What resources are available that enable a newcomer to take advantage of the power of type-level programming?

根据这个问题，Scala的类型系统是图灵完备的。有哪些资源可以让新手利用类型级编程的力量？

Here are the resources I've found so far:

以下是我目前找到的资源：

• Daniel Spiewak's High Wizardry in the Land of Scala
• Apocalisp's Type-Level Programming in Scala
• Jesper's HList

• Daniel Spiewak在斯卡拉土地上的高级巫术
• Apocalisp在 Scala 中的类型级编程
• Jesper 的HList

These resources are great, but I feel like I'm missing the basics, and so do not have a solid foundation on which to build. For instance, where is there an introduction to type definitions? What operations can I perform on types?

这些资源很棒，但我觉得我缺少基础知识，因此没有可以构建的坚实基础。例如，哪里有类型定义的介绍？我可以对类型执行哪些操作？

Are there any good introductory resources?

有什么好的介绍资源吗？

回答by dsg

Overview

概述

Type-level programming has many similarities with traditional, value-level programming. However, unlike value-level programming, where the computation occurs at runtime, in type-level programming, the computation occurs at compile time. I will try to draw parallels between programming at the value-level and programming at the type-level.

类型级编程与传统的值级编程有很多相似之处。然而，与计算发生在运行时的值级编程不同，在类型级编程中，计算发生在编译时。我将尝试在值级编程和类型级编程之间进行比较。

Paradigms

范式

There are two main paradigms in type-level programming: "object-oriented" and "functional". Most examples linked to from here follow the object-oriented paradigm.

类型级编程有两种主要范式：“面向对象”和“函数式”。从这里链接到的大多数示例都遵循面向对象的范例。

A good, fairly simple example of type-level programming in the object-oriented paradigm can be found in apocalisp's implementation of the lambda calculus, replicated here:

在 apocalisp's implementation of the lambda calculus 中可以找到一个很好的，相当简单的面向对象范式中类型级编程的例子，复制在这里：

// 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
}

As can be seen in the example, the object-oriented paradigm for type-level programming proceeds as follows:

从示例中可以看出，类型级编程的面向对象范式如下：

• First: define an abstract trait with various abstract type fields (see below for what an abstract field is). This is a template for guaranteeing that certain types fields exist in all implementations without forcing an implementation. In the lambda calculus example, this corresponds to trait Lambdathat guarantees that the following types exist: subst, apply, and eval.
• Next: define subtraits that extend the abstract trait and implement the various abstract type fields
  • Often, these subtraits will be parameterized with arguments. In the lambda calculus example, the subtypes are trait App extends Lambdawhich is parameterized with two types (Sand T, both must be subtypes of Lambda), trait Lam extends Lambdaparameterized with one type (T), and trait X extends Lambda(which is not parameterized).
  • the type fields are often implemented by referring to the type parameters of the subtrait and sometimes referencing their type fields via the hash operator: #(which is very similar to the dot operator: .for values). In trait Appof the lambda calculus example, the type evalis implemented as follows: type eval = S#eval#apply[T]. This is essentially calling the evaltype of the trait's parameter S, and calling applywith parameter Ton the result. Note, Sis guaranteed to have an evaltype because the parameter specifies it to be a subtype of Lambda. Similarly, the result of evalmust have an applytype, since it is specified to be a subtype of Lambda, as specified in the abstract trait Lambda.

• 首先：定义具有各种抽象类型字段的抽象特征（有关抽象字段是什么，请参见下文）。这是一个模板，用于保证某些类型的字段存在于所有实现中，而不强制实现。在演算示例中，这对应于trait Lambda该保证了以下类型的存在：subst，apply，和eval。
• 下一步：定义扩展抽象特征并实现各种抽象类型字段的子特征
  • 通常，这些子特征将使用参数进行参数化。在 lambda 演算示例中，子类型是trait App extends Lambda用两种类型参数化的（S和T，两者都必须是 的子类型Lambda），trait Lam extends Lambda用一种类型 ( T)参数化，和trait X extends Lambda（未参数化）。
  • 类型字段通常通过引用子特征的类型参数来实现，有时通过哈希运算符引用它们的类型字段：（#这与点运算符非常相似：.用于值）。在性状Applambda演算示例的，类型eval是这样实现的：type eval = S#eval#apply[T]。这实质上是调用eval特征参数的类型S，并在结果上调用apply参数T。注意，S保证有一个eval类型，因为参数指定它是 的子类型Lambda。类似地， 的结果eval必须有一个apply类型，因为它被指定为 的子类型Lambda，如抽象特征中所指定Lambda。

The Functional paradigm consists of defining lots of parameterized type constructors that are not grouped together in traits.

功能范式包括定义许多未在特征中组合在一起的参数化类型构造函数。

Comparison between value-level programming and type-level programming

值级编程与类型级编程的比较

• abstract class
  • value-level: abstract class C { val x }
  • type-level: trait C { type X }
• path dependent types
  • C.x(referencing field value/function x in object C)
  • C#x(referencing field type x in trait C)
• function signature (no implementation)
  • value-level: def f(x:X) : Y
  • type-level: type f[x <: X] <: Y(this is called a "type constructor" and usually occurs in the abstract trait)
• function implementation
  • value-level: def f(x:X) : Y = x
  • type-level: type f[x <: X] = x
• conditionals
  • see here
• checking equality
  • value-level: a:A == b:B
  • type-level: implicitly[A =:= B]
  • value-level: Happens in the JVM via a unit test at runtime (i.e. no runtime errors):
    • in essense is an assert: assert(a == b)
  • type-level: Happens in the compiler via a typecheck (i.e. no compiler errors):
    • in essence is a type comparison: e.g. implicitly[A =:= B]
    • A <:< B, compiles only if Ais a subtype of B
    • A =:= B, compiles only if Ais a subtype of Band Bis a subtype of A
    • A <%< B, ("viewable as") compiles only if Ais viewable as B(i.e. there is an implicit conversion from Ato a subtype of B)
    • an example
    • more comparison operators

• 抽象类
  • 价值层面： abstract class C { val x }
  • 类型级别： trait C { type X }
• 路径依赖类型
  • C.x（在对象 C 中引用字段值/函数 x）
  • C#x（在特征 C 中引用字段类型 x）
• 函数签名（未实现）
  • 价值层面： 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）
    • 一个例子
    • 更多比较运算符

Converting between types and values

类型和值之间的转换

• In many of the examples, types defined via traits are often both abstract and sealed, and therefore can neither be instantiated directly nor via anonymous subclass. So it is common to use nullas a placeholder value when doing a value-level computation using some type of interest:

  • e.g. val x:A = null, where Ais the type you care about

• Due to type-erasure, parameterized types all look the same. Furthermore, (as mentioned above) the values you're working with tend to all be null, and so conditioning on the object type (e.g. via a match statement) is ineffective.

• 在许多示例中，通过特征定义的类型通常既是抽象的又是密封的，因此既不能直接实例化，也不能通过匿名子类实例化。因此，null在使用某种类型的兴趣进行值级计算时，通常用作占位符值：

  • 例如val x:A = null，A您关心的类型在哪里

• 由于类型擦除，参数化类型看起来都一样。此外，（如上所述）您使用的值往往都是null，因此对对象类型的调节（例如通过匹配语句）是无效的。

The trick is to use implicit functions and values. The base case is usually an implicit value and the recursive case is usually an implicit function. Indeed, type-level programming makes heavy use of implicits.

诀窍是使用隐式函数和值。基本情况通常是隐式值，递归情况通常是隐式函数。事实上，类型级编程大量使用了隐式。

Consider this example (taken from metascalaand apocalisp):

考虑这个例子（取自 metascala和apocalisp）：

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

Here you have a peano encoding of the natural numbers. That is, you have a type for each non-negative integer: a special type for 0, namely _0; and each integer greater than zero has a type of the form Succ[A], where Ais the type representing a smaller integer. For instance, the type representing 2 would be: Succ[Succ[_0]](successor applied twice to the type representing zero).

在这里，您有自然数的皮亚诺编码。也就是说，每个非负整数都有一个类型：0 的特殊类型，即_0; 并且每个大于零的整数都有一个形式为 的类型Succ[A]，其中A是代表较小整数的类型。例如，表示 2 的类型将是：（Succ[Succ[_0]]后继应用于表示零的类型两次）。

We can alias various natural numbers for more convenient reference. Example:

我们可以给各种自然数取别名，方便参考。例子：

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

(This is a lot like defining a valto be the result of a function.)

（这很像将 a 定义val为函数的结果。）

Now, suppose we want to define a value-level function def toInt[T <: Nat](v : T)which takes in an argument value, v, that conforms to Natand returns an integer representing the natural number encoded in v's type. For example, if we have the value val x:_3 = null(nullof type Succ[Succ[Succ[_0]]]), we would want toInt(x)to return 3.

现在，假设我们要定义一个值级函数def toInt[T <: Nat](v : T)，它接受一个参数值v，它符合Nat并返回一个整数，表示以v的类型编码的自然数。例如，如果我们有值val x:_3 = null（null类型为Succ[Succ[Succ[_0]]]），我们希望toInt(x)返回3.

To implement toInt, we're going to make use of the following class:

为了实现toInt，我们将使用以下类：

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

As we will see below, there will be an object constructed from class TypeToValuefor each Natfrom _0up to (e.g.) _3, and each will store the value representation of the corresponding type (i.e. TypeToValue[_0, Int]will store the value 0, TypeToValue[Succ[_0], Int]will store the value 1, etc.). Note, TypeToValueis parameterized by two types: Tand VT. Tcorresponds to the type we're trying to assign values to (in our example, Nat) and VTcorresponds to the type of value we're assigning to it (in our example, Int).

正如我们将在下面看到的，TypeToValue每个Natfrom _0up to (eg)都会有一个从 class 构造的对象，每个对象_3都将存储相应类型的值表示（TypeToValue[_0, Int]即将存储值0，TypeToValue[Succ[_0], Int]将存储值1等）。注意，TypeToValue由两种类型参数化：T和VT。T对应于我们尝试为其分配值的类型（在我们的示例中为Nat）并VT对应于我们为其分配的值的类型（在我们的示例中为Int）。

Now we make the following two implicit definitions:

现在我们做以下两个隐式定义：

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())

And we implement toIntas follows:

我们实现toInt如下：

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

To understand how toIntworks, let's consider what it does on a couple of inputs:

要了解如何toInt工作，让我们考虑一下它在几个输入上的作用：

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

When we call toInt(z), the compiler looks for an implicit argument ttvof type TypeToValue[_0, Int](since zis of type _0). It finds the object _0ToInt, it calls the getValuemethod of this object and gets back 0. The important point to note is that we did not specify to the program which object to use, the compiler found it implicitly.

当我们调用 时toInt(z)，编译器会寻找一个隐式参数ttv类型TypeToValue[_0, Int]（因为z是类型_0）。它找到该对象_0ToInt，调用getValue该对象的方法并返回0。需要注意的重要一点是我们没有指定程序使用哪个对象，编译器隐式地发现了它。

Now let's consider toInt(y). This time, the compiler looks for an implicit argument ttvof type TypeToValue[Succ[_0], Int](since yis of type Succ[_0]). It finds the function succToInt, which can return an object of the appropriate type (TypeToValue[Succ[_0], Int]) and evaluates it. This function itself takes an implicit argument (v) of type TypeToValue[_0, Int](that is, a TypeToValuewhere the first type parameter is has one fewer Succ[_]). The compiler supplies _0ToInt(as was done in the evaluation of toInt(z)above), and succToIntconstructs a new TypeToValueobject with value 1. Again, it is important to note that the compiler is providing all of these values implicitly, since we do not have access to them explicitly.

现在让我们考虑一下toInt(y)。这一次，编译器寻找ttv类型的隐式参数TypeToValue[Succ[_0], Int]（因为y是类型Succ[_0]）。它找到函数succToInt，该函数可以返回适当类型 ( TypeToValue[Succ[_0], Int])的对象并对其求值。这个函数本身接受一个隐式参数 ( v) 类型TypeToValue[_0, Int]（即， aTypeToValue其中第一个类型参数少了一个Succ[_]）。编译器提供_0ToInt（如在toInt(z)上面的评估中所做的那样），并succToInt构造一个TypeToValue具有 value的新对象1。同样，重要的是要注意编译器隐式提供所有这些值，因为我们无法显式访问它们。

Checking your work

检查你的工作

There are several ways to verify that your type-level computations are doing what you expect. Here are a few approaches. Make two types Aand B, that you want to verify are equal. Then check that the following compile:

有多种方法可以验证您的类型级计算是否按照您的预期进行。这里有一些方法。使两种类型Aand B，您要验证的类型相等。然后检查以下编译：

• Equal[A, B]
  • with: trait Equal[T1 >: T2 <: T2, T2](taken from apocolisp)
• implicitly[A =:= B]

• Equal[A, B]
  • with: trait Equal[T1 >: T2 <: T2, T2](取自 apocolisp)
• implicitly[A =:= B]

Alternatively, you can convert the type to a value (as shown above) and do a runtime check of the values. E.g. assert(toInt(a) == toInt(b)), where ais of type Aand bis of type B.

或者，您可以将类型转换为值（如上所示）并对值进行运行时检查。例如assert(toInt(a) == toInt(b))， where ais of typeA和bis of type B。

Additional Resources

其他资源

The complete set of available constructs can be found in the types section of the scala reference manual (pdf).

完整的可用结构集可以在 scala 参考手册 (pdf)的类型部分找到。

Adriaan Moorshas several academic papers about type constructors and related topics with examples from scala:

Adriaan Moors有几篇关于类型构造函数和相关主题的学术论文，并附有来自 Scala 的示例：

• Generics of a higher kind (pdf)
• Type Constructor Polymorphism for Scala: Theory and Practice (pdf)(PhD thesis, which includes the previous paper by Moors)
• Type Constructor Polymorphism Inference

• 高级泛型 (pdf)
• Scala 的类型构造函数多态性：理论与实践 (pdf)（博士论文，其中包括 Moors 之前的论文）
• 类型构造函数多态推理

Apocalispis a blog with many examples of type-level programming in scala.

Apocalisp是一个包含许多 Scala 类型级编程示例的博客。

• Type-Level Programming in Scalais a fantastic guided tour of some type-level programming which includes booleans, natural numbers (as above), binary numbers, heterogeneous lists, and more.
• More Scala Typehackeryis the lambda calculus implementation above.

• Scala中的类型级编程是一些类型级编程的精彩导览，其中包括布尔值、自然数（如上）、二进制数、异构列表等。
• 更多 Scala Typehackery是上面的 lambda 演算实现。

ScalaZis a very active project that is providing functionality that extends the Scala API using various type-level programming features. It is a very interesting project that has a big following.

ScalaZ是一个非常活跃的项目，它提供使用各种类型级编程功能扩展 Scala API 的功能。这是一个非常有趣的项目，有很多追随者。

MetaScalais a type-level library for Scala, including meta types for natural numbers, booleans, units, HList, etc. It is a project by Jesper Nordenberg (his blog).

MetaScala是 Scala 的类型级库，包括自然数、布尔值、单位、HList 等的元类型。它是Jesper Nordenberg（他的博客）的一个项目。

The Michid (blog)has some awesome examples of type-level programming in Scala (from other answer):

该Michid（博客）在斯卡拉型高级编程的一些例子真棒（从对方的回答）：

• Meta-Programming with Scala Part I: Addition
• Meta-Programming with Scala Part II: Multiplication
• Meta-Programming with Scala Part III: Partial function application
• Meta-Programming with Scala: Conditional Compilation and Loop Unrolling
• Scala type level encoding of the SKI calculus

• 使用 Scala 进行元编程第一部分：加法
• Scala 元编程第二部分：乘法
• 使用 Scala 进行元编程第三部分：部分函数应用
• 使用 Scala 进行元编程：条件编译和循环展开
• SKI 演算的 Scala 类型级别编码

Debasish Ghosh (blog)has some relevant posts as well:

Debasish Ghosh（博客）也有一些相关的帖子：

• Higher order abstractions in scala
• Static typing gives you a head start
• Scala implicits type classes, here I come
• Refactoring into scala type-classes
• Using generalized type constraints
• How scalas type system words for you
• Choosing between abstract type members

• Scala 中的高阶抽象
• 静态类型为您提供一个良好的开端
• Scala 隐含类型类，我来了
• 重构为 Scala 类型类
• 使用广义类型约束
• Scalas 如何为您键入系统单词
• 在抽象类型成员之间进行选择

(I've been doing some research on this subject and here's what I've learned. I'm still new to it, so please point out any inaccuracies in this answer.)

（我一直在对这个主题进行一些研究，这是我学到的东西。我还是个新手，所以请指出这个答案中的任何不准确之处。）

回答by michid

In addition to the other links here, there are also my blog posts on type level meta programming in Scala:

除了这里的其他链接之外，还有我关于 Scala 中类型级元编程的博客文章：

• Meta-Programming with Scala Part I: Addition
• Meta-Programming with Scala Part II: Multiplication
• Meta-Programming with Scala Part III: Partial function application
• Meta-Programming with Scala: Conditional Compilation and Loop Unrolling
• Scala type level encoding of the SKI calculus

• 使用 Scala 进行元编程第一部分：加法
• Scala 元编程第二部分：乘法
• 使用 Scala 进行元编程第三部分：部分函数应用
• 使用 Scala 进行元编程：条件编译和循环展开
• SKI 演算的 Scala 类型级别编码

回答by GClaramunt

As suggested on Twitter: Shapeless: An exploration of generic/polytypic programming in Scala by Miles Sabin.

正如 Twitter 上所建议的：Shapeless：Miles Sabin对 Scala 中的泛型/多型编程的探索。

回答by Kenji Yoshida

• Sing, a type-level metaprogramming library in Scala.
• The Beginning of Type-level Programming in Scala

• Sing，Scala 中的类型级元编程库。
• Scala 类型级编程的开始

回答by Vasil Remeniuk

Scalazhas source code, a wiki and examples.

Scalaz有源代码、维基和示例。