Small Brainfuck

[Hippo]

Here is my 330 code solution (not my current best, but at least a solution).
You can see, there are acually aditional threads, as I should generate spaces around the main line at the runtime.

Code: Select all

&\92+024g4\
/}}\!     4
19+s3  $  g
-5,/\  >  s
1+-0)  1 /\
xsp\/  0 |@uu                                                                                       
:\\    -/#/uu                                                                                       
5x/    1,\/uu                                                /  \                                   
x8?    <1  uu /    \                               /                                         \      
-* /==\1^ /x?s\1+x?/1+1+1+1+1+1+1+1+1+1+1+1+1+1+x?s\2]1+1+x?s\x?/1+1+1+1+1+1+1+1+1+1+1+2[1-x?/2]xp! 
|& s  |0- }u  \    /                               \                                         /      
1\]48*\\x }                                                  \  /                                   
[1 |  1@0 }                                                                                         
\/\s<0//:\|                                                                                         
$0{  /\\\@|
w0]| 6\\xs|
-<2s s @|\/
1w}//@:/21 
>\/|720 ^4 
2 [|@g|/:#\
s/2//7-@ |s
2@]027^\8#\
s\\1g\#2\sx
00g<6 \/\\0
0111\623\|s
x-s\+01>\#\
+\\/-w==$s@
1 0\1<00\//
< \1<*9+//2
\009g===/s/

Actually this is the code state at the end of simulation, it started in the 11x30 box.

[Hippo]

Damn, it looked well formated in preview.

Code: Select all

&\92+024g4\
/}}\!     4
19+s3  $  g
-5,/\  >  s
1+-0)  1 /\
xsp\/  0 |@
:\\    -/#/
5x/    1,\/
x8?    <1 
-* /==\1^ /
|& s  |0- }
1\]48*\\x }
[1 |  1@0 }
\/\s<0//:\| 
$0{  /\\\@|
w0]| 6\\xs|
-<2s s @|\/
1w}//@:/21 
>\/|720 ^4 
2 [|@g|/:#\
s/2//7-@ |s
2@]027^\8#\
s\\1g\#2\sx
00g<6 \/\\0
0111\623\|s
x-s\+01>\#\
+\\/-w==$s@
1 0\1<00\//
< \1<*9+//2
\009g===/s/

Actually using } instead of 2] would short the code, but for >>> the 6] would become better (what I have not implemented) and actually test cases seems do not contain more than two consecutive >'s so it's definitely thing to consider not only in code size optimization challenge, but even in time optimization challenge.

[Hippo]

And

Code: Select all

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

Could be compiled to

Code: Select all

\sssssss/ssss=\ssssss/ssssssss=\s 
\001+x?s/}+,x?\{1-x?s/1+xp{1-x?\!
ssssssss\=ssss/ssssss\=ssssssss/s

(leading x? could be removed (without look at inputs) but question is if it would be worth doing)

Here is an idea for speedup:

Code: Select all

001+s/x?\{1-s/x?\!
     \/@/    \/@/ 
      }       1   
      +       +   
      ,       x   
      $       p   
              {
              1
              -   
              $   

Pros:
1) Loops are treated as repeated function calls so "looping" in long loops is faster.
2) Speedup on the fly is possible as alternative function implementation can be plugged by changing just one slot.
Cons:
1) Compillator should take care on topology when there are nested loops
Here is the accelerated case (compiller must know the used addresses):

Code: Select all

