RoboZZle Forums

Well, yes, I agree with axorion that learning to know the stack would make sense for VB- and C#- programmers as well and that it is possible to make huge optimizations as to processor working time. Yet I stick to the idea that these Microsoft languages shield the programmer from stack behaviour, which is a different thing from saying that they block access to this world. (There is a large discussion here underneath about optimization, which, I believe, should not be followed up at this place.)

Certainly, thorough and high level explanations of stack behaviour are valuable. I welcome them on these fora, as I welcome them in the comments on specific puzzles (and there is quite a lot of material by now). But I also want to say: RoboZZle is something for fun. It is not about serious programming. And if someone wants join in, and is working her way through a number of puzzles, and if she wants to know more about stacks without having a programmer’s background, she should be served

That's funny keba, funny but true. It's been so long since I've had to put these concepts into words. I guess I've always liked FILO better because it feels more holistic and visionary. LIFO has always felt fickle and shortsighted to me. I'm guessing it's a left brain right brain thing.

I think the term LIFO is more commonly used than FILO. They mean the same thing.

Note that it is nearly possible to encode the equivalent of a conditional return by using 2 functions (only nearly, because it requires 2 conditional function calls, in place of the single conditional return, and those function calls will be pushing different program counters onto the stack).

kraker: I do not wish to seem contentious but I have also done much programming in VB and C/Java. I do not agree with your assessment that these languages shield programmers from stacking issues. While it may be true that many problems can be resolve without a working knowledge of the stack, it is false that these languages block such methods. Avoiding deliberate stack manipulation will result in more lines of code, longer coding times, slower execution speeds, unnecessary memory structure complexity and so forth.

I once wrote a maze creation algorithm in VB using an array to hold the path from my current position back to the start. The code moved randomly until it reached a dead end. It then backed up until it found an unmapped adjacent cell. It continued forth and back until it was forced all the way back to the start at which point the maze was complete. It was just under 300 lines. A year later after I had learn to use stacks I rewrote the code in just over 50 lines and it ran in one quarter the time. This is only one of many function I have rewritten in this way. The proof is irrefutable. If your algorithm uses FILO think stack!

And so I stand by my statement "If you are serious about programming ... learn to manipulate stacks." You may have programmed successfully for years without this knowledge but that fact makes doing so nether desirable nor advisable.

Finally, If the subject matter is too complex for the average 12 year old then I don't see the need for baby talk. It would result in talking down to the very people actually capable of grasping the concept.

First of all I want to say that I really appreciate axorion’s initiative. Still it is very difficult to write a fine stack handling tutorial because the concept of stacking, and related concepts like pushing and popping, largely depend on intimate knowledge of computer programming and are difficult to bring across to people who have never had any experience as software developers whatsoever. Axorion wrote “stacks are even hardwired into microprocessors themselves” – well, this is true, and well, this is just the problem in explaining stack behaviour to people who have never have had to handle this beast.

As a Visual Basic and C# programmer, I feel I have been shielded from all kinds of stack problems and the memory issues they involve. Now, playing RoboZZle, I feel like a pampered programmer, and for solving the puzzles, this earlier protection proves to work out as a disadvantage. Apperently, every advantage has its disadvantage.

I think I would very much welcome in this thread a short bottom-rock explanation of stack-handling, phrased in Jip-and-little-Jan-language, which is something like Winnie-the-Pooh-like language.

Looping

If you have understood everything up to now then you are ready to learn to count cells in RoboZZle. Remember that every function call pushes the stack. So then what happens when a function calls itself? This is called looping. Let's make a loop. F5: Forward, F5 if blue, Forward. When F5 is called it first moves. Then if it is on blue it calls itself and pushes F5:2. It then moves again. If it once again lands on blue it pushes a second F5:2. It will continue pushing this same address to the stack until it lands on something other than blue.

