Dip
Dip is a stack-based Turing tarpit created by User:D.
Commands
| Command | Behavior |
|---|---|
0 |
Push 0.
|
' |
Increment TOS. |
; |
Pop TOS. Append it to the bottom of the stack. |
( _b_ ) |
While loop. (See below) |
While loop
- While (pop stack as
N) !=0:
- push
N-1 - run
_b_as dip code
- push
Examples
Predecessor
A plain (0) would pop the stack with a 0 input.
So we'll need to sneak a 0 value under the stack:
0;(;)
Add
This just does a bounded for loop, which increments the 2OS.
(;';)
Multiply
0; 0; (;(;';';;);0;;) ()()
Computational class
Dip is Turing-complete. One way to demonstrate this is to compile The Waterfall Model to it.
We'll compile the following program to Dip:
[[10, 3, 3, 3], [ 1, 3, 0, 6], [ 2, 0, 6, 3], [ 3, 6, 3, 0]]
The waterclocks are named A, B, and C, respectively.
First, initialize the waterclocks:
0''' 0'' 0'
This pushes C B A onto the stack.
Next, we use the following structure to simuate the outer infinite loop:
0' (() ... 0')
... is where we put the individual implementations of the waterclocks.
Compiling individual waterclocks
We use a ( ... ) loop to simulate an individual waterclock. Here, we simulate the second row of the program.
(; 0' 0 ;; [;]
Walkthrough:
(;
This shifts A-1 to the bottom of the stack. (Configuration: A C B)
0' 0
Push the value of the flag (initially 1) and the preserved A counter, respectively. (Configuration: A C B _flg_ _A'_)
;;
Move the flag and the preserved A counter to the bottom.
[;]
Use #_of_counters - 1 ;s to make A float to the top of the stack. (In this case, two ;s.)
For the rest of this implementation, [;] means #_of_counters - 1 ;s.
Inner loop 1: The flag & A' loop
Then, we use a repeat loop to 1) set flag to 0 and increment our preserved A counter, respectively:
(; ()0; '; [;])
Here's a walkthrough of what each part does:
(;
Decrement the value of A, and move it to the bottom of the stack.
()0;
() discards one value on the stack (i.e. decrements it until it's 0, after which the value is popped). Then we push 0, which sets our flag to 0. Last, we shift the value to the bottom of the stack.
';
Increments A', and shift it down.
[;] )
#_of_counters - 1 ;s, to shift A to the top of the stack again.
Inner loop 2: The actual incrementing
This part is a bit trivial. We were left with the configuration
C B A' _flg_
at the end of our previous loop, so we just need to repeat the incrementing process _flg_ times to simulate the full functionality of the zeroing trigger.
Since we're compiling the first waterclock, here's an implementation:
(;''';;'''''';)
Self-evident, so I won't explain it.
End of outer loop
We need to ensure that our outer loop is exitted after the conditional is done, so we do this:
0)
To switch to the next waterclock (after which you can chain another waterclock implementation), use ;.