## Lab Assignment 02b

### Goals

These exercises are intended to give you more practice with function calling—in particular, what goes onto the stack.

Sections 2.5-2.7 (3rd) or 2.6-2.8 (4th) in P&H.

### Initial preparation

You may work with a partner on these exercises.

Copy the directory ~cs61c/labs/02b to an appropriate directory under your home directory.

### Survey (Required)

Please complete our survey here. It contains important information for the next project, plus some other feedback questions.

### Exercise 1 (2 points)

This exercise uses the file `listmanips.s`.

We might have left Scheme behind with CS61A, but we definitely want to bring our friends `map` and `reduce` along with us! In this exercise, you will complete an implementation of `map` in MIPS. Our function will be simplified to mutate the list in-place, rather than creating and returning a new list with the modified values. Our `map` procedure will take two parameters; the first parameter will be the address of the head node of a singly-linked list whose values are 32-bit integers. So, in C, the structure would be defined as

```struct node {
int value;
struct node *next;
};
```

Our second parameter will be the address of a function that takes one int as an argument and returns an int. We'll use `jalr` (see below) to call this function on the list node values.

Our `map` function will recursively go down the list, applying the function to each value of the list nodes, storing the value returned in that node. In C, this would be something like this:

```void map(struct node *head, int (*f)(int))
{
}
```

If you haven't seen the `int (*f)(int)` kind of declaration before, don't worry too much about it. Basically it means that `f` is a pointer to a function, which in C is used exactly like any other function.

You'll need to use an instruction you might not have learned before to implement this: `jalr`. `jalr` is to `jr` as `jal` is to `j`. It jumps to the address in the given register and stores the address of the next instruction (i.e., `PC+4`) in `\$ra`. So, if I didn't want to use `jal`, I could use `jalr` to call a function like this:

```# I want to call the function garply, but not use jal.
la \$t0 garply # so I use la to load the address of garply into a register (\$t0)
jalr \$t0      # and then use jalr to jump and link to it.
```

There are 7 places (6 in `map` and 1 in `main`) in the provided code where it says "YOUR_INSTRUCTION_HERE". Replace these with instructions that perform as indicated in the comments to finish the implementation of `map`, and to provide a sample call to `map`with `square` as the function argument. When you've filled in these instructions, running the code should provide you with the following output:

```List Before: 9 8 7 6 5 4 3 2 1 0
List After: 81 64 49 36 25 16 9 4 1 0
```

### Exercise 2 (1 point)

Add the prologue and epilogue to the code in nchoosek.s so that it computes "n choose k". the number of combinations of n distinct elements taken k at a time. (This is also the (n,k) entry in Pascal's triangle.)