This is a hobby project of mine that I started a few years ago to learn about programming language implementation. It was created 95% without AI, although a few recent commits include code from Gemini CLI. I started out following Crafting Interpreters, but gradually branched off that until I had almost nothing left in common. Tech stack: Rust, Cranelift (JIT compilation), LALRPOP (parser). Original title: "A small programming language where everything is a value" (edited based on comments) |
I've worked on systems where we spent more time reasoning about shared state than writing actual logic. The typical answer is "just make everything immutable" but then you lose convenient imperative syntax. This sits in an interesting middle ground.
Curious about performance in practice. Copy-on-write is great until you hit a hot path that triggers lots of copies. Have you benchmarked any real workloads?
Use immutable pass by reference. Make a copy only if mutability is requested in the thread. This makes concurrent reads lock-free but also cuts down on memory allocations.
This is essentially what Herd does. It's only semantically a pass by value, but the same reference counting optimizations still apply.
In fact, Herd's approach is a bit more powerful than this because (in theory) it can remove the copy entirely if the caller doesn't use the old value any more after creating the thread. In practice, my optimizations aren't perfect and the language won't always detect this.
The big downside is that we have to use atomic reference counts for _everything_. From memory this was about a 5-15% performance hit versus non-atomic counters, though the number might be higher if other bottlenecks were removed.
Nothing "real", just the synthetic benchmarks in the ./benchmarks dir.
Unnecessary copies are definitely a risk, and there's certain code patterns that are much harder for my interpreter to detect and remove. E.g. the nbodies has lots of modifications to dicts stored in arrays, and is also the only benchmark that loses to Python.
The other big performance limitation with my implementation is just the cost of atomic reference counting, and that's the main tradeoff versus deep cloning to pass between threads. There would definitely be room to improve this with better reference counting optimizations though.
In C, you can simply mutate the underlying characters. So changing the fifth character in a string is as easy as:
str[4] = 0;
str = str.substr(0, 4) + "\0" + str.substr(4);I've only read the first couple paragraphs so far but the idea reminds me of a shareware language I tinkered with years ago in my youth, though I never wrote anything of substance: Euphoria (though nowadays it looks like there's an OpenEuphoria). It had only two fundamental types. (1) The atom: a possibly floating point number, and (2) the sequence: a list of zero or more atoms and sequences. Strings in particular are just sequences of codepoint atoms.
It had a notion of "type"s which were functions that returned a boolean 1 only if given a valid value for the type being defined. I presume it used byte packing and copy-on-write or whatever for its speed boasts.
I've got a hobby language that combines this with compile time code execution to get static typing - or I should say that's the plan, it's really just a tokenizer and half of a parser at the moment - I should get back to it.
The cool side effect of this is that properly validating dynamic values at runtime is just as ergonomic as casting - you just call the type function on the value at runtime.
[1] https://github.com/FransFaase/IParse/?tab=readme-ov-file#mar...
Things of course become a lot more fun with concurrency.
Now if you want a language where all the data thingies are immutable values and effects are somewhat tamed but types aren't too fancy etc. try looking at Milner's classic Standard ML (late 1970s, effectively frozen in 1997). It has all you dream of and more.
In any case keep having fun and don't get too bogged in syntax.
But those go further in that they don't even have any mutable data. Instead of
var foo = { a: 1 };
var bar = foo; // make a copy of foo
set bar.a = 2; // modify bar (makes a copy)
foo = Baz { a = 1 }
bar = foo { a = 2 } // make a modified copy of foo- All functions are still referentially transparent, which means we get all the local reasoning benefits of pure functions. - We can mutate local variables inside loops (instead of just shadowing bindings), which makes certain things a lot easier to write (especially for beginners). - Mutating nested fields is super easy: `set foo.bar[0].baz = 1;` (compare this to the equivalent Haskell).
In practice I have found that it's very painful to thread state through your program. I ended up offering global variables, which provide something similar to but worse than generalized reference semantics. My language aims for simplicity so I think this may still be a good tradeoff, but it's tricky to imagine this working well in a larger user codebase.
I like that having only value semantics allows us, internally, to use reference counted immutable objects to cut down on copying; we both pass-by-reference internally and present it as pass-by-value to the programmer. No cycle detection needed because it's not possible to construct cycles. I use an immutable data structures library[2] so that modifications are reasonably efficient. I recommend trying that in Herd; it's almost always better than copy-on-write. Think about the Big-O of modifying a single element in an array, or building up a list by repeatedly appending to it. With pure COW it's hard to have a large array at all--it takes too long to do anything with it!
For the programmer, missing reference semantics can be a negative. Sometimes people want circular linked lists, or to implement custom data structures. It's tough to build new data structures in a language without reference semantics. For the most part, the programmer has to simulate them with arrays. This works for APL because it's an array language, but my BASIC has less of an excuse.
I was able to avoid nearly all reference counting overhead by being single threaded only. My reference counts aren't atomic so I don't pay anything but the inc/dec. For a simple language like TMBASIC this was sensible, but in a language with multithreading that has to pay for atomic refcounts, it's a tough performance pill to swallow. You may want to consider a tracing GC for Herd.
for x in arr (something ())
\ /-- function call
for x in arr (something ())
\ /-- loop body
A more fitting example would be to support:
for x in arr do set z += x;
for x in arr do something x;
Just modify the value inside the function and return it, then assign back. This is what the |= syntax is designed for. It's a bit more verbose than passing mutable references to functions but it's actually functionally equivalent.
Herd has some optimisations so that in many cases this won't even require any copies.
> What about concurrent mutable containers?
I've considered adding these, but right now they don't exist in Herd.
x = [1, [2]];
var y = x;
set y.[0] = 3; // clones the outer array, keeps a reference to inner array
set y.[1].[0] = 4; // clones the inner array here. Outer array is now exclusive so it doesn't need another clone.
var z = x;
set z.[1].[0] = 4; // clones both arrays at onceHowever, for Erlang and Elixir ‘pass-by-value’ is otherwise called ‘call-by-value’. In this case, it is a statement that arguments to functions are evaluated before they are passed into the function (often at the call site). This is in opposition to ‘call-by-name/need’ (yes, I know they aren’t the same) which is, for instance, how Haskell does it for sure, and I think Python is actually ‘by-name’ as well.
So, Herd’s usage here is a statement of semantic defaults (and the benefits/drawbacks that follow from those defaults) for arguments to functions, and Elixir’s usage is about the evaluation order of arguments to functions, they really aren’t talking about the same thing.
Interestingly, this is also a pair of separate things, which are both separate from what another commenter was pedantically pointing out elsewhere in the thread. Programming language discussion really does seem to have a mess of terminology to deal with.
Although I don’t particularly like the ‘|’ to be used for chaining functions, I certainly know that it has been a long term syntax coming from Unix. My only issue with the ‘|=‘ is that it should be unnecessary. The only reason I can see that the special operator is required is that the ‘set’/‘=‘ syntax pair is a non-functional keyword ‘set’ with an (I think) overloaded keyword ‘=‘. If the equal sign was an ordinary function (i.e. a function that take a value, and an identifier, associates the value and the identifier, then returns the new value like the Lisps and derived lands) it could just be used arbitrarily in chains of functions.
- We can avoid quite a few allocations in loops by mutating lists/dicts in place if we hold an exclusive reference (and after the first mutation, we always will). Updates to persistent data structures are relatively cheap, but they're a lot more expensive than an in-place update.
- Herd has syntax sugar for directly modifying nested values inside lists/dicts. E.g. `set foo.bar.[0].baz = 1;`.
In practice, is this faster than a different implementation of the same semantics using persistent data structures and a tracing GC? That will depend on your program.
So basucally everything is var?
There are two ways to define a variable binding:
x = 1; // declares x as immutable
var y = 2; // declares y as mutable
You can apply meaning to a particular shape of that tree which could be executed, but then you basically just added another layer before you parse your AST that becomes executable.
> Standard ML [...] It has all you dream of and more
The main thing here that's missing in Standard ML (and most other functional languages) is the "mutable" part of "mutable value semantics" - i.e., the ability to modify variables in-place (even nested parts of complex structures) without affecting copies. This is different from "shadowing" a binding with a different value, since it works in loops etc.
SML has mutation, but only for Ref Cells, which humorously are values themselves. Not that’s what you’re really talking about here.
Now for the wordy part…
As another of your sibling commenters said GP was being incredibly pedantic. While his reference to Plotkin/Winskel and the PCF thread of research is formative, it is of particular note for Structural Operational Semantics.
The real issue GP is raising that in programming language semantics there are two distinct ways in which the term ‘value’ is used. Worse still is that the terms are not just distinct but are broadly from two very distinct fields in PLT. So, what are the two uses:
1) when the domain of discourse is Operational Semantics of Programming Languages, a ‘value’ is a term in the formal abstract syntax of the language which is not subject to reduction via any other transition defined over the syntax;
2) when the domain of discourse is the Evaluation and Default Kinds of arguments passed to functions and the semantic implications of those defaults, a ‘value’ is defined in the negative as those semantic objects which ARE NOT references [1];
While GP’s usage of ‘value’ is in line with a long standing tradition, that tradition is firmly within the academic/functional programming language syntax and semantics sphere. Your usage, as is PLAINLY APPARENT from context, is absolutely correct and in line with long standing usage within discussion (and academic work) on imperative (and otherwise non-functional) programming language semantics. So keep phrasing discussions about Herd using the ‘pass-by-value’ and ‘everything is a value’. It’s not only contextually correct and historically justified, it is utterly within the ‘vernacular’ of normal programming language discussions.
One last thought, your language’s adoption of totally defaulting to passing arguments (to functions, threads, basically any control construct), with copy-on-write being an optimization only, should make implementing a non-reified linearity qualifier on types relatively simple to implement, that would address some of the locking anti-optimizations and address some of your static analysis that you mentioned where not working 100%.
———————
1: Reference here include Rust/C++ style lightly abstracted references, nearly zero abstraction pointers, and then the references as discussed when talking about Python, Ruby, JavaScript, C++ smart pointers, Rust’s higher level abstractions over references, etc which are a very abstract concept of reference.
This is why the syntax "encourages" immutability by making it the easiest option (similar to e.g. Rust, F#). On the other hand, if it was an extra keyword nobody would use it (e.g. like Java).
Also, copy by value in itself is just a semantic requirement, it doesn't say how it's implemented.
And shared mutable memory is pretty damn slow (given you are not fine with data race garbage), because atomic operations destroy caches. So it's the usual space-time tradeoff at the end of the day.
(Ah, no, your example elsewhere in the thread suggests that the referred-to structures get implicitly copied all over the place.)
Optimization specifically for function calls, or... ?
Because if you're doing all this copy-on-write anyway, the indirection seems to be a needless cost in other contexts.
I intentionally didn't add this, mostly because I wanted to explore how far you can get without it (and keep the language simple). Having a "real" pointer as a first class type wouldn't work though, since it would break a lot of the assumptions I use for optimizations.
I did think about two different versions of this but didn't end up adding either:
- Something like `inout` parameters in Swift, which aren't first class pointers. This is really just an alternate syntax for returning multiple values. - A "ref" type, which is essentially a mutable container for an arbitrary value. Passing the container around would share a reference to the same mutable value. This still wouldn't allow modifying values "outside" of the container though.
> needless cost
Are you comparing to a language with mutable references or a our functional language? A language with mutable references will of course be faster, but this is more intended as an alternative to pure functional languages (since functions are referentially transparent).
In this case, the cost of the indirection is approximately zero (relative to the cost of just doing reference counting), since passing a reference just requires a bump to the refcount. And most of the time the refcount increments are skipped by "moving" instead of copying the reference.
But I think at this point I'd have to read and analyze the code to have a proper understanding.
... Although granting that you already have paid the cost of reference-counting GC (and, I assume, per-object allocation), it probably is indeed insignificant. And special-casing where the reference count == 1 is also kinda neat. (E.g. CPython doesn't "move references" per se if I'm thinking clearly; but it does detect cases where it can safely mutate the underlying implementation of a type that's "immutable" from the perspective of language syntax.)