Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Baby's first type checker

austinhenley.com

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Baby's first type checker

#11

Post by grumpyprole »

zem wrote: post #10
chubot wrote: post #4

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=…

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.

No it's not pleasant at all. It's boilerplate heavy, non-local and indirect. It's presumably a large part of why pattern matching is arriving in Python.

Re: Baby's first type checker

#12

Post by zem »

grumpyprole wrote: post #11
zem wrote: post #10

Earlier quoted context omitted.

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.

No it's not pleasant at all. It's boilerplate heavy, non-local and indirect. It's presumably a large part of why pattern matching is arriving in Python.

I guess that's subjective - I'm as big a fan of pattern matching as anyone, but when I was writing a type checker in python we made heavy use of visitors and it made the code pleasant to maintain.

Re: Baby's first type checker

#13

Post by thechao »

mananaysiempre wrote: post #5
chubot wrote: post #4

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=…

> 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…

TaPL really falls down when trying to bootstrap your way to understanding the notation. A lot of the notation and theory revolves around, essentially, implementing a concurrent virtual machine. I like the original algorithm W paper because it doesn't gloss this conceptual step: it is very much a virtual machine & you can see the authors handling the edge cases. The operational semantics in TaPL are (frankly) obtuse. Also, TaPL makes it seem like new features can be desugared to old features — and they can — but a little more prose explaining the feature's behavior directly without just tossing you into the semantic deep end would've made a much nicer text.

Re: Baby's first type checker

#14

Post by flare_blitz »

grumpyprole wrote: post #11
zem wrote: post #10

Earlier quoted context omitted.

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.

No it's not pleasant at all. It's boilerplate heavy, non-local and indirect. It's presumably a large part of why pattern matching is arriving in Python.

That's a lot of buzzwords to say that you enjoy shoving everything in one function. :)

Re: Baby's first type checker

#15

Post by onestay42 »

goku12 wrote: post #6
onestay42 wrote: post #3

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

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.)

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

Re: Baby's first type checker

#16

Post by mhh__ »

onestay42 wrote: post #3

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

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.

Re: Baby's first type checker

#17

Post by mhh__ »

goku12 wrote: post #6
onestay42 wrote: post #3

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

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.)

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

Re: Baby's first type checker

#18

Post by grumpyprole »

flare_blitz wrote: post #14
grumpyprole wrote: post #11

Earlier quoted context omitted.

No it's not pleasant at all. It's boilerplate heavy, non-local and indirect. It's presumably a large part of why pattern matching is arriving in Python.

That's a lot of buzzwords to say that you enjoy shoving everything in one function. :)

In hindsight, I think your description is indeed better!

Re: Baby's first type checker

#19

Post by mrkeen »

zem wrote: post #10
chubot wrote: post #4

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=…

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.

Doing it this way maxes coupling and minimises cohesion.

Your language will have a number of phases/passes to carry out. Let's say LambdaLifting, TypeChecking and Inlining.

All the code for lambda lifting belongs in one module, all the code for type-checking in another module, etc.

If you instead use visitor pattern, you will be looking at all the code related to Variable, Function, Literal in those files respectively.

So when you're working on Function.typecheck(), it will sit in source code just under Function.lambdalift() and just above Function.inline() - things which you don't want to consider together. Meanwhile, you'll need to switch between source files to work on Variable.typecheck() and Literal.typecheck().

Re: Baby's first type checker

#20

Post by Jtsummers »

mrkeen wrote: post #19
zem wrote: post #10

Earlier quoted context omitted.

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.

Doing it this way maxes coupling and minimises cohesion. Your language will have a number of phases/passes to carry out. Let's say LambdaLifting, TypeChecking and Inlining. All the code for lambda lifting belongs in one module, all the code for type-checking in another module, etc. If you instead use visitor pattern, you will be looking at all the code related to Variable, Function, Literal in those files respectivel…

> If you instead use visitor pattern, you will be looking at all the code related to Variable, Function, Literal in those files respectively.

I've never organized visitor pattern code that way. Usually it's something like:

  TypeChecker
    visitFunction
    visitVariable
    visitLiteral
  PrettyPrinter
    visitFunction
    visitVariable
    visitLiteral
So related functions (across the types you're visiting) are kept together, you're not revisiting the Function module to add a new visitor there. That would almost defeat the purpose of the pattern.

https://en.wikipedia.org/wiki/Visitor_pattern - See the UML diagram here.

Post reply on HN