[SOLVED] I need help with understand a recursive assembly program.

joeBuffer · 08-12-2009, 02:02 AM

I've read through almost half this book, and have not had a problem understanding a program from it, except for this program. It's "Programming from the Ground Up" by Jonathan Bartlett.
This is a real headache. I would really appreciate a simple explanation of why this works. Maybe someone else will, too, sometime.
It's been a well-explained, easy-to-understand book, except for this:

Code:

#PURPOSE - Given a number, this program computes the
#          factorial. For example, the factorial of
#          3 is 3 * 2 * 1, or 6. The factorial of
#          4 is 4 * 3 * 2 * 1, or 24, and so on.
#
#This program shows how to call a function recursively.
.section .data

#This program has no global data
.section .text
.globl _start
.globl factorial  #this is unneeded unless we want to share
                  #this function among other programs
_start:
 pushl $4         #The factorial takes one argument - the
                  #number we want a factorial of. So, it
                  #gets pushed
 call factorial   #run the factorial function
 addl $4, %esp    #Scrubs the parameter that was pushed on
                  #the stack
 movl %eax, %ebx  #factorial returns the answer in %eax, but
                  #we want it in %ebx to send it as our exit
                  #status
 movl $1, %eax    #call the kernel’s exit function
 int   $0x80
#This is the actual function definition
.type factorial,@function
factorial:
 pushl %ebp          #standard function stuff - we have to
                     #restore %ebp to its prior state before
                     #returning, so we have to push it
 movl %esp, %ebp     #This is because we don’t want to modify
                     #the stack pointer, so we use %ebp.
 movl  8(%ebp), %eax #This moves the first argument to %eax
                     #4(%ebp) holds the return address, and
                     #8(%ebp) holds the first parameter
 cmpl $1, %eax       #If the number is 1, that is our base
                     #case, and we simply return (1 is
                     #already in %eax as the return value)
 je end_factorial
 decl %eax           #otherwise, decrease the value
 pushl %eax          #push it for our call to factorial
 call factorial      #call factorial
 movl 8(%ebp), %ebx  #%eax has the return value, so we
                     #reload our parameter into %ebx
 imull %ebx, %eax    #multiply that by the result of the
                     #last call to factorial (in %eax)
                     #the answer is stored in %eax, which
                     #is good since that’s where return
                     #values go.
end_factorial:
 movl %ebp, %esp #standard function return stuff - we
 popl %ebp       #have to restore %ebp and %esp to where
                 #they were before the function started
 ret             #return to the function (this pops the
                 #return value, too)

I have no idea if I'm missing something, or didn't pay attention when I should've, or what. The rest of the book is all very easy for me to understand. For whatever reason, learning about recursive functions in C took me a few minutes ... but it only took a few minutes for me to slap myself.

This is ridiculous. I understand all the parts of this program, but not how they add up somehow. I've written it out, gone over it, maybe someone else would appreciate having a good explanation, I'm sleepy, etc.

nowonmai · 08-12-2009, 05:32 AM

It looks pretty straightforward...
The factorial keeps calling itself and decrementing its parameter (in eax) until it's equal to 1 at which point it returns, and moves the eax to ebx which will be returned to the calling program (or OS).

johnsfine · 08-12-2009, 05:56 AM

It would be hard to improve on the comments in that program. They explain everything clearly.

It is even harder to guess which aspect of the program you don't understand. If you understand each part, the total should take care of itself. With more complicated recursive functions that is the only way to "understand" the whole thing:

1) Assume the recursive function works correctly in all the places where it is called by itself.

2) Check whether it works correctly in all cases at the top level. (Including that the recursion is on "simpler" input).

For (2) we see the function is correct on its own if the input is 1. Then we see that for inputs greater than 1 it uses the (assumed correct) recursion to compute factorial for input minus one (which is "simpler" input) and then multiplies that result by the input.

Did you not know the recursive definition of factorial?
factorial(0) = 1
factorial(N) = N * factorial(N-1)

Do you not see how the asm code performs that operation (except they work only for 1 and up, not for 0).

In most asm coding you need to give some extra thought to understanding the stack layout. The comments in that code pretty well covered that (except they said "pops the return value, too" when they should have said "pops the recursive calling parameter if any").

You should understand the stack and calling conventions from the outside as well as from the inside:

From the outside:
pushl calling_parameter
call factorial
;now or later remove the calling parameter from the stack
;the result is in eax

From the inside
;calling parameter is at 4(%esp) return address is at 0(%esp)
pushl %ebp
movl %esp, %ebp
;now calling parameter is at 8(%ebp) return address is at 4(%ebp)

