Brainfuck

[CraigD]

Craig, perhaps you didn't read my previous post, i am writing a brain**** compiler in brain**** (it will compile into x86 assembly) well or at least laying it out now.

So, lemme get this straight, Alexander: you’re writing a Brain**** program – a string of “+”, “,”, “-“, “.”, “<”, and “>”s, lets call it A – that will read a stream of these same characters – lets call them B – and write an assembly language program in x86 opcodes and arguments, which, compiled into an executable and that executable executed, will output what B would output if interpreted as a Brain**** program?

 

Seems to me that the interesting part of this is writing the part of A that interprets B – “a brain**** interpreter written in brain****”. Once A has produced the output of B, it should be pretty easy (some someone who knows x86 assembly language adequately! ;)) to output a simple “wrapper” assembly language program equivalent to the python/BASIC program:

print “

the output of B goes here

”

I’d be impressed just to see a version of A that read B and wrote the output of B – “a brain**** interpreter written in Brain****”, or, if you find it catchier “a universal brain**** program” (UBP). :P

…or that other programming classic, a Brain**** program that produces itself as output? :)

This is another classic programming task. Such a program is known as a quine. How short a quine is possible in a give language is considered by some to say something deep about the language.

 

Per Gary Thompson’s quine page , AFAIK the best authority on them, the record for the shortest brain**** quine is 978 characters, so the challenge, I’d say, is to beat that. :)

 

It’s also interesting to write little programs to do elementary things. This one:

,>,[-<+>]<.

for example, accepts 2 single bytes and outputs their sum. A usable base ten calculator would be cool.

[alexander]

a friend of a friend of mine is working on a calculator, if i am not mistaken a float point calculator at that... i'll see if that ever gets accomplished :P

 

Oh and i am nearly there with my design...

 

i have identified the two stages of this project, first get the 6 simple instructions compiling (<>-+,) and then the looping functions

 

all code should be compilable with NASM

 

here's what i have so far:

 

every program starts with

[bits 32]

extern _putchar
putchar equ _putchar
extern _getchar
getchar equ _getchar
extern _GetProcessHeap@0
GetProcessHeap equ _GetProcessHeap@0
extern _HeapAlloc@12
HeapAlloc equ _HeapAlloc@12
extern _HeapFree@12
HeapFree equ _HeapFree@12
extern _ExitProcess@4
ExitProcess equ _ExitProcess@4

global _start
_start:

call GetProcessHeap
push dword 30000
push dword 8
push eax
call HeapAlloc
mov esi, eax
mov edi, eax

L0.0:

 

the instructions for the first stage are:

 

>

inc edi

<

dec edi

+

inc byte [edi]

-

dec byte [edi]

.

xor eax, eax
mov al, byte [edi]
push eax
call putchar

,

call getchar
mov byte [edi], al

 

 

finally close with

L0.1:
xor eax, eax
mov al, byte [edi]
push eax
call GetProcessHeap
xor edi, edi
push esi
push edi
push eax
call HeapFree
call ExitProcess

 

the last two characters are dependent on the level that they are in or rather how far into loop structure they are so

 

[

L#.0:
mov al, byte [edi]
test al, al
jz L#.1

 

and ]

jmp L#.0
L#.1

 

the numbers represent how deep the loops are for convenience

 

here's an example that you posted

,>,[-<+>]<.

 

translation into assembly looks like this (just so you can get a feel for it):

[bits 32]
extern _putchar
putchar equ _putchar
extern _getchar
getchar equ _getchar
extern _GetProcessHeap@0
GetProcessHeap equ _GetProcessHeap@0
extern _HeapAlloc@12
HeapAlloc equ _HeapAlloc@12
extern _HeapFree@12
HeapFree equ _HeapFree@12
extern _ExitProcess@4
ExitProcess equ _ExitProcess@4

global _start
_start:

       call GetProcessHeap
       push dword 30000
       push dword 8
       push eax
       call HeapAlloc
       mov esi, eax
       mov edi, eax

L0.0:
       call getchar
       mov byte [edi], al
       inc edi
       call getchar
       mov byte [edi], al

L1.0:
       mov al, byte [edi]
       test al, al
       jz L1.1
       dec byte [edi]
       dec edi
       inc byte [edi]
       inc edi
       jmp L1.0

L1.1:
       dec edi
       xor eax, eax
       mov al, byte [edi]
       push eax
       call putchar

L0.1:
       xor eax, eax
       mov al, byte [edi]
       push eax
       call GetProcessHeap
       xor edi, edi
       push esi
       push edi
       push eax
       call HeapFree
       call ExitProcess

[CraigD]

Oh and i am nearly there with my design...

I’m impressed! :P Assembly language programming makes me long for the days when I had some idea what was actually going on with my underlying hardware, before I was seduced into a career of programming in high-level languages. :)

 

One point: you write

…

L0.0:

 

…

the last two characters are dependent on the level that they are in or rather how far into loop structure they are so

 

[

L#.0:
mov al, byte [edi]
test al, al
jz L#.1

 

and ]

jmp L#.0
L#.1

 

