brainf*** interpreter/compiler

  • (2 Pages)
  • +
  • 1
  • 2

28 Replies - 20909 Views - Last Post: 26 July 2013 - 09:39 AM

#16 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 23 March 2012 - 08:09 PM

yum, python. I wanna see some other languages now; how about Haskell? I'll make an interpreter in Haskell real quick.

Here's a taste of the bytecode my compiler is outputting right now...it's untested so it *could* be making an incorrect optimization(there is only 1 right now) sense I haven't written the bytecode interpreter or JITer to test it but it seems to be correct.

this brainfuck program
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'



compiles to this byte code(the byte-code very closely corresponds to x86). r0 corresponds to ebx. the labels are printed kinda funny but the indentation should make that more clear. the 'print' instruction will be compiled to a call to putchar. this is also exclusively 32-bit so you're not limited to 1 byte

	add [r0] 10
lbl 1 
	cmp [r0] 0
	je 2 
	dec [r0] 
	add [r0 + 1] 7
	add [r0 + 2] 10
	add [r0 + 3] 3
	inc [r0 + 4] 
	jmp 1 
lbl 2 
	add [r0 + 1] 2
	inc r0 
	print [r0] 
	inc [r0 + 1] 
	inc r0 
	print [r0] 
	add [r0] 7
	print [r0] 
	print [r0] 
	add [r0] 3
	print [r0] 
	add [r0 + 1] 2
	inc r0 
	print [r0] 
	add [r0 + -2] 15
	sub r0 2
	print [r0] 
	inc r0 
	print [r0] 
	add [r0] 3
	print [r0] 
	sub [r0] 6
	print [r0] 
	sub [r0] 8
	print [r0] 
	inc [r0 + 1] 
	inc r0 
	print [r0] 
	inc r0 
	print [r0] 



the optimization takes a series of add, sub, inc, and dec instructions and averages out the effect of them to the smallest number of operations.

