CS 136 Assignment 4

LANGUAGE FEATURES

In this assignment, you may only use the C features covered in class up to and including Section 05.
To avoid any possible issues with stack overflow you may not use recursion.
You may not use read_int or read_char to read input, but you may use scanf and read_symbol.
No int in any of the questions or your tests can exceed +/- 2,147,483,647. None of our private tests will intentionally cause an integer overflow.

Question 1: Introduction to structures with pointers.

[20 marks correctness]

In this question, we will explore some basic uses of structures and pointers.

BLACK QUESTIONS (moderate collaboration allowed)

[q1a-people] This question is about people, but it is also about learning some common techniques on how to implement and work with structures.

Making structures: By now we know how to initialize structures, for example, struct foo my_foo = {` ... `};. An oftentimes preferred alternative is the use of make-functions, such as, struct foo foo_make(...);. These functions accept the structure values as parameters, create a new structure, assign the values to the structure fields, and finally return the new structure. The advantage of such functions is that they can already check and / or process some of the structure data before storing them in the structure fields.

Structures as parameters and return values: By now we know that functions can receive structures as parameters and also return structures to the caller function, for example, struct foo func(struct foo param) {` ... `}. The parameter param is not a pointer; therefore, it is passed by value. This means that the structure itself is copied into the stack frame of func upon being called. This implies that any mutation to param in func will happen on the stack frame of func only. Any mutation is therefore lost the moment func returns, as its stack frame is "popped off" the stack memory on return. To make any changes persistent, you must copy param, update the fields of its copy accordingly, and then return the copy.

Structure pointers as parameters: By now we know that function calls can be "expensive" in terms of performacne because a substantial amount of data may be copied into the stack frame of the called function. A more efficient solution is using a pointer to the data as parameters, for example, void func(struct foo *param) {`... `}. The parameter param is a pointer. This means that the address of the structure is copied into the stack frame of func, and the actual data remains on the stack frame of the caller function, e.g., main: therefore, struct foo is passed into func by reference. As a result, any mutation to param in func will take place on the stack frame of the caller function. Any mutation is therefore maintained even after func returns, because the caller's stack frame remains in stack memory. There are several advantages of passing by reference: first, it makes function calls faster since less data has to be copied into the stack frame of the called function; second, since all mutations happen through the pointer, we now do not have to use the return-statement anymore to return the mutated structure; instead, we can use it as an additional communication channel. Oftentimes, this channel is used to indicate if the function encountered an error.

Implement the struct person for storing information related to a, well, person. This struct has three fields: the name of the person, for simplicity sake modelled as a single char and the age and height of the person, both modelled as int.
Implement the function person_make(name, age, height). This function takes the name, the age, and the height of a person and returns a struct person that is filled with this information. The function should make sure that name is an upper-case letter and that both age and height are positive.
Implement the function birthday_byvalue(p). This function first increments the age of p by one, and then adds 6 to height if age is 18 or lower. The function returns a struct person with the updated field values.
Implement the function birthday_byref(p). This function first increments the age of p by one, and then adds 6 to height if age is 18 or lower. Since birthday_byref is a quite simple function, we can assume that it will never fail; therefore, the function does not return anything.
Implement the function person_print(p). This function prints out information p to the console. Please use the format string "Name %c: age %d, height %d\n" in your printf-call.

For this question, the Marmoset basic tests ("public" tests) will be the same as in simple.in.

Hints:

We have already implemented a simple main-function, which provides basic I/O-testing. Please don't hesitate to modify this function to fit your needs and don't forget to include more test.

GOLD QUESTIONS (no collaboration allowed)

[q1b-family] This question is about family, but it is also an introduction to linked data.

Re-implement struct person. This struct has four fields: the name of the person, for simplicity sake modelled as a single char, the age and height of the person, both modelled as int, and child, which is of type struct person *.
Re-implement the function person_make(name, age, height). This function takes the name, the age, and the height of a person and returns a struct person that is filled with this information. Like before, person_make should assert that name is an upper-case letter and that both age and height are positive.
Re-implement the function person_print. This function prints out information about a person to the console. Please use the format strings "Name %c: age %d, height %d, child -\n" and "Name %c: age %d, height %d, child %c\n" in your printf-call. (Think about when to use which of the two outputs.)
Implement the function add_child(parent, child). This function attaches a child to a parent. The function returns 0 if it succeeds, 1 if parent already has another child attached (unfortunately, our implementation only allows for single-child families), 2 if child is older than parent (unfortunately, our implementation does not allow for time travel), {`and 3 if parent already has another child attached, and child is older than parent [ADDED JUN 14]`}. This function showcases the above-mentioned use of the return-value as error code. Semantically, the return-value can be interpreted as an answer to the question "Was an error encountered?": 0 translates to false, i.e., no error encountered, and any larger value translates to true, i.e., some error encountered. If necessary, the returned (error) number gives additional details.
Implement the function family_print(p). This function prints out information (using person_print) about p, their child, their child's child, their child's child's child, and so on, to the console.

