11
\$\begingroup\$

first time writing this source-to-source (i think) compiler, not an expert, not a pro, not an advanced person, just a beginner, I don't think this is cross platform.

# dependencies:
# - fasm

import sys
import subprocess
from dataclasses import dataclass
from pathlib import Path
from typing import List, Dict, Union

# TODO: Implement Copy, and Multiply
clear = (['[', '-', ']'],['[', '+', ']'])

@dataclass
class Token:
    "Token"
    instruction: str
    extra: Union[int,List[int]] # extra information used for counts or other things

def filter_valid(code: str) -> str:
    "Filter valid brainfuck code"
    return filter(lambda x: x in '[]+-,.<>', code)

def remove_cancel(code: str) -> str: # im getting canceled with this
    "remove instructions that cancel each other like '++--' become ''"
    opposite: Dict[str, str] = {'>':'<','<':'>','+':'-','-':'+'}

    code_list: List[str] = list(code)
    i: int = 0
    while i < len(code_list) - 1:
        if code_list[i] == opposite.get(code_list[i + 1]):
            del code_list[i:i + 2]
            i = max(0, i - 1)
        else:
            i += 1

    new_code = ''.join(code_list)
    return new_code

def count_consecutive(program: List[str], current: str) -> int:
    "Count consecutive operations"
    count = 1
    while program and program[0] == current and not current in "[]":
        program.pop(0)
        count += 1
    return count

def optimize_ir(oir: List[Token]) -> List[Token]:
    "Optimize Intermediate Representation"
    i: int = 0
    ir: List[Token] = oir
    while i < len(ir):
        skip: int = 1
        pattern_clear = [x.instruction for x in ir[i:i + 3]]
        if pattern_clear in clear:
            ir = ir[:i] + [Token("clr", 1)] + ir[i + 3:]
            skip += 3
        i += skip
    return ir

def inter_repr(code: str) -> List[Token]:
    "Generate an Intermediate Representation"
    valid_code: str = filter_valid(code)
    filtered_code: str = remove_cancel(valid_code)
    program: List[str] = list(filtered_code)
    ir: List[Token] = []

    while program:
        current: str = program.pop(0)
        extra: int = count_consecutive(program, current)
        token: Token = Token(current, extra)
        ir.append(token)

    ir: List[Token] = optimize_ir(ir)
    
    return ir

def precompute_loop(ir: List[Token]) -> Dict[int, int]: # interpreter
    "Precompute loops"
    stack: List[int] = []
    result: Dict[int, int] = {}

    for index, op in enumerate(ir):
        if op.instruction == '[': #]
            stack.append(index)
        elif op.instruction == ']':
            loop: int = stack.pop()
            result[loop] = index
            result[index] = loop

    return result

def interpreter(ir: List[Token]) -> None:
    "Interpret intermediate representation"
    mem: List[int] = [0] * 30_000
    mem_pointer: int = 0
    loops_map: Dict[int, int] = precompute_loop(ir)
    i: int = 0
    while i < len(ir):
        op: Token = ir[i]
        match op.instruction:
            case '+':
                mem[mem_pointer] = (mem[mem_pointer] + op.extra) % 256
            case '-':
                mem[mem_pointer] = (mem[mem_pointer] - op.extra) % 256
            case '>':
                mem_pointer = (mem_pointer + op.extra) % 30_000
            case '<':
                mem_pointer = (mem_pointer - op.extra) % 30_000
            case '.':
                print(chr(mem[mem_pointer])*op.extra, end='')
            case ',':
                for _ in range(op.extra):
                    mem[mem_pointer] = ord(sys.stdin.read(1))
            case '[': #]
                if mem[mem_pointer] == 0:
                    i = loops_map[i]
            case ']':
                if mem[mem_pointer] != 0:
                    i = loops_map[i]
            case 'clr':
                mem[mem_pointer] = 0
            case _:
                pass
        i += 1

