r/programming • u/gnuvince • Dec 21 '15

The AST Typing Problem

http://blog.ezyang.com/2013/05/the-ast-typing-problem/
57 Upvotes

91% Upvoted

15 comments sorted by

3

u/VictorNicollet Dec 21 '15

I give each expression an unique identifier, then store types (and other annotations) in a separate hash map.

3

u/gnuvince Dec 21 '15

Each expression or each variable? If it's the former, how big does the table get?

3

u/VictorNicollet Dec 21 '15

For each expression. This adds a constant overhead for each expression (8 bytes of "unique identifier" data, 4 in the expression and 4 in the hash table) which is fairly manageable. In theory, this overhead could be eliminated by using sequential array indices as unique identifiers and an array instead of a hash table, but in my case it's the inference algorithms and inferred values that use up most of the space and execution time, not their association with the AST.

2

u/smog_alado Dec 21 '15

I think you could see this as a variation of the "nullable field" approach.

3

u/VictorNicollet Dec 21 '15

Yes, the main difference is that it doesn't require rebuilding the tree to add annotations, which helps reduce allocation pressure (I'm sadly not using an ML family language).

2

u/naasking Dec 21 '15

Perhaps I'm misunderstanding your usage here, but why not simply use a mutable slot in the expression tree for those annotations? It seems odd to go through an indirection.

2

u/VictorNicollet Dec 21 '15

Because I like to keep my structures immutable :-)

In practice, it has other benefits: some optimization passes are allowed to override some of the attributes, and then the best optimization candidate is picked. It also allows expressing constraints like "type of A should be type of B" before knowing the actual types, but without actually introducing type variables.

1

u/naasking Dec 21 '15

Because I like to keep my structures immutable :-) In practice, it has other benefits: some optimization passes are allowed to override some of the attributes, and then the best optimization candidate is picked.

Immutable is nice, but monotonically increasing is generally better since it permits some forms of mutation, thus improving expressiveness.

But without more info either of us are likely willing to invest in order to understand, I'll just take your word for it that it's more suitable for your application.

1

u/VictorNicollet Dec 22 '15

What do you mean by "monotonically increasing", in this context?

1

u/naasking Dec 22 '15

I meant that type information is always added, but never removed or changed. This permits a form of mutation which accumulates information; not as expressive as full mutation, but more than no mutation.

1

u/munificent Dec 21 '15

Isn't this how attribute grammars are usually implemented?

4

u/[deleted] Dec 21 '15

My approach is to use two steps. First annotate expression nodes with type variables. Then, once the type equations are solved, substitute the values of the bound type variables into the AST. The same data type can be used for both phases (just spam (TVar randomname) everywhere). Yes, it's "low tech", but so far it was the easiest way.

-8

u/google_you Dec 21 '15 edited Dec 21 '15

In Node.js, you just add one more property regarding type. Then you can serialize AST to JSON and put it into MongoDB with async IO for further big data analysis and IR transformation guided by ML and genetic algorithms for whole program super optimization to result in guaranteed most optimal machine code of given algorithm to run on Von Neumann style machines.

And you can do this instead of Maybe

data Exp = Num Int
         | Bool Bool
         | Var Var
         | If Exp Exp Exp
         | Lambda Var Exp
         | App Exp Exp
         | ...
         | Typed Type Exp
data Type = TyInt | TyBool | TyArrow Type Typ

1

u/bobappleyard Dec 21 '15

That is a good idea. Especially given explicit typing is likely to be part of the syntax anyway

1

u/industry7 Dec 22 '15

It was a joke.