For this question, the Marmoset basic tests ("public" tests) will be the same as in main.

Hints:

Feel free to copy and extend your code from [q1a-people].
Please don't hesitate to modify the main-function to fit your needs and don't forget to include more test.

Question 2: Introduction to pointers with structures.

[20 marks correctness]

In this question, we want you to explore the wonderful world of rational numbers in C. Quick reminder: rational numbers are those that can be expressed as a fraction, i.e., a numerator divided by a denominator. For example, 5 can be written as ⁵/₁; 3.75 as ³⁷⁵/₁₀₀ or simplified as ¹⁵/₄; and -3.333... as ^-10/₃.

We must disappoint you, however, if you thought that we will be using floating-point data types: they are just not precise enough for our purpose! (If you don't believe us try printf("%f\n", 100000010.0f); and see for yourself.) Instead, we want you to create your own data type!

BLACK QUESTIONS (moderate collaboration allowed)

[q2a-rationals] In this part, we want to set up some basic functionality for rational numbers.

Implement struct rtnl for storing rational numbers. This struct has two fields, num (short for numerator) and den (short for denominator); both fields are of type int.
Implement the function rtnl_simplify(r). This function simplifies r as much as possible. For example, ²/₆ would be simplified to ¹/₃ and ^-4/_-5 to ⁴/₅. If r is negative, the function assures that the numerator is negative and not the denominator; for example, ⁴/_-5 would become ^-4/₅.
Implement the function rtnl_make(num, den). This function accepts the numerator num and the denominator den of a rational number as parameters and returns a struct rtnl. The returned rational number must be simplified.
Implement the function rtnl_plus(a, b). This function calculates the sum of two rational numbers, a and b, and returns it as a struct rtnl. The returned rational number must be simplified.

For this question, the Marmoset basic tests ("public" tests) will be the same as in main.

Hints:

For the simplification algorithm, you might have to implement some helper functions, e.g., for calculating the greatest common divisor.

GOLD QUESTIONS (no collaboration allowed)

[q2b-rationals] Now, let us add some more functionality, which we will need for more complex operations later.

Implement the function rtnl_minus(a, b). This function calculates the difference of two rational numbers, a and b, and returns it as a struct rtnl. The returned rational number must be simplified.
Implement the function rtnl_mult(a, b). This function calculates the product of two rational numbers, a and b, and returns it as a struct rtnl. The returned rational number must be simplified.

As the final step, we want to use our rational numbers to solve a real-world problem in 2D linear algebra: the distance between two points in Euclidean space.

Implement struct p2d for storing a point in two-dimensional Euclidean space. This struct has two fields, x and y; both fields are of type struct rtnl *.
Implement the function p2d_make(x, y). This function accepts the x- and y-coordinates of a point in two-dimensional Euclidean space as parameters and returns a struct p2d.
Implement the function p2d_dist_euclid(p, q). This function calculates the Euclidean distance of two points, p and q, and returns it as a struct rtnl. The returned rational number must be simplified.

For this question, the Marmoset basic tests ("public" tests) will be the same as in main.

Hints:

For your convenience, we have implemented all functions from [q2a-rationals] in the library rtnl_math in [q2b-rationals]. There is no need to re-implement or copy any code from [q2a-rationals].
If you are stuck, please realize that the functions we want you to implement as well as their order in the assignment is chosen carefully and on purpose.
For p2d_dist_euclid, you have to calculate the square-root of a struct rtnl. We have implemented the function rtnl_sqrt for you. Be aware that due to the nature of square root and limitation of C, the results of this function are inherently imprecise.

[5 BONUS marks]

[q2c-bonus] As a bonus step, we want to solve another, more complex 2D linear algebra problem.

Implement struct l2d for storing a line in two-dimensional Euclidean space. This struct has two fields, both of type struct p2d *.
Implement the function l2d_dist_to_p2d(l, p). This function calculates the distance between a line l and a point p, and returns it as a struct rtnl. The returned rational number must be simplified.

For this question, the Marmoset basic tests ("public" tests) will check if your code compiles.

Hint:

Please don't hesitate to copy already implemented functions from [q2b-rationals] over to [q2c-bonus]. You will probably also need a few additional helper functions.

Question 3: I/O testing suite

[20 marks correctness]

The goal of this question is to do the "other half" of Assignment 1 Question 2 (A1 [q2-bakery]). In that assignment question, you were tasked to implement a series of functions that modelled the behaviour and state of a cookie-bakery. You were also able to issue commands, such as, bake and dough 10, to the bakery via the console or a .in-file. The connection between these commands and the called functions, however, was implemented by us, and you were not able to see any details. We hid these implementation details because you did not have the knowledge back then to implement an I/O test suite yourself. Congratulations, you now know everything to implement the entire bakery!

We have provided you with an implementation of all six bakery-functions (just like in A1 [q2-bakery], the functions are in the file main.c). We did, however, change one crucial detail of the code: instead of using global (mutable) variables, we are now using a struct bakery named my_bakery to store the state of the bakery (i.e., the amount of dough and chocolate chips in the bowl, and the amount of cookies baked). The struct-definition was added to bakery.h. my_bakery is initialized in the main function in main.c, and it is then passed by reference into run_bakery in bakery.c. As a result, we also had to add struct bakery as a parameter to all six bakery-functions. Essentially, my_bakery (or more precisely: a pointer to my_bakery) is supposed to "travel" from main, via run_bakery, into show_bowl, backe_cookie, and all other bakery-functions.

GOLD QUESTIONS (no collaboration allowed)

[q3-bakery] Your task is completing this "travel" by implementing run_bakery. As we said before, the purpose of run_bakery is reading commands and, if necessary, additional parameters from the console or a .in-file and then calling the correct bakery-function. In [q3-example], you can see how such an I/O-test suite can be implemented with the help of lookup_symbol, read_symbol, loops, conditionals, etc. The only major difference between [q3-example] and [q3-bakery] is that the I/O-test suite and the functions to be tested are split into two files, bakery.c and main.c respectively. To make these two files work together in a single program, you would need to know more about modules, which we will discuss in Section 06. All you need to know in the meantime is that the code at the top of bakery.c allows you to call the six bakery-functions in main.c from within the run_bakery-function just as if they were defined in the same file.

Just like in A1 [q2-bakery], there is a list of all supported commands in bakery.h; note that the commands are the same as in A1 [q2-bakery]! If an unsupported command is issued, print "Error: not a command\n"; if an invalid number is issued as a parameter, print "Error: not a number\n". In both cases, exit the program.

For this question, the Marmoset basic tests ("public" tests) will be the same as in simple.in.

Question 4: Function pointers and higher-order functions

[20 marks correctness]

One "strange", yet totally awesome concept that emerged from functional programming are higher-order functions. A higher-order function takes one or more other functions as parameters and apply them to data. For example, the higher-order function map[func list] would apply func to all elements on list. Unfortunately, higher-order functions are not part of the core C99-standard. Luckily, function pointers exist in C, which allows us to implement higher-order functions ourselves.

BLACK QUESTION (moderate collaboration allowed)

[q4a-mapping] For this question, you have to implement the higher-order function map.

Implement main. This function performs I/O-based testing by reading a symbol, which indicates the name of the function to use, from input and then calling the function map using a pointer to that function as parameter. The three supported symbols are abs, neg, and sgn.
Implement map(func). This function takes a single parameter func, which is a pointer to a function. It uses scanf to read all remaining integers from input and applies func to each integer individually. It then outputs each integer as well as the result of the call to func using the following printf format string: "%d => %d\n".

The function uses the "standard" approach for I/O-based testing, similar to [q3-example]. The program in main_ptr.c in [q3-example] showcases quite nicely how the use of function pointers can result in shorter, less repetitive, and cleaner code, compared to the one in main.c.

You can assume that all input will be well-formatted, i.e., each line consists of a symbol followed by a series of integers. If the function [Jun 18] is invalid, i.e., belonging to an unregistered function, output "Invalid function.\n" and exit the program.

Hint:

A good test case would be adding a new math-function, for instance, int cube(int n), to your program. You have succeeded in your implementation of map if you only have to modify main but not map.
For this question, the Marmoset basic tests ("public" tests) will be the same as the tests provided. You must create your own I/O tests.

GOLD QUESTIONS (no collaboration allowed)

[0 BONUS marks]

LANGUAGE FEATURES: For [only] this question, you may use recursion.

[q4b-bonus] This bonus question is worth 0 marks! Only attempt it if you have some spare time and are curious about function pointers with function pointers.

In [q4a-mapping] we saw how we can use function pointers to write more abstract code: instead of needing I/O functionality for each of the three math functions (abs, nrg, and sgn), we only had to write a single I/O function, map, which then delegated result calculation to the correct math function. We were also able to add more math-functions without having to modify map or duplicate any code. The call to map itself, however, was hard-coded in our main-function. What happens if we don't want this call to be hard-coded? What happens if we want to obtain the higher-order function from input as well?

We can achieve this easily (?) by adding another layer around the existing code from [q4a-mapping]. To make things a bit more interesting, we shifted away from mapping and towards folding for our higher-order functions. For your convenience, we already implemented the main-function.

Implement hof_apply. This function reads a symbol representing a function name from input and applies it to hof.
Implement the functions foldr and foldl. These functions read integers from input and fold them right / left using func. They also print a visual representation of the function calls. Please see the .expect-file for details.

The format of the input command is as follows: <hof> <func> [numbers] # [base], where <hof> can be foldr or foldl, <func> can be sum or prod, [numbers] is a series of int, and [base] is exactly one int. Like in [q4a-mapping], you can assume that all input will be well-formatted.

For this question, the Marmoset basic tests ("public" tests) will check if your code compiles.

Question 5: Style

[20 marks style]

BLACK QUESTION (moderate collaboration allowed)

You do not need to do anything for this question. By having this question, we want to let you know that one or more of the questions on this assignment will be hand-marked for coding style and the quality of your tests. We are not stating which question(s) because you should use proper style and testing on all questions.