在抽象语法树中键入信息

Question

抽象语法树中存在哪些类型信息？ AST如何用于类型推理？我不明白在没有任何节点指示具体类型时，如果给定AST，可以如何派生类型输入和输出。这些类型是从树结构中推断出来的吗？例如有一堆IfStatement(Statement)，所以它可能会返回一个bool？例如，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的类型推理的好的阅读材料。谢谢。

Answer 1

CAST如何用于类型推断？

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

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

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

函数应用程序f(x)的类型，其中f: a -> b和x: a是b。

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

在let x = y in z，其中y: a，推论在环境中添加了一个绑定的x: a并推断z的类型（这是整个let表达的类型），因此它可以在遇到x: a时查找x。

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

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

使用int和fun的最小ML方言的类型推断是在100行代码下，并且在现代计算机上只是合理的实现是快速的。

您可能会欣赏以下链接：

https://pfudke.wordpress.com/2014/11/20/hindley-milner-type-inference-a-practical-example-2/ http://okmij.org/ftp/ML/generalization.html http://okmij.org/ftp/Haskell/AlgorithmsH.html#teval http://www.cs.cornell.edu/courses/cs6110/2013sp/lectures/lec32-sp13.pdf https://www.doc.ic.ac.uk/~scd/icooolps15_GC.pdf http://janvitek.org/pubs/oopsla17a.pdf http://www.cs.columbia.edu/~sedwards/classes/2016/4115-spring/proposals/JSJS.pdf https://github.com/7sharp9/write-you-an-inference-in-fsharp https://people.eecs.berkeley.edu/~wkahan/LOG10HAF.TXT http://www.elsman.com/pdf/masters.pdf https://courses.cs.washington.edu/courses/csep505/03au/hw/hw1.html http://lucacardelli.name/Papers/BasicTypechecking.pdf http://okmij.org/ftp/ML/generalization.html http://www.smlnj.org/doc/Conversion/types.html