Super Brainfuck

[Hippo]

I have a question to solvers:
Did you codded compiler or interpretter?

My codes so far are compilers. I still don't know how the fast version would look like ...

[a.goth]

Did I miss something? How are the Brainfuck challenges solved with a compiler?

[Hippo]

Did I miss something? How are the Brainfuck challenges solved with a compiler?

My (single threaded) code used w instruction extensively (compiled to shvm) and than after end of bf code was found it went to the "entry point of the compiled code".

BTW: Now I am working on "Accelerator" ... it would be more interpretter than compiller (I am not sure there would be compiller portion at the end).

My code transformation so far reduced the code set to +()>().,[], I am going to get rid of >() somehow, and I am planning to remove [] cycles (at least easy ones ... and quiestion is what are the easy ones).

Symplifying cycles depending on inputs is almost nonsense, but even nested cycles could quickly become unmanageable. So I am ready to resign optimisation at some complexity level ... testing cases gave the bounds where to stop optimisation.

So maybe cycles including inputs would be compiled at the end. ... I am afraid that optimisation overhead could be too huge to be paid off at small test examples the challenge provides.

[a.goth]

Oh yeah, now that you mention it. Initially, I had also considered to solve the Brainfuck challenges that way. The idea was to translate Brainfuck programs into SuperHack using the following substitutions:

Code: Select all

Brainfuck command | SuperHack equivalent
------------------+---------------------
(Program Start)   | %0
(Program End)     | !
>                 | }
<                 | {
+                 | 1+
-                 | 1-
.                 | xp
,                 | 1[,

Finally, each [] loop can be coded idiomatically, using s\/?x commands.

Consider the following trivial Brainfuck program for a better understanding:

Code: Select all

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

This is translated into the following SuperHack program:

Code: Select all

        /x?\            \       /x?\               \
%0  1+  / s\  }1[,  x?\s\  {1-  / s\  1+xp{1-  x?\s\  !
        \             /         \                /

I found it very inconvenient to translate nested loops in this manner and I feared that the compilation could violate the cycle limit. That is why I had rejected this idea and instead began an interpreter. Maybe I revive the idea, but I would be curious to see the source code of your compiler. In fact, I am pretty impressed that your compiler uses less than 10,000 cycles.

Furthermore, I believe that you need a small, fast interpreter to solve challenge 'Super Fast Brainfuck'. Therefore, I plan to solve challenge 'Tiny Brainfuck' first and then start to optimize the solution. Maybe you want to discuss this challenge with me? Consequently, I have not thought much about optimization. I am sorry!

[Hippo]

Unfortunately I have only solutions not longer than 330 instructions so I should publish it in another thread, but You have already solved it so we can continue talk there.

Essentially your proposal is fine, {} is better than mine solution, +, is faster than 1[,.
My code is almost unraedable to me now.

No, I don't think I need help here, I just point to an interesting Challenge.

[a.goth]

That is right, if the program starts with %00 instead of %0, then you can replace 1[, by +,. Or you can use a different arithmetic operation. Nice trick.

I will post my solution of challenge 'Small Brainfuck' within the next few days in the appropriate thread.

And yes, the SuperHack challenges are really interesting.