(07-10-2018 07:17 AM)Thomas Klemm Wrote: Not a suggestion but looking at Thomas Okken's program here:
Code:
<< DUP 1 - -> n n1
<< 1 n FOR i i INV NEXT
n 1 + n n1 + FOR i n1 DUPN i INV NEXT
n DUP 2 ->LIST ->ARRY
>>
>>
I wonder how you would ever end up with something like this:
Code:
double[][] hilbert(int n) {
double[][] h = new double[n][n];
for (int j = 0; j < n; j++)
h[0][j] = 1.0 / (j + 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - 1; j++)
h[i][j] = h [i - 1][j + 1];
h[i][n - 1] = 1.0 / (i + j + 1);
}
return h;
}
Commands like DUPN, ->LIST or ->ARRY consume or produce an arbitrary number of parameters. We know their exact numbers only at runtime.
Thus using local variables like in case of + or MOD wouldn't work.
Yes, those commands are trouble, one way to handle them could be for this decoder to explicitly output those "push/drop" that I was doing in the background, then have special rules to cancel them out and remove them in the cleanup phase. The stack would then be used as a vector, and whatever is not removed would look like the user storing elements in a vector.
Now the C code you show is not the target of this decoder, I wasn't thinking of specifically targetting constructs of a different language, but mostly to help the reader understand the algorithm by turning it into code in a language he's more familiar with. The decoder cannot rewrite an algorithm, merely try to present it in a way the programmer would be able to understand and "recode" properly in a language of choice.
Back to the example you presented, with explicit stack being output for example with a vector called 'stk' and an index called 'stkidx':
Code:
<< ----> output 'function fcn1() {'
DUP ----> Empty stack! The decoder will need to detect this and push 'arg1', while adding the argument to the function declaration above 'function fcn1(arg1)'. Now we make the pushes explicit: output 'stk[stkidx++]=arg1'. After that bit, output 'l1=arg1', 'stk[stkidx++]=l1'
1 -----> 'l2=1', 'stk[stkidx++]=l2'
- -----> output 'stkidx--', 'stkidx--' (drop 2 arguments explicitly), 'l1=l1-l2', 'stk[stkidx++]=l1'
-> n n1 << -----> output 'stkidx--','stkidx--', 'n=arg1', 'n1=l1'
1 -----> 'l3=1', 'stk[stkidx++]=l3'
n -----> 'l4=n', 'stk[stkidx++]=l4'
FOR i -----> 'stkidx--', 'stkidx--', 'for i= l3 to l4 {'
i -----> 'l5=i', 'stk[stkidx++]=l5'
INV -----> 'stkidx--', 'l5=1/l5', 'stk[stkidx++]=l5'
NEXT -----> output ' } '
n -----> 'l6=n', 'stk[stkidx++]=l6'
1 -----> 'l7=1', 'stk[stkidx++]=l7'
+ -----> 'stkidx--', 'stkidx--', 'l6=l6+l7', 'stk[stkidx++]=l6'
n -----> 'l8=n', 'stk[stkidx++]=l8
n1 -----> 'l9=n1', 'stk[stkidx++]=l9'
+ -----> 'stkidx--', 'stkidx--', 'l8=l8+l9', 'stk[stkidx++]=l8'
FOR i -----> 'stkidx--' 'stkidx--' 'for i= l6 to l8 {'
n1 -----> 'l10=n1', 'stk[stkidx++]=l10'
DUPN -----> 'stkidx--', here output NDUPN as a loop 'for tmp1=1 to l10 { stk[stkidx++]=stk[stkidx-l10] }'
i -----> 'l11=i', 'stk[stkidx++]=l11'
INV -----> 'stkidx--', l11=1/l11', 'stk[stkidx++]=l11'
NEXT -----> ' } '
n -----> 'l12=n', 'stk[stkidx++]=l12'
DUP -----> 'l13=l12', 'stk[stkidx++]=l13'
2 -----> 'l14=2', 'stk[stkidx++]=l14
->LIST -----> 'stkidx--', and implement it as a loop as well: ' l15={ }', 'for tmp2=0 to l14-1 { l15[tmp2+1]=stk[stkidx-l14+tmp2] } 'stkidx=stkidx-l14' 'stk[stkidx++]=l15'
->ARRY -----> 'stkidx--', and implement as a loop as well: 'l16=[][]', 'for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } } stkidx=stkidx-l15[1]*l15[2] stk[stkidx++]=l16'
>> -----> ' } '
>> -----> ' } '
Which results in:
Code:
/*function fcn1() {*/
function fcn1(arg1) {
stk[stkidx++]=arg1
l1=arg1
stk[stkidx++]=l1
l2=1
stk[stkidx++]=l2
stkidx--
stkidx--
l1=l1-l2
stk[stkidx++]=l1
stkidx--
stkidx--
n=arg1
n1=l1
l3=1
stk[stkidx++]=l3
l4=n
stk[stkidx++]=l4
stkidx--
stkidx--
for i= l3 to l4 {
l5=i
stk[stkidx++]=l5
stkidx--
l5=1/l5
stk[stkidx++]=l5
}
l6=n
stk[stkidx++]=l6
l7=1
stk[stkidx++]=l7
stkidx--
stkidx--
l6=l6+l7
stk[stkidx++]=l6
l8=n
stk[stkidx++]=l8
l9=n1
stk[stkidx++]=l9
stkidx--
stkidx--
l8=l8+l9
stk[stkidx++]=l8
stkidx--
stkidx--
for i= l6 to l8 {
l10=n1
stk[stkidx++]=l10
stkidx--
for tmp1=1 to l10 { stk[stkidx++]=stk[stkidx-l10] }
l11=i
stk[stkidx++]=l11
stkidx--
l11=1/l11
stk[stkidx++]=l11
}
l12=n
stk[stkidx++]=l12
l13=l12
stk[stkidx++]=l13
l14=2
stk[stkidx++]=l14
stkidx--
l15={ }
for tmp2=0 to l14-1 { l15[tmp2+1]=stk[stkidx-l14+tmp2] }
stkidx=stkidx-l14
stk[stkidx++]=l15
stkidx--
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
Now applying the same 3 previous rules + the new "stack" rule for cleanup.
* Whenever stkidx-- is found, search for a previous stk[stkidx++]=... statement, but do not cross { } boundaries. If found, remove both statements.
For clarity, let's apply the new rule first:
Code:
function fcn1(arg1) {
/*stk[stkidx++]=arg1*/ // CANCELED OUT
l1=arg1
/*stk[stkidx++]=l1*/ CANCELED OUT
l2=1
/*stk[stkidx++]=l2
stkidx--*/ // BOTH CANCEL OUT TOGETHER
/*stkidx--*/ // cancels out with the l1
l1=l1-l2
/*stk[stkidx++]=l1
stkidx--*/ // CANCELED OUT
/*stkidx--*/ // CANCELS OUT THE arg1 PUSH
n=arg1
n1=l1
l3=1
/*stk[stkidx++]=l3*/
l4=n
/*stk[stkidx++]=l4
stkidx--*/
/*stkidx--*/ // CANCELS OUT THE l3 PUSH
for i= l3 to l4 {
l5=i
/*stk[stkidx++]=l5
stkidx--*/ // CANCEL OUT TOGETHER
l5=1/l5
stk[stkidx++]=l5
}
l6=n
/*stk[stkidx++]=l6*/
l7=1
/*stk[stkidx++]=l7
stkidx--*/
/*stkidx--*/ // CANCELS OUT THE l6 PUSH
l6=l6+l7
/*stk[stkidx++]=l6*/
l8=n
/*stk[stkidx++]=l8*/
l9=n1
/*stk[stkidx++]=l9
stkidx--*/
/*stkidx--*/ // CANCELS OUT THE l8 PUSH
l8=l8+l9
/*stk[stkidx++]=l8
stkidx--*/
/*stkidx--*/ // CANCELS OUT THE l6 PUSH
for i= l6 to l8 {
l10=n1
/*stk[stkidx++]=l10
stkidx--*/
for tmp1=1 to l10 { stk[stkidx++]=stk[stkidx-l10] }
l11=i
/*stk[stkidx++]=l11
stkidx--*/
l11=1/l11
stk[stkidx++]=l11
}
l12=n
stk[stkidx++]=l12
l13=l12
stk[stkidx++]=l13
l14=2
/*stk[stkidx++]=l14
stkidx--*/
l15={ }
for tmp2=0 to l14-1 { l15[tmp2+1]=stk[stkidx-l14+tmp2] }
stkidx=stkidx-l14
/*stk[stkidx++]=l15
stkidx--*/
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
Now let's do the other rules with the cleaner output:
Code:
// CODE BEFORE THE FIRST PASS, AFTER THE STACK CLEANUP RULE ABOVE:
function fcn1(arg1) {
l1=arg1
l2=1
l1=l1-l2
n=arg1
n1=l1
l3=1
l4=n
for i= l3 to l4 {
l5=i
l5=1/l5
stk[stkidx++]=l5
}
l6=n
l7=1
l6=l6+l7
l8=n
l9=n1
l8=l8+l9
for i= l6 to l8 {
l10=n1
for tmp1=1 to l10 { stk[stkidx++]=stk[stkidx-l10] }
l11=i
l11=1/l11
stk[stkidx++]=l11
}
l12=n
stk[stkidx++]=l12
l13=l12
stk[stkidx++]=l13
l14=2
l15={ }
for tmp2=0 to l14-1 { l15[tmp2+1]=stk[stkidx-l14+tmp2] }
stkidx=stkidx-l14
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
// FIRST PASS OTHER RULES
function fcn1(arg1) {
l1=arg1
l2=1
l1=l1-1 // l2 never used, replace
n=arg1
n1=arg1-1 // l1 never used after this, recursively replace by value since first replacement included l1 again
l3=1
l4=n
for i= 1 to n { // l3 and l4 never used after this, replace by value
/*l5=i*/
l5=1/i // CONSECUTIVE ASSIGNMENT, MERGE
stk[stkidx++]=1/i // l5 never used after
}
l6=n
l7=1
l6=l6+1 // l6 is still used, only l7 can be replaced
l8=n
l9=n1
l8=l8+n1 // l8 still used, only replace l19
for i= n+1 to n+n1 { // recursively replace l6 and l8, never used after here
l10=n1
for tmp1=1 to l10 { stk[stkidx++]=stk[stkidx-n1] } // replace l10, never used
/*l11=i*/
l11=1/i // CONSECUTIVE ASSIGNMENT, MERGE
stk[stkidx++]=1/i // l11 replaced, never used after here
}
l12=n
stk[stkidx++]=l12
l13=n // l12 replaced, never used
stk[stkidx++]=l13
l14=2
l15={ }
for tmp2=0 to l14-1 { l15[tmp2+1]=stk[stkidx-l14+tmp2] }
stkidx=stkidx-2 // l14 replaced
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
// SECOND PASS OTHER RULES
function fcn1(arg1) {
l1=arg1
/*l2=1*/ // never used, remove
/*l1=l1-1*/ // never used, remove
n=arg1
n1=arg1-1
/*l3=1*/ // never used, remove
/*l4=n*/ // never used, remove
for i= 1 to n {
/*l5=1/i*/ // never used, remove
stk[stkidx++]=1/i
}
l6=n
/*l7=1*/ // never used, remove
/*l6=l6+1 */ // never used, remove (after replacing l6 with n but doesn't matter)
l8=n
/*l9=n1*/ // never used, remove
/*l8=l8+n1*/ // never used, remove
for i= n+1 to n+n1 {
l10=n1
for tmp1=1 to n1 { stk[stkidx++]=stk[stkidx-n1] } // replace other l10, never used
/*l11=1/i*/ // never used, remove
stk[stkidx++]=1/i
}
l12=n
stk[stkidx++]=n // l12 replaced, never used after
l13=n
stk[stkidx++]=n // l13 never used after this, replace
l14=2
l15={ }
for tmp2=0 to l14-1 { l15[tmp2+1]=stk[stkidx-2+tmp2] } // l14 replaced, never used after
stkidx=stkidx-2
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
// THIRD PASS OTHER RULES
function fcn1(arg1) {
/*l1=arg1*/ // never used, remove
n=arg1
n1=arg1-1
for i= 1 to n {
stk[stkidx++]=1/i
}
/*l6=n*/ // never used, remove
/*l8=n*/ // never used, remove
for i= n+1 to n+n1 {
/*l10=n1*/ // never used, remove
for tmp1=1 to n1 { stk[stkidx++]=stk[stkidx-n1] }
stk[stkidx++]=1/i
}
/*l12=n*/ // never used, remove
stk[stkidx++]=n
/*l13=n*/ // never used, remove
stk[stkidx++]=n
l14=2
l15={ }
for tmp2=0 to 2-1 { l15[tmp2+1]=stk[stkidx-2+tmp2] } // l14 replaced, never used after
stkidx=stkidx-2
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
// FOURTH PASS OTHER RULES
function fcn1(arg1) {
n=arg1
n1=arg1-1
for i= 1 to n {
stk[stkidx++]=1/i
}
for i= n+1 to n+n1 {
for tmp1=1 to n1 { stk[stkidx++]=stk[stkidx-n1] }
stk[stkidx++]=1/i
}
stk[stkidx++]=n
stk[stkidx++]=n
/*l14=2*/ // never used, remove
l15={ }
for tmp2=0 to 2-1 { l15[tmp2+1]=stk[stkidx-2+tmp2] }
stkidx=stkidx-2
l16=[][]
for tmp3=1 to l15[1] { for tmp4=1 to l15[2] { l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)] } }
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
}
And this leads to the following final code:
Code:
// FINAL OUTPUT OTHER RULES
function fcn1(arg1)
{
n=arg1
n1=arg1-1
for i= 1 to n {
stk[stkidx++]=1/i
}
for i= n+1 to n+n1 {
for tmp1=1 to n1 { stk[stkidx++]=stk[stkidx-n1] }
stk[stkidx++]=1/i
}
stk[stkidx++]=n
stk[stkidx++]=n
l15={ }
for tmp2=0 to 2-1 { l15[tmp2+1]=stk[stkidx-2+tmp2] }
stkidx=stkidx-2
l16=[][]
for tmp3=1 to l15[1] {
for tmp4=1 to l15[2] {
l16[tmp3][tmp4]=stk[stkidx-(l15[1]*l15[2])+l15[2]*(tmp3-1)+(tmp4-1)]
}
}
stkidx=stkidx-l15[1]*l15[2]
stk[stkidx++]=l16
}
It's a bit convoluted at the end, not sure if it helps as it is. To make it more like the actual code you would write, a more advanced decoder should detect that the loop 'for tmp2=0 to 1 ...' is determined at compile time, and should try to unroll the loop and simplify further, showing that l15[1]=l15[2]=n, replacing and removing it all. It would help a lot with readability in the last part, which is merely trying to fill up a matrix, the first couple of loops where the actual math is done came out pretty nice.
Anyway, this was a nice experiment as a proof of concept, perhaps one day I'll actually code it for newRPL giving it the power to decompile RPL into something like Lua or Python.
Search
Member List
Calendar
Help
