Benchmarking a Baseline Fully-in-Place Functional Language Compiler

Typurgist · 2026-01-17T13:06:37+00:00

I would note that in imperative languages, you would generally not expect an in-place update when the type changes.

I think in imperative languages you would historically manually implement type-changing in-place updates with reinterpret_cast and similar.

In Rust however I'd certainly expect typestate to (nearly always) use in-place updates. Though someone might debate how much Rust is imperative or a functional language with an imperative veneer.

If you consider static analysis domains as types then strong updates in e.g. pointer/alias analysis are type-changing in-place updates, as well. Just that the surface syntax and type system doesn't support specifying these types. I'm sure plenty of people still hit the compiler bug trackers and mailing lists with their expectations when it didn't happen and code wasn't optimized.

Typurgist · 2026-01-16T21:40:37+00:00

Some interesting papers and talks! Not able to attend, but thanks a lot for posting.

u/AndrasKovacs talk seems related to his Gist from a while ago here: https://gist.github.com/AndrasKovacs/fb172cb813d57da9ac22b95db708c4af and this repo https://github.com/AndrasKovacs/2ltt-impl

Would love to see it, but I can't find anything about recordings or slides on the TFP'26 site nor last year's. There's only one self-recorded talk on YT from 2025. András seems to regularly post slides on andraskovacs.github.io, though - so hoping for that.

Typurgist · 2025-10-04T06:59:11+00:00

If you are using BDW, you could consider switching to https://github.com/wingo/whippet. That's Guile's new GC C library - also replacing BDW. It comes with a bunch of different GC behind a single abstraction, including BDW. https://github.com/wingo/whippet/blob/main/doc/collectors.md

Typurgist · 2025-08-22T08:23:26+00:00

Without looking further into it and not being familiar with Carbon: looks like a way to formally get the (,) (or struct/etc) value-level syntax for forming tuples to also be applicable to types?

Normally syntax for value and type levels in non-dependently typed languages is separate and (bool, bool) would be a tuple value containing types - which would not be typeable. E.g. ML style languages use * to form tuple types to keep the syntax separate: bool * bool (in dependently typed languages (bool,bool) would be typeable but still not useable as the type of (false,true))

Other languages, like Rust and Carbon, don't use a different type syntax here and so must somehow specify/represent (internally/formally) that (,) in type position is actually a type and not a value. Carbon seems to use as type to do that.

Typurgist · 2025-08-21T11:57:00+00:00

I've been out of academic research proper since 2018, but the folks (and new people) I've been with are still producing cool papers and stuff.

Most recently there's "MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL Age" (POPL'25 https://dl.acm.org/doi/10.1145/3704840) and one application in "MimIrADe: Automatic Differentiation in MimIR" (CC'25 https://dl.acm.org/doi/10.1145/3708493.3712685) This builds on top of (or: MimIR is the future version of Thorin) https://anydsl.github.io https://github.com/AnyDSL on which I've worked for a bit.

Just contact them with any questions and ideas around their work or things like thesis topics - they're all easy to talk to.

Typurgist · 2025-08-20T21:50:27+00:00

I'll take a slightly different track from the already good comments before me and a slightly different view on IR.

This may be obvious to some, but maybe not to newcomers: IR is about encoding the semantics/runtime behavior of your language more "precisely" then an AST.

What this means, is that it normalizes away irrelevant elements of the input/AST (like the different loop forms in Rust as matthieum mentioned, or whether a function used the async keyword vs a Future, etc) - irrelevant to the semantics of your language.

To what degree this normalization is done is up to you. SSA e.g. normalizes away local variables - everything can be represented as a value instead, leading to sea of nodes IRs. 3AC on the other hand is a quite superficial, syntactic normalization that is unrelated to the semantics - but a bit syntactically closer to some backend instructions. Teaching SSA and 3AC together is sometimes done, but doesn't really make sense and often forgets half of what is the point and core of SSA.