def compiler(ir: List[Token]) -> str:
    "Compile intermediate representation to assembly"
    
    lines: str = "format ELF64 executable\n"
    lines += "segment readable writeable\n"
    lines += "mem: rb 30000\n\n"
    lines += "segment readable executable\n"
    lines += "entry _start\n"
    lines += "putchar:\n"
    lines += "\tmov rax, 1\n"
    lines += "\tmov rdi, 1\n"
    lines += "\tmov rsi, r8\n"
    lines += "\tmov rdx, 1\n"
    lines += "\tsyscall\n"
    lines += "\tret\n\n"
    lines += "getchar:\n"
    lines += "\tmov rax, 0\n"
    lines += "\tmov rdi, 0\n"
    lines += "\tmov rsi, r8\n"
    lines += "\tmov rdx, 1\n"
    lines += "\tsyscall\n"
    lines += "\tret\n\n"
    lines += "_start:\n"
    lines += "\tmov r8, mem\n"
    loops: List[int] = []
    open_loops: int = 0
    i: int = 0
    while i < len(ir):
        op: Token = ir[i]
        match op.instruction:
            case '+':
                lines += f"\tadd byte [r8], {op.extra}\n"
            case '-':
                lines += f"\tsub byte [r8], {op.extra}\n"
            case '>':
                lines += f"\tadd r8, {op.extra}\n"
                # lines += "\tand r8, 29999\n"
            case '<':
                lines += f"\tsub r8, {op.extra}\n"
                # lines += "\tand r8, 29999\n"
            case '.':
                lines += '\tcall putchar\n'*op.extra
            case ',':
                lines += '\tcall getchar\n'*op.extra
            case '[': #]
                open_loops += 1
                lines += "\tcmp byte [r8], 0\n"
                lines += f"\tje close_loop_{open_loops}\n"
                lines += f"open_loop_{open_loops}:\n"
                loops.append(open_loops)
            case ']':
                if len(loops) < 1:
                    assert False, "close before opening loop"
                last = loops.pop()
                lines += "\tcmp byte [r8], 0\n"
                lines += f"\tjne open_loop_{last}\n"
                lines += f"close_loop_{last}:\n"
            case 'clr':
                lines += "\tmov byte [r8], 0\n"
        i += 1
    lines += "  mov rax, 60\n"
    lines += "  mov rdi, 0\n"
    lines += "  syscall\n"
    return lines

def help_message():
    "Print help message"
    return f"""
USAGE: {sys.argv[0]} <command> <file>

command:
    compile   - compile file
    interpret - interpret file
"""

def call(commands: List[str]) -> None:
    "Call and print information"
    print("[INFO] Running " + ' '.join(commands))
    subprocess.call(commands)

def main() -> None:
    "Main function"
    if len(sys.argv) < 2:
        print(help_message())
    else:
        if sys.argv[1] == "compile":
            file_content: str = ""
            output_file: str = Path(sys.argv[2]).stem
            with open(sys.argv[2], "r") as file:
                file_content = file.read()
            compiled_program: str = compiler(inter_repr(file_content))
            with open(output_file + ".asm", "w") as file:
                file.write(compiled_program)
            call(["fasm",output_file + ".asm"])
        elif sys.argv[1] == "interpret":
            file_content: str = ""
            with open(sys.argv[2], "r") as file:
                file_content = file.read()
            interpreter(inter_repr(file_content))
        else:
            print("invalid input")

if __name__ == "__main__":
    main()
\$\endgroup\$
2
  • \$\begingroup\$ Compiling to assembly is normally not described as "source to source". Assembly language only needs to get assembled, not compiled; it's just a way for the compiler to avoid implementing its own object-file handling. For example GCC just outputs asm and runs the assembler on it, but nobody calls GCC a "source to source" compiler - that implies compiling to a (usually portable) higher-level language than asm, which can be fed to an optimizing compiler. Does a compiler always produce an assembly code? \$\endgroup\$ Commented Jun 13 at 7:38
  • \$\begingroup\$ You could use RSI instead of R8 for the cursor, for smaller machine-code size (no REX prefix in the memory-destination add/sub). And you wouldn't need a mov to set up the operand for syscall; the Linux syscall ABI leaves arg regs unmodified (except RAX with the return value). Note that your system-call usage is specific to x86-64 Linux; different OSes have different system-call numbers and ways of passing args. \$\endgroup\$ Commented Jun 13 at 7:52

1 Answer 1

8
\$\begingroup\$

I tested the interpreter on different programs and it seemed to work correctly. So good job on that. But it was terribly slow for "Towers of Hanoi by Clifford Wolf", I waited a minute or two before sending a SIGTERM. It would be nicer if the program accepted input from standard input.

i don't think this is cross platform

