Show HN: A small programming language where everything is pass-by-value

[jcparkyn]

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)

[augusteo]

The threading story here is what grabbed my attention. Pass-by-value with copy-on-write means you get data-race immunity without any locks or channels. You just pass data to a thread and mutations stay local. That's a genuinely useful property.

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?

[sheepscreek]

Hmm this is a bit like peeling a banana only to throw the banana and eat the peel. Pass by value reduces the true benefit of copy-on-write.

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.

[jcparkyn]

> Have you benchmarked any real workloads?

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.

[MetricExpansion]

Swift actually does this copy-on-mutation strategy as well for its standard library’s container types like Array and Dictionary, and it does indeed make multithreaded programming much easier without requiring full copies. The downside is that you pay reference-counting overhead.

[rao-v]

Why don’t we just do this by default for threading in most languages? It’s pretty rare for me to actually want to do memory sharing while threading (mostly because of the complexity)

[zahlman]

Why exactly is imperative syntax "convenient" specifically in the context of inter-thread communication?

[jagged-chisel]

Pass-by-value is already a copy.

[ekipan]

(Edit: in the old post title:) "everything is a value" is not very informative. That's true of most languages nowadays. Maybe "exclusively call-by-value" or "without reference types."

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.

https://openeuphoria.org/ - https://rapideuphoria.com/

[p1necone]

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

[jcparkyn]

Thanks, I updated the post title based on this and another comment. Thanks for the pointer to Euphoria too, looks like an interesting language with a lot of similar ideas.

[fjfaase]

I have implemented similar behavior in some of my projects. For one, I also have also implemented 'cursors' that point to some part of a value bound to a variable and allow you to change that part of the value of the variable. I have used this to implement program transformations on abstract parse (syntax) trees [1]. I also have implemented a dictionary based on a tree where only part of the tree is modified that needs to be modified [2]. I have also started working on a language that is based on this, but also attempts to add references with defined behavior [3].

[1] https://github.com/FransFaase/IParse/?tab=readme-ov-file#mar...

[2] https://www.iwriteiam.nl/D1801.html#7

[3] https://github.com/FransFaase/DataLang

[discarded1023]

At the risk of telling you what you already know and/or did not mean to say: not everything can be a value. If everything is a value then no computation (reduction) is possible. Why? Because computation stops at values. This is traditional programming language/lambda calculus nomenclature and dogma. See Plotkin's classic work on PCF (~ 1975) for instance; Winskel's semantics text (~ 1990) is more approachable.

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.

[bayesnet]

IMHO this is both unnecessarily pedantic and not really quite right. Let’s say we accept the premise that “everything is a value” means reduction is impossible. But a value is just the result of reducing a term until it is irreducible (a normal form). So if there is no reduction there can’t really be values either—there is just “prose” (syntax) and you might as well read a book.

[doug-moen]

I am unable to extract any meaning from your post. You appear to be making a general claim: it is impossible to design a programming language where everything is a value. You at least admit that "data thingies" can be values. Are you claiming that it is not possible for functions to be values? (If we assume that the argument and the result of a function call is a value, then this would mean higher order functions are impossible, for example.) If not that, then what? Please give a specific example of something that can never be a value in any programming language that I care to design.

[jcparkyn]

Thanks, some interesting reading there that I will check out (I wasn't aware of PCF). Perhaps I should've used more precise wording: "All types are value types".

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

[DemocracyFTW2]

Excuse me if I didn't get it right, but as a practical example, I'd assume that I can rewrite every program into JavaScript using the usual control structures and, beyond that, nothing but string values (which are immutable). Simple arithmetic would already be kind of a chore but can be done. (Input and output already happens only via serialized values (cf also webworkers) so there's that; for convenience use TypedArrays wrapped in classes that shield you from immutability). It is not obvious to me where `a = '[1,2]'; a1 = JSON.stringify( JSON.parse( a ).push( 3 ) ) );` is fundamentally different from just pushing a value to a copy of `a`. Also, you could write `a1 = a.slice(0,-1) + '3]'` which only uses non-mutating stuff under the hood.

[netbioserror]

Nim has a similar, strong preference for value semantics. However, its dynamic heap types (strings, seqs, tables) are all implemented as wrappers that hide the internal references and behave with value semantics by default, unless explicitly escape hatched. It makes it incredibly easy to manipulate almost any data in a functional, expression-oriented manner, while preserving the speed and efficiency of being backed by a doubling array-list.

[vrighter]

that is exactly what this one is doing too, according to OP

[tromp]

This sounds quite similar to pure functional languages like Haskell, where a function call cannot have any side effect.

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)