> +++++ ++              add  7 to cell #1
> +++++ +++++           add 10 to cell #2 
> +++                   add  3 to cell #3
> +                     add  1 to cell #4
<<<< -                  decrement counter (cell #0)


get's optimized to just a few instructions

dec [r0] 
add [r0 + 1] 7
add [r0 + 2] 10
add [r0 + 3] 3
inc [r0 + 4] 


later I'm going to look at some loop optimization.

This post has been edited by ishkabible: 23 March 2012 - 08:19 PM

Was This Post Helpful? 1
  • +
  • -

#17 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,050
  • Joined: 15-July 08

Re: brainf*** interpreter/compiler

Posted 23 March 2012 - 08:12 PM

Yeah, I need to optimize my compiler like... a lot
Was This Post Helpful? 0
  • +
  • -

#18 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 23 March 2012 - 08:22 PM

ya; I'm going to try to make some really aggressive optimization for this; that''s the fun part :P
Was This Post Helpful? 0
  • +
  • -

#19 MathiasVP  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 154
  • Joined: 08-August 10

Re: brainf*** interpreter/compiler

Posted 24 March 2012 - 04:10 PM

Here's a quick 'n dirty interpreter I made in C++. Hopefully I'll find time to write a compiler after my last exam!

Spoiler

This post has been edited by MathiasVP: 24 March 2012 - 04:59 PM

Was This Post Helpful? 2
  • +
  • -

#20 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 24 March 2012 - 09:24 PM

cool! I'm actully scraping the byte code in my compiler for an IR in the form of an AST. I designed my byte code all wrong and it just isn't ideal for optimization. I'm going to create something more ideal for optimization.
Was This Post Helpful? 0
  • +
  • -

#21 MathiasVP  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 154
  • Joined: 08-August 10

Re: brainf*** interpreter/compiler

Posted 25 March 2012 - 02:20 PM

Here's the asm code my compiler currently is creating from the Hello World ishkabible showed earlier on this page, plus an additional "," to keep the console open.

Spoiler

Hopefully I'll be able to feed a complete asm program to an assembler by Tuesday.
The only optimization I've done so far is to reduce a sequence of equal inc/dec instructions into a single add/sub instruction.

This post has been edited by MathiasVP: 25 March 2012 - 02:23 PM

Was This Post Helpful? 1
  • +
  • -

#22 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 25 March 2012 - 03:05 PM

neat! you got basically what I did.

I'm using a small function for printing however to increase locality. that's why I left the printing code alone(you optimized out a lot of the increments by using [ebx + X] kinda code for pushing).

print_char:
   add esp, 4
   push dword[ebx]
   jmp _putchar
   ret



this tail calls putchar so it''s basically the same as what you have but it drastically increases locality. the strange thing it does is per-cleans the stack. because we can over write what's on the stack so there is no need to clean up after wards, we can just do it ahead of time. this allows for the tail call which makes it almost as fast as inlining the call like you did. my *hope* is that the increase in locality gives me the same speed as yours but with less code...not a tested theory just yet.

this way each one of my 'print' instructions gets reduced to just 1 instruction.
call print_char


I scraped my byte code however becuase I'm working on a new IR that should be easier to optimize.

This post has been edited by ishkabible: 25 March 2012 - 03:09 PM

Was This Post Helpful? 1
  • +
  • -

#23 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 25 March 2012 - 06:11 PM

So I think I found the best optimization, pre-interpretation :P. Really it's not just a joke, I'm not done with it but this should be a generalization of my previous optimization. the idea is to sort of interpret the code with respect to the last user input. this gets rid of all code which the effects of can be determined at compile time.

the other optimization I have just merges 'putc' instructions in my byte code to 'puts' instructions which output constant string.

so I get the following:
puts "Hello World!\n"
add [r0] 0
add [r0 + 1] 87
add [r0 + 2] 100
add [r0 + 3] 33
add [r0 + 4] 10
add r0 4


the stuff at the end is dead code but I don't have dead code elimination just yet. after I "pre-interpret" the code it prints the constant output AND changes the global state becuase the stuff after the optimized block might need it. I'll make a contrived dead code eliminator that will take out all instructions that don't preform IO at the end.
Was This Post Helpful? 1
  • +
  • -

#24 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 680
  • View blog
  • Posts: 2,357
  • Joined: 31-December 10

Re: brainf*** interpreter/compiler

Posted 26 March 2012 - 10:45 AM

MathiasVP what compiler are you using that outputs ASM like that?
Was This Post Helpful? 0
  • +
  • -

#25 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 26 March 2012 - 01:25 PM

@vividexstance: I think he output the code himself.

After I finish that optimization above I'm going to look at register allocation and vectorization.

think about it, how many times do have 3 add instructions right next to each other in this code...alot. 2 isn't very good because there is some overhead in packing the data into SMID registers but at 4 additions this becomes a big bonus(and even 3 sense you can add 0 to the odd ball out). brainfuck just begs for vectorization.

loop merging is also something I want to look into.
Was This Post Helpful? 0
  • +
  • -

#26 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: brainf*** interpreter/compiler

Posted 25 July 2013 - 10:45 PM

Sorry to necro this thread.

I decided to give this a shot and wrote a solution in Lua.

require "io"
require "os"
require "string"

symbols = { 
    ['<'] = '--ptr;',
	['>'] = '++ptr;',
	['+'] = '++*ptr;',
	['-'] = '--*ptr;',
	['.'] = 'putchar(*ptr);',
	[','] = '*ptr = getchar();',
	['['] = 'while (*ptr) {',
	[']'] = '}'
}

c_init = "#include <stdio.h> \nint main() {\n" ..
         "\tchar array[30000];\n\tchar* ptr = array;\n"
c_complete = "\treturn 0; \n}\n"

file_r = io.open(arg[1], "r")
lines = file_r:read("*all")
file_r:close()

file_w = io.open("tmp_brainf.c", "w+")
file_w:write(c_init)
  
for i = 1, string.len(lines) do
    if symbols[string.sub(lines, i, i)] ~= nil then 
        file_w:write('\t' .. symbols[string.sub(lines, i, i)] .. '\n')
    end
end

file_w:write(c_complete)
file_w:close()

os.execute("gcc tmp_brainf.c -o tmp_brainf_exe;")


To run
$ lua filename.lua nameofbrainfuckfile.bf
$ ./tmp_brainf_exe 



This was a fun thing to do while I'm stuck in a hotel room. I think I spent most of my time figuring how how to declare the table since it uses symbols that the language uses. I initially declared an empty one and was able to use
symbols["<"] = something
but I thought it was pretty ugly. Later I learned you can use brackets if you are initializing a table with clashing identifiers. I thought about a few ways I could consolidate the lua code to under 20 lines, but I didn't want to sacrifice readability or get myself into more bad habits :D

This post has been edited by raspinudo: 25 July 2013 - 10:49 PM

Was This Post Helpful? 0
  • +
  • -

#27 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 26 July 2013 - 06:47 AM

Cool! I want to do this again knowing what I know now lol. Goodbye weekend, it was nice knowing you

This post has been edited by ishkabible: 26 July 2013 - 06:50 AM

Was This Post Helpful? 0
  • +
  • -

#28 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5901
  • View blog
  • Posts: 12,805
  • Joined: 16-October 07

Re: brainf*** interpreter/compiler

Posted 26 July 2013 - 06:53 AM

Yeah, this evil little diversion has killed more hours than I thought possible.

I'd like to see this in the functional forums. I'd do something in F#. Maybe even Scheme.

On second thought, I have things to do...

This post has been edited by baavgai: 26 July 2013 - 06:53 AM

Was This Post Helpful? 0
  • +
  • -

#29 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: brainf*** interpreter/compiler

Posted 26 July 2013 - 09:39 AM

View Postbaavgai, on 26 July 2013 - 06:53 AM, said:

Yeah, this evil little diversion has killed more hours than I thought possible.


I know right?! I set out to do it when I left for LA about six hours prior to my hotel encapsulation. It proceeded to consume my thought process for the remaining driving time until I could get to my computer. I kept catching myself, "Why are you thinking this much about extending out this brainf*** compiler" haha.

This post has been edited by raspinudo: 26 July 2013 - 09:43 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2