Yes, you are emitting Intel assembly. I can suggest transpiling to C instead, and then letting a C compiler compile and optimize the generated C source code (but mind you, you'd have to deal with integer overflow et cetera). It would run order of magnitudes faster too, both compared to the interpreter and the generated assembly. (I wrote one too: tbf - An Optimizing Brainfuck Interpreter and Transpiler in C, tbf standing for "The One Brainfuck Interpreter to Rule Them All").

Or you could compile to native code with a compiler backend like QBE (or some other), which currently can target amd64 (linux and osx), arm64, and riscv64.

Check for invalid square brackets during or before generating IR:

This is perhaps the first thing we should be doing. What's the point of filtering out invalid code (or comments), performing optimizations, and generating an intermediate representation, only to then crash during compiling or interpreting due to an extra or missing square bracket?

Validate the code first, then do the rest of the things. This way, you would be able to provide better error messages than this:

case ']':
    if len(loops) < 1:
        assert False, "close before opening loop"

For a program containing 1000 or more lines of obscure sequences of characters (brainfuck code), seeing this without the error location would take a very long time to debug.

And whilst you do that, consider using byte positions instead of line numbers for error messages because Byte Positions Are Better Than Line Numbers, and the editor I use (Vim) can jump to a byte easily with go <byte-number>.

Handling cell value overflow:

C's uint8_t type and implicit unsigned overflow integer would be quite useful for handling cell value overflow. In the ctypes library, I see:

class ctypes.c_uint8 Represents the C 8-bit unsigned int datatype. Usually an alias for c_ubyte.

The documentation for c_ubyte mentions that no overflow checking is done, which is exactly what is required.

Allow user to configure the memory buffer size, cell size et cetera:

Some programs might want a buffer larger than 30000 bytes, or a cell able to hold more than 256 values, or negative values. This can all be configured through command-line arguments.

Type-hints:

From Python 3.9 (PEP 585) onwards tuple, list and various other classes are now generic types. Using these rather than their typing counterpart is now preferred. From Python 3.9 you can now just do:

# def call(commands: List[str]) -> None:
def call(commands: list[str]) -> None:

Incorrect specification, or implementation:

def help_message():
    "Print help message"
return f"""
USAGE: {sys.argv[0]} <command> <file>

command:
    compile   - compile file
    interpret - interpret file
"""

As per PEP 257:

For consistency, always use """triple double quotes""" around docstrings. Use r"""raw triple double quotes""" if you use any backslashes in your docstrings.

You are using single-quotes instead.

Moreover, your function is documented to print the help message, but it does not do so. It instead returns the help message as a string. Is the documentation incorrect, or the implementation? That is for you to decide.

Only declare as many variables as you require:

In count_consecutive():

new_code = ''.join(code_list)
return new_code

No need of new_code, simply return ''.join(code_list).

In inter_repr():

valid_code: str = filter_valid(code)
filtered_code: str = remove_cancel(valid_code)
program: List[str] = list(filtered_code)

valid_code and filtered_code are not referenced again, so you can change it to:

program = List[str] = list(remove_cancel(filter_valid(code)))

Simplify main():

This part:

        if sys.argv[1] == "compile":
            file_content: str = ""
            output_file: str = Path(sys.argv[2]).stem
            with open(sys.argv[2], "r") as file:
                file_content = file.read()
            compiled_program: str = compiler(inter_repr(file_content))
            with open(output_file + ".asm", "w") as file:
                file.write(compiled_program)
            call(["fasm",output_file + ".asm"])
        elif sys.argv[1] == "interpret":
            file_content: str = ""
            with open(sys.argv[2], "r") as file:
                file_content = file.read()
            interpreter(inter_repr(file_content))
        else:
            print("invalid input")

can be moved to a separate function. And then further broken down into compile(), assemble(), and interpret(). Perhaps the argparse module can take better care of this?

String-concatenation:

From the reference manual:

Multiple adjacent string or bytes literals (delimited by whitespace), possibly using different quoting conventions, are allowed, and their meaning is the same as their concatenation. Thus, "hello" 'world' is equivalent to "helloworld". This feature can be used to reduce the number of backslashes needed, to split long strings conveniently across long lines, or even to add comments to parts of strings, for example:

re.compile("[A-Za-z_]"       # letter or underscore
           "[A-Za-z0-9_]*"   # letter, digit or underscore
          )

Note that this feature is defined at the syntactical level, but implemented at compile time. The ‘+’ operator must be used to concatenate string expressions at run time. Also note that literal concatenation can use different quoting styles for each component (even mixing raw strings and triple quoted strings), and formatted string literals may be concatenated with plain string literals.

So:

lines: str = "format ELF64 executable\n"
    lines += "segment readable writeable\n"
    lines += "mem: rb 30000\n\n"
    lines += "segment readable executable\n"
    lines += "entry _start\n"
    lines += "putchar:\n"
    lines += "\tmov rax, 1\n"
    lines += "\tmov rdi, 1\n"
    lines += "\tmov rsi, r8\n"
    lines += "\tmov rdx, 1\n"
    lines += "\tsyscall\n"
    lines += "\tret\n\n"
    lines += "getchar:\n"
    lines += "\tmov rax, 0\n"
    lines += "\tmov rdi, 0\n"
    lines += "\tmov rsi, r8\n"
    lines += "\tmov rdx, 1\n"
    lines += "\tsyscall\n"
    lines += "\tret\n\n"
    lines += "_start:\n"
    lines += "\tmov r8, mem\n"

becomes:

lines = (
    "format ELF64 executable\n"
    "segment readable writeable\n"
    "mem: rb 30000\n\n"
    "segment readable executable\n"
    "entry _start\n"
    "putchar:\n"
    "\tmov rax, 1\n"
    "\tmov rdi, 1\n"
    "\tmov rsi, r8\n"
    "\tmov rdx, 1\n"
    "\tsyscall\n"
    "\tret\n\n"
    "getchar:\n"
    "\tmov rax, 0\n"
    "\tmov rdi, 0\n"
    "\tmov rsi, r8\n"
    "\tmov rdx, 1\n"
    "\tsyscall\n"
    "\tret\n\n"
    "_start:\n"
    "\tmov r8, mem\n"
)

Use an enum:

            case '+':
                lines += f"\tadd byte [r8], {op.extra}\n"
            case '-':
                lines += f"\tsub byte [r8], {op.extra}\n"
            case '>':
                lines += f"\tadd r8, {op.extra}\n"
                # lines += "\tand r8, 29999\n"
            case '<':
                lines += f"\tsub r8, {op.extra}\n"
                # lines += "\tand r8, 29999\n"
            case '.':
                lines += '\tcall putchar\n'*op.extra
            case ',':
                lines += '\tcall getchar\n'*op.extra
            case '[': #]

These character literals work, but named-constants would be clearer.

The match is perfectly nice, but there is an opportunity to dispatch using a dict that maps from character to code, if you like.

Be consistent in your use of f-strings:

You can use a f-string in call() as well:

# print("[INFO] Running " + ' '.join(commands))

print(f"[INFO] Running {' '.join(commands)}")

Be more descriptive in your documentation:

def optimize_ir(oir: List[Token]) -> List[Token]:
    "Optimize Intermediate Representation"

I would have liked seeing how, and not what repeated twice. How does it optimize the intermediate repesentation?

\$\endgroup\$
5
  • \$\begingroup\$ Only nit is that I'm not a fan of the """ string here. The lines code is indented 1 level inside compiler(), but to avoid concatenating leading whitespace, the multi-line """ string would need to be unindented all the way to column 0. Stylistically I'd prefer the parentheses approach here (a la the quoted example). \$\endgroup\$
    – tdy
    Commented Jun 13 at 2:03
  • \$\begingroup\$ @tdy Okay, I have edited the answer now. \$\endgroup\$
    – Harith
    Commented Jun 13 at 2:31
  • 1
    \$\begingroup\$ but mind you, you'd have to deal with integer overflow et cetera - Or you could make source intended to be compiled by GCC or Clang -fwrapv. But yeah for a BF compiler, uint8_t gives well-defined wrapping for cell values. \$\endgroup\$ Commented Jun 13 at 7:43
  • 1
    \$\begingroup\$ I'd write your lines = (...many strings with implicit concatenation...) as '\n'.join((...same lines without \n...)) for readability - since this only happens once for the program, performance impact will be zero. \$\endgroup\$
    – STerliakov
    Commented Jun 13 at 11:06
  • \$\begingroup\$ program = List[str] = ... should be program: list[str] = ... \$\endgroup\$
    – MT0
    Commented Jun 13 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.