Due Date: Friday, June 19, 2020 at 9:00 pm.

- Before every assignment, make sure you read the
**updated**preamble. - Monitor the OFFICIAL A4 Piazza Post for any corrections, updates, or frequently asked questions.
- The assignment files are available here (they are also provided in Seashell).
- The questions are listed in (approximate) course chronological order, not necessarily in order of their difficulty or the amount of effort required.

- 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.

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

[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.

- Implement the

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.

[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.

- Re-implement

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.

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 ^{5}/_{1}; 3.75 as ^{375}/_{100} or simplified as ^{15}/_{4}; and -3.333... as ^{-10}/_{3}.

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!

[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,^{2}/_{6}would be simplified to^{1}/_{3}and^{-4}/_{-5}to^{4}/_{5}. If`r`is negative, the function assures that the*numerator*is negative and not the*denominator*; for example,^{4}/_{-5}would become^{-4}/_{5}. - 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.

- Implement

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.

[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.

- Implement the function
- 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.

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.

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.

[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.

- Implement

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.

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.

[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`.

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.

[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 ~~symbol~~ 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.

[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.

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.