Design Compiler - Join and Meet 类型

Question

我正在使用 SML 为另一种函数式语言设计编译器（您可以在此处查看其定义 http://corelab.postech.ac.kr/~hanjun/2016S_compiler/hw/fun_language_definition.php）。我的任务是设计一个类型检查。什么是 return 类型？ if a>0 then <<3, 4>, 5> else <<6>, 7, 8>

为了回答这个问题，我需要找到上述 2 类型的 "join"。 "Join"：是最不常见的超类型。例如，t1 <: t3 和 t2 <: t3 => t3 是 join(t1,t2)。 "Meet" 是最常见的子类型。 t3 <: t1 和 t3 <: t2 => t3 是 meet(t1, t2)。

我的任务是设计相互递归的相遇和加入。你能给我一个如何实现它们的提示吗？

Answer 1

您需要研究子类型化规则以推导出递归定义。例如，使用元组类型。由于较长的元组是较短元组的子类型，假设公共前缀类型匹配，并且如果元素类型是成对子类型，则一个元组类型是花药的子类型，你将有：

join(<t1, ... tm>, <u1, ... un>) = <join(t1,u1), ... join(tp,up)>
    where p = min(m,n)

和

meet(<t1, ... tm>, <u1, ... un>) = <meet(t1,u1), ... meet(tm,um), u_m+1, ... un> 
    when (wlog) m <= n

大部分规则都会像这样自递归。由于参数反转，函数类型除外。在这里你需要 meet 来定义连接，反之亦然。我不会通过给出答案来破坏你的乐趣。

基本情况当然只是

meet(int, int) = join(int, int) = int

Design Compiler - Join and Meet 类型

Design Compiler - Join and Meet type

compiler-construction

types

type-systems

typechecking