There’s actually much smaller turing-complete languages, see https://en.wikipedia.org/wiki/Iota_and_Jot. In Jot, any bit sequence is a valid “program”, so any natural number can be turned into one.
I like some of the properties of Iota and Jot; I actually have a half-finished rewrite of one of my BitBitJump projects that uses Zot instead (it’s been that way for about 5 years now!).
My main problem is I haven’t been able to grok, intuitively, what those combinators do/are; my gut still seems to find SK “simpler”, despite having 2 combinators. Maybe I just need to play around with them some more?
A few years ago I came across a 3 instruction Forth. It’s not turing-complete, as it consists of “peek”, “poke” and “exec”, but it seems to be mainly used to load code into a minimal system to run.
FWIW, after playing a little with brainfuck, I decided it was not even a language. It’s a machine.
The problem is that it doesn’t have any features that compose, which I consider critical to be a language (human language shares this feature). Every nontrivial brainfuck program I’ve seen GENERATES it, e.g. using the C preprocessor or some other program. It just doesn’t have enough features to write by hand.
e.g. http://www.clifford.at/bfcpu/bfcomp.html is a compiler that generates some of the popular programs like Towers of Hanoi. There are many programs floating around, but they don’t always attribute their source. In general, they’re not written by hand!
Interesting examples! I don’t understand them yet but it looks like there is some composed structure.
To me assembly language is a “language” because jumps and labels essentially compose as primitive procedures / functions. I don’t understand how to do the same thing in brainfuck, but these examples look like they have some clues.
It might be fun to write an LLVM backend for BF… unless someone has already done that? I wouldn’t be too surprised - I would be happy, but not surprised.
Ahhh I see. I don’t think that would be possible because bf doesn’t actually support all the things you would need to make it an llvm target. I did see somewhere a compiler to bf from a subset from c, though; lost the link, but that was cool.
I’m pretty sure brainfuck could be an LLVM target? If JavaScript can be an LLVM target (Emscripten), then why not brainfuck? The output will be impossibly long and convoluted, and it might have a huge runtime, e.g. for floating point numbers, but I think it’s possible.
As long as its Turing complete I think you can emulate everything, with enough effort. Of course there are no syscalls and so forth, but JavaScript doesn’t have those either.
I get what you’re saying, but I think such “generate-only” languages are still useful; e.g. as machine code for very simple processors, or as an interesting domain for search algorithms. BitBitJump has a similar feel, and I’ve used it for the latter.
There’s actually much smaller turing-complete languages, see https://en.wikipedia.org/wiki/Iota_and_Jot. In Jot, any bit sequence is a valid “program”, so any natural number can be turned into one.
I like some of the properties of Iota and Jot; I actually have a half-finished rewrite of one of my BitBitJump projects that uses Zot instead (it’s been that way for about 5 years now!).
My main problem is I haven’t been able to grok, intuitively, what those combinators do/are; my gut still seems to find SK “simpler”, despite having 2 combinators. Maybe I just need to play around with them some more?
A few years ago I came across a 3 instruction Forth. It’s not turing-complete, as it consists of “peek”, “poke” and “exec”, but it seems to be mainly used to load code into a minimal system to run.
FWIW, after playing a little with brainfuck, I decided it was not even a language. It’s a machine.
The problem is that it doesn’t have any features that compose, which I consider critical to be a language (human language shares this feature). Every nontrivial brainfuck program I’ve seen GENERATES it, e.g. using the C preprocessor or some other program. It just doesn’t have enough features to write by hand.
e.g. http://www.clifford.at/bfcpu/bfcomp.html is a compiler that generates some of the popular programs like Towers of Hanoi. There are many programs floating around, but they don’t always attribute their source. In general, they’re not written by hand!
FWIW, while the big programs are generated, there are some cool stuff written by hand. As far as I know, everything at http://www.hevanet.com/cristofd/brainfuck/ was manually written, and there are also programs like https://codereview.stackexchange.com/questions/194538/json-formatter-in-your-least-favorite-language and https://codereview.stackexchange.com/questions/57382/fizzbuzz-in-brainfuck, which are actually kind of readable with the comments.
Interesting examples! I don’t understand them yet but it looks like there is some composed structure.
To me assembly language is a “language” because jumps and labels essentially compose as primitive procedures / functions. I don’t understand how to do the same thing in brainfuck, but these examples look like they have some clues.
It might be fun to write an LLVM backend for BF… unless someone has already done that? I wouldn’t be too surprised - I would be happy, but not surprised.
See https://github.com/Wilfred/bfc, which seems to have some bf-specific optimizations as well.
This is a front-end that compiles BF to LLVM IR and then to an executable
I believe the parent comment is seeking something where you can use
clangor similar, and emit brainfuck as the result.Ahhh I see. I don’t think that would be possible because bf doesn’t actually support all the things you would need to make it an llvm target. I did see somewhere a compiler to bf from a subset from c, though; lost the link, but that was cool.
I’m pretty sure brainfuck could be an LLVM target? If JavaScript can be an LLVM target (Emscripten), then why not brainfuck? The output will be impossibly long and convoluted, and it might have a huge runtime, e.g. for floating point numbers, but I think it’s possible.
As long as its Turing complete I think you can emulate everything, with enough effort. Of course there are no syscalls and so forth, but JavaScript doesn’t have those either.
Javascript doesn’t have syscalls, but it still has object storage, so it’s reasonable to implement files and such on it.
Yes, exactly. I’m sure it would be a practically insurmountable challenge for a single developer, but where’s the fun otherwise? ;)
This should get you started: https://eli.thegreenplace.net/2017/adventures-in-jit-compilation-part-1-an-interpreter/
I get what you’re saying, but I think such “generate-only” languages are still useful; e.g. as machine code for very simple processors, or as an interesting domain for search algorithms. BitBitJump has a similar feel, and I’ve used it for the latter.
You might count things like G machine that Haskell compiled to. Maybe still does.