the numbers represent how deep the loops are for convenience

I believe you may be misinterpreting how brain**** should interpret “[” and “]”. When “[“ is encountered and the current pointed-to data byte is zero, the program pointer should advance to the next “]”. When “]” is encountered and the byte is not zero, the program pointer should retreat to the previous “[“. This doesn’t have nesting, nor require that “[]” be matched the way “()”s and “{}” are in typical programming languages. For example, “>>>+++++++++++++[<++++++<<++++>>>-]<<<[>]+<-][.]<[.<<[.>>>]” is a valid program with output “M3” and stops.

[CraigD]

When “[“ is encountered and the current pointed-to data byte is zero, the program pointer should advance to the next “]”. When “]” is encountered and the byte is not zero, the program pointer should retreat to the previous “[“. This doesn’t have nesting, nor require that “[]” be matched the way “()”s and “{}” are in typical programming languages. For example, “>>>+++++++++++++[<++++++<<++++>>>-]<<<[>]+<-][.]<[.<<[.>>>]” is a valid program with output “M3” and stops.

I’m wrong in the above. Per the wikipedia article “brain****”, the []s must be matched, and interpreted in the normal, nested.

 

This makes it much easier to use, but IMHO considerable less fun! :P

[alexander]

it does have to be matched per original specification, actually i dont think its in the original specification either, its soooo vague, lol. But since there are a gazillion different implementations of brain****, and slight variants and derivatibes, in some, you are totally right in saying this. However, i might eventually create a version that will do what you are talking about, but there are so many ways to make my goal implementation better by generating better code, cool thing is that you can then compile that code with this code, and then recompile that code with the compiler compiled with that code again to get a more efficient compiler and then the whole cycle begins again, it's actually how gcc got started, which is a neat thing to reference, considering that at some point it was thought pointless and useless to write a compiler in the same language it compiles... lol :P

[Dianenoleen]

i love puzzles :P

 

the answer is

 

01000010011100100110000101101001011011100110011001110101011000110110101100100000011001100111010101100011011010110111001100100000011101110110100101110100011010000010000001111001011011110111010101110010001000000110001001110010011000010110100101101110001000000011101000101001

 

and in reply

 

yes it does lol

[GAHD]

if you like brain****, you may also like COW

[CraigD]

Hi Dianenoleen, and a belated welcome to hypography! ( :lol: on naming your oldest, BTW :eek: )

the answer is …

As a test to see if you’re interpreting brain****, or just translating ASCII to binary (in short, a rought classification of your geekitude), what’s the output of

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

:eek:

Another challenge: who can write an algorithm (in their language of choice, including pseudocode or precise English), that will generate a shortest brain**** program that generates a given output?

[alexander]

GAHD, COW looks like a slightly atypical brain**** derivative, though may be not, it's actually easier then brain****, because of more available commands and things you can do. And you can probably write a brain**** to COW converter :phones:

 

72 121 112 110 103 114 97 112 104 121 32 114 117 108 101 115 33

 

you forgot a 10 at the end for good measure, Craig :P

[alexander]

also here's a more efficient version of your program

 

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

[Dianenoleen]

OK lol i get the message "Hypography rules!"

 

Do i get a badge saying geek yet? :cup:

[alexander]

you would have to prove your geekdom.... if you wish to, it will take 5 sets of questions in another thread, but if you are a true geek, should pass fairly easily :cup:

[CraigD]

OK lol i get the message "Hypography rules!"

 

Do i get a badge saying geek yet? :naughty:

Alas, we don’t have a geek badge feature installed on hypography at present, but you are now officially on my personal honor-roll of those who can not only talk the geek talk, but walk the geek walk, Diane!

 

I eagerly anticipate being awed by you geekish brilliance in posts to come, a feeling I hope is mutual.

[CraigD]

also here's a more efficient version of your program

 

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

Indeed it is! :)

 

It’s 157 characters long, and outputs “Hypography rules!” in 587 steps (counting its halt step).

 

Here’s one with the same first 51 characters that’s 2 characters and steps shorter:

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

>.>+.---------.-.>-----.<+++.>------.<--.>+++++++.<+++++++++.>>----.

<<-------.+++.>++++.-------.<--.>>+.

 

I brute-force checked, and the above is the shortest that begins with these 51 characters.

 

Here’s one with 167 characters that completes in 476 steps:

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

>.>+.---------.-.<+++++++++++++++++++++++++++++++.>+++.<------.>--.<+++++++.>+++++++++.>----.

<-------.+++.<++++.-------.>--.>+.

 

I remain challenged to write a program that generates the shortest possible program that outputs a given string, or the program that outputs a given string in the fewest possible steps. Though simple to state, I think it’s a pretty deep problem.

[Southtown]

Well, thank God. For a while there, I actually thought I was a geek. lol :hihi:

[alexander]

no no, lets not get ahead of ourselves, South :confused: course you are a geek

 

btw craig, i have come up with another way to do that same task in the same amount of characters, thought you might be interested in how weird this code is ;)

 

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

 

[alexander]

and here is another way to do this in 155 characters

 

 

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