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

Replying to

and

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.

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

Replying to

and

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

Brendan Zabarauskas

@brendanzab

Apr 20, 2020

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.

Show replies