The Museum of HP Calculators

HP Forum Archive 16

 Recursion in RPL using local variablesMessage #1 Posted by Tom Barber on 26 Sept 2006, 11:06 a.m. I was recently playing around on the 49g+ with some recursive algorithms. It was of course straightforward to implement recursive algorithms using global variables. For example, I previously had posted the Euclidean algorithm for finding the greatest common divisor of two integers: << DUP {SWAP OVER MOD EUCLID} {DROP} IFTE >> This program assumes two arguments, and always dups the level 1 argument, in order that IFTE can test to see if it is 0. If it is zero, the remaining copy of the L1 argument is dropped, and the argument that was in L2, is returned. If the L1 argument is not 0, then the longer of the two argumets to IFTE, i.e., the L2 argument to IFTE, is evaluated. By example, if the L2 argument to this program is 20 and the L1 argument is 16, then after SWAP and OVER, the stack is: L3:16 L2:20 L1:16. After MOD, the stack is: L2:16 L1:4, and then the program calls itself recursively. Immediately prior to the next recursive call, the stack looks like L2:4 L1:0, so with that next recursive call, the 0 is dropped and 4, which is the largest common divisor of the two original arguments 20 and 16, is returned. You could easily embed this sort of recursive program within another program, in order to save the program in a global variable having the name that is used in the recursive call. Yet, it would be better to use a local variable for this purpose, in order to avoid the need to delete the global variable afterwards, and in order to avoid the potential for conflict with an existing global variable. If you attempt to do this using a local variable, you may possibly find that your knowledge of the scoping rules for local variables is being challenged. How, exactly, do you store a program in a local variable, so that that program can call itself, using the name of the local variable in which it is stored? If you haven't given this much thought, the natural first try is the simplest approach, which would be this: << {DUP {SWAP OVER MOD Euclid EVAL} {DROP} IFTE} -> Euclid <> >> This program simply puts the recursive program (actually a list) on the stack, then uses it as the initial value for the local variable that is subsequently created, then within the nested procedure wherein the scope of that local variable is defined, the content of the local variable is recalled and evaluated. This program does not work, for the simple reason that the scoping rules for local variables do not work that way. Even though the program that is stored in the variable is recalled within the declarative scope of the local variable, the instance of the name of that variable, which is found within the recursive program, is not within the declarative scope of the variable. (Note, by the way, that the reason that it doesn't work has nothing to do with the use of lists. Using a list in lieu of a program would prevent the quoting of variables within the list, but no variables are quoted within the list, and whether you use a list or a program for the content of the local variable, that content will be recalled automatically just the same, and either way, you still have to use EVAL, due to the difference in the rule for evaluating a local variable vs. a global variable.) To make this program work, you have to place the program that contains a reference to the variable in which it will be stored, within the declarative scope of that variable: << NOVAL -> Euclid << {DUP{SWAP OVER MOD Euclid EVAL}{DROP}IFTE} 'Euclid' STO Euclid EVAL >> >> Hence, the general form of a program that uses a local variable to store a program that calls itself recursively, is: << NOVAL -> its_name << <> 'its_name' STO its_name EVAL >> >> Tom

 Re: Recursion in RPL using local variablesMessage #2 Posted by Marcus von Cube, Germany on 26 Sept 2006, 12:02 p.m.,in response to message #1 by Tom Barber Hi Tom, another interesting reading! I've almost read through your book and it's getting more and more fun to use my HP 50g. (I'm just playing around, keeping my mind busy; my job doesn't require me using a calculator.) Marcus

 Re: Recursion in RPL using local variablesMessage #3 Posted by Artur-Brazil on 26 Sept 2006, 5:11 p.m.,in response to message #1 by Tom Barber HP 48 had a special local variable which name started with _ Does HP 49G+ have this kinf of local variable? I don't have the manual on my hands now, but this could be a hint to you search a little more ...

 Re: Recursion in RPL using local variablesMessage #4 Posted by Kiyoshi Akima on 26 Sept 2006, 7:33 p.m.,in response to message #1 by Tom Barber Try it this way: << {DUP {SWAP OVER MOD <-Euclid EVAL} {DROP} IFTE} -> <-Euclid << <-Euclid EVAL>> >> where <- is the single-character left-arrow and is part of the variable name.

 Re: Recursion in RPL using local variablesMessage #5 Posted by GE on 27 Sept 2006, 6:35 a.m.,in response to message #4 by Kiyoshi Akima Yuck awful (you're right Kiyoshi this is the standard answer). However, there should never have been a fix for something that should never have been broken : local variables must always be visible from called subroutines IMHO. Congratulatins Tom, may I call this the first "design pattern" in RPL ? It can be actually useful. It might be better not to use NOVAL, which is not present on the 28 for instance (and maybe even not the 48S ?). You can perfectly well use 0 -> Euclid in your code. Another point, why lists ??? It is much better to use the normal << >> construct instead of { }, which happens to work but wasn't designed for this. There is also a minor optimization like this : replace 'its_name' STO its_name EVAL with DUP 'its_name' STO EVAL Sorry for the flack, and thank you for a nice idea.

 Re: Recursion in RPL using local variablesMessage #6 Posted by Kiyoshi Akima on 27 Sept 2006, 4:55 p.m.,in response to message #5 by GE Quote: However, there should never have been a fix for something that should never have been broken : local variables must always be visible from called subroutines IMHO. A local variable is visible from any subroutines defined within the scope of the local variable. If it were visible from any called subroutine, then it wouldn't be a local variable :-) There are good reasons for making local variables local to a scope, which is why almost every programming language does it that way. The potential confusion occurs because in RPL an object is not bound to a name when it is defined; the binding doesn't happen until the -> . RPL is an attempt (not perfect by any means) to make everything postfix. Recursion works in RPN (ignoring the limits of the return stack) because RPN breaks the postfix paradigm by defining the name first, similar to the way it's done in most programming languages. Likewise with RCL nn, which specifies the operation first and then the argument.

 Re: Recursion in RPL using local variablesMessage #7 Posted by GE on 28 Sept 2006, 5:40 a.m.,in response to message #6 by Kiyoshi Akima I think that recursion works if an object can call itself, that is if it can embed a call to itself before being defined. So it is rather related to the fact that RPL references objects by storing the alpha string of their names instead of (a la Forth) a pointer to the object. You are right about the locality of variables - but it was fixed with the '<-' trick, was badly needed, and should have been here on day one. Also, I don't see any reason for local variables not to propagate down to called subroutines. If the same local variable were defined again, it would hide previous same named ones. My biggest complaint regarding RPL could be the very bad job done by the editor, which very effectively obfuscates the code when you press [Enter] - and we know there is a hard, theoretical reason for that.