From hufnagel Thu Dec 1 09:16:15 1994 Return-Path: Received: by zippy.sonoma.EDU (4.1/SMI-4.0) id AA23081; Thu, 1 Dec 94 09:16:14 PST Date: Thu, 1 Dec 94 09:16:14 PST From: hufnagel (Michael Hufnagel) Message-Id: <9412011716.AA23081@zippy.sonoma.EDU> To: kendrick Subject: here Status: RO >From KENDRICK@sonoma.edu Thu Dec 1 08:26:00 1994 To: bob@zippy.sonoma.EDU, LYLEM@sonoma.edu, HUFNAGEL@sonoma.edu, comp-sys-atari-8bit@cs.utexas.edu Subject: Recursion in Action! This seems to do it! (STACKTST.ACT/.C/.BAS) The following file is the C code I first came up with when I was thinking of how to go about adding a local-variable stack to Action! so that PROCedures and FUNCtions can be made to do recursion. I tested it out in Think C++ on a Macintosh but didn't trust it since, well, C handles this by itself, so all I could be doing is wasting memory! But never fear, two files follow this: -----------------begin-stacktst.c---------------------- /* StackTst.c: Stack Test program for adding recursion to Action! */ #include "stdio.h" int sp; int stack[1024]; void overflow() { printf("Overflow\n"); } void underflow() { printf("Underflow\n"); } void init() { sp=0; } void push(int x) { stack[sp]=x; sp=sp+1; if (sp>1024) overflow(); } int pop() { if (sp==0) underflow(); else { sp=sp-1; return(stack[sp]); } } /* -- */ int factorial(int n) { int m; if (n<=1) m=1; else { push(n); m=factorial(n-1); n=pop(); m=m*n; } return m; } void main() { prinf("6!=%d\n",factorial(6)); } /* By Bill Kendrick 11/29/1994 */ /* See STACKTST.ACT... */ -----------end---------- Well, since I didn't trust it, I started writing another text program in QBASIC on an IBM. Of course, at first I started out writing the thing with "SUBS" and "FUNCTIONS"! Duh! QBASIC probably uses a stack for local variables too! So I started over and just used GOSUBS and passed variables to my GOSUB'd functions via "x" and "n" variables. The code looks much more drawn out than it needs to be in a higher level language, but for you Atari BASIC and TurboBASIC XL users, you may find this useful nonetheless. BTW: This seems to work too! :) ----------begin-stacktst.bas------- 1 ' StackTst.Bas 2 ' by Bill Kendrick 11/29/1994 3 ' Test of StackTst.c code in (Q)BASIC without using real 4 ' FUNCs. 5 DIM stack(100) 6 GOTO 1000 10 ' push 11 stack(sp) = x 12 sp = sp + 1 13 RETURN 20 ' pop 21 sp = sp - 1 22 x = stack(sp) 23 RETURN 100 ' factorial 101 IF n <= 1 THEN 102 m = 1 103 ELSE 104 x = n ' \ push(n) 105 GOSUB 10 ' / 106 n = n - 1 ' \ 107 GOSUB 100 ' > m=factorial(n-1) 108 m = x ' / 109 GOSUB 20 ' \ m=pop() 110 n = x ' / 111 m = m * n 112 END IF 113 x = m ' return(x) 114 RETURN 1000 ' main 1001 n = 6 ' \ 1002 GOSUB 100 ' > print factorial(6) 1003 PRINT x ' / 1004 END ----------end---------- Finally, after this last sucessful trial, I came up with the following Action! code, based on the C code above. I ran it, got "720" as a result (6!=720), screamed and jumped up and down; proceeded to tell the person on the other line what had just happened (giving her a breif description of recursion and factorial), then apologized and asked her to repeat what she was saying a moment before. ANYWAYS, I hadn't booted any DOS with the thing and was planning on using SIO2PC's Print-Thru and Atari's built in P:rinter device to make a copy of the thing as a file on my PC, but accidentally hit "D" for DOS instead of "E" for editor in Action!'s monitor and poof it was gone and I was enjoying the OS's Self-Test menu . The following is obviously not my ORIGINAL code , AND IS NOT IDENTICAL to the C code! This gives you a menu letting you chose between FACTORIAL, FIBONACCI, and ACKERMANN recursive functions. ACKERMANN has not been tested, and when doing FACTORIAL and FIBONACCI, remember that I used INTs, so when it calculates values over 32767 or below -32768, the variable will have over-/under-flowed and answers will be wrong, but hell, at least it works for INTs! :) ----begin-stacktst.act----- ; STACKTST.ACT ; Local variable stack handler for ; Action! test program. ; By Bill Kendrick 11/29/1994 DEFINE STACKSIZE="200" DEFINE LARGESTTYPE="CARD" ; Type mismatches don't create errors, ; so use the largest (2-bytes) available CARD SP ; Stack pointer LARGESTTYPE ARRAY STACK(STACKSIZE) ; Stack storage space PROC OVERFLOW() PRINTE("OVERFLOW") ; Display error PRINT("STACK POINTER ABOVE ") PRINTCE(STACKSIZE) BREAK() ; and abort program RETURN PROC UNDERFLOW() PRINTE("UNDERFLOW") PRINTE("STACK POINTER BELOW 0") BREAK() RETURN PROC INIT() ; All we need to do here is reset the SP=0 ; stack pointer either before a RETURN ; recursive function's called or at ; program start. PROC PUSH(LARGESTTYPE V) STACK(SP)=V ; Store value SP=SP+1 ; Increment stack pointer IF SP>=STACKSIZE-2 THEN ; Test for overflow OVERFLOW() FI RETURN LARGESTTYPE FUNC POP() LARGESTTYPE V IF SP=0 THEN ; Test for possible underflow UNDERFLOW() ELSE SP=SP-1 ; Decrement stack pointer V=STACK(SP) ; Retrieve value FI RETURN(V) ; ---------------------------------- INT FUNC FACTORIAL(INT N) INT M ; Temporary variable; its value is ; RETURN'd IF N<=1 THEN ; 1!=1.. M=1 ELSE PUSH(N) ; Push before recursion M=FACTORIAL(N-1) ; Call function for N-1, store in M N=POP() ; (Get old N after last recursion was ; returned from) M=M*N ; Multiply.. FI RETURN(M) ; ..and return value INT FUNC ACKERMANN(INT X,Y) INT R R=0 IF X=0 AND Y>=0 THEN R=Y+1 ELSEIF Y=0 AND X>0 THEN PUSH(X) PUSH(Y) R=ACKERMANN(X-1,1) Y=POP() X=POP() ELSE PUSH(X) PUSH(Y) R=ACKERMANN(X,Y-1) Y=POP() X=POP() PUSH(X) PUSH(Y) R=ACKERMANN(X-1,R) Y=POP() X=POP() FI RETURN(R) INT FUNC FIBONACCI(INT N) INT R1,R2 ; Temporary variable; its value is ; RETURN'd IF N=0 OR N=1 THEN ; FIB(0)=0,FIB(1)=1 R1=N R2=0 ELSE PUSH(N) ; Push before recursion R1=FIBONACCI(N-1) ; Call function for N-1, store in M N=POP() PUSH(R1) ; Push before recursion PUSH(N) ; Push before recursion R2=FIBONACCI(N-2) ; Call function for N-1, store in M N=POP() R1=POP() ; (Get old N after last recursion was ; returned from) FI R1=R1+R2 RETURN(R1) ; ..and return value PROC MAIN() INT A,B,RESULT INIT() ; Init Stack PRINTE("1=FACTORIAL") PRINTE("2=ACKERMANN") PRINTE("3=FIBONACCI") A=INPUTB() IF A=1 THEN PRINTE("Factorial") ; Title/instructions: PUTE() ; (blank line (PUT End Of Line)) PRINTE("Enter 'A' and I will") PRINTE("show you 'A!'.") PUTE() PRINTE("Enter '0' to quit.") DO PUTE() PRINT(" A=") ; Prompt (no EOL after) A=INPUTI() ; Read integer RESULT=FACTORIAL(A) ; Call function PRINT("A!=") ; Display results PRINTIE(RESULT) UNTIL A=0 OD ; Quit when A=0 ELSEIF A=2 THEN PRINTE("Ackermann") ; Title/instructions: PUTE() ; (blank line (PUT End Of Line)) PRINTE("Enter 'A' and 'B' and I") PRINTE("will show you") PRINTE("ACKERMANN(A,B).") PUTE() PRINTE("Enter '0' to quit.") DO PUTE() PRINT(" A=") ; Prompt (no EOL after) A=INPUTI() ; Read integer PRINT(" B=") ; Prompt (no EOL after) B=INPUTI() ; Read integer RESULT=ACKERMANN(A,B) ; Call function PRINT("ACKERMANN(A,B)=") ; Display results PRINTIE(RESULT) UNTIL A=0 OD ; Quit when A=0 ELSEIF A=3 THEN PRINTE("Fibonacci") ; Title/instructions: PUTE() ; (blank line (PUT End Of Line)) PRINTE("Enter 'A' and I will show") PRINTE("you FIBONACCI(A).") PUTE() PRINTE("Enter '0' to quit.") DO PUTE() PRINT(" A=") ; Prompt (no EOL after) A=INPUTI() ; Read integer RESULT=FIBONACCI(A) ; Call function PRINT("FIBONACCI(A)=") ; Display results PRINTIE(RESULT) UNTIL A=0 OD ; Quit when A=0 FI PRINTE("Bye!") RETURN -----end----- Final notes: With the C code, you are restricted (unless you can get C to ignore type mismatches) to using INTs (or whatever you make your stack out of); oh, wait, perhaps I'm wrong. It has been a while. Well, anyways, don't TRUST any code you make using that (why would you use the C one is beyond me ) until you have TESTED it thoroughly. In BASIC, you should be restricted to "reals"/"floats"/whatever you want to call them. This of course includes INTs because BASIC handles conversion to/from for you (this is in QBASIC; Atari BASIC / TurboBASIC XL don't actually have any other type other than INTs). In Action!, CARD is the largest type (2-bytes) and everything else is as big or smaller (INT=2 bytes, addresses=2 bytes, BYTEs=1 byte, CHARs=1 byte, POINTERs=2 bytes, etc.). Be warned not to try to do recursion with CHAR ARRAYs (strings) or any other type of array, or with records without being careful, and perhaps rewriting some of the PUSH/POP code. Also, I'm sure you could do something like this as well: PROC PUSH(BYTE many, CARD a1,a2,a3,a4,a5,a6) ; I think Action! handles ; only 8 params max. ... PROC POP(BYTE many, CARD POINTER a1,a2,a3,a4,a5,a6) ; not FUNC any more to pass more than one value at a time to/from the stack. Well, that's it! Have fun! Has anyone found an easier/better way to do recursion in Action! !? Later! -bill! kendrick@vax.sonoma.edu ||| kendrick@zippy.sonoma.edu William (Bill) Kendrick / | \ ** New Breed Software ** NEW BREED SOFTWARE: Atari 8-bit and IBM PC software! E-mail for info!