AST tools & type inference

[decorator-factory]

I just made a simple alternative parser that outputs an AST. This could allow doing some introspection

For example, you can now get all imported names given an AST:

Once we implement docstrings and/or stack diagrams, we could do some type inference!

Step-by-step type inference example

Suppose we have this definition:

{ dup * swap dup * + }
:add-squares jar

These types are given in the stdlib:

dup : (a -- a a)
swap : (a b -- b a)
* : (Int Int -- Int)
+ : (Int Int -- Int)

1. First, add-squares's type is assigned to (*?1 -- *?2) (where *?N is an unknown, but distinct "star-type", like *Int Str).
2. Then, the first instruction is analyzed. Application (a -- a a) on *?1 requires that *?1 is at least one element deep. So let *?1 be *?3 ?4. Now the temporary type is (*?3 ?1 -- *?2), and the current "accumulated" type inside the function is *?3 ?4 ?4.
3. Then we'll infer the type of { * swap dup * + } with the initial stack type being *?3 ?4 ?4.
4. First, * is of type (Int Int -- Int), so ?4 must be Int. (Int Int -- Int) on *?3 ?4 ?4 assigns ?4 to Int and returns *?3 Int.
5. Then we'll infer the type of { swap dup * + } with the initial stack type being *?3 Int
6. First, swap is of type (a b -- b a). (a b -- b a) on *?3 Int assigns *?3 to *?6 ?5 Int and returns *?6 Int ?5.
7. Then we'll infer the type of { dup * + } with the initial stack type being *?6 Int ?5
8. First, dup is of type (a -- a a). (a -- a a) on *?6 Int ?5 doesn't assign anything and returns *?6 Int ?5 ?5
9. Then we'll infer the type of { * + } with the initial stack type being *?6 Int ?5 ?5
10. First, * is of type (Int Int -- Int). (Int Int -- Int) on *?6 Int ?5 ?5 assigns ?5 to Int and returns *?6 Int Int.
11. Then we'll infer the type of { + } with the initial stack type being *?6 Int Int.
12. First, + is of type (Int Int -- Int). (Int Int -- Int) on ?6 Int Intdoesn't assign anything and returns?6 Int`
13. Then we'll infer the type of {} with the initial stack type being *?6 Int.
14. We've reached the end, the return type is *?6 Int. Keeping that in mind and going back the chain.
15. *?2 = *?6 Int. Now we need to figure out how *?6 is related to *?1.
16. We know that ?5 = Int (from 10), *?3 = *?6 ?5 Int (from 6), ?4 = Int (from 4), *?1 = *?3 ?4 (from 2).
17. From the end of last sentence to its start: *?1 = *?3 ?4 -> *?1 = *?3 Int -> *?1 = *?6 ?5 Int -> *?1 = *?6 Int Int.
18. *?1 = *?6 Int Int and *?2 = *?6 Int. Therefore, the type of add-squares is (*?6 Int Int -- *?6 Int), which simplifies to (Int Int -- Int).

[decorator-factory]

The example is probably way too explicit, but it shows exactly how the implementation would think. I'll try to come up with a general algorithm soon.

[decorator-factory]

I implemented the type inference engine prototype in Haskell:
https://repl.it/@int6h/AppropriateValuableTransfer#main.hs

main :: IO ()
main = infer [ dup, mul, swap, dup, mul, add ]

-- Input type: (int (int *?13))
-- Output type: (int *?13)