baris-inandi / bfgo Goto Github PK

A fast, optimizing, BF compiler, interpreter, and REPL. Also includes a BF formatter and minifier! Implemented in Go. Batteries included.

License: GNU General Public License v3.0

Go 98.89% Makefile 0.24% Python 0.87%

esolang golang go bf compiler interpreter repl cli

bfgo's Introduction

bfgo

bfgo is an overengineered BF toolkit written in Go.

Features

The toolkit includes the following features:

Native Compiler
JVM Compiler
JavaScript Compiler
Interpreter
REPL
Formatter
Minifier

Compiler

The compiler can compile for three different targets:

Binary for native execution
JVM bytecode
JavaScript for running in the browser

Native

Example: $ bfgo examples/hello.bf
Creates a binary hello. Run with ./hello.

JVM Compiler

Example: $ bfgo -jvm examples/hello.bf
Generates a JVM classfile Hello.class. Run with java Hello.

JavaScript Compiler

Example: $ bfgo -js examples/hello.bf
Generates a JavaScript file hello.js and an HTML file hello.html.
Run your favorite HTTP server and load hello.html in the browser. The output will replace the document <body>.

The Optimizer

All compile targets can be compiled with the optimizer. The optimizer options are:

-F: Fast
- Uses fast IR generation
- Results in fast compile times
- Causes Slow execution
- use -o-compile or -F
-B: Balanced
- Default behaviour
- Applies some optimizations
- Balance between -F and -O
- use -o-balanced or -B
-O: Optimized
- Uses the full optimizer
  - Dead code elimination
  - Canonicalization
- Smaller binary size
  - Also performs binary stripping
- Causes Slow compile times
- Results in very fast execution
- use -o-performance or -O

Interpreter

Executes given BF file. There is still room for improvement when it comes to performance. Feel free to submit a PR.

use -interpret

REPL

The REPL is a command line interface for the interpreter. It can be used to execute BF interactively.

use -repl

bffmt

BF formatter bundled with bfgo.

Warning: bffmt currently omits all comments. Feel free to submit a PR for support for comments.
use -fmt

Example formatted snippet from examples/fibonacci.bf:

  [
    +++++
    [>++++++++<-]> .
    <++++++
    [>--------<-]+<<<
  ]

Minifier

bffmt can also minify BF code, leaving only valid characters, minimizing file size.

Cli Flags

--run, -r                  Immediately run binary after compilation (default: false)
--output value, -o value   Specify output binary
--compile-only, -C         Only compile, do not output a binary (default: false)
--clang                    Use clang instead of default gcc (default: false)
--jvm                      Compile to JVM bytecode (default: false)
--js                       Compile to JavaScript (default: false)
--o-compile, -F            Disable optimizations and use fast compiler: fast compile time, slow execution (default: false)
--o-balanced, -B           Minimal optimizations for balanced compile time and performance, default behavior (default: false)
--o-performance, -O        Enable optimizations: fast execution, slow compile time (default: false)
--interpret                Interpret file instead of compiling (default: false)
--repl                     Start a read-eval-print loop (default: false)
--c-compiler-flags value   Pass arbitrary flags to the compiler (gcc, clang or javac)
--c-tape-size value        Integer to specify length of BF tape (default: 30000)
--c-tape-init value        Integer value used to initialize all elements in BF tape (default: 0)
--c-cell-type value        Type used for BF tape in intermediate representation (default: "int")
--d-dump-ir                Dump intermediate representation (default: false)
--d-keep-temp              Do not remove temporary IR files (default: false)
--d-print-ir-filepath      Dump temporary IR filepath, use -d-keep-temp to keep them from being deleted (default: false)
--d-print-compile-command  Print C IR compiler command (default: false)
--verbose, -v              Print verbose output (default: false)
--debug, -d                Produce debug output, overrides -o (default: false)
--time, -t                 Prints out execution time before exiting (default: false)
--fmt                      Format code (omits comments) (default: false)
--minify                   Minify code (default: false)
--help, -h                 show help (default: false)

