Recursion in RPL using local variables



#2

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 <<Euclid EVAL>> >>

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 << <<program_that_references_its_name>> 'its_name' STO its_name EVAL >> >>

Tom


#3

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

#4

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 ...

#5

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.


#6

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.


#7

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.


#8

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.


#9

Quote:
You [Kiyoshi] 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.

Even though I don’t presume to understand everything that GE writes, I believe that I understand this adequately to be confident that I don’t agree. The mechanism of compiled variables is demonstrably superfluous. While I may not have demonstrated the general truth of that, I certainly demonstrated conclusively, in the post that initiated this thread, that the problem at hand, i.e., the problem of how to use a local variable to implement recursion, is readily solvable using only the ordinary mechanisms of local variables. Those ordinary mechanisms solve the problem entirely, provided only that you have no objection to placing the recursive program within the declarative scope of the name that you wish to assign to that program. I have no problem whatsoever with doing that, and so far as I can tell when looking at it from the procedural perspective, it works perfectly.

Quote:
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.

The problem with that is that local scope has precedence over global scope. If local variable scope were to automatically extend into called subroutines, there would be no straightforward way to know, upon inspecting the subroutine, whether a name within that subroutine, which is not locally scoped within the subroutine, will bind to a variable declared locally in the calling routine, or will default to global scope. Manifestly, this is the reason for the additional requirement that a variable that is to be treated as a compiled variable must be named specially, starting with “<-“. You cannot create an actual global variable using that. The naming rule requires you to explicitly differentiate, particularly within programs that will be called from other programs, the names for which you desire this behavior, from the names for which you desire the behavior of defaulting to global scope. If you do not ever want any of the variables in any of the programs that will be called from other programs to default to global scope, then even though it would be cumbersome, you could apply the special naming rule for all your variables in all your programs. Personally, I would not desire that, because from my perspective, all this actually does is to give you an alternative to using the stack to pass parameters and receive results in the manner that is endemic to a stack-based language.

Quote:
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.

I agree with this. I was highly annoyed at this behavior, but eventually realized that the integrated behavior of the editors and OBJ->, yields a consistent system of sorts. Once you commit to the practice of maintaining programs as strings, you discover that the true obstacle is not with the behavior of the editor, but is rather that when the program that is encapsulated within a string is not syntactically correct, OBJ-> does not identify the error to you. When that happens, you find yourself in a bit of a predicament, but even then, the medicine that you must swallow, isn’t so bad.

Here are some excerpts from my book, specifically from the section that is devoted to using strings to encapsulate programs:

“There are significant advantages to writing and maintaining your programs as strings, i.e., using strings to encapsulate your programs. Each time that the editor exits, the content is evaluated in the familiar manner of the command line interpreter. As programs are pushed onto the stack, subtle changes occur. The voluntary white space characters that have no effect in the program, which includes line breaks, are stripped. Moreover, even though the editor permits you to put comments in your program, it strips them out of the program as the program exits the editor. (Comments start with the ‘@’ character and continue until the next ‘@’ or line break.) If you encapsulate your programs within strings, your indentation and comments will be preserved.”

“When OBJ-> is applied to a string, the command line interpreter receives the proper content of the string, i.e., the string as it appears within the type-aware editor. A syntactically correct program will be pushed onto the stack. If the proper content of the string is not a syntactically correct program, OBJ-> will put the string back on the stack and will report an error. When this occurs, your best option is to do the conversion manually, using the editor that is not type-aware. You can use the global text replacement capability to remove the escape characters, and then manually remove the double-quote characters that encapsulate the program. The error will then be identified as you attempt to leave the editor, but if you proceed to make the corrections then and there, the string version stored in the variable will not benefit from the correction.”

Edited: 28 Sept 2006, 4:28 p.m.

#10

Hardly a new idea. I used something similiar,although not so nicely presented, in my HP-28S
chess program back in the late 1980s.


- Pauli


#11

A very nice program, and your efforts to lay out everything nicely are obvious. However, it is still hard to read. Actually I (too quickly) browsed the code and saw no (really) obvious case of the aforediscussed technique.

And again, I am impressed.

#12

GE, I find it necessary to allow myself to have a little fun with this, and if perchance it has the effect that I hope it will, then I should be able to be nicer in the future!

