Sou*_*uet 1 types type-inference abstract-syntax-tree hindley-milner
抽象语法树中存在哪些类型信息？如何使用 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 类型推断的好读材料。谢谢。
\n\n如何使用 AST 进行类型推断？
\n
类型推断通过遍历传播“环境”的树将非类型化 AST 转换为类型化 AST，“环境”是将变量名称（包括函数）映射到其类型的字典。这会沿着 AST 传播到叶子。
\n文字整数或字符串的类型是intor string。
在环境中查找变量的类型。
\n函数应用程序的类型，f(x)其中f: a -> b和x: a是b。
fun x -> ywherex: a和y: bis的类型a -> b。
在let x = y in zwhere 处y: a，推理添加了对环境的绑定x: a，并在新环境的上下文中推断 的类型z（即整个表达式的类型），以便在遇到 时let可以进行查找。x: ax
等等。Hindley-Milner 类型系统更为复杂，因为它包含泛型，但其实现只不过是为了获取有关类型变量的一系列约束并解决这些约束以计算出尽可能多的类型变量。类型变量通常在let绑定处进行泛化，例如，let id x = x定义一个泛型标识函数\xe2\x88\x80a id: a -> a。
此外，在存在突变的情况下，源自扩展类型的类型变量不会被泛化，因此，例如，ref None: \'_a具有 OCaml 中表示的弱多态类型，\'_a意思是“该类型变量只能解析为一种具体类型”，即\xe2\x88\x83a而不是\xe2\x88\x80x。
最小 ML 方言的类型推断int不到fun100 行代码，并且合理的实现在现代计算机上速度很快。
您可能会喜欢以下链接：
\n