Benchmark

The following is a benchmark of examples/mandelbrot.bf

Optimization Level	-F	-B	-O
Native (arm64)	8 secs	580 millis	370 millis
Native (x64)	16 secs	710 millis	440 millis
JVM	22 secs	13 secs	13 secs
JavaScript	35 secs	19 secs	5 secs

Native arm64 using entry level M2 MacBook Air
Native x64 using Ryzen 5 3600
JavaScript using Google Chrome 106.0.5245.0 dev
JVM using latest OpenJDK 18 release

bfgo's People

Contributors

Stargazers

Watchers

Forkers

rudxain

bfgo's Issues

Better minifier

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:

~~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.
Remove chunks of 256 consecutive + or - (because of mod 256 wrap-around)
Remove mutual-cancel opcodes (+ or - followed by its opposite, same for < and >)
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 (-).
Replace odd-count cell-reset loops by [-] and even-count by [--] (this exploits mod 2^n arithmetic)
Remove useless arithmetic if reset is found: +++[-] -> [-]
Zero-loop removal. If there are loops before the 1st cell-mutation happens, then all can be removed.
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]
Increase compression ratio by replacing [-] by [+] and vice-versa (frequency analysis for "compressor-friendly" output)
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.

ℹ️ More info: mathiasbynens/brnfckr#2
JS implementation of some of these features
Reddit post
Related: codegolf stackexchange: minify-brainfuck

Segfault when running native random.bf

Repro:

cd into repo root
go run . examples/random.bf
./random

This is the output on my sys:

��PO[y�KKXi)�������(V����d���'����a=([�WRp
    g�� +��+}~�(6��P�0=�3�xr1̷����n�G.���"�T@Z|��t�sC
                                                    u�ϪG`��+�k`w��U��H|O��u�ۚ� O}���3w5-Y�it�����t\,��B���p���.2Q��x���A�w��SH~�PW�v�3��&�5��d�o���HA���r�Y�&�|87�����N��|���`
                                               q�1�8ٽ��yT2��
�W�D���;q�r{>輒���R�p[�a�I�����X�gh�g_�6(�3�;�  �=�VJ��V�&��+�����.�
����sFs�L�      Ry2ՁR����Ea�H�y�.��mE4��V��Z�ǟ�ތ���J�'1|�-*ͻ�a�L���}�^��78�I��8F��m���`.
                                                                                        ��f��pR�xw_�֙^]�5�#S+x�hG�.X?j�.T�껤r�@����?f�,fߝ�Q���>�D�\��=���|1��#�B"��N=f�{�~�uL�z �]65���=��%���e�ҩ""��aӅ�
                                                                         cH2���=T���:֏$���5���ؤ$}�z��wW5�� P�
                                                                                                             �f�b��P��"���a5?�
                                                                                                                             ?�<_�Q���B6�ѐˍ�g1�l�ȶ��m0p
Segmentation fault (core dumped)

I tried piping it to xxd but got no output. Tried redirecting to a file, still no output (but this time, it only prints "Segmentation fault (core dumped)")

OS+DE: Linux Mint 21 Cinnamon
Device: Dell Inspiron 15R
Terminal: VScode built-in term (haven't tested in GNOME term)

Use the `bf.style` standard for code formatting

Hello @baris-inandi,

I've seen your repository on r/brainfuck and decided to reach out. I was especially interested in the formatter part of the toolkit. What are the formatting rules you're using? I see there is nested indentation for loops and spacing around I/O characters, but can you specify the exact behavior?

I also suggest that you rely on battle tested and de-facto standard bf.style formatting and its bundled format.bf script as a benchmark. This way, we will have more consistent indentation styling and code reusability in the Brainfuck community 🤗

Best of luck,
Artyom Bologov,
Community Manager,
Brainfuck Enterprise Solutions
One step ahead of the future