Let's say it pushes three times then lands on green. It will now skip the F5 instruction and execute the second forward for the first time. This is just normal conditional fall through so we get two extra moves that don't involve the stack. Next the function returns and pops the last address pushed. It executes the second forward a second time and returns again. It will continue in this manner until it has popped all three loops. I sometimes refer to this as recursive fall through.

It will thus have moved a distance of eight. That's push 3, extra 2, pop 3. The distance covered by F5 will always be twice the push count plus two. The next address popped will be a return to whatever point called the F5 function in the first place. If you pop an empty stack execution terminates. If you create an unconditional infinite loop then all alloted stack memory will eventually be filled. Have you ever seen the "Error! Stack Overflow." pop up? The 1000 step limit in RoboZZle ether prevents this error or is such an error depending on your perspective.

Complex Stacking

The excessive use of conditional function calls can lead to stacks filled with seemingly chaotic return addresses. This in turn can lead to migraine headaches. You have been warned!

Conditional Returns

It has been suggested in the requested features forum that a "return instruction" be added to the game. The main purpose for this would be conditional returns. This would allow remaining instructions within a given function to be discarded based on the current cell color. While I am for adding this instruction I would not want it to be available to puzzles created prior to its existence as it would cause both solution lengths and difficulty ratings to fall. This is mostly conjecture but I don't think any major changes to RoboZZle are being planned anyway.

Well, That's about it. I hope this helps one or two of you out there.

I have been a member of this site for over three months now and the number one request from new members is overwhelmingly, "Can you help me understand how to use the stack?" And so putting aside the many wonderful resource which may be found online, I will do my best to put the concepts in the simplest terms as they relate to RoboZZle.

Stacks are not just part of this game. They are an integral part of computing and can be found at the core of an innumerable variety of processes. Stacks are even hardwired into microprocessors themselves. If you are serious about programming it behooves you to learn to manipulate stacks.

Functions

Before you can understand stacks you must have a clear understanding of functions. A function is a series of instruction that can be called by a label as a single instruction. For example: You are looking at a puzzle and notice that all or most of the distances you need to move are devisable by two. You look down and see that F3 has a length of two so you fill it with, "Forward, Forward" From this point on you may place the F3 instruction elsewhere in your code and even though it only takes one instruction space it will execute two forward movements. More importantly like any other instruction you can use it in more than one location within your code.

Now this raises an interesting question. How does the program flow remember which F3 instruction called it? It must remember because it knows where to return. If you call F3 from position F1:0 it will return to F1:1. If you call you call it from F2:8 it will return to F2:9. The short answer is it remembers by storing it on the stack. This means the stack is memory.

Nesting

A second concept you must understand before the power of the stack can be reveled is nesting. Nesting is when a function has been called and then proceeds to call a function. For example: Program F2: F3, Right Turn, F3. And F1: F2, Paint Red. When the code runs F1 call F2. Now this next part is very important. Every function call is stored on the stack. So when the F2 instruction executes it not only passes control to the F2 function but also places the return address F1:1 on the stack.

This is known as pushing the stack. And look what happens next. F2 calls F3. This passes control to F3 and pushes F2:1 to the stack. So what happened to the F1:1 that we pushed earlier? Let's fallow the program flow a bit farther. F3 just moves forward twice. It has no more code so it returns to the place it was called. It goes to F2:1 and also removes that address from the stack.

This is known as popping the stack. Some languages require a return instruction. RoboZZle has what is know as implied returns. I think of it as an invisible instruction just to the right of the last real instruction of every function. Anyway, on with the example. F2:1 executes the right turn. Then another push/pop in and out of F3. Now it is time for F2 to return which it does without fail to F1:1 and the red paint.

This not only proves the stack is memory. It proves that it can hold more than one thing. The trick is that you can only get at one piece of information at a time. The addresses are nested one within the next. This is known as "first in last out" or FILO and is a fundamental behavior of all stacks. The term nesting is normally used to refer to a function call within a function but because every function call pushes and every function return pops, nesting and FILO are essentially synonymous. At this point it should be clear why program stacks are called stacks.