In this case, I was the anonymoose. It was the only way SF seems to let me post a new topic now, but the editor was even glitchier than usual and posted prematurely. In this program, if the recursion depth guard at about line 300 is disabled, the program compiled and run, and 7500 input, it freezes when the actual recursion depth reaches 467 or so. With the guard, the program runs to completion, eventually, but then not all possible longest palindromic subsequences can be calculated. I realize the call stack is a finite resource and this can be worked around using another matrix like in the FORTRAN II days. :)
:::basic#!/usr/bin/xbasicProgramPalindromicShowKInput"How long? ",N%HideKStart=TimerAlpha$="GATTACA"!Alpha$="non~EXO xenon"!Alpha$="Able was I, ere I saw Elba."!Alpha$="Eva, can I see beezies ~~ in a cave???"!Alpha$="!!A MAN. A PLAN. A CANAL. PANAMA!"Alpha$=Upper$(Alpha$)LenA%=Len(Alpha$)IfGlob(Alpha$,"*[-{}]*")ThenPrint"Forbidden characters in Alpha$"StopEndIf' Belt, suspenders, drones, crane, cargo helicopter, orbital skyhook Dim Alpha%(256) Clr Alpha%() For i% = 1 To Len(Alpha$) 'Parallelizable,butwoulditactuallybeworthit?Alpha%(Asc(Mid$(Alpha$,i%,1)))=TrueNexti%Corpus$=String$(N%,"-")!NosentinelsthistimePrint"Allocated ";Len(Corpus$);" bytes in ";Timer-StartClri%,j%,k%,VPA%,VPC%' Randomize 'Watchouton64-bitVPA%=VarPtr(Alpha$)VPC%=VarPtr(Corpus$)Fori%=1ToN%If(i%And0xFFF)=0ThenPrint" ";i%;" ";Chr$(13);FlushEndIf' Parallelizable, I guess 'Repeat!RANDOMsometimesb0rksinWinblowsj%=Random(LenA%)' Until (0 = j%) Or (j% < LenA%) 'k%=Asc(Mid$(Alpha$,j%+1,1))k%=Peek(VPA%+j%+1-1)' Caution, this sanity check adds significant overhead If Not Alpha%(k%) ! InStr(Alpha$, Chr$(k%)) = 0 Then Print "Invalid character at 0x"; Hex$(VPA%); " + "; j%, k% Stop EndIf 'Mid$(Corpus$,i%,1)=Chr$(k%)PokeVPC%+i%-1,k%Nexti%Print"Corpus$ initialized in ";Timer-StartIfN%<=600ThenPrint"'";Corpus$;"'"EndIfIfGlob(Corpus$,"*[!" + Alpha$ + "]*")ThenPrint"Invalid characters!"StopEndIfPrint"Sanity checked in ";Timer-Start' Bottom-up algorithm blatantly ripped off from: 'https://www.techiedelight.com/longest-palindromic-subsequence-using-dynamic-programming/IfN%<LenA%ThenPrint"'";Alpha$;"'"Corpus$=Upper$(Alpha$)N%=Len(Corpus$)EndIfIfN%<=600ThenPrint"'";Corpus$;"'"EndIfDimLookup%(N%+1,N%+1)!Thisdoesn't seem too terribly bad Clr Lookup%() Print ((N% + 1) ^ 2) * 4; " bytes of "; Print "monster matrix allocated in "; Timer - Start Flush Clr i%, j%, k%, l%, VPC% VPC% = VarPtr(Corpus$) For i% = 1 To N% Print Chr$(13); "Row "; i%; " "; For j% = 1 To N% 'k%=Asc(Mid$(Corpus$,i%,1))' l% = Asc(Mid$(Corpus$, N% - j% + 1, 1)) k% = Peek(VPC% + i% - 1) l% = Peek(VPC% + N% - j% + 1 - 1) If (Not Alpha%(k%)) Or (Not Alpha%(l%)) Then Print "Bad chars from Corpus$?", k%, l% Stop Else If k% = l% Then Lookup%(i%, j%) = Lookup%(i% - 1, j% - 1) + 1 Else If Lookup%(i% - 1, j%) > Lookup%(i%, j% - 1) Then Lookup%(i%, j%) = Lookup%(i% - 1, j%) Else Lookup%(i%, j%) = Lookup%(i%, j% - 1) EndIf Next j% Print " "; Round(Timer - Start, 3); " "; Next i% Print Print Lookup%(N%, N%); " length of longest palindromic subsequence(s)," Print "Found length in "; Timer - Start 'EvenmoreGlobals???DimH%(128)!HashtableforS$(),sizemustbepoweroftwoDimS$(16)!DYNAMIC,DuplicatedstringtableforStringInsanityDimC%(16)!DYNAMIC,OpenhashingchainsforS$()andH%()HMask%=UBound(H%())-1ArrayFillH%(),-1ClrS$(),C%()SCount%=0' Still more Globals, call stack limits are nasty Clr R$, PalindromeCount%, MaxCallDepth%, MaxActualCallDepth% GoSub StringInsanity(N%, N%, 0, 0) Print PalindromeCount%, SCount%, MaxCallDepth%, MaxActualCallDepth% Print "Found some/all/most? in "; Timer - Start Print "OK"End'INC$,N%,i%,j%,R$,CallDepth%' OUT NIL'IN/OUTPalindromeCount%,MaxCallDepth%,MaxActualCallDepth%' COMMON Alpha%(), Lookup%(), S$(), H%(), C%(), SCount%Procedure StringInsanity(i%, j%, CallDepth%, ActualCallDepth%) 'LocalVPC%,VPR%Localk%,l%' Local KeepGoing%, PalindromeOK% 'GlobalAlpha%()IncActualCallDepth%IfActualCallDepth%>MaxActualCallDepth%ThenMaxActualCallDepth%=ActualCallDepth%'Print MaxActualCallDepth%, MaxCallDepth% EndIfTailCallElimination: Inc CallDepth% If CallDepth% > MaxCallDepth% Then MaxCallDepth% = CallDepth% EndIf Print " "; ActualCallDepth%; " "; CallDepth%; " "; Print MaxActualCallDepth%; " "; MaxCallDepth%; Print " "; Chr$(13); Flush VPC% = VarPtr(Corpus$) If (i% = 0) Or (j% = 0) Then k% = 1 l% = Len(R$) VPR% = VarPtr(R$) KeepGoing% = (l% = Lookup%(N%, N%)) PalindromeOK% = (l% = Lookup%(N%, N%)) While KeepGoing% If Not (k% < l%) Then PalindromeOK% = True KeepGoing% = False Else If (Not Alpha%(Peek(VPR% + k% - 1))) Or (Not Alpha%(Peek(VPR% + l% - 1))) Then Print "Bad character(s) at", k%, l% Stop Else If Not (Peek(VPR% + k% - 1) = Peek(VPR% + l% - 1)) Then PalindromeOK% = False KeepGoing% = False Else Inc k% Dec l% EndIf Wend If Not PalindromeOK% Then Print PalindromeOK%, Len(R$), k%, l%, "'"; R$; "'" Stop EndIf Hash% = CRC(R$) And HashMask% Prev% = 0xDEAFBEEF Curr% = H%(Hash%) Do Exit If Curr% < 0 Exit If S$(Curr%) = R$ Prev% = Curr% Curr% = C%(Curr%) Loop If Curr% < 0 Then If SCount% = UBound(S$()) Then Print "*"; Flush Dim S$(SCount% + ShR(SCount%, 2) + 4) ! REDIM PRESERVE Dim C%(SCount% + ShR(SCount%, 2) + 4) ! REDIM PRESERVE Print "*"; Flush EndIf S$(SCount%) = R$ C%(SCount%) = H%(Hash%) H%(Hash%) = SCount% Inc SCount% Inc PalindromeCount% Print PalindromeCount%; " '"; R$; "' "; Timer - Start Else If Prev% >= 0 Then 'Movethefoundduplicatestringuptothefront' of the hash chain in case of repeated searches C%(Prev%) = C%(Curr%) C%(Curr%) = H%(Hash%) H%(Hash%) = Curr% EndIf Print " DUP "; 'Print"'";R$;"' ";Hash%;" ";Prev%;" ";Curr%;" ";' Print Chr$(13); EndIf Flush Else If Peek(VPC% + i% - 1) = Peek(VPC% + N% - j% + 1 - 1) Then 'R$=R$+Mid$(C$,i%,1)R$=R$+Chr$(Peek(VPC%+i%-1))k%=Lookup%(N%,N%)-Len(R$)+1l%=Len(R$)ClrPalindromeOK%IfNot(k%<l%)ThenPalindromeOK%=TrueElseIfMid$(R$,k%,1)=Mid$(R$,l%,1)ThenPalindromeOK%=TrueElsePalindromeOK%=FalseEndIfIfNotPalindromeOK%ThenPrint"'";R$;"' NOT OK"StopElseIfk%<l%Then' Print "'"; R$; "' OK" R$ = R$ + Reverse$(Left$(R$, Lookup%(N%, N%) - Len(R$))) Clr i%, j% GoTo TailCallElimination Else 'Print"'";R$;"' ???"' GoSub StringInsanity(C$, N%, i% - 1, j% - 1, R$) Dec i% Dec j% GoTo TailCallElimination EndIf Flush Else If Lookup%(i% - 1, j%) > Lookup%(i%, j% - 1) Then 'Shouldmorecompilersrecognizetailrecursion' GoSub StringInsanity(C$, N%, i% - 1, j%, R$) Dec i% GoTo TailCallElimination Else If Lookup%(i%, j% - 1) > Lookup%(i% - 1, j%) Then 'andturnitintoaGOTO' GoSub StringInsanity(C$, N%, i%, j% - 1, R$) Dec j% GoTo TailCallElimination Else 'Finally,somenon-tailrecursion' Print "Actual recursive call", i% - 1, j% 'ObviousSPAWNthreadcandidateisobviousl%=Len(R$)IfActualCallDepth%<465Then!RECURSIONDEPTHGUARDGoSubStringInsanity(i%-1,j%,CallDepth%,ActualCallDepth%)EndIfIfl%<Len(R$)ThenPrint" Trimming R$ back to ";l%;Space$(20);Chr$(13);FlushR$=Left$(R$,l%)ElseIfl%>Len(R$)ThenStopEndIf' ...and back to the tail recursion 'GoSubStringInsanity(C$,N%,i%,j%-1,R$)Decj%GoToTailCallEliminationEndIfReturn
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
FYI: The call stack size is 512. This will limit recusion depth. The value is arbitrary and comes from 20 years ago when RAM was expensive and limited. What stack size would your program need?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I have no idea. I tend to keep trying larger and larger problems to see what breaks. Could the stack be dynamically expanded by perhaps 25% and contracted by 50% as needed like half my arrays? You know, I haven't actually contracted an array yet in xbasic. I should try it.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I have fixed it. Now the statck sizeis dynamically adjusted in steps of 512 up to a (hardcoded) maximum which is 8000 (recusion depth) at the moment, or better say in the next release of X11-Baisic.
Also the app will not crash, when the limit is reached, but will print out an error message instead.
The upper maximum is necessaary, because an endless recursion loop would oherwise eat all of the available system memory which in the end causes a crash, but before wold slow down and freeze the device.
BTW: The stack does store return addresses and pointers to all local variables.
Last edit: Markus Hoffmann 2019-06-20
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Wow, thank you! Does moving arguments and local variables into globals help increase the recursion depth limit, or does that not matter? Should there be some way to optionally declare which global variables a function or procedure can access? I currently try to do so with comments, but something like Option Explicit and Global or Common enforced by the language would be awesome. I don't ask for all that much, do I? (Don't answer that!)
If this keeps up, X11 BASIC might eventually mutate into X11 SPARK or something.
Any progress on what an X11 BASIC way to do UDTs might look like? And then expanding on that into modules and interfaces? Don't worry, no multiple or even single implementation inheritance. Extends is evil.
I'm going to need a list of things to try stress testing in the next release. I'm actually going to try some bioinformatics algorithms which ought to do it.
Thanks again!
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Crazy amounts of recursion in compiled programs appears to freeze the VM, at least on Android 5.1.1, and now the SF forums editor hates me.
Hm, OK. Can you be more specific? What version of X11-Basic are you using? What is the kind of recursion problem you see?
In this case, I was the anonymoose. It was the only way SF seems to let me post a new topic now, but the editor was even glitchier than usual and posted prematurely. In this program, if the recursion depth guard at about line 300 is disabled, the program compiled and run, and 7500 input, it freezes when the actual recursion depth reaches 467 or so. With the guard, the program runs to completion, eventually, but then not all possible longest palindromic subsequences can be calculated. I realize the call stack is a finite resource and this can be worked around using another matrix like in the FORTRAN II days. :)
OK, I am also confused why I have to approve your post.... Well, SF has bugs.
FYI: The call stack size is 512. This will limit recusion depth. The value is arbitrary and comes from 20 years ago when RAM was expensive and limited. What stack size would your program need?
I have no idea. I tend to keep trying larger and larger problems to see what breaks. Could the stack be dynamically expanded by perhaps 25% and contracted by 50% as needed like half my arrays? You know, I haven't actually contracted an array yet in xbasic. I should try it.
Well, increasing the stack size from 512 to any other number would be a quick fix. Implementing a dynamic adaption is a lot of work. Thats why I ask.
I'd table it for now then. I can simulate the dynamic stack myself if need be, which I think I'll try. Thank you for looking into it though.
I have fixed it. Now the statck sizeis dynamically adjusted in steps of 512 up to a (hardcoded) maximum which is 8000 (recusion depth) at the moment, or better say in the next release of X11-Baisic.
Also the app will not crash, when the limit is reached, but will print out an error message instead.
The upper maximum is necessaary, because an endless recursion loop would oherwise eat all of the available system memory which in the end causes a crash, but before wold slow down and freeze the device.
BTW: The stack does store return addresses and pointers to all local variables.
Last edit: Markus Hoffmann 2019-06-20
Wow, thank you! Does moving arguments and local variables into globals help increase the recursion depth limit, or does that not matter? Should there be some way to optionally declare which global variables a function or procedure can access? I currently try to do so with comments, but something like Option Explicit and Global or Common enforced by the language would be awesome. I don't ask for all that much, do I? (Don't answer that!)
If this keeps up, X11 BASIC might eventually mutate into X11 SPARK or something.
https://en.m.wikipedia.org/wiki/SPARK_(programming_language)#Contract_examples
https://en.m.wikipedia.org/wiki/SPARK_(programming_language)#Verification_conditions
Any progress on what an X11 BASIC way to do UDTs might look like? And then expanding on that into modules and interfaces? Don't worry, no multiple or even single implementation inheritance. Extends is evil.
I'm going to need a list of things to try stress testing in the next release. I'm actually going to try some bioinformatics algorithms which ought to do it.
Thanks again!