![](https://csdnimg.cn/release/download_crawler_static/88749506/bg4.jpg)
M.
苏尔茨曼河
Voicu/Electronic Notes in Theoretical Computer Science 174
(
2007
)
129
追加Nil ys = ys
append(Cons x xs)ys = Cons x(append xs ys)
实际上,我们已经通过
GADT
和
CHR
的组合编码了索引类型但是,程序文本似
乎与类型注释相例如,在第一个子句中,我们返回类型为
List
a m的ys。 这与
annotation
声明结果值的类型为
List
a n。重要
观察到的是,我们需要考虑由模式匹配
Nil
产生的总之,Sum
l
m
n和l=Z意味着m=n
通过规则(
I1
)。因此,我们可以将ys的类型更改为
List
a n。关键点在于,因
此,第一个子句类型正确。类似的推理也适用于
到第二条。
根据我们的经验,CHR对于表示约束属性非常有用文献[41,7]中提出了类似的
机制。例如,在
Omega
语言
[24]
中,上述
CHR
可以使用相关的类型表示法
[6]
类型sum
::
*->*-
>*
s
u
m
Z
m
=
m
sum(S
l)
m
= S(sum
l
m)
也就是说,
Omega
使用函数而不是关系样式来指定类型条件。我们可以很容易
地通过适当的编码来支持这样的源代码级符号到我们的内部编译器语言(这是
图灵完备的)。此外,我们可以通过指定规则(如
规则
Sum
Int
a b ==>
False)
和
其他更复杂的改进条件来强制执行总体性。一些不可能的事情
当使用函数式书写类型条件时。此外,通过
CHR
,我们可以表达具有扩展的类型
类,例如多参数类型类和函数依赖[26],这些在其他系统中没有处理[41,24]。
2.2
类型检查
我们简要地看一下如何对EADT执行类型检查。 我们假设函数都提供了类型注释。
标准的方法是将类型问题转化为约束问题。与标准Hindley/Milner相比,我们需要
更丰富的
蕴涵
约束集。这样的约束是必要的,因为我们需要在不同的局部类型假设
(由GADT和类型注释上的模式匹配引起)下对不同的程序部分进行类型化
例如,如果
append
::
Sum
l
m
n
=>
List a
l
-> List a
m
-> List
a n append Nil ys
=
ys
append(Cons x xs)ys = Cons x(append xs ys)