Have you ever thought of using a version of binary lambda calculus as your spec? I see you mentioned it as a joke ISA, but not as the possibly simplest backend
I was wondering the same thing, it was a let down to realize later that the article took a hard turn away from some kind of future-proofing for a time when RAM might not be as ubiquitous, and chose something that is likely to be ridiculed in the years to come.
Sorry to disappoint; you're right, this architecture is not highly optimized for RAM usage! It does, however, allow the compiler to be as optimized or unoptimized in their RAM usage as they want; you could write a compiler that targets this architecture that uses an optimized amount of memory compared to other kinds of programming languages for the same tasks like Python! Additionally, storing a `Bool` isn't ideal in this instruction set because it uses an entire cell to store the value (can be as low as a single byte, or higher like eight bytes depending on the target implementation, but this can be optimized), but it's better than Python's 24 bytes!
It's a good problem space to explore, so I hope that you keep on pushing this research further :) I have a few things that might give you some ideas if you're interested in this sort of Chifir-aligned thinking.
I take it that you've already considered other register OISCs like subleq, of course, but you might not have considered Fractran. It's a OISC register machine with mul as its only operation, worth a look if you're rooting for register/tape machines.
Looking the other way, toward SKI/BLC, you might enjoy Iota/Jot as a ultra-minimal reduction system. Implementing such a system is even faster than doing something like bfs.
My opinion is that all these sequential machines are going to fall out of favor for highly parallelizable systems in the near future. For a future system of a size comparable to brainfuck. I'd look at interaction nets, with only 6 reduction rules, interaction nets are a likely candidate, or are at least worth a look. It's just a stack of interaction between nodes that can be reduced in any order to achieve computation.
Moving beyond, it's likely that cellular automata systems will prevail over everything else that I've mentioned above. Something like a 4-state(a-la wireworld, qu-ant), is easily communicable with pictograms, highly parallelizable, and in some cases reversible.
On communicating ideas in the far future, the movie Into Eternity, talks about how to communicate a danger to the people who would stumble on a nuclear deposit. There is a segment about language that might be interesting to you.
I have written a few functional programming languages built on lambda calculus based backends, but I've had problems with compiling it efficiently; it's hard (at least to me)! I find that combinator based compilers are difficult, but very elegant; I've written a few in the past but problems always spring up when trying to evaluate expressions properly AND do side-effects correctly. I would love to pursue writing a combinator compiler, but I haven't yet come up with a good system of combinators that can represent I/O and foreign functions properly; although this probably isn't even as difficult as writing a compiler to a Turing-tape architecture.
[0] and [1] seem pretty promising to me, although I believe that the problem come from the fact that these languages do not expose a way to describe a sequence of bits, which may make them not lambda calculus anymore, but probably much more usable (you could then implement a soft version of integer/float operations and a compiler that convert this code into a single instruction, easier as there is no side effect guarantee)
> but I haven't yet come up with a good system of combinators that can represent I/O and foreign functions properly
I do not believe that you should support either.
I/O could simply be the program arguments & the final reduction of the expression. The input being your mouse position and the output being a window shouldn't be the responsibility of your program.
Foreign functions are IMO a bad idea, especially if the goal is for the program to outlive you, you lose the guarantee if these functions depend on the environment. Why couldn't you copy/paste the code into your own project?
Reify side effects in some fashion and then run the combinator graph reduction at compile time, as far as reasonable to do so. Partial evaluation works really well.
Basically combinators for the pure parts and functions that get optimised much less enthusiastically for IO or FFI.