图灵完备类型系统的原因是什么

Question

Scala 和 Haskell 有 "Turing complete type systems"。通常，图灵完备性是指computations and languages。它在类型上下文中的真正含义是什么？

有人可以举例说明程序员如何从中受益吗？

PS 我不想比较 Haskell 与 Scala 的类型系统。它更多的是关于一般术语。

PSS 如果有更多 Scala 示例。

Answer 1

What does it really mean in the context of types?

这意味着类型系统中有足够的特性来表示任意计算。作为一个非常简短的证明，我在下面展示了 SK 演算的类型级实现；有很多地方讨论这个微积分的图灵完备性及其意义，所以我不会在这里重复。

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE TypeOperators #-}

infixl 1 `App`
data Term = S | K | App Term Term

type family Reduce t where
    Reduce S = S
    Reduce K = K
    Reduce (S `App` x `App` y `App` z) = Reduce (x `App` z `App` (y `App` z))
    Reduce (K `App` x `App` y) = Reduce x
    Reduce (x `App` y) = Reduce (Reduce x `App` y)

您可以在 ghci 提示符下看到这个动作；例如，在 SK 微积分中，术语 SKSK 减少（最终）为 K:

> :kind! Reduce (S `App` K `App` S `App` K)
Reduce (S `App` K `App` S `App` K) :: Term
= 'K

这里还有一个有趣的尝试：

> type I = S `App` K `App` K
> type Rep = S `App` I `App` I
> :kind! Reduce (Rep `App` Rep)

我不想破坏乐趣 -- 自己试试吧。但要知道如何先终止具有极端偏见的程序。

Could some one give an example how a programmer can benefit from it?

任意类型级计算允许您在类型上表达任意不变量，并让编译器验证（在编译时）它们是否被保留。想要一棵红黑树？编译器可以检查的红黑树如何保留红黑树不变量？那会很方便，对吧，因为这排除了整个 class 的实施错误？静态已知与特定模式匹配的 XML 值的类型怎么样？事实上，为什么不更进一步，写下一个参数化类型，其参数代表一个模式？然后你可以在运行时读入一个模式，并让你的编译时检查保证你的参数化值只能代表该模式中格式正确的值。不错！

或者，也许是一个更平淡无奇的例子：如果您希望编译器检查您从未使用不存在的键为字典编制索引怎么办？使用足够先进的类型系统，您可以。

当然，价格总是有的。在 Haskell（可能还有 Scala？）中，非常令人兴奋的编译时检查的代价是花费大量程序员时间和精力让编译器相信您正在检查的东西是真实的——这是通常既有高昂的前期成本，也有高昂的持续维护成本。

图灵完备类型系统的原因是什么

What is the reason for a Turing complete type system

haskell

scala

turing-complete