Monash University > School of Computer Science and Software Engineering > CSE1303 > Part B > Tutorials > Tutorial B6

CSE1303 Computer Science
Semester 3 (summer), 2002
Part B
Tutorial B6

This tute covers material from lectures B14 to B16.

Attempt the questions marked (*) like this before the tutorial. If you have specific questions about unmarked questions, you can ask the tutor about them during the tutorial.

Functions: the big picture
1. Review the following list of reasons for writing functions, taken from lecture B14:
  - The basic unit of code re-use:
    - functions can be called repeatedly
    - functions can generalize by taking parameters
    - functions can inform through return values
    - functions are self-contained
  - Abstraction of implementation:
    - functions hide complexity from caller
    - functions can have their own private (local) variables/data
    - functions can call other functions
    - functions don't affect caller's environment
  What elements of the C language help to achieve the above goals?
2. Consider the simple leaf-function function calling convention given in lecture B14, in which arguments are passed in registers, and the stack is not used to save any values.
  Which of the list of reasons from the previous questions does this convention satisfy? Which does it fail to provide?
3. Consider the full stack-based function calling convention given in lecture B15. How does it solve the shortcomings of the leaf-function convention from the previous question?
Writing functions
1. (*) Consider the following uncommented MIPS code:
```
min:    subu $sp, $sp, 8
        sw $ra, 4($sp)
        sw $fp, 0($sp)
        move $fp, $sp
        subu $sp, $sp, 4

        lw $t0, 8($fp)
        lw $t1, 12($fp)
        bge $t0, $t1, one

        lw $t0, 8($fp)
        sw $t0, -4($fp)
        j end

one:    lw $t0, 12($fp)
        sw $t0, -4($fp)

end:    lw $v0, -4($fp)
        addu $sp, $sp, 4
        lw $fp, 0($sp)
        lw $ra, 4($sp)
        addu $sp, $sp, 8
        jr $ra
```
  Add comments to the code, and suggest what this function does and how it might be called. Suggest the C code that would have generated this function.
  Remark on the symmetry of the function entry (up to the first blank line) and exit (from the label end). In particular, comment on the statement, "Every subtract applied to the stack pointer has an equal and opposite addition later in the code."
2. The function calling convention given in lectures typically has functions accessing their first parameter at 8($fp), the second at 12($fp), the third at 16($fp), and so on.
  Is this order necessary? In other words, would it be possible to have the last parameter at 8($fp) instead, and the second-last at 12($fp), and so on (provided that all functions are changed to agree with this new convention)?
3. Why do you seldom see functions accessing the memory at address 4($fp)? (Hint: consult a stack diagram.)
4. (*) Say you are calling a function that has one 4-byte parameter, and returns a value in $v0. You write the following code:
```
        # y = func(x);
        subu $sp, $sp, 4   # one argument.
        lw $t0, x          # first argument is x
        sw $t0, 0($sp)
        jal func           # call function
        sw $v0, y          # store result
```
  Assuming that x and y are valid labels, what is wrong with this code?
  What is likely to happen to the program when it runs this code? What if this code were in a loop which repeats 1 million times?
5. In CSE1303, we've been writing the main function as it it were not a function at all. We don't save $fp or $ra, and we exit with a system call 10 rather than jr $ra.
  How would main's stack diagram differ if main were coded the same way as other functions? Would this complete main's (normally partial) stack frame? What does this tell you about the contents of the part of the stack that exists before main begins (the part that we always draw diagonal lines in)?
6. (*) Consider this C code:
```
#include <stdio.h>
#include <stdlib.h>

/* Prototype for isdigit() function. */
int isdigit(const int c);
int atoi(const char *s);

int main()
{
    int n;
    char s[20];

    printf("Enter a number: ");

    /* Read string. */
    fgets(s, 20, stdin);

    /* Find number at start of string. */
    n = atoi(s);

    printf("Number is: %d.\n", n);

    exit(0);
}

/* atoi(s): extract the integer value
 * encoded in ASCII at the beginning of
 * string s, and return it.  Radix is 10. */
int atoi(const char *s)
{
    int sign = 1;
    int result = 0;
    int digit;

    if (*s == '-')
    {
        /* Leading minus sign. */
        sign = -1;
        s++;
    }
    else if (*s == '+')
    {
        /* Leading plus sign. */
        s++;
    }

    /* Stop at end of string. */
    while (*s != '\0')
    {
        /* Pass character to isdigit as an int,
           to preserve stack alignment. */
        if (!isdigit((int) *s))
        {
            /* Also stop if non-digit found. */
            break;
        }

        /* What value does this digit have?
         * This works because in ASCII, '0' (48) to
         * '9' (57) are contiguous. */
        digit = *s - '0';

        /* Append this digit to our running total. */
        result = result * 10 + digit;

        /* Next character. */
        s++;
    }

    /* Return result multiplied by sign. */
    return result * sign;
}
```
  Assume that printf and fgets are implemented using system calls as usual, and that isdigit is another function which obeys the normal function calling convention.
  Draw a stack diagram for main.
  Draw the stack as it appears on entry to atoi.
  Draw the stack as it appears on entry to isdigit (assume that this function has no local variables).
  Translate the above two functions (main and atoi) into MIPS. Try to make your translation as faithful as possible.
7. Write the isdigit function as described in the previous question, in C and MIPS.
Recursion
1. Function calling is implemented in MIPS (and other assembly languages) by saving a program's state (variables, return address, ...) on a stack before jumping to the start of a function, and restoring the state upon returning from the function. The same thing could also be done in C.
  Suggest a method for turning a recursive C function into a non-recursive C equivalent, with the help of a stack data structure. You are permitted to use goto statements in your code, though you should make an effort to clean them up afterwards.
  Under what circumstances could you dispense with the stack entirely?
2. (*) Consider this C code:
```
#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b);

int main()
{
    int x;
    int y;

    printf("Enter two numbers: ");
    scanf("%d%d", &x, &y);

    printf("Greatest common divisor is %d.\n", gcd(x, y));

    exit(0);
}

int gcd(int a, int b);
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}
```
  Draw a stack diagram for this program, at the point where the stack is the deepest, for the input x = 84, y = 30. Mark the stack frames on your diagram.
  Translate this program into MIPS. Try to make your translation as faithful as possible.

[ Top | Home ]

Last modified 2002-02-04

CSE1303 Computer Science Semester 3 (summer), 2002 Part B Tutorial B6

Functions: the big picture

Writing functions

Recursion

CSE1303 Computer Science
Semester 3 (summer), 2002
Part B
Tutorial B6