Haskell has

    foo = Baz { a = 1 }
    bar = foo { a = 2 } // make a modified copy of foo

[jcparkyn]

Personally I think local mutability is quite a useful property, which was part of the inspiration for making this instead of just another pure functional language:

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

[electroly]

My hobby language[1] also has no reference semantics, very similar to Herd. I think this is a really interesting point in the design space. A lot of complexity goes away when it's only values, and there are real languages like classic APL that work this way. But there are some serious downsides.

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.

[1] https://tmbasic.com

[2] https://github.com/arximboldi/immer

[tylerhou]

You should check out Perceus! https://www.microsoft.com/en-us/research/wp-content/uploads/...

[jasperry]

Syntax comment: in your control structures you use a keyword ("do", "then") to start a block as well as wrapping the block in parentheses. This feels superfluous. I suggest sticking with either keywords or parens to delineate blocks, not both.

[jcparkyn]

This is a little bit tricky because the parser has to distinguish between:

  for x in arr (something ())
           \                 /-- function call

and

  for x in arr (something ())
               \            /-- loop body

This is consequence of combining "blocks" and "precedence" into the same construct ().

A more fitting example would be to support:

  for x in arr do set z += x;
  for x in arr do something x;

IIRC these both currently require an explicit block in my parser.

[Panzerschrek]

But what if mutation is intended? How to pass a mutable reference into a function, so that it can change the underlying value and the caller can observe these changes? What about concurrent mutable containers?

[jcparkyn]

> How to pass a mutable reference into a function, so that it can change the underlying value and the caller can observe these changes?

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.

[jbritton]

The article mentions shallow copy, but does this create a persistent immutable data structure? Does it modify all nodes up the tree to the root?

[jcparkyn]

Yes, if you modify a nested dict/list entry, all nodes above it will be cloned. Here's an example:

  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 once

[travisgriggs]

Curious if erlang/elixir isn’t the same sort of thing? Or am I misunderstanding the semantics of “pass by value”?

[throwaway17_17]

Your assumption is somewhat correct, for both Erlang and Elixir, however the phrase under discussion doesn’t mean the same thing for immutable languages. Both are ‘pass-by-value’ but that term is being overloaded in a particular way. As I said in another comment, ‘value’ in the language from TFA means any object that IS NOT a reference. The qualifier that every semantic object is a ‘value’ and that therefore, all arguments to a function call, threads spawn, etc are independent values which are (logically, at least) copied to new values that are then passed to the new context.

However, 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.

[zem]

the pipe-equal operator is pretty neat, don't think I've seen any other language do that.

[throwaway17_17]

I wrote the following and then realized maybe it is just a quirk of the example in the reader that the ‘set’/‘=‘ pair comes at the end of the chain. If so, it is just a unique syntax sugar for a function, I don’t think it is, so I’m leaving my comment as I wrote it letting this act as a caveat:

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.

[anacrolix]

Nobody has heard of persistent data structures?!

[jcparkyn]

This is similar but not quite the same as persistent data structures. In particular:

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

[rvba]

> In herd, everything is immutable unless declared with var

So basucally everything is var?

[jcparkyn]

I'm not sure if I understand the question?

There are two ways to define a variable binding:

    x = 1; // declares x as immutable
    var y = 2; // declares y as mutable

The "default" behaviour (if no keyword is used) is to define a new immutable variable.

[drnick1]

Small programming language with everything passed by value? You reinvented C?

[jcparkyn]

Not everything in C is pass-by-value. Sure, you can argue that a pointer itself is passed by value, but the data it points to is definitely not.