Baby's first type checker

[ashwinsundar]

Very much looking forward to spending some time implementing this alongside the article. I really enjoyed your posts about making a Teeny Tiny compiler a while back too!

[chubot]

It's very nice to see a small type checker in Python, for Python! This became much easier in the last 10 years, since the MyPy team basically "upstreamed" the typed_ast library they were using into the stdlib.

I found that there are not enough good teaching materials on type checkers -- e.g. the second edition of the Dragon Book lacks a type checker, which is a glaring hole IMO - https://news.ycombinator.com/item?id=38270753

Also, teaching material tends to have a bias toward type inference and the Hindley-Milner algorithm, which are NOT used by the most commonly used languages

So I appreciate this, but one thing in this code that I find (arguably) confusing is the use of visitors. e.g. for this part, I had to go look up what this method does in Python:

    # Default so every expr returns a Type.
    def generic_visit(self, node):
        super().generic_visit(node)
        if isinstance(node, ast.expr):
            return ANY

Also, the main() calls visit(), but the visitor methods ALSO call visit(), which obscures the control flow IMO. Personally, if I need to use a visitor, I like there to just be a single pass

---

In contrast, Essentials of Compilation was released 1 or 2 years ago, in Racket and in Python. And the Python version uses the same typed AST module.

https://www.amazon.com/Essentials-Compilation-Incremental-Ap...

But it uses a more traditional functional style, rather than the OO visitor style:

https://github.com/IUCompilerCourse/python-student-support-c...

So one thing I did was to ask an LLM to translate this code from OO to functional style :-) But I didn't get around to testing it

(I looked at this code a week ago when it appeared on lobste.rs [1], and sent a trivial PR [2])

[1] https://lobste.rs/s/opwycf/baby_s_first_type_checker

[2] https://github.com/AZHenley/babytypechecker/pull/1

[mananaysiempre]

> I found that there are not enough good teaching materials on type checkers -- e.g. the second edition of the Dragon Book lacks a type checker, which is a glaring hole IMO

Pierce’s Types and Programming Languages[1] is excellent. It starts with very little (if you understand basic set-theory notation, you’re probably OK), gets you to a pretty reasonable point, and just generally makes for very pleasant reading. You should probably pick something else if you want a hands-on introduction with an immediate payoff, but then you probably wouldn’t pick the Dragon Book, either.

[1] https://www.cis.upenn.edu/~bcpierce/tapl/

[zem]

once you get used to it, visitors are a very pleasant way to write ast walking code in python. they are essentially generating your case statement for you, so instead of `case ast.Expr: handle_expr(node)` you just write a `self.visit_expr` method and have the visitor match the node type to the method name and call it.

[onestay42]

It's amazing to me that a python program can be written to make sure another python program is pythoning properly.

[goku12]

Just curious. Isn't that how development tools generally work? Would you be surprised if it was in and for a compiled language? (This isn't a dismissal. I'm curious about the aspect of this specific case that amuses you.)

[mhh__]

You can see from how quickly the code becomes extremely busy and annoying to read that python being flexible is a blessing and a curse. Maybe curse is the wrong word, but none of this was really designed cohesively so it's usually very janky and a bit slow.