I've been enjoying trying to understand this Sierpinski curve program. It's led to a number of interesting diversions. My efforts have been set back somewhat by the fact that the Internet Archive is still offline. I have a large number of computer magazines from the 70s and 80s already downloaded locally, but not that July 84 issue of Creative Computing. When my iMac started showing signs of instability (Finder wouldn't run, "relaunch" even.), I had to reboot to get everything back in order and those tabs with three issues of Creative Computing opened at archive.org became inert.
Anyway, I do have Niklaus Wirth's Algorithms + Data Structures = Programs, which was the original source of the algorithm that became the BASIC program that Ahl was converting. If you have the book, the discussion begins on page 134. I can't say I truly understand Wirth's Pascal implementation, at least not by inspection, but it's less opaque than the BASIC version.
So I've been adding PRINT statements to various subroutines, chiefly those controlling the stack. This has the effect of breaking up the TRACE output into digestible chunks, which are far more illuminating than anything else I've tried so far. The program draws one segment, then three segments, then one segment, and so on. Which subroutine is called depends on which way that portion of the curve has to go, right, left, up or down (whether you're adding or subtracting values to the preceding coordinate).
To be clear, the program works insofar as it draws the Sierpinski curve for orders 1 through 5 (the limit of the Apple II's hi-res screen). But the first order curve is drawn twice, for reasons I don't understand, and the program always ends with a RETURN WITHOUT GOSUB ERROR AT 190. And it hasn't, until yesterday, been clear to me exactly what was going on in terms of the flow. It's basically (Hah.) a list of subroutines that call each other recursively.
One brief diversion was to try and answer definitively whether Applesoft could do recursion. The answer is yes, it can. But I was put off briefly by Lon Poole's assertion on page 136 of the second edition of his Apple II User's Guide,
While it is perfectly acceptable and even desirable for one subroutine to call another, a subroutine cannot call itself. Neither can a subroutine call another subroutine that in turn calls the first subroutine. This is called recursion and is not allowed in BASIC on the Apple II.
To be fair to Poole, I suspect that this was text that was left over from the first edition, which may have only covered Woz's Integer BASIC, which may not have allowed recursion. Applesoft does.
The test that kind of satisfied my uncertainty was in a cool little book, Illustrating BASIC (A Simple Programming Language) by David Alcock. He writes about BASIC in general and some versions don't permit recursion. To find out if one does, on page 55 he offers a little routine to find the highest common factor of two numbers, which calls itself. I entered it, and played around with it for a while, entering successively higher numbers. I didn't get to a point where it error'ed out, but I believe the stack depth for GOSUB is 25 in Applesoft and I probably didn't enter a large enough second number to exceed that limit before I was satisfied Applesoft does indeed allow recursion.
Of course, the fact that the Sierpinski curve program worked should have resolved that question from the beginning, but I had a little nagging doubt (plus all these books on my shelf). Interestingly, the Applesoft BASIC Programmer's Reference Manual, volume 1 (for //e only), doesn't mention recursion at all, nor does it explicitly address a subroutine calling itself. It does mention that you can nest GOSUB calls up to 25 levels deep, as mentioned above. Exceeding that results in an OUT OF MEMORY error, which really means "out of stack space."
I think I need a POP statement when the last curve is completed to get rid of that final RETURN WITHOUT GOSUB AT 190 error.
Anyway, I've got a doctor's appointment this morning, so further investigation will have to wait. It's more like a "wellness check" than a physical or anything. I never look forward to these things.
Originally posted at Nice Marmot 05:25 Monday, 21 October 2024