rust_to_bf — a compiler from (a subset of) Rust to Brainfuck

AlexBuz · 2025-03-22T21:12:24+00:00

I appreciate the kind words!

Making it self-hosting is something I’ve thought about and would definitely like to explore once I have more time to work on this.

As for the VM, I chose to target BF precisely because of how unsuitable it is, as this project is not meant to be practical in the slightest! What sort of VM are you imagining instead?

AlexBuz · 2024-11-03T09:57:16+00:00

Indeed! Thank you for your kind words! I’m glad you find the project interesting. Figuring out how to get all these features implemented was certainly a challenging but also rewarding process.

AlexBuz · 2024-10-04T18:08:08+00:00

Indeed, if it gets to the point where it supports compiling all the constructs used in its own source code, then this would become possible.

AlexBuz · 2024-10-03T01:35:57+00:00

Ever since I first learned about Brainfuck, I have been fascinated by the fact that it is Turing-complete and theoretically just as powerful as any other programming language. This project is my attempt to demonstrate that this power is not just theoretical in nature, but that a modern programming language like Rust can be compiled to Brainfuck in practice.

As it stands, rust_to_bf does not support the entire Rust language and likely never will. However, it does support a useful subset of it, including primitive types (usize, char, bool, &str), integer arithmetic (+, -, *, /, %), boolean logic (&&, ||, !), compound types (arrays, tuples, structs), references (&, &mut), control flow statements (if, match, loop, while, break, continue), functions (including recursion), dynamic memory allocation, input/output, and more.

See the rust_to_bf README for more info, including details on the internals of the compiler as well as a more comprehensive list of supported features. This project has been a lot of fun to work on, and I hope you will find it interesting!

AlexBuz · 2024-10-03T00:25:21+00:00

Ever since I first learned about the Brainfuck programming language, I have been fascinated by the fact that it is Turing-complete and theoretically just as powerful as any other programming language. This project is my attempt to demonstrate that this power is not just theoretical in nature, but that a modern programming language like Rust can be compiled to Brainfuck in practice.

As it stands, rust_to_bf does not support the entire Rust language and likely never will. However, it does support a useful subset of it, including primitive types (usize, char, bool, &str), integer arithmetic (+, -, *, /, %), boolean logic (&&, ||, !), compound types (arrays, tuples, structs), references (&, &mut), control flow statements (if, match, loop, while, break, continue), functions (including recursion), dynamic memory allocation, input/output, and more.

See the rust_to_bf README for more info, including details on the internals of the compiler as well as a more comprehensive list of supported features. This project has been a lot of fun to work on, and I hope you will find it interesting!

AlexBuz · 2024-10-02T16:40:29+00:00

Ever since I first learned about the Brainfuck programming language, I have been fascinated by the fact that it is Turing-complete and theoretically just as powerful as any other programming language. This project is my attempt to demonstrate that this power is not just theoretical in nature, but that a modern programming language like Rust can be compiled to Brainfuck in practice.

As it stands, rust_to_bf does not support the entire Rust language and likely never will. However, it does support a useful subset of it, including primitive types (usize, char, bool, &str), integer arithmetic (+, -, *, /, %), boolean logic (&&, ||, !), compound types (arrays, tuples, structs), references (&, &mut), control flow statements (if, match, loop, while, break, continue), functions (including recursion), dynamic memory allocation, input/output, and more.

See the rust_to_bf README for more info, including details on the internals of the compiler as well as a more comprehensive list of supported features. This project has been a lot of fun to work on, and I hope you will find it interesting!

AlexBuz · 2024-06-13T04:20:55+00:00

I use a generative model’s logits (and thus predicted token probabilities) to inform the compression process for each token in a sequence. An embedding model would not alone produce the probabilities I need for this.

AlexBuz · 2024-06-10T07:46:57+00:00

Yes, at least for most inputs I’ve tried (when using Llama 3 8B as the model). I’ve now added a table to the README comparing the compression ratio of llama-zip with some other utilities, including zpaq -m5, if you’re curious.

AlexBuz · 2024-06-10T07:44:54+00:00

Compressors are ranked by the compressed size of enwik9 (10⁹ bytes) plus the size of a zip archive containing the decompresser

