How to go from method to method without making the call stack grow.

Ravenkallen

Hey, as still being new to the propeller, i have had a question that has really bothered me. Can a program go to one method and then to another, and then, while in that method go back and forth from another method without increasing the stack. Is there some way to constantly cut the stack? If not then would one handle going back in forth between methods? I know in BASIC, one can just use the goto command to zip around the program without worrying about a "Call stack". ANY info would be greatly appreciated

Mike Green

You can't do it. As you've noticed, there is no GOTO in Spin. A method call is a call and requires a RETURN. Although there's a stack pointer kept in low memory, it's not intended to be manipulated by the program. It's not that hard to write your program from the beginning to work without GOTOs. That's what the various REPEAT statements are for.

About the only thing that's difficult to do without GOTOs is an exit from several levels deep, usually for some kind of error recovery. The ABORT statement and "catch" operator ("\") are intended for that case and work quite well. Read the Propeller Manual for details.

Ravenkallen

It is just so hard trying to put a whole system in just one method. That is a bummer. So if a method calls its parent method will that reduce the call stack?

Mike Green

No, that's called recursion. It can expand the call stack to fill all available memory. It's one method calling another method which calls the first method again.

I'm really not talking about putting a whole system in just one method. I'm talking about separating the various functional pieces into separate methods, then combining them via method calls into sequences of functional pieces, maybe several levels deep.

How about a description of what you're trying to do?

Have you looked at programs in the Object Exchange? It's kind of complex, but you could look at BoeBotBasic for examples of this kind of structuring. Most of the program exists in only a few levels. For expression handling, there's recursion being used, but the program checks to make sure that there's some stack space left, so the recursion is explicitly limited. Most of the methods are relatively short except for one having to do with expressions and one having to do with statements. In both cases, there are large CASE statements to handle the many possible cases, but the cases are pretty independent and not very complicated.

localroger

You need to be clearer with your terms. It's not clear if by 'method' you mean what Parallax calls an 'object,' really a module that contains various data and public and private routines, or a PUB or PRI routine within such an object. It sounds like you might mean 'object' by 'method.'

If so, you can theoretically include a parent object as a sub-object of a child object, but the behavior is a bit weird. Whenever you use an object in more than one place, Spin creates a new set of VARs for each instance, so they essentially act independently; the sub-child object will have different data and not know anything that the parent object knows. BUT Spin only creates one set of an object's DAT data, which is shared between all instances of the object. It's possible to do this deliberately -- you can use DAT interchangeably with VAR for a lot of purposes -- and since all instances of an object share DAT, they will all have the same state and calls to methods of any instance would all have the same effect. This is really useful for things like debug output objects, since you can put them under all your other real objects and they all send data to the same place.

Ravenkallen

I am trying to make a simple menu system for my project.It is working right now, but i know that there might be trouble down the line. Do you have any suggestions on how to make a menu system?

Ravenkallen

@localroger....Uh, don't they call the PRI or PUB things "Methods". That is what it said in the book. Yeah, i am not talking about objects.

localroger

There's a book? OK. Well the word 'method' is used like that but I wasn't sure. In that case, no if you Pub A calls Pub B which calls Pub A again, that is called recursion and it leaves the returns for the previous calls on the stack.

I suspect your problem is falling out of a menu selection back to the menu, from any point (including all kinds of buried errors) within the selected function. That's what abort is for. When you abort, it doesn't return to the PUB or PRI that called it; it returns all the way up the chain until it reaches a call that was issued with the catch flag \. (In fact, abort works across objects, so you can abort all the way out of one object into a call from its parent object.) Here's how you might use it:

PUB PickMenuSel
  case pickmenu
    option_a: \suba
    option_b: \subb
    option_c: \subc

Now in your subfunctions you use return or fall out of the method to return normally, but you use abort from ANYWHERE to wash your hands and go back to pickmenu:

PUB suba
  somefunction
  if everything_went_ok
    return
  else
    abort

PRI somefunction
  do_something
  if everything_ok
    return
  else
    abort

What happens here is if somefunction fails and issues its abort, it doesn't return to its call in suba; it returns to the call OF \suba because that has the abort catch \. Combined with the repeat stuff this lets you do pretty much everything you need to for pretty complex call chains.

Mike Green

Menu systems are usually tree structured, so they fit easily into a GOTO-less control structure. You might also consider a table-driven menu structure. That would make the whole thing very compact and pretty easy to debug / refine.

Ravenkallen