===31<+}41<+{s/x?\{xp!
             /\s@/    
             5 }      
             1 1      
             < +      
             + {      
             5 1      
             1 -      
             > $      
             0
             $        

[a.goth]

Wow, I am even more impressed. You wrote a multi-threaded compiler which is smaller than my interpreter. (In fact, I have a smaller interpreter, but it requires too many cycles.) First, the whole Brainfuck program is loaded into memory cells (0++, 0). The memory cells (0++, 1) are used as the tape. An instruction pointer is stored at (0, 2), a data pointer at (1, 2), and a brackets counter at (2, 2):

Code: Select all

.[] /%,x\          /======\s\
  /=:g94/>02+1<02[1/s>12+<\\0
/s\s\==s\020<<x13g-xx*1:21/|>
>  /<<121=/?-1*xx-g60x?/<<p/0
0  \1v-\ !\1[x00g-?\121/   s2
2/><121/s,:^1g60===/       |x
+?        \02g-?\===121<<?s//
12   /02/s?<<121/
<0   <  \122>s/020<1+x20><x0\
\/s02/s======\\/s?-g20/s?-g1/
             |s\22<1-\\?22\
             \\?=>22x/s+1</

So far I have not fully understood your source code. For that I need a better SuperHack IDE. Currently I use the one from eike42. What do you use? But I see that you also found no simple solution for nested loops. Thank you for sharing your source code!

[Hippo]

Actually nested loops are simple in the already implemented code, which didn't try to be fast so no
s's are used for back loops ... you count number of opened ['s and put '/','\' given number of lines above or under ('\' is switched with '/' when [ is switched with ]).

When using s's an option is to use 1,3,5,7 and -1,-3,-5,-7 line distances to speed up compilation.
using of all lines requires to replace of s by # on too many places (I don't know whats better ).

I have tried to read the code today ... the left down corner writes the code, a lot of ways lead here with parameters "from which place to copy the instruction". It uses global "column pointer at (0,0)".
OK (0,1) contains number of opened ['s. ... It would help to rewrite the instructions in branches to lines for reading (without \/s instructions and rewriting ?,: as comments)... the code sharing and combining the paths made it hard to read ...

Loop in middle of 2nd and third column is used by other threats to allocate the space for loop paths ... they use the (0,0) pointer. I have not checked the part compiling [ and ] insructions. ... OK I have finished reading ... columns 0 and 2 contain at propper rows the code for compilation so the table is used instead of a lot of cases ... it is used for +,-.<> instructions and 8th row for [] instructions as well.
position 23 is used for the [ case and \/ are placed by 01<*9+00<1-w command to do nested loops.
instruction and (+/-1) must be on stack. Even when there is codding table, there is a lot of code shared by several branches (the 1-w addressing is used to prevent rewriting by spaces spaces could be put to 00<1+ as another option ... but chosen version have t least 24 steps among increments of 00 pointer and fillers needed 12 steps to fill so they do it for sure, with 22 steps and 14 steps to fill there could be "gaps" created in the code).

I have written Excell VBA interpretter for SuperHack.
Actually it differs in encodding of nonascii characters, but otherwise it well matches php implementation. It is slow, but I often trace code cycle by cycle and it's perfect there.
It does a lot of logging, so much that I do not read it ... history of all cells, history of memory pointers ... it colors code and memory by timecolor it was accessed last ...

Writing big superhack code elsewhere than in spreadsheet or at least "columnbased editor" must be pain...

[Hippo]

Few notes to your code: Accessing stack is faster than memory so I would try to have memory pointer at 2nd row to have fast access to PC and MP. (Question is if it would be stored by > command or v would be faster.)
"," command nicely joins +/- path.
The loop implementation is really (time) bottleneck in the interpretter (it costs a lot of time to detect the loop and a lot of time to find where to jump). I would expect jumps to be precomputed in interpret.
(Actually this is the only place where interpretter gains against (original) compiller as long jumps just rewrite the PC while superhack needs to loop).
BTW: Using @ often simplifies the layout (for the time cost of 2, what is compensated by a lot of needed /\ otherwise).

[a.goth]

Actually using } instead of 2] would short the code, but for >>> the 6] would become better (what I have not implemented) and actually test cases seems do not contain more than two consecutive >'s so it's definitely thing to consider not only in code size optimization challenge, but even in time optimization challenge.

I am not an experienced Brainfuck developer, but after inspecting some examples, I think it is more useful to translate +{n} into n+ and -{n} into n-, respectively. Looks as if consecutive angle brackets were less frequent. Nonetheless, a nice trick to use only every other memory cell.

It might further be useful to identify no-ops such as >>><<< and not to compile them. Just a thought.

[a.goth]

Actually nested loops are simple in the already implemented code, which didn't try to be fast so no s's are used for back loops ... you count number of opened ['s and put '/','\' given number of lines above or under ('\' is switched with '/' when [ is switched with ]).

When using s's an option is to use 1,3,5,7 and -1,-3,-5,-7 line distances to speed up compilation.
using of all lines requires to replace of s by # on too many places (I don't know whats better ).

Very well, but let me put it this way, you found no much better solution than me and I would not call this solution simple. I was kind of hoping that nested loops could be arranged as a one-liner.

[Hippo]

Oh OK simple is relative . Your compiller cycle solution was hard to extend to nested loops, my original layout works for arbitrary level of nesting (level 4 is max, but starting on line 9 would allow levels upto 9).
One liner for general while cycle is impossible. Oneliners are possible for cycles of known maximal number of repetitions. ... oh there is 300 brainfuck rounds limit ... so may be ...

+{n} is what I am working on, but the problem is SVHM n encodding one can use 57< for small number of constants or their "translation to expressions". I am going to use 9+9+3+ instead. Again I have not seen more than +{18} in test cases so for test cases this is optimal with no need of fast addressing.

[a.goth]

The loop implementation is really (time) bottleneck in the interpretter (it costs a lot of time to detect te loop and a lot of time to find where to jump). I would expect jumps to be precomputed in interpret.
(Actually this is the only place where interpretter gains against (original) compiller as long jumps just rewrite the PC while superhack needs to loop).

Yes, detecting loops cost a lot of cycles. Assumption was that the test cases do not contain too many loops. In other words, the other commands are presumably more frequent. At least the re-entry point of the loop is stored on top of stack for a quick loop back. This is also the reason why IP, DP, and BC are stored in memory and not on the stack. Otherwise, the stack is too crowded.

I think this approach to solve the challenge is maxed out and cannot be improved very much. I am already working on a different approach to reduce the code size of the interpreter.

[Hippo]

This is also the reason why IP, DP, and BC are stored in memory and not on the stack. Otherwise, the stack is too crowded.

I often use construction like 5^1+00> to increment 0,0 memory when I know memory pointer is on 0,5.
You could take from the access methods what is (shorter/faster) (of course it saves really small code size).

In the compiller example I had variable depth of stack so only the 00<1+00> method worked.

[a.goth]

How small is your smallest solution? My last approach resulted in an interpreter with code size 189:

Code: Select all

/%,x\/-\ /02^<x01gd?s!-11^0\  /-x35*-?\14^<p$ /9+-xx*1\/,15^>$
:g10//s+\?d9^2\//s=0s/s*x+0s/-=\g60$?^2\xx*1:x=\8=sv3v3\:14^<+\
\6]s\20g1@/1[1/\:x3^?/116^<?/+s\3v+2v2v/    \0s\4v1v-3v/$0>^41/

I have no clue how to make this spaghetti code even smaller. Moreover, this solution requires too many cycles. Stupid limit! Any advice? Nevertheless, I have one last idea to solve the challenge.

[Hippo]

I am at size about 270 with my compiller (it still have bugs and I bet 288 would easily solve it).
I don't think I could do it much smaller.

[a.goth]

Yes, I have climbed the hill!

Next, I might try to solve challenge 'Super Fast Brainfuck', although I still do not know how to use or synchronize threads in SuperHack. For questions, I get back to you via PM if that is okay?

[Hippo]

Yes, I have climbed the hill!

Next, I might try to solve challenge 'Super Fast Brainfuck', although I still do not know how to use or synchronize threads in SuperHack. For questions, I get back to you via PM if that is okay?

Wow, congrats You have improved a lot. ... You could PM me, but I prefere public talk about challenges.

Synchroniying threads: Just remember the & creates thread with highest number ... it will make one step in the cycle it was born. First thread makes step fisrt ... .

The main problem is sharing memory/stacks ... it's better to place their MP to separate places as fast as possible. (I often made a mistake with stack collisions).