search

dragonwasrobot / brainfuck

A brainfuck interpreter written in Elm
MIT License
7 stars 0 forks source link

Out of memory #6

Closed reynir closed 11 years ago

reynir commented 11 years ago

I get out of memory when running a benchmark program.

$ coffee brainfuck.coffee 
FATAL ERROR: JS Allocation failed - process out of memory

This is the benchmark program (found on esolangs).

>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.
dragonwasrobot commented 11 years ago

Hmm...interesting! I wrote a brainfuck-to-coffeescript compile function so I could play with the benchmark function in more familiar settings. The above benchmark becomes the following CoffeeScript function,

# Compiled Brainfuck code:
cells = (0 for i in [0...100])
pointer = 0
fun = () ->
    pointer++
    cells[pointer]++
    pointer++
    cells[pointer]++
    pointer++
    cells[pointer]++
    pointer++
    cells[pointer]++
    pointer++
    cells[pointer]++
    cells[pointer]++
    pointer--
    while cells[pointer] > 0
        pointer++
        while cells[pointer] > 0
            pointer--
            cells[pointer]++
            cells[pointer]++
            cells[pointer]++
            pointer++
            cells[pointer]--
            pointer++
            pointer++
            pointer++
            pointer++
            pointer++
            pointer++
            cells[pointer]++
            pointer++
            cells[pointer]++
            pointer++
            cells[pointer]++
            pointer++
            cells[pointer]++
            pointer++
            cells[pointer]++
            cells[pointer]++
            pointer--
            while cells[pointer] > 0
                pointer++
                while cells[pointer] > 0
                    pointer--
                    cells[pointer]++
                    cells[pointer]++
                    cells[pointer]++
                    pointer++
                    cells[pointer]--
                    pointer++
                    pointer++
                    pointer++
                    pointer++
                    pointer++
                    pointer++
                    cells[pointer]++
                    pointer++
                    cells[pointer]++
                    pointer++
                    cells[pointer]++
                    pointer++
                    cells[pointer]++
                    pointer++
                    cells[pointer]++
                    cells[pointer]++
                    pointer--
                    while cells[pointer] > 0
                        pointer++
                        while cells[pointer] > 0
                            pointer--
                            cells[pointer]++
                            cells[pointer]++
                            cells[pointer]++
                            pointer++
                            cells[pointer]--
                            pointer++
                            pointer++
                            pointer++
                            pointer++
                            pointer++
                            pointer++
                            cells[pointer]++
                            pointer++
                            cells[pointer]++
                            pointer++
                            cells[pointer]++
                            pointer++
                            cells[pointer]++
                            pointer++
                            cells[pointer]++
                            cells[pointer]++
                            pointer--
                            while cells[pointer] > 0
                                pointer++
                                while cells[pointer] > 0
                                    pointer--
                                    cells[pointer]++
                                    cells[pointer]++
                                    cells[pointer]++
                                    pointer++
                                    cells[pointer]--
                                    pointer++
                                    pointer++
                                    pointer++
                                    pointer++
                                    pointer++
                                    cells[pointer]++
                                    cells[pointer]++
                                    cells[pointer]++
                                    while cells[pointer] > 0
                                        cells[pointer]--
                                        pointer++
                                        cells[pointer]++
                                        cells[pointer]++
                                        cells[pointer]++
                                        cells[pointer]++
                                        cells[pointer]++
                                        pointer--
                                    pointer++
                                    while cells[pointer] > 0
                                        cells[pointer]--
                                    pointer--
                                    pointer--
                                    pointer--
                                    pointer--
                                    pointer--
                                    pointer--
                                pointer--
                                pointer--
                            pointer++
                            while cells[pointer] > 0
                                cells[pointer]--
                            pointer--
                            pointer--
                            pointer--
                            pointer--
                            pointer--
                        pointer--
                        pointer--
                    pointer++
                    while cells[pointer] > 0
                        cells[pointer]--
                    pointer--
                    pointer--
                    pointer--
                    pointer--
                    pointer--
                pointer--
                pointer--
            pointer++
            while cells[pointer] > 0
                cells[pointer]--
            pointer--
            pointer--
            pointer--
            pointer--
            pointer--
        pointer--
        pointer--
    pointer++
    console.log(String.fromCharCode(cells[pointer]))
fun()

If I run coffee output.coffee I (unsurprisingly) still get the out of memory error. However, if I then compile it to javascript, coffee --compile output.coffee, and execute it, node output.js, it terminates. So a guess as to why coffee fails and node doesn't? We should remember that CoffeeScript treats everything as expressions, including while-statements (or while-expressions if you will), which means that the coffee-to-js compiler probably optimizes away the return value of the while loop. Unfortunately, the CoffeeScript interpreter seems to be naively storing a lot of state under the execution of the while loop because of this fact, which then results in a out of merror error (or at least that is my best guess).

reynir commented 11 years ago

Interesting. I did not think of compiling the code - I have not used coffeescript myself before. I took a look at it. Apparently, it builds up a huge tree (list whose elements are numbers and lists). The values are either pointer or cells[pointer]. It's essentially an execution trace.

The code that's causing the problems would be this as you suggested. The for and while loop are building up a list (Array).

This may be useful http://stackoverflow.com/questions/7391493/is-there-any-way-to-not-return-something-using-coffeescript

dragonwasrobot commented 11 years ago

Since this is only a toy example, I'd rather go for simple code than sprinkle 'undefined' all over the place to please a benchmark program ;)