@localroger.... i was talking about the pe kits book. sorry if i came off kind of brash. that stuff you say about the abort command is interesting. so that command would also clear the stack, right? @mike.... do you have any more info on these various menu structures?

localroger

@Ravenkallen, yep, abort clears the stack. That's what it's there for. No problem on the misunderstanding; I asked because I know it's a problem. I don't have the book you're using so I needed a little clarification. The Prop needs better documentation, but Parallax is a small company and we'd also like them to keep developing more cool products, so there is a tension between more cool products and better docs for the products they have.

heater

Looks like localroger has captured your problem. Assuming we are talking about a menu structure. A BASIC programmer may well represent the structure of the menus directly in his code. As the user makes selections the program jumps to some different code to display the next option or do the required action. Eventually the user wants to get back to "home" in the menu structure so the code jumps back too the beginning. Here the menu structure is in the code and the "state" of the user interaction is represented by the current execution point in that code.

This usually leads to large tangled and unmanageable code.

As Mike says a better way to do this is to have a data structure to represent the menus. Could be just arrays of menu item strings and associated action codes etc. Then you have some "state" variable to indicate the current position in the menu system, perhaps just an index into those arrays With that in place one can use the same smaller pice of code to navigate around all parts of the menu system. This has the bonus that when you want to add more menu items you add them to the data structure and you don't need to change the menu navigation code.

Basically move your problem out of code into data structure(s). Add a little more "abstraction".

This can be a good technique with menus or many other programming tasks.

I might disagree with localroger about the use of ABORT to do this. I suspect that ABORT should only be used for error situations rather than implementing the main logical pathways through the code.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

localroger

Heater, I'm the guy telling people in my industry who do event-driven embedded programming to use state machines, so I'd be the first to say you're right -- except that, in a simple system, doing a state machine "right" tends to be expensive in ways that seem foolish and wasteful (until it gets complicated enough that you figure out refactoring with a real state machine is worth the effort).

I would disagree that abort should only be used for errors; I'd say it should be used for aborts. Sometimes a main logical pathway IS an abort, and that's the tool Spin gives us to bail out of deep code when there is a good reason. There are many non-error related reasons to want to do this, and without abort I can think of several situations I've been in already where Spin's extra-pure no-goto-ness would have made life impossible.

Ravenkallen

Hey, heater that sounds kind of cool. I never though of a menu like that. You could just have character strings located in the array and when you navigated it, a pointer would point to a different string. Huh, i will have to give that some thought. My current system is working, but i just didn't want to run into a unidentified bug later. My current menu system displays character strings on a display using a lookupz command. It then branches based upon the value of the key press. Do you have any more suggestions/ code samples of such a menu system?

@localroger.... You have not heard of the Propeller Education Kit Labs Fundamentals book? It is like the official beginners guide.

Mike Green

Basically, you'd have something like this with a table size no more than 128 bytes long:

Table DAT
  byte  "Menu Title",0
  byte  Sub1-Table, "A", "Choice 1",0
  byte  Sub2-Table, "B", "Choice 2",0
  byte  0
Sub1 byte
  byte  "Submenu 1",0
  byte  $80, "A", "Choice 1",0
  byte  $81, "B", "Choice 2",0
  byte  0
Sub2 byte
  byte  "Submenu 2",0
  byte  $82, "A", "Choice 1",0
  byte  $83, "B", "Choice 2",0
  byte  0

Each menu starts with a menu description string followed by several choices ended by a zero byte.
The first choice byte is either a relative pointer to a submenu to be used if this choice is selected or
a value $80 or greater that's returned by the menu routines as the final choice code. The next byte
is the character to be typed by the user followed by a string with the menu choice description.

You'd have a simple interpreter that starts with the index of the first entry in the table, displays the
menu description and choices allowed, then waits for the user to enter the code for the choice or
uses the arrow keys or a front panel up and down button to select the choice to be used. If the
choice selects a submenu, you could recursively call the display routine with the index of the
submenu or you could have a small internal stack that remembers where in the menu hierarchy
you might be and the display routine would be in a REPEAT statement. You'd only need a small
byte array for this since the menu table index would be less than 256 bytes the way I've described it.

All sorts of variations on this scheme are possible depending on the specific circumstances involved.

heater

Sounds like you have got the idea. Give that Spin does not have "structures" like C or Pascal or whatever where you can define a thing that contains a mixture of strings, bytes, words etc and then define arrays of those things, you might want to some arrays in "parallel". One holds the menu strings, others might hold codes indicating what options are available etc. All arrays get indexed by the same "pointer" at any given moment.

Sadly I have no such examples.

