如何使用匹配类型实现 SKI 组合子演算？

Question

我正在尝试使用匹配类型在 Dotty 中实现 SKI combinator calculus。

SKI 组合子演算的简要说明：

S、K 和 I 是术语
(xy) 是一个术语，如果 x 和 y 是术语，就像函数应用程序
(((Sx)y)z)（与Sxyz相同）returns xz(yz)（与(xz)(yz)相同）
((Kx)y)（与Kxy相同）returns x
(Ix) returns x

以下是我使用的（R 尽可能减少术语）。术语 (xy) 写成元组 (x,y)，S、K 和 I 是特征。

trait S
trait K
trait I

type R[T] = T match {
  case (((S,x),y),z) => R[((x,z),(y,z))]
  case ((K,x),y) => R[x]
  case (I,x) => R[x]
  case (a,b) => R[a] match {
    case `a` => (a, R[b])
    case _ => R[(R[a], R[b])]
  }
  case T => T
}

但是，以下两行无法编译（出于相同的原因）(Scastie):

val check: (K, K) = ??? : R[(((S,I),I),K)]
val check2: (K, K) = ??? : R[((I,K),(I,K))]

错误说它需要 (K,K) 但找到了 R[((I, K), (I, K))]。我预计它首先看到 S 并将其变成 (IK)(IK)，或 R[((I,K),(I,K))]，之后它应该匹配第一个 (I, K) 的评估并看到它是 K，这与 (I, K) 不同，它变成了 return R[(R[(I,K)], R[(I,K)])]，变成了 R[(K,K)]，变成了 (K,K).

但是，它不会超过 R[((I,K),(I,K))]。显然，如果它是嵌套的，它不会减少术语。这很奇怪，因为我尝试了相同的方法，但使用了实际的运行时函数，而且它似乎可以正常工作 (Scastie)。

case object S
case object K
case object I

def r(t: Any): Any = t match {
  case (((S,x),y),z) => r(((x,z),(y,z)))
  case ((K,x),y) => r(x)
  case (I,x) => r(x)
  case (a,b) => r(a) match {
    case `a` => (a, r(b))
    case c => (c, r(b))
  }
  case _ => t
}

println(r((((S, I), I), K))) 的输出是 (K,K)，符合预期。

有趣的是，删除 K 的规则使其可以编译，但它无法将 (K, K) 和 R[(K, K)] 识别为同一类型。也许这就是导致问题的原因？ (Scastie)

def check2: (K, K) = ??? : R[(K, K)]
//Found:    R[(K, K)]
//Required: (K, K)

Answer 1

S、K 和 I 不相交。 K with I等路口有人居住：

println(new K with I)

在匹配类型中，仅当类型不相交时才会跳过大小写。所以，例如这失败了：

type IsK[T] = T match {
  case K => true 
  case _ => false
}
@main def main() = println(valueOf[IsK[I]])

因为不能跳过case K => _分支，因为有I的值是K。所以，例如在你的情况下 R[(K, K)] 卡在 case (I, x) => _，因为有一些 (K, K) 也是 (I, x)（例如 (new K with I, new K {})).你永远不会到达 case (a,b) => _，这会把我们带到 (K, K).

您可以创建 S、K 和 I class，这会使它们不相交，因为您不能继承两个 class 立即。

class S
class K
class I

type R[T] = T match {
  case (((S,x),y),z) => R[((x,z),(y,z))]
  case ((K,x),y) => R[x]
  case (I,x) => R[x]
  case (a,b) => R[a] match {
    case `a` => (a, R[b])
    case _ => R[(R[a], R[b])]
  }
  case T => T
}

@main def main(): Unit = {
  println(implicitly[R[(K, K)] =:= (K, K)])
  println(implicitly[R[(((S,I),I),K)] =:= (K, K)])
}

Scastie

另一种解决方案是将它们全部设为单例类型：

object S; type S = S.type
object K; type K = K.type
object I; type I = I.type
// or, heck
type S = 0
type K = 1
type I = 2

如何使用匹配类型实现 SKI 组合子演算？

How to implement the SKI combinator calculus with match types?

scala

pattern-matching

scala-3

dotty

match-types