Conversation

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

Quote Tweet

· 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

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.

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.

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.

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.

Pull-based tree processing for lambda calculi.

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.

Replying to

and

The other thing I'd like to try is pull-based compilation - but IIRC that might require better support for generators in Rust if I wanted to maintain my own sanity… here's something I was messing with ages ago:

gist.github.com

Pull-based tree processing for lambda calculi. GitHub Gist: instantly share code, notes, and snippets.

1:59 AM · Apr 21, 2020Twitter Web App

Replying to

Oh hey this was the first idea I had too. :) twitter.com/glaebhoerl/sta I started to doubt whether it even made made sense after learning of the push-based "finally tagless" approach (and after not receiving a response there).

Quote Tweet

· Apr 19, 2020

Replying to @pervognsen

Huh. I was thinking of trying to write a single-pass parser+typechecker with the TC in direct style, and the lexer+parser it pulls nodes from then state machines (but also written directly, as generators). This seems to be the other way around. Is either direction possible?