search

baris-inandi / bfgo

A fast, optimizing, BF compiler, interpreter, and REPL. Also includes a BF formatter and minifier! Implemented in Go. Batteries included.
GNU General Public License v3.0
9 stars 1 forks source link

Better minifier #2

Closed Rudxain closed 2 years ago

Rudxain commented 2 years ago

I want to open a PR to improve the minifier, but I'll need to learn more Golang (my main langs are Rust and JS). I suggest the following optimizations:

  1. ~Return an empty string if the input doesn't contain . .~ No, this is unsafe! Infinite loops aren't "output", but still count as "behavior". Link to commit that removed the bug. Instead, remove all ops after last ., only if . isn't followed by ] or , anywhere.
  2. Remove chunks of 256 consecutive + or - (because of mod 256 wrap-around)
  3. Remove mutual-cancel opcodes (+ or - followed by its opposite, same for < and >)
  4. Replace excessive + or - if an equivalent sequence of opposite op does the same thing (replace 129 (or more) by a smaller sequence, exploiting mod 256). For example, if we add 255 times (+ * 0xff), it does the same as subtract once (-).
  5. Replace odd-count cell-reset loops by [-] and even-count by [--] (this exploits mod 2^n arithmetic)
  6. Remove useless arithmetic if reset is found: +++[-] -> [-]
  7. Zero-loop removal. If there are loops before the 1st cell-mutation happens, then all can be removed.
  8. Loop followed by loop: Example [.-.]...[foobar] can be turned into [.-.].... The 1st loop can contain arbitrary code, iff the opcodes between both loops are dots (or no-op). This can be extended indefinitely [foo][foo][foo][foo][foo] -> [foo]
  9. Increase compression ratio by replacing [-] by [+] and vice-versa (frequency analysis for "compressor-friendly" output)
  10. Use a multiplicative algorithm to reduce + and -. This is very hard to implement (halting problem), so I won't do it. It's hard because it requires knowing the exact value of adjacent cells, to safely use them as temporary registers. Example >++++++++++++< -> +++[->++++<] (add 12 to M1 while M0 is 0). If done wrong, it can increase the size of output, >++< -> ++[->+<], so it's another reason to avoid that risk.
Rudxain commented 2 years ago

Wait I have an idea. I can write the full algorithm in TypeScript, then you manually transpile it to Go. What do you think?

baris-inandi commented 2 years ago

Thank you for your comments, I'm kinda busy right now, will definitely look into this tomorrow.

baris-inandi commented 2 years ago

Hey @Rudxain, just read your comments, took a look at the brnfckr repo and read the linked stackexchange page. Seems like all solutions you mentioned can be implemented. To start off the feature, a reasonable approach would be adding the optimizations to /bffmt/minify.go under func MinifyFile:

https://github.com/baris-inandi/brainfuck-go/blob/c658055bb9ab7b203579b548bf2a4c33fdae3081/bffmt/minify.go#L9

https://github.com/baris-inandi/brainfuck-go/blob/c658055bb9ab7b203579b548bf2a4c33fdae3081/bffmt/minify.go#L11

and we can wrap this line with a minify(string) function:

 minified := minify(readcode.ReadBrainfuck(f))

This function (and readcode.ReadBrainfuck(f) for that matter) currently only removes all non-brainfuck characters (this minification essentially removes newlines and comments so it won't deal with bad code logic that can be fixed). We can start working on an improved minifier anytime.

PS If you already know Rust and JS, a transition to Go should be quite easy. Manually transpiling TS code might take some time so it would be great if you could consider Go for implementing the improved minifier. If you have a Go-related question I would be happy to help. LMK what you think about that.

Rudxain commented 2 years ago

Thank you for the info! I've been considering learning some Go, and I could use the official VSCode Golang extension for faster development. So that's fine for me! But it'll take some time, please be patient (I'm slow)

baris-inandi commented 2 years ago

Great, make sure you open a pull request when you're ready and keep me updated

Rudxain commented 2 years ago

Ok 👍

Rudxain commented 2 years ago

VSCode says "Error: there is no registered task type 'cppbuild'. Did you miss installing an extension that provides a corresponding task provider?". It seems .vscode/tasks.json is the file that defines that task. Can that error be safely ignored?

baris-inandi commented 2 years ago

VSCode says "Error: there is no registered task type 'cppbuild'. Did you miss installing an extension that provides a corresponding task provider?". It seems .vscode/tasks.json is the file that defines that task. Can that error be safely ignored?

Yeah, tasks.json wasn't supposed to be there anyways, we can remove it

baris-inandi commented 2 years ago

https://github.com/baris-inandi/brainfuck-go/pull/3