SuperHack

[Allosentient]

Are you trying to make my brain explode or something Adum?

[gfoot]

This code doesn't do what I'd expect, in the PHP version:

Code: Select all

9}00<!

After '}' the stack seems empty, whereas I'd expect it to contain a zero or something random. In the Javascript version, the stack at this point has one entry, which is printed blank, which is also inconsistent (you could never put that value onto the stack).

Then, after the '<' instruction, in PHP the stack changes from 0,0 to 9,0, which is bizarre - it should go to just one entry, 9, if that input stack was correct. Or if the input stack was actually x,0,0 then it should go to x,9.

Which is the reference implementation - the PHP or the Javascript? If it's the PHP version then could you please publish the source code?

[m!nus]

i second that.

also:

Code: Select all

9}1[00<p!

whereas the js version behaves correctly:

Code: Select all

9 (0,0) [9]
} (1,0) []
1 (2,0) [,1]
[ (3,0) []
0 (4,0) [0]
0 (5,0) [0,0]
< (6,0) [9] <-- 9 on the stack
p (7,0) []
! (8,0) []

the PHP version shows 0

Code: Select all

[Thread 0] 9 @0,0 []
[Thread 0] } @1,0 [9]
[Thread 0] 1 @2,0 []
[Thread 0] [ @3,0 [1]
[Thread 0] 0 @4,0 []
[Thread 0] 0 @5,0 [1]
[Thread 0] < @6,0 [0,0]
[Thread 0] p @7,0 [0]
[Thread 0] ! @8,0 []
Array ( [result] => 0 [message] => [cycles] => 9 [output] => 9 ) 

the output is still 9 though

[adum]

i apologize that the VM's aren't totally robust yet. hopefully we can fix any issues soon.

as someone requested, here's the source for the PHP VM:
http://www.hacker.org/sh/shphp.phps

i haven't had time to look over the 'v' instruction yet, or the differences in accessing undefined memory.

the PHP is meant to be the definitive VM because that's the one that grades the challenges. but i'd like the JS to work identically for all reasonable input.

adum

[ShardFire]

After seeing the source and actually reading it properly it is obvious why the v instruction fails. When splicing the array, all numbers after the splice point are now shifted one to the left in memory. This is fine in HVM because that's the whole point, and the spliced value is put back onto the end of the array using push presumably. However, if the memory pointer lies to the left of defined memory then we only want those values between the rotate point and the stack pointer to shift left in address (not including the parameter to v). But instead this happens all the way along to the end of that row of memory. And then when the spliced value is pushed back on it overwrites the parameter to v, when in fact it should be inserted before it, and the entire array is decreased in length by 1. So basically you just need to use the inverse function of array_splice instead of pushing the spliced value and that problem is fixed.

As for the debug output the main problem is that using implode seems to ignore undefined values, and also the trace line is written before the shvm instruction is executed rather than after which is when it should be done (as in the js version).


OK I found how to fix it in javascript version

'v': function() { var i = Pop(); var v = Memory[t['mY']].splice(t['mX'] - i, 1); Memory[t['mY']].splice(t['mX'], 0, v[0])},

Also in the javascript one, I would like to request some other changes

traceBuffer += tindex + ': ' + instruction + ' (' + ox + ',' + oy + ') ['+Memory[t['mY']].slice(0, t['mX'] + 1)+']\n';

Actually the ox and oy variables aren't required, just use the t['pcX']...

And please delete traceOutput.value = traceBuffer; and put it AFTER the try catch block so that it doesn't freeze the browser! And same for HVM...

Thanks!

[adum]

thanks shardfire -- your analysis seems good. i have implemented all your suggestions. please let me know if you see any further problems. i have made the corresponding change in the PHP version.

[MagneticMonopole]

This is my view of how the normal stack of SHVM works. Might be completely wrong; if so, I am perfectly willing to reconsider . But maybe it is of some help.

Normal stack and memory layout:


The "normal" stack uses the upper line of memory.
With S0 being the top of the stack, the situation is

Code: Select all

  S0        S1        S2       mem(0,3) mem(0,4) ...
  mem(1,0)  mem(1,1)  mem(1,2) mem(1,3) mem(1,4) ...
  ...

The memory used as stack can be addresses like normal memory.
Consider the example:

Code: Select all

   7 00<p!  --> "7"

(we push "7" on the stack and recover this "7" be reading memory at (0,0).)
Please not that "7" remains on the stack!

Same example with three values:

Code: Select all

    789 00<p 01<p 02<p !  -> "789"

Stack and "}":


Example:

Code: Select all

   000>001>002>010>011>012> 98 } 7 00<p 01<p 12<p !  -> "987"

