9 ms·

Baby's first type checker

78 points by alexmolas 1y ago

ashwinsundar 1y ago
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!
onestay42 1y ago
It's amazing to me that a python program can be written to make sure another python program is pythoning properly.
- goku12 1y ago
  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.)
  - onestay42 1y ago
    I suppose it is how this kind of tool generally works. I think it's just some subset of the feeling I get when someone writes(implements?) $LANGUAGE in $LANGUAGE(e.g. brainf*ck in brainf*ck) EDIT: escaped censorship
  - mhh__ 1y ago
    Foundational tooling not being written in a compiled language (fast is good, it could be jitted, but ideally it's a single binary) is actually a huge tax that I'm quite glad we're getting over as an industry. Python is probably the apex of the "slow + doesn't work without a magic environment" problem
- mhh__ 1y ago
  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.
chubot 1y ago
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 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-Approach-Python/dp/0262048248 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-code/blob/main/type_check_Lfun.py 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 https://lobste.rs/s/opwycf/baby_s_first_type_checker [2] https://github.com/AZHenley/babytypechecker/pull/1 https://github.com/AZHenley/babytypechecker/pull/1
- mananaysiempre 1y ago
  > 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/ https://www.cis.upenn.edu/~bcpierce/tapl/

78 points by alexmolas 1y ago

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!

onestay42 1y ago

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

goku12 1y ago
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.)
- onestay42 1y ago
  I suppose it is how this kind of tool generally works. I think it's just some subset of the feeling I get when someone writes(implements?) $LANGUAGE in $LANGUAGE(e.g. brainf*ck in brainf*ck) EDIT: escaped censorship
- mhh__ 1y ago
  Foundational tooling not being written in a compiled language (fast is good, it could be jitted, but ideally it's a single binary) is actually a huge tax that I'm quite glad we're getting over as an industry. Python is probably the apex of the "slow + doesn't work without a magic environment" problem
mhh__ 1y ago
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.

chubot 1y ago

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 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-Approach-Python/dp/0262048248 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-code/blob/main/type_check_Lfun.py 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 https://lobste.rs/s/opwycf/baby_s_first_type_checker [2] https://github.com/AZHenley/babytypechecker/pull/1 https://github.com/AZHenley/babytypechecker/pull/1

mananaysiempre 1y ago
> 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/ https://www.cis.upenn.edu/~bcpierce/tapl/