We can optionally push or not push another value on the stack because
movl %ebp, %esp
;Restored esp to what it was just after the above pushl %ebp
popl %ebp
ret
;The stack is back the way it was before the call

joeBuffer · 08-12-2009, 05:59 AM

I can't believe it. It's obviously very simple. I'm missing something, here.
Everything up to

Code:

je end_factorial
 decl %eax           #otherwise, decrease the value
 pushl %eax          #push it for our call to factorial
 call factorial      #call factorial
 movl 8(%ebp), %ebx  #%eax has the return value, so we
                     #reload our parameter into %ebx
 imull %ebx, %eax    #multiply that by the result of the
                     #last call to factorial (in %eax)
                     #the answer is stored in %eax, which
                     #is good since that’s where return
                     #values go.
end_factorial:
 movl %ebp, %esp #standard function return stuff - we
 popl %ebp       #have to restore %ebp and %esp to where
                 #they were before the function started
 ret             #return to the function (this pops the
                 #return value, too)

is very straightforward and easy for me to understand. I have no idea, past this point, what I'm missing. I don't see what is happening, the order it's happening, anything, to cause this to work properly.
WHY, when you get to the test, and %eax does equal 1, and you jump to end_factorial, is everything else taken care of? What happens? I swear on anything ... I have never once seen a code example of any kind that has annoyed me so much in my life. Never.
So, like a C program, then you hit 1, jump to end_factorial, the rest finish and fall through to end_factorial? The %eax does double duty. It's decremented, and it's multiplied by %ebx to hold the return value. %eax doing double duty is one confusing thing to me, maybe one of the reasons I have lost track here.
I'm very, very, very tired of looking at this code.

joeBuffer · 08-12-2009, 06:11 AM

Quote:

Did you not know the recursive definition of factorial?
factorial(0) = 1
factorial(N) = N * factorial(N-1)

I know that, for instance, 5! is 5*4*3*2*1, and I didn't get the ! from the assembly book, either. The recursive definition I've never thought of.

Quote:

In most asm coding you need to give some extra thought to understanding the stack layout. The comments in that code pretty well covered that (except they said "pops the return value, too" when they should have said "pops the recursive calling parameter if any").

You should understand the stack and calling conventions from the outside as well as from the inside:

1. "pops the return value, too" I noticed myself. I thought it should've said "pops the return address". ?????
2. This book is using the C calling convention. Everything in this book so far I understand, yes. I understand the stack, and the process that is taking place in the rest of the examples in this book, so far.

Quote:

It would be hard to improve on the comments in that program. They explain everything clearly.

VERY.

I have no idea what I'm not understanding, that's the problem. Possibly, like I said in my last post, %eax doing double duty. I'm very frustrated, I have never run into a problem like this when reading code, especially examples like this, with comments and everything, in the middle of a book that is easy for me to understand. I'm used to C and PERL and bash scripting, and things like that. For some reason, this code just fell apart for me.

johnsfine · 08-12-2009, 06:57 AM

Look at this C code

Code:

int factorial(int input) {
   int result = input;
   if ( result == 1 ) goto end_factorial;
   --result;
   result = factorial( result );
   result *= input;
end_factorial:
   return result; }

Do you understand that C code? Do you understand the many uses of the variable "result" in that C code?

In asm %eax is the result variable (that is a rule of the calling convention). %eax also gets used a lot for other things. There are only a few registers and %eax is the most convenient register for most operations.

Compare to some better looking C code

Code:

int factorial(int input) {
   int result = input;
   if ( result != 1 ) {
      result *= factorial( result - 1 ); }
   return result; }

Why can't we do that version in asm?

1) We don't have general purpose if statements, we can only use if in combination with goto. So we needed the label.