Explanation:
Memory content is

9 8 0 . . .
0 0 7 . . .

Stack wanders down, but stack x position remains!

Furthermore:

Code: Select all

   000>001>002>010>011>012> 98 } 7 00<p 01<p 12<p ppp !  --> "987700"

Memory:

9 8 0 . . .
0 0 7 . . .

So we can pop values from the stack we have never pushed on it (here: twice "0").


Stack and Threads:

Do threads share a stack? Does each thread have its own stack?
The truth is much more horrible:

Consider

Code: Select all

  &\1  p
   \2 p!

Result: "22"

Why? The trace shows the answer:

[Thread 0] & @0,0 []
[Thread 1] \ @1,0 []
[Thread 0] 1 @2,0 []
[Thread 1] \ @1,1 []
[Thread 0] @3,0 [1] <-- here the stack of thread 0 has loaded "1" - ok.
[Thread 1] 2 @2,1 []
[Thread 0] @4,0 [2] <-- now the stack is [2]. The "1" got overwritten by thread 1.
[Thread 1] @3,1 [2]
[Thread 0] p @5,0 [2]
[Thread 1] p @4,1 [2]
[Thread 0] @6,0 []
[Thread 1] ! @5,1 []

However, both "p" instruction work - no stack underflow error.

Why is that?

Well, there is no thing like a stack . There only is stack pointers (called memory pointers in the SHVM description) and memory.
Stack pointers advance through memory (right during push, left during pop).
Pushes to the stack write to the memory cell that happens to be under the stack
pointer and move the stack pointer right,
pops move the stack pointer left and then read that memory cell.

Enter threads. Threads share the memory, but indeed do have seperate stack pointers.
Starting a thread with "&" simply makes a copy of the parent's stack pointer,
but not the stack memory. The stack pointers of both threads point to the same memory region!

In above example, both threads use the memory at (0,0) (0,1) (0,2) ... as stack.
Their initial stack pointer is (0,0).
Thread 0 writes "1" to (0,0) and advances its stack pointer to (0,1).
Thread 1 writes "2" to (0,0) and also advances its stack pointer to (0,1).

Then, thread0 does "p", writes the contents of (0,0) - which is "2"- and lefts its stack pointer to (0,0) again.
The stack pointer of thread1 remains unaffected at (0,1).
When thread1 encounters "p", it lefts its stack pointer to (0,0) and prints "2" as well.

(What? Ok, but there SHOULD be verbs for that!)


So, to have separate stacks for threads, one should use "}" soon after &. Anything else is asking for madness.

[MerickOWA]

Just a clarification but memory would be ...

Code: Select all

9 8 2 . . .
0 0 7 . . .

Since the main thread is using memory location (0,0) (0,1) (0,2) when you're doing your

Code: Select all

010>011>012>

2 is the last value left in location (0,2) and thats the last time it's touched.

I agree that threads should do a '}' command just after the '&' command. I suppose as an alternative you could do "9]" or something similar to give the new thread stack room in memory.

If someone finds a use for having 2 threads sharing stack for some kinda communication that would indeed be madness/genius

[therethinker]

I've noticed a small JS bug in both SuperHack & HackVM that I keep mentioning to bring up. If you select "Show Trace", long programs take forever to run. The program itself isn't slow, really the textbox is just refreshing 50K times with lines and lines of text.
To speed it up, rather than write to the trace at each step, have an output accumulator variable and write to the textbox at the end.