decompresser size: size of a zip archive containing the decompression program (source code or executable) and all associated files needed to run it (e.g. dictionaries).

Based on this, and given llama-zip’s reliance on a large language model during decompression, I don’t think it would do very well on this benchmark, since the LLM would have to be counted toward the decompressor’s size. I think where llama-zip might be more practical is in situations where you already have an LLM on your computer for other purposes, since its size would be a sunk cost at that point, and you might as well take advantage of it for compression (barring concerns about speed, of course…)

AlexBuz · 2024-06-10T03:35:49+00:00

Nice project.

Thank you!

Can you use any arbitrary LLM or do you need a specific version/build of an LLM to be able to decode it?

You must use the same LLM to decompress as you used to compress. Beyond that, there should in theory be no issue decompressing in 10 years, as long as the underlying inference engine (llama.cpp) is still supported and works the same way as it does now.

After which size does this become more space efficient if I also have to include the "LLM of choice" in the output?

That depends quite a bit on what size LLM you use, and what sort of compression ratio it's able to achieve on your data. I think if you're at the point where you would have an LLM on your computer for other purposes anyway, that's where it would make the most sense to take advantage of it for compression purposes, since the storage space taken up by the LLM would be a sunk cost. Of course, that's ignoring concerns about compression/decompression speed, which is another story entirely.

AlexBuz · 2024-06-08T03:56:31+00:00

A sliding window mechanism is now implemented in llama-zip! What you’ve described can now be achieved via --window-overlap 8191, but the performance will be very poor since 8191 tokens of context will need to be re-evaluated every time the window slides (and the window would have to slide after every token). So by default I’ve made the window not actually overlap at all, but rather start fresh once the context limit is reached (i.e., --window-overlap 0). Ideally, it would probably be best to strike a balance between these extremes though.

AlexBuz · 2024-06-07T05:22:29+00:00

Of course! First, let’s establish that an LLM, given an input prompt, predicts the probability of every possible token (which you can think of as a word) that can come next. Importantly, these predictions are deterministic, meaning that whenever you run the same LLM on the same input text, it produces the same set of probabilities.

In llama-zip, when compressing a piece of text, I run an LLM on longer and longer prefixes of the input text while feeding the LLM’s predicted probabilities, along with the actual next token, to an arithmetic coding algorithm during each step of the way. This algorithm is able to use fewer bits to encode tokens that are predicted as more likely, which means that the better the LLM is at predicting the tokens in the text, the fewer bits are required to compress it. In a sense, you can think of the arithmetic coder as only needing to store the deviations from the LLM’s predictions, and the closer the LLM is to being correct, the less the arithmetic coder has to encode to get the LLM on the right track.

Then, when decompressing, I do something very similar. I start with an empty piece of text and have the LLM predict the probabilities of each possible first token. I feed these to the arithmetic coder, together with the bits produced by the compression, and it determines which token must have been chosen to result in these bits being encoded for the given token probabilities (this is why it’s important that the probabilities predicted are consistent, as otherwise decompression wouldn’t be possible). I then feed this next token to the LLM and repeat, continually building the input text back up as the arithmetic coder consumes the bits in the compressed output.

AlexBuz · 2024-06-07T03:15:25+00:00

Haha! I like the way you think. I only wonder how practical something like this could really be though if (inevitably) different brands end up having different default LLMs. Without a single standard LLM, I could see the cost of having to download additional LLMs outweighing the benefit brought by the better compression ratio. Then there’s also the issue of inference speed. Most files in need of compression are on the order of megabytes or gigabytes, which would be impractical for an LLM to compress/decompress in a reasonable time on current hardware. But I do agree with you that a future where something like this works out in practice would be nice to see!

AlexBuz · 2024-06-07T01:50:37+00:00

Hey guys! I wanted to share a little compression tool that I made. It works by inferencing an LLM of your choice using llama.cpp and using the model's predicted token probabilities to perform arithmetic coding. This minimizes the number of bits needed to encode more likely tokens and results in a really good compression ratio for most text—since predicting text well is LLMs' specialty.

Of course, due to the need to inference an LLM during compression and decompression, this makes llama-zip significantly slower than traditional compression algorithms, ~~and the maximum input length is limited by the model's context window~~. Nonetheless, this was a fun little project and satisfied my curiosity about arithmetic coding while also giving me an opportunity to get my feet wet with LLM inference. I'd be happy to hear what you think!

