title: Type information in Abstract Syntax Trees
body: <p>What type information exists in an abstract syntax tree? How are ASTs used for type inferencing? I don't understand how type input and output can be derived given an AST when none of the nodes indicate the concrete types. Are the types inferred from the tree structure alone? e.g. There are a bunch of <code>IfStatement(Statement)</code>, so it's likely to return a bool? For example, the javalang python module uses these AST nodes:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>Given some toy code, it spits out the following AST for the functions:</p>
  
  <pre><code>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)
          )
      )
  )
  </code></pre>
  
  <p>Also if anyone could point me to some good reading material on type inferencing given ASTs. Thanks.</p>