2) The function result is always returned in %eax, so when we call factorial recursively we lose the value of result replacing it with the result of the recursive call. So we cannot do
result *= factorial( ...
We can only do
result = factorial( ...
Now look back at my first C version and it should make sense.

joeBuffer · 08-12-2009, 07:37 AM

To tell the truth, other than applying it to computers, I have absolutely no interest in math or 95% of science. Some geometry is good to know, etc. I've sort of been learning and doing as much as possible without getting into extremely mathematical topics. When a simple, silly example like this makes me scratch my head for 24 hours, I feel very, very far from caring enough about it to extend the amount of time spent to 10 years in school and college just so I can breeze through an introductory assembly book.
On a separate topic, and at the risk of having this thread moved to general, what is your opinion on why mathematics is a good thing to learn? Take computers for instance, what do you apply it to? What else is it good for?

johnsfine · 08-12-2009, 08:19 AM

Quote:

Originally Posted by joeBuffer

On a separate topic, and at the risk of having this thread moved to general, what is your opinion on why mathematics is a good thing to learn?

All math concepts were trivial for me when I was a teenager (though I was quite impatient with a lot of the terminology and symbols), so I didn't worry about what it was good for. It just was easy.

I can't really imagine what life would be like not knowing math well. When I read any news story involving any aspect of economics or public policy or many other topics, I always notice the mathematical aspects of it and usually see that the authors of the story depend on their readers not understanding the math of the situation in order to mislead those readers (most news is written with a liberal bias and clear intent to mislead).

When I shop, I like to get the best value and I notice that "unit prices" on the shelf labels in the supermarket are often incorrect (sometimes wildly incorrect) so if you want to compare by unit price you need to be comfortable with arithmetic.

I'm not very handy with mechanical or physical things, so when I do them (repair a bike, cut down a tree, buy the right amount of paint to paint something, etc.) I try to plan well to compensate for lack of skill. Planning physical tasks (especially when done in an unusual amateur way) often requires significant math.

Quote:

Take computers for instance, what do you apply it to?

Graphics and game programming involve a lot of trig and matrix math. Even calculus can be applied to good effect if you are used to it.

The computer work I currently do involves a lot of more serious math, most of which is beyond my current level of math expertise. (Near the end of high school I found myself loosing most of my math skills and they never came back. I retained math skills well above the top 1% of ordinary people, but that is only a fraction of what I had when I was 15).

The work requires math skills beyond what I have, electrical engineering knowledge beyond what I have, and software engineering skills beyond what anyone at my work other than me has. That is why hard projects need good teams. But relative to your question, there are important parts of computer programming where math skill merely way better than ordinary people doesn't even start to cover it.

neonsignal · 08-12-2009, 09:11 AM

Recursion is not always an easy concept to grasp, so don't be hard on yourself. The 'aha' moment will come. It is worth thinking about the concept before you get caught up in the implementation, because it is one of the most significant concepts in programming.

The factorial example is not the best use of recursion, but it keeps the example short.

Imagine that you wrote a whole lot of functions to give factorial values:

int f1() {return 1;}
int f2() {return 1*2;}
int f3() {return 1*2*3;}
int f4() {return 1*2*3*4;}
int f5() {return 1*2*3*4*5;}

and so on.

But then you see a lot of code is in common, so you rewrite to make use of the earlier functions in the later ones:

int f1() {return 1;}
int f2() {return f1()*2;}
int f3() {return f2()*3;}
int f4() {return f3()*4;}
int f5() {return f4()*5;}

and so on.

When you evaluate f5, it calls f4, which calls f3, etc.

Then you can see that f2, f3, f4, f5 are really all the same function, just with different values being used in the multiply.

So they can be roughly rewritten as:

int f1() {return 1;}
int fn(int x) {return fn(x-1)*x;}

This is the heart of the recursion. But it doesn't work properly yet. The problem is that when fn is called, it just keeps calling itself forever. It needs a termination condition, so that it stops at f1. This is done by combining fn and f1:

int fn(int x) {if (x == 1) return 1; else return fn(x-1)*x;}

And there is your recursive function. The 'if' stops it from going on forever, and the 'else' is the heart of the recursion.

When using recursion in practice, the approach is sometimes the opposite to this. Recursion is most useful when the problem is too complicated, and needs to be broken up into stages.

For example, if you were coding a chess game player, you want to examine all the possible moves and their consequences. This is difficult, because each move leads to many other moves, and so on. You can't just write a loop to search all the moves, because there are many branches ahead.

So instead of writing a hugely complicated function, you just assume that this 'all-the-following-moves()' function already exists. You write a function that merely evaluates the first move, then calls the pretend function to do the rest.

"for each possible current move, choose the best according to all-the-following-moves()"

Of course, the rules of chess don't change from move to move, so the simpler function you have written already encompasses the whole problem; instead of calling a pretend 'all-the-following-moves', the function just calls itself (recursion). Each invocation checks the current possible moves, then uses itself to check the second move, and so on.

That's an oversimplification: you have to find some way to end the recursion; in chess you have to alternate between the players; and you might need to reduce the number of possibilities or it will take too long. But it demonstrates how recursion can turn a complicated problem into a simpler one.

joeBuffer · 08-12-2009, 04:56 PM

I think I basically understand, I'll have to read some more. These posts have been helpful, but it's just this assembly example, sort of. I'll figure it out completely before reading more of this book, so it doesn't bother me.

RaptorX · 08-12-2009, 05:49 PM

Quote:

Originally Posted by neonsignal

So they can be roughly rewritten as:

int f1() {return 1;}
int fn(int x) {return fn(x-1)*x;}

This is the heart of the recursion. But it doesn't work properly yet. The problem is that when fn is called, it just keeps calling itself forever. It needs a termination condition, so that it stops at f1. This is done by combining fn and f1:

int fn(int x) {if (x == 1) return 1; else return fn(x-1)*x;}

And there is your recursive function. The 'if' stops it from going on forever, and the 'else' is the heart of the recursion.

And this, my friend, was a quality post.

I would add to the whole topic that when you are tired things simply dont go through, you should try and stand up from the computer, take some air, eat something, and then come back and write everything up or talk out loud to help your brain to `just get it, damn it!!`...

Everybody can understand everything but the most important thing is to understand how YOUR brain understands things easier... do you get it?

joeBuffer · 08-12-2009, 06:18 PM

Okay, I have a more specific question. How does %eax end up with the right return value.
When you make a recursive call to the function, and make a recursive call to the function, and make a recursive call to the function, and then it ends, then the rest finish up. How does the proper return value end up in %eax? If %eax is used for pushing the argument to the stack AND used for holding the return value, how do both work?
How are the values built up to the return value?
The whole function at the end is like someone put it in a blender, to me.

Also, using Google and entering "recursion", then clicking on recursion when it asks "did you mean recursion" has helped me so far, but I'll have to use it some more.

RaptorX · 08-12-2009, 06:51 PM

Code:

 cmpl $1, %eax       #If the number is 1, that is our base
                     #case, and we simply return (1 is
                     #already in %eax as the return value)
 je end_factorial
 decl %eax           #otherwise, decrease the value
 pushl %eax          #push it for our call to factorial
 call factorial      #call factorial

I guess there is the answer.

recursion is basically doing the same over and over again UNTIL you reach a specific condition [or that is one of the ways of using recursion].

In this case you are decreasing the value of %eax over and over again with the factorial function UNTIL it reaches 1. Each time you decrease it you perform a specific task OVER AND OVER. That is recursion in a very general way.

So, we get !5, we pass that number to our function, which then checks if 5==1, not true, then decrease that number, which makes 4, and do all over again. Hence I pointed out that
everything is explained right here:

Quote:

int fn(int x) {if (x == 1) return 1; else return fn(x-1)*x;}

Look closely. The function "fn" says, IF x==1, then exit. Thats the condition to go out of the loop, and while x != 1 then you gonna (5-1 * 4) OVER AND OVER AND OVER, you keep calling the function to make sure to test if x == 1.

The answer IS there you just have to make your brain see it. Talk the function out loud, write the output of the program like:

fn (int 5) { if (5 == 1) return 1; else return fn(5-1)*5;}

note that the return is then:

fn (int 4) { if (4 == 1) return 1; else return fn (4-1)*5;}
fn (int 3) { if (3 == 1) return 1; else return fn (3-1)*5;}

and so on...

Dont forget the multiplication at the end of the function... note that the multiplication will happen at the end because it is NESTED..

By writing it or talking it maybe you get the idea of what is it doing... it should be the same with the original code that you posted, probably the comments are making it difficult for you to see it.

neonsignal · 08-12-2009, 07:20 PM

Quote:

If %eax is used for pushing the argument to the stack AND used for holding the return value, how do both work?

Ah, but it isn't used for both at the same time. It is used for the argument on the way in, and for the answer on the way out.

Once you reach the bottom, the values (5, 4, 3, 2, 1) have all been pushed on to the stack by the 'pushl %eax' before the recursive call to factorial.

On the way out, eax can no longer be used to get the parameter (because it has been overwritten with the working result). Instead, the parameter is grabbed from the stack and put into ebx by the 'movl 8(%ebp), %ebx' following the recursive call to factorial.

It might have been clearer if they had used different registers for the parameter and for the result (especially the termination value 1, which relies on the trick that the parameter is the answer, so they don't bother explicitly setting eax).

joeBuffer · 08-12-2009, 07:50 PM

thank you

Quote:

On the way out, eax can no longer be used to get the parameter (because it has been overwritten with the working result). Instead, the parameter is grabbed from the stack and put into ebx by the 'movl 8(%ebp), %ebx' following the recursive call to factorial.

This is what I completely overlooked. Like I said, I was sitting here looking at it, and it got to a point where it was like someone hit the button on a blender. That's exactly what I was missing, for some reason.