Reminds me of about the first program I ever wrote when myself and a friend were teaching ourselves ALGOL (would you believe?). We were wanting to draw an electronic circuit diagram on a pen plotter. Well every component was drawn stroke by stroke by a different piece of code. There was a transistor routine, a capacitor routine, a resistor routine, etc etc etc. Then a big main function to call all of those and draw all the connections. Well it worked. It was huge, it was unmaintainable. Then it dawned on us "Lets have a function that draws symbols, any symbol, and let the shape of the each be an array of points so that we can easily add more or change what we have" and then "lets do the same for positioning the symbols and drawing the connections"....

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

Ravenkallen

hey, Mike. i don't understand how the system you described would work. just a few more details would be great. i have not really used the DAT command a lot yet and as such, i am still kind of green.....thanks for the help guys!!!

StefanL38

Hello Ravenkallen,

if you jump down into menu-items maybe 20 levels deep by calling methods with one or two parameters the RAM used for the stack is not that much.
When ever you RETURN from a method the used stackspace will be reduced. This means if you don't allow to jump from sub-sub-sub-sub-menu A to jump DIRECTLY
to sub-sub-sub-sub-menu B like in a fishermans net. If you just allow to jump down Menu-tree A and before you can jump down menu-tree B you have to go back
to the main-menu that way

Path-A
Main-Asub
Main-Asub-sub
Main-Asub-sub-sub
Main-Asub-sub-sub-sub
Main-Asub-sub-sub-sub-sub

going back ONLY upwards possible
Main-Asub-sub-sub-sub-sub
Main-Asub-sub-sub-sub
Main-Asub-sub-sub
Main-Asub-sub
Main-Asub
Main

and then start jumping along the B-path

Path-B
Main-BSub
Main-BSub-Sub
Main-BSub-Sub-Sub
Main-BSub-Sub-Sub-Sub
Main-BSub-Sub-Sub-Sub-Sub
Main-BSub-Sub-Sub-Sub-Sub-Sub

the amount of stack uses for the method-calls will stay pretty small

So I asked myself where is the problem at all?

best regards

Stefan

Ravenkallen

Okay, i have another question. If a method calls it's own method, will that make the stack space grow?

jazzed

Ravenkallen said...
Okay, i have another question. If a method calls it's own method, will that make the stack space grow?

Can you offer an example? Methods don't have methods. Objects have methods. Methods call other methods in same or different objects.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

Ravenkallen

Okay, like for instance....

Pub main

repeat
·if somevar == 1
· somevar := 0
· main
·if somevar == 2
· waitcnt(clkfreq + cnt)
<More code below>

The first if statement would go to the beginning of pub Main. Would that increase stack space? I don't think it would seeing as you are in the same method.

jazzed

Ravenkallen said...
Okay, like for instance....

Pub main

repeat
if somevar == 1
somevar := 0
main
if somevar == 2
waitcnt(clkfreq + cnt)
<More code below>

The first if statement would go to the beginning of pub Main. Would that increase stack space? I don't think it would seeing as you are in the same method.

Pub main calls itself. This is called recursion. The base or exit point is whenever somevar <> 1. If somevar always == 1, you will quickly run out of stack space.

There are very few reasons to use recursion such as in advanced data structures or some math toys. Even there, methods can be written to be iterative (non-recursive).

It is very unlikely that you really need to use recursion. Take Mike and others' advice given here.

Good luck.
--Steve

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

JRetSapDoog