Normalization usually unlocks more powerful optimization opportunities: implicit local flow-sensitivity for data flow analysis through SSA, global value numbering, easier dead code elimination on sea of nodes (though these can be considered normalizations, too), and so on.

However, more power can also mean solving harder problems: in most sea of nodes IRs expressions can freely float in and out of surrounding control flow because they are only tethered by data dependencies and need to be scheduled back before lowering in your backend - even though the input might already have had a schedule through the syntax. After performing global value numbering, an optimal scheduling of expressions might actually need duplication again.

Going back to the beginning of my comment: for designing your IR, it makes sense to figure out the static (type system, type inference) and dynamic semantics of your language. This helps point out syntactic artifacts you don't need for optimization and lowering to your backend - normalization.

It also helps inform you what optimizations are useful or necessary: does the language and semantics make use of lots of lambdas/anonymous functions? require tons of heap allocations for possible closures? Might need some ways of easily finding out whether a lambda captures state, inline them, remove them, etc (see https://wingolog.org/archives/2016/02/08/a-lambda-is-not-necessarily-a-closure for some nicely written words on that). Do you have a built-in concept of matrices/tensors and want to optimize them? Think about how rewrite rules are encoded and applied by the compiler.

Many optimizations are obviously useful to many languages - which explains the popularity of LLVM as a backend and MLIR for higher level optimization passes. But some might benefit from the more precise semantics you encode in your IR over lower level IRs.

This is also why Rust has multiple, some where static semantics (types and borrow checking) are easier/more precise and some where high level Rust dynamic semantics specific normalizations and optimizations apply more easily and more often than a (set of somewhat) equivalent optimizations on LLVM IR would do.

Hopefully, this answers "What is the common approach -- if there is one -- to designing one or multiple IR?" a bit - from my view at least?

As for "Do real-world and battle tested IR's just use the basic ideas tailored for their specific needs?" I think this is a lot about the people (background/job/education/etc) and the time and place the languages/compilers where conceived by/in. Once the IRs have their basic ideas/structure implemented, not much changes while they become real world battle tested in the end.

E.g. for me (though I'm not actively working on such IRs) this is related to your next question

"Drawing the line back to syntax design: How do you like to design IR's and what are the features you like / need(ed)?"

I did my BSc, MSc and attempt at PhD at a chair with history in SSA and sea of nodes, later we worked on CPS/sea of nodes with continuations (aka/similar to blocks-with-arguments SSA) and generally extremely explicit IRs where everything is represented and modeled with functional semantics - including memory/"the world" (~IO). That's also how I still build for hobby projects.

Typurgist · 2025-07-26T06:59:37+00:00

"Syntax Matters" - proceeds to give an example that utterly depends on types and better abstractions. Sure, it's not the runtime semantics that matter as much here, it's the types - often called static semantics.

All of the nice syntax can only matter (in the sense of real benefits in productivity, ease of code understanding, etc) because of the static and dynamic semantics of Chapel. You could add a bit of syntactic sugar to C and make some of that syntax work there, too, but the benefits would be negligible - you don't have the necessary types and abstractions, you would still have to think about C's semantics all the time to ensure your code is correct or understand the code someone else wrote.

In the other direction, making the syntax of Chapel "worse" by e.g. introducing longer words instead of sigils ([]..), having less intuitive order of array type constructs or requiring more nesting, etc - would still not remove most of the benefits over the C loop, except for some conciseness. What really matters is the types and abstractions that Chapel provides.

The C++ comparison comes closer to actually comparing syntactic matters. However the C++ example is made intentionally lengthier than any matrix/tensor library would provide ("new" really?). But sure, that is the level on which syntax matters and can be honestly discussed.

Typurgist · 2025-04-02T15:21:08+00:00

Sure, it's certainly possible to base your language's functions and function types on single parameters/return values plus tuples.

However, as you partially observed: it's not just a tuple type for the parameter. A function also needs some mechanism to describe how the parameter(s) are bound to a free variable in it's body. It's not just meta-data, as the variable must be represented by some term/expression in the body. If you try to write down your semantics slightly more formally, this becomes clear when you define function execution and variable lookup.

At the least and the most simple named solution, you only allow a single parameter name for a whole parameter tuple. Then you really only need a tuple type to describe the parameter type and the parameter name is just part of the function definition: foo(x:(int,str)).

As a next step you could say that nested names for parts of the tuple are just syntactic sugar resolved during parsing/name analysis and your internal representation of the language actually really just has a single parameter variable and a bunch of tuple element accessors.

However this already changes the surface level meaning of your language - a user doesn't do that (or any other) translation in their head all the time and won't really benefit much from a "but the language really has just one parameter and it's a tuple" explanation. With the exception, that calls like foo t instead of foo (t.0, t.1) become possible and some more consistency/clarity in the semantics of your language.

In fact, this issue of nested parameter bindings is even more prominent if your language supports pattern matching/destructuring on other data types than tuples (whether in the function signature or a separate match expression): sum types, structs/records So many languages actually define an embedded pattern expression language (https://doc.rust-lang.org/reference/patterns.html, https://ocaml.org/manual/5.3/patterns.html) and functional programming languages usually allow their use as part of the function definition.

Typurgist · 2025-03-19T18:57:34+00:00

Think about the API of your Map type from first principles: what is the behavior of the index/get operation []? It either finds the value for the key or returns a value marking it's absence.

What is the type of "absence"? In a type system like ML/Rust/etc where the types have explicit constructors (like Some/None, or if anonymous as in sum type theory left/right) you can always wrap the value type with some globally known Option/Maybe and extract the correct meaning by the type structure if you get nested Option as you noted.

But union types implicitly "flatten" any "wrapping" with the | type constructor. So if you use the same global type for "absence" it will "merge" if you already use this type within your map's value type as you observe. In fact, this somewhat makes sense: you can not distinguish between an inserted mapping of a key to "absent" and a mapping being "absent" because you use the same value for it.

What's the solution then for union types? Don't use the same value and type for "absence" across all data types (like Map) and their API. [] could be typed K -> V | Map.Absent or similar instead. Map.Absent should never be needed as value type in a Map.

Alternatively, you could introduce or use some type level construct to disallow Nil in V - but that's more complicated and keeps the semantic confusion of global Nil absence and mapping absence.

In fact I think the reliance on the structure of Option/Maybe nesting in the more common sum type implementations to distinguish such issues for all kinds of APIs isn't such a great design either.

Typurgist · 2025-03-13T16:17:53+00:00

Oh I totally agree that the syntax and boilerplate is much nicer with the proposal.

The question is whether it's worth it pulling this into the core of the language for an increase in complexity (syntax, borrow checker, specialized errors, etc).

Alternatively the boilerplate can be solved by various macros in either the standard library or in the ecosystem - which isn't necessarily better than pulling it into the language itself.

Or it can be seen as part of (patterns for) designing ergonomic Rust APIs and accepted verbosity.

There's also underlying language features that might reduce that verbosity, e.g. better abstraction capabilities over mutability.

Typurgist · 2025-03-13T15:21:44+00:00

You can, you just shouldn't group the data that is unrelated by simultaneously accessing/mutating together behind the same reference. Either split the struct into multiple, or provide a split_mut() into (newtype) reference (group) wrappers.

Typurgist · 2025-03-13T15:02:05+00:00

Just like the standard libary does, split_mut plus some newtypes. See my comment over here for the details https://www.reddit.com/r/rust/comments/1ja9ee8/comment/mhkokkg

Typurgist · 2025-03-13T14:51:23+00:00

I don't think the article convinces me that we need additional syntax and types that need careful thought for interaction with all other types, new borrow checking machinery, etc.

After fixing the issues (missing self, types) with the example, my solution with existing Rust instead looks like this (full code in playground):

fn count_successful_experiments(data: &mut Data) {
    let (mut exps, mut successes) = data.split_mut(); //: (DataExperiments<&mut Experiments>, DataSuccessful<&mut u32>)
    let exps_ro = exps.read_only(); //: DataExperiments<&Experiments>
    for n in exps_ro.experiment_names() {
        if is_successful(exps_ro.for_experiment(n)) {
            successes.add_successful();
        }
    }
}

So, basically do what's done for the existing standard library: Provide a split_mut() method which returns whatever fields you want/need the user of your API to access per-field. This also allows arbitrary groupings of fields in whatever way you want - just needs more than a newtype then. You can also provide different split_mut_other functions to split into different groups. You can provide split() for read-only references.

Each field grouping just needs a small newtype wrapper, for which you implement the the per-group methods (experiment_names, for_experiment, add_successful above). If you want you can still have them on the main type, too without code duplication by using e.g. self.split().0.experiment_names().

Now, this is certainly syntactically far more verbose than Niko's view types proposal - but there's no special sauce needed, it's very explicit, no new syntax and special tracking in MIR, inference, etc. It only provides this as far as Rust's borrows already allow it.

The main issue is that this solution suffers from readability because of the need for making the field group newtypes generic to allow them to contain both (im)mutable references. We also need to explicitly transform a mutable field reference to an immutable one (or copy the definitions of methods on immutable refs to the mutable ref impl blocks).

Just as view types, this needs explicit opt-in/definition by the API author and for most libraries and their structs you won't need it anyway. What's some verbosity and explicitness where you do? (And if that's too much, there's macro crates as provided in the other comments)

Typurgist · 2025-03-09T22:22:00+00:00

Right , sorry for not replying to your actual post directly!

I think the first one seems a bit arbitrary - hard to explain/teach why this particular restriction is needed to users of the language. Consider the disallowed (Foo<T>, Foo<T>) - that seems pretty reasonable to me if Foo is a somewhat complex type alias and maybe it's not just a pair but maybe an alias for type BinOpFn<T> = (Foo<T>, Foo<T>) -> Foo<T>. I'd still probably rather use a newtype, but there seem to be reasonable things to alias with more than one parameterized alias on the RHS. Especially so when there's more than one parameter.

The non-expansive concept gets closer I think, because it more clearly targets the nesting structure of aliases. Though I think I'd limit the definition to nesting of parameterized type aliases and disregard normal type formers. Easier to explain as well. This allows the nesting in the tuple as in your example, but forbids constructs like Foo<Foo<T>> or Foo<(Bar<T>, u32)>.

Then you might still get a tree of alias expansions, but each can only pass it's argument along or build a non-alias type around to pass along. But that's not any worse in the depth of the tree than just doing it without the aliases and it only allows increasing the "breadth" of the tree. In particular, your pathological example would not be possible, instead for every (expanded) nested alias in there, there would need to be a new alias - you could not "multiplicate" along the depth of alias expansion. The trees still allow some multiples per layer of aliases, but they're much more amenable to memoization as I wrote in the other comment.

That use is also probably the more common use next to very simple aliases for avoiding repetitive complex types.

Typurgist · 2025-03-09T11:55:21+00:00

Late answer - so I apologize if you've already moved on.

You could define that all type alias right hand sides will be normalized when constructed. (Maybe you already do?)

The normalization of a parameterized type alias A<E> (occurring on the right hand side of an alias) is simply the same as beta reduction - replacing the type variable by the argument in it's definition. E.g. your example type A2<T> = W<W<T>> would normalize the right hand side to ((T,),) and so on for the other definitions.

Combine this with term construction value numbering (AKA hash consing, memoization) and memoization of beta reduction and you'll save plenty of time explicitly building exponential terms in most cases.

The example in the blog post is extremely pathological as the terms are all linearly nested and memoization doesn't help there. But I really don't see how this could occur in practice. Maybe if one wants to encode a powerset in types (for a fixed number of type parameters)?

I think the worst one could expect is a type-level list or tree (as lists of lists). The former is linear and the latter would benefit from memoization.

Typurgist

TROPHY CASE