Conversation

Wonder how much of bidirectional type checking can be done in that manner...

Quote Tweet

· Apr 18, 2020

For FP nerds, parsing an AST from a string is an unfold for the AST data type, type checking and generating code from the AST is a fold, and if you do fold/unfold fusion you have a one-pass compiler.

Show this thread

Brendan Zabarauskas

@brendanzab

Apr 20, 2020

Reminds me of twitter.com/glaebhoerl/sta - I'm thinking of making a core language like this.

Quote Tweet

crow emoji

@glaebhoerl

· Feb 22, 2020

If you have an LL(k) grammar, require all names to be declared prior to their use, and have a sensible type system that can be typechecked in one pass, I think you could get through the whole front end of the compiler without ever materializing an AST in memory?

Show this thread

crow emoji

@glaebhoerl

Apr 20, 2020

I think this is essentially "finally tagless": instead of defining your structures (AST or IR) as data, define them as classes; in the parser resp. elaborator, "construct" the AST resp. IR by calling methods; make instances do elaboration, resp. perhaps code generation, directly.

crow emoji

@glaebhoerl

Apr 20, 2020

You can also define instances to construct an actual AST/IR as data, if you need that, for example to do analysis/optimization. (I'm not sure if you couldn't also do those as a directly fused chain, but I'm pretty sure you couldn't if you need to compute fixed points.)

Brendan Zabarauskas

@brendanzab

Apr 20, 2020

Yeah, I was thinking of doing the this using visitors (very similar). I couldn't figure out how to make something like this work though: lihaoyi.com/post/ZeroOverh - ie. because this is a depth-first traversal it is hard to manage your context.

Replying to

and

Like, you jump into your body of the lambda, but you haven't bound the variable in the context yet.

10:20 AM · Apr 20, 2020Twitter Web App

Replying to

and

There also might be downsides in terms of blowing out your instruction cache (or something like that) with too much fusion, which could reduce throughput I think? But yeah, it would be interesting to measure this.

Brendan Zabarauskas

@brendanzab

Apr 20, 2020

You might inspire me to try this again though - I think it could be super fun to try, even with something like STLC. Would be cool if you could fuse ANF, closure conversion, SSA, etc all the way down.

Show replies

Replying to

and

I've been wanting to try implementing this myself, but haven't done so yet... there may be wrinkles. :) Maybe you'd need to add the notion of a context explicitly as part of the classes' APIs? (and tl;dr on that link, alas)