Scala 类型编程资源

Question

根据 this question ，Scala 的类型系统是 Turing complete 。有哪些资源可以让新手利用类型级编程的力量？

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

Daniel Spiewak's High Wizardry in the Land of Scala

Apocalisp's Type-Level Programming in Scala

Jesper's HList

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

有什么好的介绍资源吗？

Answer 1

概览

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

范式

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

在 apocalisp 的 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
}

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

第一:定义具有各种抽象类型字段的抽象特征(有关抽象字段是什么，请参见下文)。这是一个模板，用于保证某些类型字段存在于所有实现中而不强制实现。在 lambda 演算示例中，这对应于 trait Lambda保证以下类型存在:subst , apply , 和 eval .

下一步:定义扩展抽象特征并实现各种抽象类型字段的子特征

通常，这些子特征将使用参数进行参数化。在 lambda 演算示例中，子类型是 trait App extends Lambda它被参数化为两种类型( S 和 T ，两者都必须是 Lambda 的子类型)， trait Lam extends Lambda用一种类型( T )和 trait X extends Lambda 参数化(未参数化)。

类型字段通常通过引用子特征的类型参数来实现，有时通过哈希运算符引用它们的类型字段:# (这与点运算符非常相似:. 用于值)。在特质 App在 lambda 演算示例中，类型 eval实现如下:type eval = S#eval#apply[T] .这实质上是在调用 eval特征参数的类型 S ，并调用 apply带参数 T结果上。注意，S保证有 eval type 因为参数指定它是 Lambda 的子类型.同样，eval的结果必须有 apply类型，因为它被指定为 Lambda 的子类型，如抽象特征 Lambda 中指定的那样.

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

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

abstract class

值(value)级别:abstract class C { val x }

类型级别:trait C { type X }

路径依赖类型

C.x (引用对象 C 中的字段值/函数 x)

C#x (引用特征 C 中的字段类型 x)

函数签名(未实现)

值(value)级别:def f(x:X) : Y

类型级别:type f[x <: X] <: Y (这称为“类型构造函数”，通常出现在抽象特征中)

功能实现

值(value)级别:def f(x:X) : Y = x

类型级别:type f[x <: X] = x

条件句

see here

检查相等性

值(value)级别: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 的子类型的隐式转换)

an example

more comparison operators

类型和值之间的转换

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

例如val x:A = null ，其中 A是你关心的类型

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

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

考虑这个例子( taken from 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 ，您要验证是否相等。然后检查以下编译:

Equal[A, B]

与:特质 Equal[T1 >: T2 <: T2, T2] ( taken from apocolisp )

implicitly[A =:= B]

或者，您可以将类型转换为值(如上所示)并对值进行运行时检查。例如 assert(toInt(a) == toInt(b)) ，其中 a类型为 A和 b类型为 B .

其他资源

完整的可用结构集可以在 the scala reference manual (pdf) 的类型部分找到。 .

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

Generics of a higher kind (pdf)

Type Constructor Polymorphism for Scala: Theory and Practice (pdf) (博士论文，其中包括 Moors 之前的论文)

Type Constructor Polymorphism Inference

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

Type-Level Programming in Scala是一些类型级编程的精彩导览，其中包括 bool 值、自然数(如上)、二进制数、异构列表等。

More Scala Typehackery是上面的 lambda 演算实现。

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

MetaScala是 Scala 的类型级库，包括自然数、 bool 值、单位、HList 等的元类型。它是 Jesper Nordenberg (his blog) 的一个项目。 .

Michid (blog)在 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

Debasish Ghosh (blog)也有一些相关的帖子:

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

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