Seen in xbasic 1.25-50 on an Android 5.1.1 device. Arrays appear to become corrupt after passing an element by Var to a procedure which modifies it. Passing variables by Var to a recursive procedure become corrupt when that procedure modifies them and uses the same variable names to refer to different variables. I have yet to try this in Windows or Linux.
Well, the way you use the VAR statement has notbeen forseen. It is ment to pass whole variables to the procedure, in this case a whole variable is the whole array and not an indexed value. (If compile the program and run it, you get an error message.)
Maybe it should also work like that, but in this case one must consider this a bug. Maybe a better error message would do.
The other thing (with recurser) shows a quirk in the interpreter, which just comes from the fact, that the variable names are equal. If you do following, it works as expected:
It comes from following:
After having passed Y% from recursed to the procedure recurser VAR x%, the variable x% has already been overwitten and such the original y% will also be passed to y% inside the recurser procedure. So you should avoid to use the same variable names inside and outside a procedure when passed by reference. This, however is a problem with the interpreter only. If you compile the program, it works as expected. Thecompiler uses a propper stackfor parameter passing, but the interpreter does not. This could be improved.
Last edit: Markus Hoffmann 2019-06-04
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I was looking to use passing array elements by VAR heavily in recursive prefix tree code, similar to Introduction to Pascal course binary tree homework programs. Now that I'm trying a persistent storage based trie, the workaround will allow me to cut down on the recursive heap usage with long keys. I've also learned to be more careful with variable names that could be passed around by VAR, but what of reusable library modules designed to be merged into other people's programs, like I'm hoping with my ISAM?
Thanks very much for your help.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I think, I have fixed it now, both. You should be able to pass indexed array entries to normal variables inside a procedure by reference. And, also the second problem with recurser is fixed, too.
It is in 1.25-54, but needs testing.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I installed the 1.26.54-unstable APK and found a problem with FOR. The N% - 1 in the first loop appears to evaluate to N%.
Thanks again!
#!/usr/bin/xbasicProgramFatPivotQuicksortClrM%,N%M%=4N%=10000DimFreqs%(M%+1)DimA%(N%)ClrFreqs%()ArrayFillA%(),0xDEADBEEFFori%=N%-1ToN%*0-1+1Step0*N%-1PrintChr$(13);i%;" ";j%=Random(M%)!MayreturnM%A%(i%)=j%IncFreqs%(j%)Nexti%PrintFori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Clrlo%,hi%,Depth%,Startlo%=0hi%=UBound(A%())-1Start=TimerPrint"Sorting..."GoSubQuicksort(A%(),lo%,hi,0,Depth%)Print"Sorted in ";Timer-StartPrint"Call depth ";Depth%,lo%,hi%Fori%=0ToN%-1DecFreqs%(A%(i%))Nexti%Fori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Fori%=1ToN%-1IfNot(A%(i%-1)<=A%(i%))ThenPrint"A%() out of order"StopEndIfNexti%Print"OK"EndProcedureMedian3(Varlo%,Varme%,Varhi%)' Any of lo%, me%, hi% could be aliasedIfNot(lo%<=me%)ThenSwaplo%,me%EndIfIfNot(lo%<=hi%)ThenSwaplo%,hi%EndIfIfNot(me%<=hi%)ThenSwapme%,hi%EndIfReturnProcedureQuicksort(VarA%(),lo%,hi%,Depth%,VarMaxDepth%)locali%,j%IncDepth%IfDepth%>MaxDepth%ThenMaxDepth%=Depth%EndIf@Median3(A%(lo%),A%(hi%),A%(lo%+((hi%-lo%)Div2)))Return
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
#!/usr/bin/xbasicProgramFatPivotQuicksortClrM%,N%,i%,j%M%=10N%=1000000DimFreqs%(M%+1)DimA%(N%)ClrFreqs%()ArrayFillA%(),0xDEADBEEFFori%=(N%-1)ToN%*0-1+1Step0*N%-1PrintChr$(13);i%;" ";j%=Random(M%)!MayreturnM%A%(i%)=j%IncFreqs%(j%)Nexti%PrintFori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Clrl%,r%,Depth%,Startl%=0r%=UBound(A%())-1Start=TimerPrint"Sorting..."GoSubQuicksort(A%(),l%,r%,0,Depth%)Print"Sorted in ";Timer-StartPrint"Call depth ";Depth%,l%,r%Fori%=0ToN%-1DecFreqs%(A%(i%))Nexti%Fori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Fori%=1ToN%-1IfNot(A%(i%-1)<=A%(i%))ThenPrint"A%() out of order"StopEndIfNexti%Print"OK"EndProcedureSort3(Varx%,Vary%,Varz%)' Any of l%, m%, r% could be aliasedIfNot(x%<=y%)ThenSwapx%,y%EndIfIfNot(x%<=z%)ThenSwapx%,z%EndIfIfNot(y%<=z%)ThenSwapy%,z%EndIfPrintx%,y%,z%ReturnProcedureQuicksort(VarA%(),l%,r%,Depth%,VarMaxDepth%)locali%,j%,k%,p%,q%,v%IncDepth%IfDepth%>MaxDepth%ThenMaxDepth%=Depth%EndIfTailCallElimination:IfNot(l%<r%)ThenGoToDijkstraWouldNotLikeThisEndIf' Corrupt program structure warning here' Exit If (Not (l% < r%))Printl%,r%,@Sort3(A%(l%),A%(r%),A%(l%+((r%-l%)Div2)))i%=l%-1j%=r%p%=l%-1q%=r%v%=A%(r%)DoDoInci%ExitIfNot(A%(i%)<v%)LoopDoDecj%ExitIfNot(v%<A%(j%))ExitIfj%=l%LoopExitIfNot(i%<j%)SwapA%(i%),A%(j%)IfA%(i%)=v%ThenIncp%SwapA%(p%),A%(i%)EndIfIfv%=A%(j%)ThenDecq%SwapA%(j%),A%(q%)EndIfLoopSwapA%(i%),A%(r%)j%=i%-1i%=i%+1k%=l%Whilek%<p%SwapA%(k%),A%(j%)Inck%Decj%Wendk%=r%-1Whilek%>q%SwapA%(i%),A%(k%)Deck%Inci%Wend@Quicksort(A%(),l%,j%,Depth%,MaxDepth%)@Quicksort(A%(),i%,r%,Depth%,MaxDepth%)DijkstraWouldNotLikeThis:Return
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
There is another issue with the interpreter when I put the original parameter names l%, m%, and r% back into Sort3 and it is called in such a way that two or more arguments are actually the same array element. I also get corrupt program structure warnings when I try to use EXIT IF to leave Quicksort early, which is why I resorted to GOTO.
See the line beginning with 40032,
#!/usr/bin/xbasicProgramFatPivotQuicksortClrM%,N%,i%,j%M%=10N%=100000DimFreqs%(M%+1)DimA%(N%)ClrFreqs%()ArrayFillA%(),0xDEADBEEFFori%=(N%-1)ToN%*0-1+1Step0*N%-1PrintChr$(13);i%;" ";j%=Random(M%)!MayreturnM%A%(i%)=j%IncFreqs%(j%)Nexti%PrintFori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Clrl%,r%,Depth%,Startl%=0r%=UBound(A%())-1Start=TimerPrint"Sorting..."GoSubQuicksort(A%(),l%,r%,0,Depth%)Print"Sorted in ";Timer-StartPrint"Call depth ";Depth%,l%,r%Fori%=0ToN%-1DecFreqs%(A%(i%))Nexti%Fori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Fori%=1ToN%-1IfNot(A%(i%-1)<=A%(i%))ThenPrint"A%() out of order"StopEndIfNexti%Print"OK"EndProcedureSort3(Varl%,Varm%,Varr%)' Any of l%, m%, r% could be aliasedIfNot(l%<=m%)ThenSwapl%,m%EndIfIfNot(l%<=r%)ThenSwapl%,r%EndIfIfNot(m%<=r%)ThenSwapm%,r%EndIfReturnProcedureQuicksort(VarA%(),l%,r%,Depth%,VarMaxDepth%)locali%,j%,k%,p%,q%,v%IncDepth%IfDepth%>MaxDepth%ThenMaxDepth%=Depth%EndIfTailCallElimination:IfNot(l%<r%)ThenGoToDijkstraWouldNotLikeThisEndIf' Corrupt program structure warning here' Exit If (Not (l% < r%))Printl%,r%,PrintA%(l%);" ";A%(r%);" ";A%(l%+((r%-l%)Div2)),@Sort3(A%(l%),A%(r%),A%(l%+((r%-l%)Div2)))PrintA%(l%);" ";A%(r%);" ";A%(l%+((r%-l%)Div2))i%=l%-1j%=r%p%=l%-1q%=r%v%=A%(r%)DoDoInci%ExitIfNot(A%(i%)<v%)LoopDoDecj%ExitIfNot(v%<A%(j%))ExitIfj%=l%LoopExitIfNot(i%<j%)SwapA%(i%),A%(j%)IfA%(i%)=v%ThenIncp%SwapA%(p%),A%(i%)EndIfIfv%=A%(j%)ThenDecq%SwapA%(j%),A%(q%)EndIfLoopSwapA%(i%),A%(r%)j%=i%-1i%=i%+1k%=l%Whilek%<p%SwapA%(k%),A%(j%)Inck%Decj%Wendk%=r%-1Whilek%>q%SwapA%(i%),A%(k%)Deck%Inci%Wend@Quicksort(A%(),l%,j%,Depth%,MaxDepth%)@Quicksort(A%(),i%,r%,Depth%,MaxDepth%)DijkstraWouldNotLikeThis:Return
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
It's still happening for me in the 1.26-55-unstable.apk. The Quicksort routine is now at least as much test harness rigging than algorithm. Most of the bugs and variable name typos so far have been in the debug cruft. I really miss OPTION EXPLICIT and DEFOBJ A-Z from VBA and 1990s Visual Basic.
#!/usr/bin/xbasicProgramMedianOf3FatPivotQuicksortPrint"Quicksort is Optimal..."ClrM%,N%,i%,j%M%=10N%=100000DimFreqs%(M%+1)DimA%(N%)ClrFreqs%()ArrayFillA%(),0xDEADBEEFFori%=N%-1ToN%*0-1+1Step0*N%-1If(i%And0xFFF)=0ThenPrintChr$(13);i%;" ";EndIfj%=Random(M%)!MayreturnM%A%(i%)=j%IncFreqs%(j%)If(i%And0xFFF)=0ThenPrint" ";j%;" ";A%(i%);" ";Freqs%(j%);Space$(8);FlushEndIfNexti%PrintFori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%FlushClrl%,r%,Depth%,Startl%=0r%=UBound(A%())-1Start=TimerPrint"Sorting..."FlushGoSubQuicksort(A%(),l%,r%,0,Depth%)Print"Sorted in ";Round(Timer-Start,2);" s, ";PrintRound(N%/(Timer-Start),2);" elements/s"Print"Call depth ";Depth%,l%,r%FlushFori%=0ToN%-1DecFreqs%(A%(i%))Ifi%=0Then!No-opElseIfNot(A%(i%-1)<=A%(i%))ThenPrint"A%() out of order",i%-1,i%,A%(i%-1),A%(i%)StopEndIfNexti%Fori%=0ToUBound(Freqs%())-1Printi%,Freqs%(i%)Nexti%Print"OK"EndProcedureSort3(Varl%,Varm%,Varr%)' Any of l%, m%, r% could be aliasedPrintl%;" ";m%;" ";r%,IfNot(l%<=m%)ThenSwapl%,m%EndIfIfNot(l%<=r%)ThenSwapl%,r%EndIfIfNot(m%<=r%)ThenSwapm%,r%EndIfPrintl%;" ";m%;" ";r%,ReturnProcedureQuicksort(VarA%(),l%,r%,Depth%,VarMaxDepth%)locali%,j%,k%,p%,q%,v%IncDepth%IfDepth%>MaxDepth%ThenMaxDepth%=Depth%EndIf' Dijkstra would not have liked thisTailCallElimination:IfNot(l%<r%)Then!No-opElseIf0!r%-l%<3Then' Should short but non-trivial runs be sorted using a simpler' algorithm like insertion sort to avoid median of three' fat pivot qsort's overhead where we don't really need it?Selectr%-l%Case1Printl%,r%,"Swap2",PrintA%(l%);" ";A%(r%),p%=A%(l%)+A%(r%)q%=A%(l%)XorA%(r%)IfNot(A%(l%)<=A%(r%))ThenSwapA%(l%),A%(r%)EndIfPrintA%(l%);" ";A%(r%)If(Not(A%(l%)<=A%(r%)))\Or(p%<>(A%(l%)+A%(r%)))\Or(q%<>(A%(l%)XorA%(r%)))ThenPrint"Swap2 Fail"StopEndIfCase2Printl%,r%,"Sort3",PrintA%(l%);" ";A%(l%+1);" ";A%(r%),p%=A%(l%)+A%(l%+1)+A%(r%)q%=A%(l%)AndA%(l%+1)AndA%(r%)@Sort3(A%(l%),A%(l%+1),A%(r%))PrintA%(l%);" ";A%(l%+1);" ";A%(r%)If(Not((A%(l%)<=A%(l%+1))And(A%(l%+1)<=A%(r%))))\Or(p%<>(A%(l%)+A%(l%+1)+A%(r%)))\Or(q%<>(A%(l%)AndA%(l%+1)AndA%(r%)))ThenPrint"Sort3 Fail"StopEndIfDefault' Alternative sorting method goes herePrintl%,r%,"???",r%-l%StopEndSelectElsePrintl%,r%,"Qsort",' Consider choosing random element between l% and r%k%=l%+ShR(r%-l%,1)!>>1)p%=A%(l%)+A%(k%)+A%(r%)q%=A%(l%)AndA%(k%)AndA%(r%)IfNot((l%<=k%)And(k%<=r%))ThenPrint"Binary chop Fail",l%,k%,r%StopEndIfPrintA%(l%);" ";A%(r%);" ";A%(k%),@Sort3(A%(l%),A%(r%),A%(k%))PrintA%(l%);" ";A%(r%);" ";A%(k%)If(Not((A%(l%)<=A%(r%))And(A%(r%)<=A%(k%))))\Or(p%<>(A%(l%)+A%(k%)+A%(r%)))\Or(q%<>(A%(l%)AndA%(k%)AndA%(r%)))ThenPrint"VAR recursive reused variable aliased array element nightmare Fail"StopEndIfk%=0xDEADBEEFp%=0xDEAFBEEFq%=0xDEAFBEEFi%=l%-1j%=r%p%=l%-1q%=r%v%=A%(r%)DoRepeatInci%UntilNot(A%(i%)<v%)RepeatDecj%' Can we use the Sort3 call to let us use A%(l%)' as a sentinel and get rid of the j% = l% test?' Exit If Not (v% < A%(j%))' Exit If j% = l%' If j% = l% Then' Print l%, j%, v%, A%(l%)' Stop' EndIfUntilNot(v%<A%(j%))Ifj%<l%ThenPrint"Out of bounds!",l%,i%,j%,r%,v%StopEndIfExitIfNot(i%<j%)SwapA%(i%),A%(j%)IfA%(i%)=v%ThenIncp%SwapA%(p%),A%(i%)EndIfIfv%=A%(j%)ThenDecq%SwapA%(j%),A%(q%)EndIfLoopSwapA%(i%),A%(r%)j%=i%-1i%=i%+1k%=l%Whilek%<p%SwapA%(k%),A%(j%)Inck%Decj%Wendk%=r%-1Whilek%>q%SwapA%(i%),A%(k%)Deck%Inci%Wend@Quicksort(A%(),l%,j%,Depth%,MaxDepth%)l%=i%GOTOTailCallEliminationPrint"DEAD CODE"Stop@Quicksort(A%(),i%,r%,Depth%,MaxDepth%)EndIfReturn
Last edit: Yet Another Troll 2019-06-06
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hm, I see. So there are no Interpretererrrors, no crashes, but the calculation result is not correct?
Can we have a more simple example which produces the error? Otherwise it is very hard for me to track it down.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I'll certainly try, but simple snippets aren't reproducing the issue. A simple snippet that does produce an interpreter crash is this, due to missing commas in PRINT statements, which had me chasing my tail for a while before I found it,
Clearing
35421840 35421984
Assigning A
35424400 35421984
Assigning B
35424400 35425424
Mangling A
35424400 35425424
Display
A
0
Cleanup
35424400 35425424
ERROR: Syntax error: missing closing parenthesis in <A$) VARPTR(B$>.
ERROR at line 51: Illegal variable name A$) VARPTR(B$. can not create.
0
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Awesome, thanks! I think I saw the address of a string variable change unexpectedly before, but it could have merely been a hallucination from too much coffee, or perhaps not enough coffee, it's difficult to tell sometimes. However, it was that which got me wondering about reference counted strings. It would certainly eliminate the temptation to pass very long strings by VAR solely for a bit of speed, but interactions with VARPTR, POKE, perhaps ABSOLUTE, lvalue MID$ support, and passing strings to C routines would become tricky.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Seen in xbasic 1.25-50 on an Android 5.1.1 device. Arrays appear to become corrupt after passing an element by Var to a procedure which modifies it. Passing variables by Var to a recursive procedure become corrupt when that procedure modifies them and uses the same variable names to refer to different variables. I have yet to try this in Windows or Linux.
I'm going to need more coffee.
Well, the way you use the VAR statement has notbeen forseen. It is ment to pass whole variables to the procedure, in this case a whole variable is the whole array and not an indexed value. (If compile the program and run it, you get an error message.)
Maybe it should also work like that, but in this case one must consider this a bug. Maybe a better error message would do.
The other thing (with recurser) shows a quirk in the interpreter, which just comes from the fact, that the variable names are equal. If you do following, it works as expected:
It comes from following:
After having passed Y% from recursed to the procedure recurser VAR x%, the variable x% has already been overwitten and such the original y% will also be passed to y% inside the recurser procedure. So you should avoid to use the same variable names inside and outside a procedure when passed by reference. This, however is a problem with the interpreter only. If you compile the program, it works as expected. Thecompiler uses a propper stackfor parameter passing, but the interpreter does not. This could be improved.
Last edit: Markus Hoffmann 2019-06-04
I was looking to use passing array elements by VAR heavily in recursive prefix tree code, similar to Introduction to Pascal course binary tree homework programs. Now that I'm trying a persistent storage based trie, the workaround will allow me to cut down on the recursive heap usage with long keys. I've also learned to be more careful with variable names that could be passed around by VAR, but what of reusable library modules designed to be merged into other people's programs, like I'm hoping with my ISAM?
Thanks very much for your help.
Hm, why not try to fix it. If you volunteer to test it...
I think, I have fixed it now, both. You should be able to pass indexed array entries to normal variables inside a procedure by reference. And, also the second problem with recurser is fixed, too.
It is in 1.25-54, but needs testing.
Thanks! I know just the thing to test them out as well as the FOR fix.
Quicksort Is Optimal For Many Equal Keys
https://arxiv.org/abs/1608.04906
Quicksort Is Optimal
https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
I installed the 1.26.54-unstable APK and found a problem with FOR. The N% - 1 in the first loop appears to evaluate to N%.
Thanks again!
I have fixed this issue now (FOR/NEXT with spaces). But before I recompile X11-Basic, maybe you find some more errors to be fixed.
Compiling appears problematic:
This is the source code:
I tested this program. The fixed version gives following output when run interpretted (not compiled):
However, when I run the compiled version:
... need to work on that...
There is another issue with the interpreter when I put the original parameter names l%, m%, and r% back into Sort3 and it is called in such a way that two or more arguments are actually the same array element. I also get corrupt program structure warnings when I try to use EXIT IF to leave Quicksort early, which is why I resorted to GOTO.
See the line beginning with 40032,
Hm, NAK: The program worked fine (with new X11-Basic in interpreter). No errors.
Could it be Android specific? I'll continue to poke at it. Still, thank you very much for your help.
Try to use the new version 1.26-55 it is out now. Maybe this issue was (accidentally) fixed.
It's still happening for me in the 1.26-55-unstable.apk. The Quicksort routine is now at least as much test harness rigging than algorithm. Most of the bugs and variable name typos so far have been in the debug cruft. I really miss OPTION EXPLICIT and DEFOBJ A-Z from VBA and 1990s Visual Basic.
Last edit: Yet Another Troll 2019-06-06
Hm, I see. So there are no Interpretererrrors, no crashes, but the calculation result is not correct?
Can we have a more simple example which produces the error? Otherwise it is very hard for me to track it down.
I'll certainly try, but simple snippets aren't reproducing the issue. A simple snippet that does produce an interpreter crash is this, due to missing commas in PRINT statements, which had me chasing my tail for a while before I found it,
Confirmed. The error causes the interpreter to crash. Shame on me. I am working on a fix.
One thing I found strange was that the B$ = A$ assignment appears to cause VARPTR(A$) to change well before the bad PRINT statements and the crash.
I cannot confirm that:
I have fixed it now. It will be in 1.25-56.
Awesome, thanks! I think I saw the address of a string variable change unexpectedly before, but it could have merely been a hallucination from too much coffee, or perhaps not enough coffee, it's difficult to tell sometimes. However, it was that which got me wondering about reference counted strings. It would certainly eliminate the temptation to pass very long strings by VAR solely for a bit of speed, but interactions with VARPTR, POKE, perhaps ABSOLUTE, lvalue MID$ support, and passing strings to C routines would become tricky.