CS 251: Programming Languages

Fall 2017

hw7: C lab, part 2

Due: Wednesday, 10/04 at 22:00

This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should code your own assignment.

1. Goals

To understand arrays, pointers, and structs in C.

2. Introduction

This is a continuation of the C lab. Follow instructions from the previous homework set.

3. Continuing with C

Write a program guess.c that picks a random number between 1 and 100 and has the user repeatedly guess the number in a while loop, reporting whether the guess is too low or too high. For random numbers, use man 3 random:
```
#include <stdlib.h>
#include <time.h>

...

srandom(time(NULL));
long num = random();
```
For example, a run of your program might go like this:
```
Guess a number: 50
Too high! Guess again: 25
Too high! Guess again: 13
Too low! Guess again: 19
Too low! Guess again: 22
Too low! Guess again: 24
Too high! Guess again: 23
Correct! The answer was 23.
```
Use Git to add, commit, and push to GitHub when complete.
Arrays
You can declare an array in C by giving the type and size of the array. (See arrays.c for the full code listing.)
```
int array[10];
```
This allocates space on the stack for an array containing 10 integers.

Like Java, you can read and write elements of the array using bracketed subscript notation.
```
for (int i = 0; i < 10; i++) {
   array[i] = i;
}
```
Unlike Java, there's no way to find out the length of an array, so you need to keep track of an array's length yourself. (If you write past the end of an array, there's no check or "out of bounds error" and it will just modify whatever happens to be next in memory!) Try uncommenting the line:
```
array[10] = 5;
```
in arrays.c. (Note clang issues a warning not to write past the end of the array, but the program should still compile.) Observe how the value of x changes. What does this imply about the layout of main's stack frame in this program?

EXERCISE: Add code to arrays.c to calculate the sum of the array and print it. Add, commit, and push to GitHub when complete.
Pointers
The variable array is actually a pointer to the first element of the array. A pointer is a special type containing the address in memory. You can use pointer arithmetic to access the elements in the array.
```
printf("Array address: %p\n", array);
for (i = 0; i < 10; i++) {
   printf("Array element at address %p: %d\n", array + i, *(array + i));
}
```
Here the expression array + i gives the address of the ith element in the array. The * operator retrieves the value stored at the following address. So the expression *(array + i) retrieves the integer value stored at the address of the ith element in the array. In other words, *(array + i) and array[i] are doing the same thing.

Here's a quick summary of C's basic pointer operations (we'll go into more depth in class).
- & is "the address of," so &x evaluates to the address of x. (This should help clarify why we pass arguments to scanf using the & operator.)
- * is "the valued stored at," so *p gives the value stored at the address p. For this so-called pointer chasing to work properly, p must have a pointer type, indicated by a * in the type declaration. For example, int * is the type representing a pointer to an int. So if p has type T *, then *p has type T.
As an example, read, compile, and run the program pointers.c. Try drawing the execution of the program on paper, with boxes for memory locations and arrows for pointers. Can you see how we end up with the final values for a and b? (You don't need to hand in your drawings or explanations.)

EXERCISE: Write a program stack.c that illustrates whether the the program stack is growing "up" or "down." In other words, are new stack frames allocated at higher or lower addresses than old stack frames? Explain your answer in comments in stack.c. You should NOT assume that variables in a single function are allocated in the order they're declared. You can define a new function much like you would define a new method in Java; for example, here is a function that takes a string and returns nothing:
```
void foo(char *s) {
   ...
}
```
Add, commit, and push to GitHub when complete.
Structs
C is not an object-oriented language: it does not have classes or objects. However, you'll often run into situations where you want to group related values together. For this purpose, you can create a struct, a special kind of user-defined type.

Structs are defined using the keyword struct, a name for the struct, and a list of member variables within curly braces. For example, here's a struct to represent a student (see student.c for the full code listing):
```
struct Student {
   char *first_name;
   char *last_name;
   int id;
};
```
You can create an instance of a struct type by declaring it with the struct keyword, and access member variables using the dot (.) operator.
```
struct Student s1;
s1.first_name = "Rory";
s1.last_name = "Gilmore";
s1.id = 16757;
printf("%d: %s %s\n", s1.id, s1.first_name, s1.last_name);
```
EXERCISE: Create a new file complex.c. In this file, add a struct type struct Complex containing two doubles representing the real and imaginary parts of a complex number. Add a function multiply_complex to complex.c that takes two complex numbers and returns a new complex number representing their product. Include code testing your multiplication function in main. Use Git to commit and push to GitHub when complete.

(Note that if you have two complex numbers $c_1=a_1+b_1 i$ and $c_2=a_2+b_2 i$, then $c_1 \cdot c_2$ is the complex number whose real part is $a_1a_2 - b_1b_2$ and whose imaginary part is $a_1b_2+a_2b_1$.)

4. Optional Challenges

In the guessing game, choose a uniform random number in the range. You may assume that random yields a uniform random number. However, note that if you choose an integer $n\in\{1,2,\dotsc,251\}$ uniformly at random, and then compute $m = n\bmod100$, it is not the case that $m$ is uniform across $\{0,1,\dotsc,99\}$.

5. Submission

Follow the instructions from the previous homework set. That is:

Update credits.txt by listing anyone who helped you with the assignment (including lab assistants and classmates), and any websites, books or other sources you used for reference. Also briefly describe how you were helped. Please try to be thorough. If you didn't get any help, you could write something like "I worked alone." Add, commit, and push.
Double check to make sure you have commited the version you want graded.
Tag and push the tag:
```
git tag hw7
git push --tags
```
(Recall that a normal git push does not push tags. Be sure to check on GitHub to make sure that it received your final submission.)

Written mostly by Laura Effinger-Dean, with help from Kochan's Programming in C and Java labs written by Dave Musicant and Andy Exley. Some modifications by Dave Musicant, David Liben-Nowell, and Jed Yang.

Start early, have fun, and discuss questions on Moodle.