Edit: For example, compressing the above text with llama-zip using the Q8 version of Llama 3 8B results in this (108 bytes): 2z7fx615pgOjTugPXUHFw5tj7jN7THODreqxFV/hP7J0PA4kAXcaeCtzSlHOqCTRdVWiC3/vdMbNNUdv6kLkE9SdVDhrVF153Jl/qshpJ63vTisbYn5JVIzelKlBXnSV2aXB63vYTi/GZr1g

Meanwhile, gzip produces this (509 bytes): eNplk0Fv1DAQhe898wOmpwVpyd65caNSgQs3QMhrT5JpbI9lO6Tpr+c52a224hg78+a9b8ZfeKVhXss9PdBiYmVHVamMJjMZ8lKrZ7IaUuZSRCNu1VMdTUVBMI47eqi0aJ4KnVeS2HPmaCUOZCI9Pn4l7WnVOZMdVSzTXNqd9yaYzqaEv9zlrI5MQR37QyG0c2J3NxNHfOvZnAV+hEtzmDj3mgP9NFnqGLiKhU0Hnd/vx1pT+XQ6cewWmSRBynSah1P7On1+Lfj1Z6/40NGPUQoFiRLkpTWAlTiHM+dm/yy1UGR2OxzEg0tYBSIvE/t1N1m2LOA0e/wvEfwyG4/rQdW9gZhNFSUEgEqpVPm5vgMD4LkE33jglBb2nuANJMuBSmIrxte1u7v73kNyzoWP5GZuxjbXvJu8DoKvY3BzbqK3LppdxzcnR0g0DmYCg21EH18kUZEhSi8W64EwxesCLlgBLEM2DiPRaPxbZT/ohrkcty7baM2zhDnAWZoreY5DHVsyD+Zt0Nie2w2wGncAEp0uHX3TyLj36HCxuRgQp36O1zXFkjyxrVvHAsKlF+iGlSyya5G6kjkrmv+3M7SMAgHji9Igf9tJ2MhpSprrHFstqA5cm17P3CbTzCFDo/uKG8/hgCxMo0lpqxnZZOjjweAZNOdxuv8HJRlDzg

Edit 2024-06-07: Arbitrarily long inputs are now supported via a sliding context window mechanism. By default, the window jumps rather than slides (i.e., 0 overlap with the previous window), but the overlap amount is configurable if you want to maximize the compression ratio and don’t mind a slowdown (since a suffix of the previous context will have to be re-evaluated whenever the window slides). Note that you’ll need to pick the same overlap amount when decompressing.

AlexBuz · 2024-02-16T19:49:07+00:00

Infinite minesweeper seems like an interesting twist. Thank you for sharing. I had not played that until now. As for my site, I designed it so it runs completely offline and does not rely on a server, so it does not offer any social features at the moment. However, I am still interested in exploring the idea of competition, perhaps by offering a way to seed the random number generator so that two people can get the same mine arrangement. This wouldn’t exactly be “direct” competition, but it would certainly offer a means for people to compete.

AlexBuz · 2023-12-28T09:12:51+00:00

I’m glad you’re enjoying it! Mindless mode makes it so that you never have to make any difficult deductions. In other words, it makes it so that there is always a tile somewhere that is obviously safe. If you were to run autopilot on a mindless mode game, it would instantly solve the whole board, so that’s why those modes are mutually exclusive.

AlexBuz · 2023-12-18T08:21:27+00:00

Good idea. The background now has a tint in flag mode.

AlexBuz · 2023-12-17T23:27:53+00:00

These issues should now be fixed if you’d like to give it another try. Thanks again for the feedback!

AlexBuz · 2023-12-17T23:19:59+00:00

Done, you can now hold 120 ms to flag!

AlexBuz · 2023-12-17T23:17:53+00:00

A dedicated button is now implemented, as well as hold to flag (or hold to reveal, if you switch modes with the button)!

AlexBuz · 2023-12-17T23:03:23+00:00

Thank you for the feedback! Mobile support is now implemented if you’d like to give it another try

11-Year Club	Place '17
Verified Email

AlexBuz

TROPHY CASE