Quote:
Yuck awful (you're right Kiyoshi this is the standard answer).

I just rang up the Bureau of Standard Answers, and inquired as to whether there is indeed a Standard Answer to this problem. They informed me that they do not have a Standard Answer on file for this. When I told them that you had indicated otherwise, they said that you had probably just made that up off the top of your head, and that no objective basis exists by which it is sensible to confer the special status of Standard Answer to any single one of the correct answers to this problem.

Quote:
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.

It is better for me personally to use NOVAL, because that emphasizes the fact that the initial value assigned to the variable is merely a dummy value. Of course, you can use 0, or any other value or object, to provide an initial value for the variable. Surely, anyone whose calculator lacks that construct would have no trouble figuring that out without my help. In fact, you have proven that!

Quote:
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.

I dislike so much about this that I hardly know where to begin. I rang up the Bureau of Normal Practices and inquired as to whether your use of the word “normal” here qualifies as a Normal Practice. They advised that the only sense in which it is even sensible to ask that question, is if I am inquiring as to the statistical frequency of that particular use of the word, relative to all potential ways to use the word. I said that I was confused, and they asked me if I could define how the word was used. I said that as best as I could determine, it was used to artificially lend meaning to a statement that is otherwise meaningless. Then they laughed and hung up the phone on me.

One absolute logical corollary, of your statement, is that lists in RPL do more than what they were intended to do. Lists do exactly what they were intended to do, no more and no less. In a situation where lists and programs are identical in their effect, it makes no difference whatsoever which one you use. In fact, it could be soundly argued that when they are identical in their effect, it is better to use lists, because that renders several things manifest, including, for example, that no variables will be modified during the immediate evaluation of that expression.

Quote:
There is also a minor optimization like this :
replace 'its_name' STO its_name EVAL
with DUP 'its_name' STO EVAL

I was initially a little dumbfounded as to why I should be concerned about the optimality of something that executes, on my calculator, so quickly that for all intents and purposes it may be regarded as instantaneous. Additionally, the portion, of the total program, that you propose should be optimized, contributes a relatively small part of the total execution time. I will concede, however, there can be a quantitative advantage to using DUP to avoid a discretionary name reference. On my 49g+, the difference between the two sequences that you identified seems to be about .00025 seconds. The comment that I would really like to make about this, though, is that if I infer a general rule from your advice and follow it to its consistent, logical conclusion, the conclusion is that I should never use a variable if that can be avoided. In other words, named variables should only be used when they are necessary in order to allow a program to call itself recursively.

Finally, I will note that I could not avoid noticing a certain irony. You eschew using lists in a way that is entirely natural and that is endemic to the essential nature of the language, yet the method that you advocate as the “standard” solution for using a local variable for storing a recursive program, uses a mechanism that is extraneous to the essential nature of the language. I am of course talking about the compiled variable mechanism. I will share some thoughts about that, but not right here.


Edited: 28 Sept 2006, 4:27 p.m.


#13

Hello,

Quote:
GE, I find it necessary to allow myself to have a little fun with this, and if perchance it has the effect that I hope it will, then I should be able to be nicer in the future!

That sounds mysterious. Anyway, I have only fun here.



Quote:
Of course, you can use 0, or any other value or object, to provide an initial value for the variable.

Zero might sound silly, but on the HP28 it uses less RAM than, say, 434 (which is kind of silly). Also, as stated NOVAL is unusable on some RPL calculators.



Quote:
In a situation where lists and programs are identical in their effect, it makes no difference whatsoever which one you use. In fact, it could be soundly argued that when they are identical in their effect, it is better to use lists, because that renders several things manifest, ...

I read the text written on my HP28S. It says :

List { }

Program << >>

Maybe myself and HP are wrong about the fact that programs use << >> and Lists use { }. Maybe HP was stupid enough to provide two types with identical behavior. I'm not sure, and without further knowledge I assume programs are programs and lists are lists. That is what I call normal. NOT like calling 'chair' an apple, even if both are solid. No irony here !!! Well..

Quote:
the difference between the two sequences that you identified seems to be about .00025 seconds.

That was exactly the point, in addition to the lesser RAM footprint (say 5 bytes, that is 0.0000005% of your 1Gb Flash on your 49G... but I am this kind of guy.

Quote:
I should never use a variable if that can be avoided

That is the correct, logical conclusion with RPL.

[/quote]
Finally, I will note that I could not avoid noticing a certain irony.
[/quote]
Actually not at all. I don't care about being the brightest or the more *insert whatever quality you like here*. I'm sorry if I ever offended anyone here, I just like thinking and rejoicing together.

#14

Quote:
I read the text written on my HP28S. It says :
List { }
Program << >>
Maybe myself and HP are wrong about the fact that programs use << >> and Lists use { }. Maybe HP was stupid enough to provide two types with identical behavior. I'm not sure, and without further knowledge I assume programs are programs and lists are lists. That is what I call normal. NOT like calling 'chair' an apple, even if both are solid. No irony here !!! Well.. [quote]List { }
Program << >>
Maybe myself and HP are wrong about the fact that programs use << >> and Lists use { }.

GE, your notions about how lists ought to be used, are entirely your own. HP is not in any way responsible for the notions that you come up with. You criticized my use of lists, without having any informed notion of what might constitute a rational basis for such a criticism, and evidently without thinking about how you would defend that criticism were I too challenge it. The tactic that you have now chosen to defend your criticisms, i.e., portraying them as somehow the consequence of HP’s having understood the need for the language to support two distinct types of lists, doesn’t make any sense at all, and won’t likely lead to any result that will be beneficial for you.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Writing RPL programs on OS X Sean Freeman 18 636 11-30-2013, 03:59 PM
Last Post: Sean Freeman
  HP: Dump the predefined variables! bluesun08 12 440 11-19-2013, 02:18 PM
Last Post: bluesun08
  48G vs 49G+ User RPL Speed Comparison John Colvin 7 237 11-16-2013, 10:07 PM
Last Post: Han
  RPL 32 David Hayden 4 199 11-11-2013, 11:34 AM
Last Post: David Hayden
  HP Prime - local variables retain their initial type BruceH 4 227 11-10-2013, 12:42 PM
Last Post: Michael de Estrada
  Shutdown with the Apps key and more than 10 variables in a program. Davi Ribeiro de Oliveira 10 436 11-05-2013, 01:26 PM
Last Post: Han
  HP Prime: Number of external Variables Davi Ribeiro de Oliveira 0 106 11-01-2013, 08:10 PM
Last Post: Davi Ribeiro de Oliveira
  HP Prime variables Davi Ribeiro de Oliveira 3 181 10-31-2013, 02:24 AM
Last Post: cyrille de Brébisson
  HP Prime - deleting variables bluesun08 1 122 10-29-2013, 06:36 PM
Last Post: Joe Horn
  HP Prime: CAS Variables - -How to save? Helge Gabert 2 175 10-27-2013, 11:26 PM
Last Post: Helge Gabert

Forum Jump: