Conversation

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

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

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

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.

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

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

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.

Replying to

and

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.

Replying to

and

The basic condition is that you can fuse something away if you use it linearly... I don't have enough compiler-writing experience to know offhand which passes satisfy that and which ones don't, so that's a fun question.