Comment by derefr

> Actually, most of the Beam instructions are non-O(1).

I said O(1) in BEAM reductions per basic-block, not O(1) in underlying CPU instructions. This is why reductions, rather than pure "instructions executed", are counted: it allows each op (or BIF/NIF call) to account for how expensive executing it was.

> The solution is that these instructions are written so that they do work on chunks of data (e.g. ++ may process 1000 elements of a list in a chunk) after which they increment the reduction counter and possibly schedule out the process.

I was eliding reference to these for simplicity. The precise semantics are that "simple ops" are required to be O(1) reduction-bounded; while BIFs/NIFs (incl. things like `erlang:++/2`) aren't, but then must necessarily be implemented with their own internal yield points; and the instructions which invoke them will also potentially yield before/after the invocation. Essentially, within the Erlang abstract-machine model, BIF/NIF invocations act as optimized remote function calls that might have associated "bytecode intrinsics" for invoking them, rather than as regular ISA instructions per se.

> The Beam ISA allows looping.

Yes, but BEAM programs that use such code shouldn't be considered valid.

The BEAM loader doesn't do load-time checks like that, but that's because the BEAM loader is on the inside of an assumed trust zone created by the Erlang compiler. (I.e. BEAM bytecode is implicitly assumed by the loader to be pre-validated at compile time. This is the reason every attempt at untrusted mobile code execution in Erlang has failed—to use Raymond Chen's phrasing, load-time is already "on the other side of the airtight hatchway." If you wanted to allow people to execute untrusted code, you'd need to move the hatchway!)

Tangent: this is an annoying aspect of calling the Erlang emulator the "Erlang Abstract Machine" — it's not. An abstract machine is a model of runtime semantics, formed by a compiler/interpreter, VM, runtime libraries, and even standard library, all working together to run code under that model.

(Compare and contrast: the C abstract machine. It is a model of runtime semantics that exists as only 1. compile-time enforcement by C compilers, and 2. libc. It has no VM component at all.)

This part might be "just my opinion, man" but: given that BEAM was designed purely for the execution of Erlang; and given that BEAM is written to assume that you used an Erlang compiler to compile the bytecode it's running (thus the trust-zone); then any feature of BEAM bytecode that goes unused by Erlang codegen, should be considered undefined behavior for the purposes of the Erlang abstract machine. Whether the BEAM VM allows the bytecode or not, the Erlang abstract machine doesn't.

In other words, yes, you can create back-references in a BEAM bytecode file. You can also load and call into a NIF that doesn't bother to do reduction accounting. In both cases, you're breaking the runtime semantics of the Erlang abstract machine by doing so, and thereby discarding the properties (e.g. soft-realtime max-bounded-latency scheduling) that you get when you stay within those runtime semantics.

(And I would argue that, if we did move the trust zone to allow for untrusted mobile code execution, such that we were doing static analysis at load time, then the bytecode loader would almost certainly toss out programs that contain back-references. They're semantically invalid for the abstract-machine model it's trying to enact.)

> Actors are free to kill not because they would run their code in uninterrupted atomic blocks, but because they don't share state (their heap) with each other.

Untrue. Many things in ERTS manipulate global emulator (or more precariously, per-scheduler) state in careful ways: fused port packet generation + enqueue done inside the calling process; ETS updates for tables with write concurrency enabled; module-unload-time constant propagation; etc.

You're even free to manipulate arbitrary shared state yourself, inside a NIF! It's not breaking Erlang abstract-machine semantics as long as that state 1. isn't ERTS state, and 2. the results aren't visible inside the abstract-machine model. Thus NIF memory handles being visible in Erlang as zero-width reference binaries — that's only necessary because NIFs are assumed to be manipulating shared mutable buffers, and so Erlang actually being able to see into those buffers would cause undefined behavior!)

BEAM can't assume that any process isn't currently executing inside a NIF that's doing precarious must-be-atomic things to shared out-of-ERTS resources. (I realize that this wasn't a part of the initial design of Erlang — NIFs didn't always exist — but it wasn't in conflict with the design, either, and after much iteration, is now fundamental to it.)

But this manipulation of global state doesn't break the runtime guarantees of Erlang's abstract machine model, so long as these operations are never pre-empted. And so the BEAM doesn't.

I also didn't mention the other, maybe more interesting things that this constraint gets you: hot-code upgrade, process hibernation, and dynamic tracing. To work, these three features all require that a process's current heap state have a clean bijection to a continuation (i.e. a remote function call MFA tuple.) This is only true at yield points; between these, the heap state's meaning is undefined to the Erlang abstract machine, and has meaning only to BEAM itself. It's only the guarantee of O(1)-in-reductions distance between yield points — and never having to yield between these points — that makes all these features practical.

("Erlang with pre-emptible actors" would basically have to use OS threads for each actor, because anything it did instead would be just as heavy in terms of context-switching costs. No green-threading architecture allows the schedulers to pre-empt the green threads they're running, for exactly this reason.)

> After that you'd have to switch to a green thread model with schedulers, which is a lot of work to implement.

My whole point is: how do you cleanly de-schedule arbitrary JVM bytecode that's doing something compute-bounded without explicit yield points? You can't, without replacing both the ISA and the compiler with ones that enforce Erlang-abstract-machine-alike semantics, as described above. And any attempt to do that would mean that this hypothetical forked JVM would now be unable to load original-JVM bytecode — and that you'd have to code in a version of Java that only supports tail calls — which makes it useless as a JVM. It'd just be an Erlang emulator.