That example involves a recursive call, i.e., a method calling itself.· In this case, if somevar == 1, then the currently running main program will be suspended and it will call main again and run it from the beginning.· When the main is suspended, it will need to place the return address for the next instruction after the suspend point on the stack, which consequently increases the need for stack space.· Incidentally, in this case, the next instruction is the somevar == 2 test, since the example uses an if statement rather than an else statement.· Anyway, before it can resume, it must finish the second call to main.· However, in that·all the code appears in a repeat·statement, it will probably never finish (unless there's·a·quit statement to break free from the loop and go to the end of the method and terminate that particular "instance"·(though not the same thing as an object instance) of the method.· An abort statement could get·out of the method, too, but works differently in terms of where·program flow goes and how the stack is handled (see above and the manual).··At any rate, during execution of the second main instance·(after the first one is suspended),·main·would be called again if somevar·== 1, which would suspend the second "instance" of main (with the·first·"instance" also still pending) and start a third·"instance."· That process could go on an on as the program digs itself in deeper and deeper with·recursive calls (until the currently executing·method terminates naturally, if ever), eating·up·stack space and eventually crashing if·all the calls don't "unwind" by terminating·naturally.· This is almost for sure not want you want nor generally the best way to design the program.· Recursive calls can·result in elegant-looking code for certain mathematical routines (such as a factorial method) and for traversing trees (a kind of data structure), but they are generally not efficient and can be coded without resorting to recursion.· Anyway, if you don't get anything else right now, for the example you've given, it's important to recognize/understand that a recursive call to main is NOT the same thing as a goto statement.· SPIN dosn't have a goto statement, and·a recursive call is not the equivalent of one, as a recursive call only suspends the calling method so that it can call itself anew but with the prior call (or "instance") still·pending.· The stack space is needed for this so that it can eventually unwind or "un-nest" from the recursion (if the recursion is properly written (all recursive routines need at least one way to terminate naturally)).· I personally haven't tried recursion on the Propeller, so there might be some technical differences in some aspects, but I believe this is generally how things would play out.· Also, I'm not certain about how local variables are handled with recursion on the Propeller.· I'd guess that they are also put on the stack along with the return address, otherwise their values would be lost.· But I'm not sure and haven't tested.· Perhaps others can comment.

MagIO2

What's a recursion good for?

It's for making the solution of some problems easier, utilizing the stack space as memory for storing intermediary results. The easiest example for a recursion is the factorial (whilst it's not very usefull to do that in a recursion).

5! = 1*2*3*4*5

Each recursion needs an end-condition, otherwise you will exceed any available memory - whether it's a propeller having at max. some kB stack or a PC having MBs of stack.
In the propeller case for each call of a function there is at least a return value, a return address, the parameters and any local variable of that function stored on the stack.

So, back to the factorial ... as a recursion you'd say:

pub fac( val )
' this is the end condition
if val=0
return 1
' this is the recursion
else
return val * fac( val-1 )

The initial call of fac with parameter 5 will then result in:
5 * fac( 4 * fac( 3 * fac( 2 * fac( 1 * fac( 0 ) ) ) ) )

The important thing in this recursion is, that the values 5, 4, 3, 2, 1, 0 are put to the stack on it's way to reaching the end-condition. On the way back the intermediary results are calculated and passed back and with the last return (the one of fac( 5 )) we'll then have the end result.

As I said this example is easy and also is easy to be coded in an iteration. But in case more functions are involved in the recursion it get's more and more complex to make it an iteration, as you then have to think about how to organize the intermediary results.

StefanL38

maybe there is some kind of misunderstanding how program-execution is done.

here an example how your example can be done without recursion

PUB Main
  repeat 
    MyMethod1


PUB MyMethod1
  If somevar == 1
    somevar := 0  'this line of code is only executed if the condition somevar == 1 is true

  If somevar == 2
    waitcnt(clkfreq + cnt) 'this lineS of code is only executed if the condition somevar == 1 is true
    'more code
      

inside this code the method main calls the method MyMethod1 again and again.

This is NOT occupying more and more RAM because the calls are done SEQUENTIALLY

Main calls MyMethod1 and a small amount of RAM is used for the callstack

After all lines of code of MyMethod1 are executed the program returns to the level of main
in that moment the stackspaces used for the callstack gets free again

then the method MyMethod1 gets called again AFTER the stackspace is free
occupying again some bytes

so the amount of stackspaces needed alternates between

example
4 bytes
0 bytes
4 bytes
0 bytes
4 bytes
0 bytes
4 bytes
0 bytes
4 bytes
0 bytes

if you do it recursive it looks like this
4 bytes
8bytes
12bytes
16bytes
.......
ALL RAM eaten up by recursive calls

best regards

Stefan

Post Edited (StefanL38) : 5/28/2010 3:42:13 PM GMT

Ravenkallen

The example i stated above was just a example. I was just wondering if it would work or not. This issue has added a whole new set of problems to my project. I have a lot of recursive calls in my program and eventually it would crash. I gotta find an alternative menu system

StefanL38

my example shows how a recursive call can be transformed in a non-recursive call

the basic principle is to have a master repeat-loop that calls other methods

To jump back to a higher menu-level you don't call the method again.
You END the execution of the code of the actual method and then the jump takes place automatically


These other methods can call methods again down ONE tree-path (like shown in a former posting)
but come back through exiting the method

I guess you are somehow locked in a kind of thinking with basic goto 100, goto 10

If you would like to attach your code to a psoting we could take a closer look into your menu construction.

best regards

Stefan

Ravenkallen

I will try the thing you said stefan. And i would post my code, but the attachment manager is not working. It has never worked for me, maybe you guys know the secret to it.