@MagneticMonopole: awesome explination.



I don't understand why

Code: Select all

9p1[p!

Throws an error rather than printing two 9's.

[MagneticMonopole]

Hm. I'll give a try.

Code: Select all

9p1[p! 

SP=Stack pointer

Code: Select all

cmd  mem   SP
9    9 . . (0,1)
p    9 . . (0,0)
1    1 . . (0,1)
[    1 . . (0,-1)
p    1 . . (0,-2)

p with stack pointer (0,-2) --> Stack underflow error.
Interesting to see that moving the stack pointer too much left causes no error until the stack is actually accessed.

consider

Code: Select all

789p1[p! 

which gives "97".
Here, "1[" skips the "8" on the stack.

What you probably meant would not happen to be

Code: Select all

29p]p!

?

[MerickOWA]

Code: Select all

9p1[p!

9 is stored in location (0,0), stack pointer now pointing to (1,0)
p takes the pops value at (0,0) and print it '9', stack pointer pointing at (0,0)
1 puts one in location (0,0), stack point now at (1,0)
[ pops value at (0,0), stack pointer now at (0,0).... now it tries to subtract 1? from the stack pointer which is already at 0 and gets an underflow exception.

if you change this to "]" then the stack pointer would add one instead and now be at (1,0) and "1" is now on your stack since this is the value at location (0,0)

p would then pop the 1 off the stack and print it.

Its kinda hard to "resuse" that 9 in memory because adjusting the stack pointer requires a number to be pushed onto the stack to know by how much the stack should be shifted by... which overwrites the very value you're trying to preserve in memory.

Perhaps if there was an instruction like "}" or "{" which shift left or right by one ... maybe '(' and ')' then you could write

Code: Select all

9p)p!

[gfoot]

therethinker: After "9p" the stack pointer is back at (0,0). Your "1" then overwrites the residual 9. The error is because after "[" pops its argument (the 1) the stack pointer is back at (0,0), and moving left by one is an error. You probably meant "]", which works for me, printing "91".

MerickOWA: be careful using 9] to reserve memory - the 9 goes on the stack again, so you need to make sure the other thread is vaguely idle for an extra cycle or two there. } is safer because it's one op and doesn't use the stack.

A couple of things seem quite hard - e.g. looping to programmatically step up/down several locations without corrupting everything. Self-modifying code seems the best way to do that, but is awkward to construct.

[tails]

Hi,

I made a code for Jeux du Sort challenge which worked in JavaScript, but was never accepted as the solution. So, wondering why, I studied PHP and read the SuperHack PHP source, and then noticed that PHP acts terrible way when doing array_splice().

Consider this example of PHP code:

Code: Select all

$a=array();
$a[1]=6;
$a[3]=7;
$a[4]=8;
print_r($a);  // (a)
array_splice($a,1,1);
print_r($a);  // (b)

(a) prints:
Array ( [1] => 6 [3] => 7 [4] => 8 )
this is OK.

I expected (b) to print:
Array ( [3] => 7 [4] => 8 )
but it was not true.
(b) prints:
Array ( [0] => 6 [1] => 8 )
thus, it seems as if all the indices are renumberd before splicing.

In the SuperHack source, array_splice() is used for 'v' instruction. So, it will be very dangerous when we use 'v' especially after moving the stack pointer to the right or when we have some isolated values in the line of the memory, because the line will get shuffled.

To workaround this, I'd like to suggest two solutions. (1) Instead of using array_splice(), rotating the values one by one in a loop. (2) Initializing all the memory cells to zero beforehand. Either of the two should improve the situation. I'd prefer (2) because it will also solve the "undefined" stuff.

[tog]

Oh, thank you for this analysis! This just saved me debugging a similar effect in my code. And btw: This also seems to be the reason for the trace-output of the stack being messed up.

[adum]

very sorry about this. i've changed the code to init all memory to zero. sorry about the trouble! thanks for the debugging, tails...