idea: brainfuck target

[folkertvanheusden]

brainfuck is a minimalistic programming language. Tons of interpreters, compilers and transpilers have been implemented for it.

[omarandlorraine]

That's a great idea, I like it!

The easiest way to get this in is to wait until after #33 has been merged.

[omarandlorraine]

Now that #33 has been merged, do you fancy taking a stab at implementing a brainfuck backend?

[omarandlorraine]

I probably want to get this into the v1.2 release sometime before Christmas.

[folkertvanheusden]

(didn't I already reply to this?)

I thought about at it but found it a bit problematic. It either has 32000 registers or none, depending on how you look at it. And assignments, well, no idea how to do that.

[omarandlorraine]

Brainfuck has assignments?

[folkertvanheusden]

No, that's the point.

…

On Fri, Sep 16, 2022 at 7:57 AM omarandlorraine ***@***.***> wrote: Brainfuck has assignments? — Reply to this email directly, view it on GitHub <#34 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AUN5IW6GJUANNE5GKAGHNEDV6QD4LANCNFSM56TDYTAA> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[omarandlorraine]

describing a virtual machine that runs brainfuck and how it could be added to strop

So currently we've got a type for each of the machines we have, and a type for each of the instruction sets we have.

Mos6502 is a struct containing the internal registers of a 6502 for example. Instruction6502 contains handlers, instruction mnemonics and whatever else. So we'd need to add something like Brainfuck and BrainfuckInstruction.

Now BrainfuckMachine would be a struct containing at least the memory and a pointer to the memory; this is the internal state of the machine.

BrainfuckInstruction needs to be some kind of Copy type which contains the handlers and whatever else, analogous to the Instruction6502 type.

It either has 32000 registers or none, depending on how you look at it.

In the same way as how the 6502 or something has 65536 bytes of memory. The 6502 backend has a HashMap<u16, Option<u8>> to deal with this. Another difference is brainfuck's memory is initialized to all zeroes, and uninitialized memory is not a thing. So I guess the brainfuck backend would have a HashMap<i32, u8> here. Then to read memory, instead of *self.heap.get(&addr).unwrap_or(&None) it would be something like *self.heap.get(&addr).unwrap_or(0).

And assignments, well, no idea how to do that.

Brainfuck has no assignments, only increment and decrement, exactly equivalent to the 6502's inc and dec commands.

So roughly, a brainfuck program can be more or less transcribed to 6502 in the following way:

• - goes to dec heap,x
• + goes to inc heap,x
• < goes to dex
• > goes to inx
• , goes to some kind of syscall maybe
• . goes to some kind of syscall maybe
• [ goes to lda heap,x; beq somewhere
• ] goes to lda heap,x; bne somewhere

I feel that the first four at least have obvious counterparts and are nearly just a case of copy pasting code from the 6502 backend.

, and . might need separate buffers or something in the BrainfuckMachine to keep track of the strings going in and out of the virtual machine

of these, I think that [ and ] are going to be the trickiest to implement. Until now, strop has only been generating branchless code, which is the BasicBlock<T> type. But branchless code in brainfuck is not as powerful as in normal languages so branching is much more important in brainfuck. So we might need to introduce a ProgramLoop<T> type as well for programs that run in loops or ExtendedBasicBlock<T> (see extended basic blocks for programs that have branching.

I thought about at it but found it a bit problematic.

I hope some of this helps, feel free to implement just what you can/want. If you like.

[folkertvanheusden]

Hi, I have been thinking about how to do so, but I can't get my head around it. Brainfuck has memory (or 32000 registers depending on how you look at it) but I can't think of a way to do an assignment from one register to another.

…

On Wed, Sep 7, 2022 at 10:15 AM omarandlorraine ***@***.***> wrote: Now that #33 <#33> has been merged, do you fancy taking a stab at implementing a brainfuck backend? — Reply to this email directly, view it on GitHub <#34 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AUN5IW4AYMUAZH75D5CMQIDV5BFJBANCNFSM56TDYTAA> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[omarandlorraine]

but I can't think of a way to do an assignment from one register to another.

It's not an issue because you tell strop which instructions the architecture does have. Strop figures the rest out.

Issue #42 is going to introduce another lot of big changes, among which are the fact I'm going to start using much more third party crates. It pulls in loads of external crates for generating instructions, emulating them, etc. etc. But the other big change is that the codebase will (hopefully!) be much easier to understand for newcomers.

I'm looking on crates.io for brainfuck emulators, and there are more than a few to choose from. Do you know which one to pick? In particular, we need one that will behave well for malformed programs like [ (mismatched bracket).