types - 抽象语法树中的类型信息

Question

抽象语法树中存在哪些类型信息？AST 如何用于类型推断？当没有节点指示具体类型时，我不明白如何在给定 AST 的情况下派生类型输入和输出。是否仅从树结构推断出类型？例如有一堆IfStatement(Statement)，所以它可能返回一个布尔值？例如，javalang python 模块使用这些 AST 节点：

CompilationUnit(Node)
Import(Node)
Documented(Node)
Declaration(Node)
Type(Node)
TypeArgument(Node)
TypeParameter(Node)
Annotation(Node)
ElementValuePair(Node)
ElementArrayValue(Node)
ArrayInitializer(Node)
VariableDeclarator(Node)
InferredFormalParameter(Node)
Statement(Node)
SwitchStatementCase(Node)
ForControl(Node)
EnhancedForControl(Node)
Expression(Node)
EnumBody(Node)
VariableDeclaration(Declaration)
FormalParameter(Declaration)
TryResource(Declaration)
CatchClauseParameter(Declaration)
AnnotationMethod(Declaration)
BasicType(Type)
ReferenceType(Type)
TypeDeclaration(Declaration, Documented)
PackageDeclaration(Declaration, Documented)
ConstructorDeclaration(Declaration, Documented)
EnumConstantDeclaration(Declaration, Documented)
ClassDeclaration(TypeDeclaration)
EnumDeclaration(TypeDeclaration)
InterfaceDeclaration(TypeDeclaration)
AnnotationDeclaration(TypeDeclaration)
Member(Documented)
MethodDeclaration(Member, Declaration)
FieldDeclaration(Member, Declaration)
ConstantDeclaration(FieldDeclaration)
LocalVariableDeclaration(VariableDeclaration)
IfStatement(Statement)
WhileStatement(Statement)
DoStatement(Statement)
ForStatement(Statement)
AssertStatement(Statement)
BreakStatement(Statement)
ContinueStatement(Statement)
ReturnStatement(Statement)
ThrowStatement(Statement)
SynchronizedStatement(Statement)
TryStatement(Statement)
SwitchStatement(Statement)
BlockStatement(Statement)
StatementExpression(Statement)
CatchClause(Statement)
Assignment(Expression)
TernaryExpression(Expression)
BinaryOperation(Expression)
Cast(Expression)
MethodReference(Expression)
LambdaExpression(Expression)
Primary(Expression)
ArraySelector(Expression)
Literal(Primary)
This(Primary)
MemberReference(Primary)
Invocation(Primary)
SuperMemberReference(Primary)
ClassReference(Primary)
Creator(Primary)
ExplicitConstructorInvocation(Invocation)
SuperConstructorInvocation(Invocation)
MethodInvocation(Invocation)
SuperMethodInvocation(Invocation)
VoidClassReference(ClassReference)
ArrayCreator(Creator)
ClassCreator(Creator)
InnerClassCreator(Creator)

给定一些玩具代码，它会为函数输出以下 AST：

public class HelloWorld{
  public static void main(String args[]){
     add(5);
  } 
  public static int add(int x){
     return x+0;
  }
}

(MethodDeclaration 
    (FormalParameter
        (ReferenceType)
    )
    (StatementExpression
        (MethodInvocation
            (Literal)
        )
    )
)

另外，如果有人可以指出一些关于给定 AST 的类型推断的优秀阅读材料。谢谢。

score 3 · Accepted Answer

AST 如何用于类型推断？

类型推断通过遍历传播“环境”的树将无类型的 AST 转换为有类型的 AST，该“环境”是将变量名称（包括函数）映射到其类型的字典。这会沿着 AST 传播到叶子。

文字整数或字符串的类型是intor string。

在环境中查找变量的类型。

函数应用程序的类型f(x)wheref: a -> b和x: ais b。

fun x -> ywherex: a和y: bis的类型a -> b。

在let x = y in zwhere 处y: a，推理添加到环境的绑定x: a，并在新环境的上下文中推断出的类型z（即整个let表达式的类型），以便x: a在遇到时进行查找x。

等等。Hindley-Milner 类型系统更复杂，因为它包含泛型，但实现只不过是为了获得关于类型变量的一系列约束并解决这些约束以计算出尽可能多的类型变量。类型变量通常在let绑定中泛化，例如，let id x = x定义一个泛型标识函数∀a id: a -> a。

此外，在存在突变的情况下，源自扩展类型的类型变量不会被泛化，因此，例如，ref None: '_a具有'_a在 OCaml 中表示的弱多态类型，意思是“此类型变量只能解析为一种具体类型”，即∃a而不是∀x.

最小 ML 方言的类型推断int，fun代码不到 100 行，在现代计算机上合理的实现速度很快。

您可能会喜欢以下链接：

types - 抽象语法树中的类型信息

1 回答 1

Related

Reference