如何输入简单类型的 lambda 演算项 (S K K)

Question

我正在尝试实现一个简单类型的 lambda 演算类型检查器。当运行健全性测试时，我尝试输入 (SK K) 并且我的类型检查器抛出此错误：

TypeMismatch {firstType = t -> t, secondType = t -> t -> t}

违规用语显然是 (S K K)

(\x:t -> t -> t.\y:t -> t.\z:t.x z (y z)) (\x:t.\y:t.x) (\x:t.\y:t.x)

我认为问题是由于缺乏多态性引起的，因为当我输入检查这个 haskell 代码时它工作正常：

k x y = x
s x y z = x z (y z)
test = s k k -- type checks

但如果我专门研究类型：

k :: () -> () -> ()
k x y = x
s :: (() -> () -> ()) -> (() -> ()) -> () -> ()
s x y z = x z (y z)
test = s k k -- doesn't type check

仅供参考，我的类型系统很简单：

data Type = T | TArr Type Type

full source

Answer 1

我会借鉴的想法来展示如何向 ghci 提问。但首先我要稍微重新表述你的问题。

在Haskell中，我们有

s :: (a -> b -> c) -> (a -> b) -> (a -> c)
k :: a -> b -> a

我们想问的问题是"What do these types look like after type-checking s k k?"。更重要的是，如果我们用不同的统一变量重写它们，

s :: (a -> b -> c) -> (a -> b) -> (a -> c)
k :: d -> e -> d
k :: f -> g -> f
s k k :: h

那么问题就变成了一个统一问题：我们正试图将 s 的类型与其使用的类型统一——即 (d -> e -> d) -> (f -> g -> f) -> h。现在我们手头有一个统一问题，我们可以按照我另一个答案中显示的格式提问：

> :{
| :t undefined
| ::   ((a -> b -> c) -> (a -> b) -> (a -> c))
|    ~ ((d -> e -> d) -> (f -> g -> f) -> h)
| => (a, b, c, d, e, f, g, h)
| :}
undefined
::   ((a -> b -> c) -> (a -> b) -> (a -> c))
   ~ ((d -> e -> d) -> (f -> g -> f) -> h)
=> (a, b, c, d, e, f, g, h)
  :: (f, g -> f, f, f, g -> f, f, g, f -> f)

现在我们可以看到为什么您的版本不起作用：在您的版本中，您已将所有多态变量实例化为基本类型 T；但是由于 b ~ g -> f、e ~ g -> f 和 h ~ f -> f 显然是箭头类型，所以这肯定行不通！但是，如果我们尊重上面的替换，f 和 g 的任何选择都将起作用；特别是如果我们选择 f ~ T 和 g ~ T，那么我们有

s :: (T -> (T -> T) -> T) -> (T -> (T -> T)) -> (T -> T)
k1 :: T -> (T -> T) -> T
k2 :: T -> T -> T
s k1 k2 :: T -> T

如何输入简单类型的 lambda 演算项 (S K K)

How to type the simply typed lambda calculus term (S K K)

haskell

lambda

functional-programming

k-combinator

s-combinator