## CS 3 (Spring 2022)Lab 03: C Abstraction

This lab will focus on various ways to utilize abstraction in your code to avoid code duplication.

# Setup

Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

# Sorting Arrays

In this lab, you will implement various algorithms which can benefit from using C abstractions to reduce code duplication. We’ll begin by writing functions that seem different and discover how to generalize across parameters, functions, and types. You’ve already seen most of these concepts, but this lab will teach you the C syntax for these patterns and reinforce noticing when these patterns exist.

Since this lab comes with a pre-made Makefile, we can use make main to compile our code, and then run it with ./main. Additionally, this lab comes with tests. To run them, use make test in the terminal.

## Conclusion 1: Abstraction by Parameterization

One way of reducing duplicated code or redundancy is identifying argument parameterizations of the problem that allow us to generalize. That is, adding the right parameters can allow us to solve harder problems with approximately the same code.

## Part 2: Writing More Sorts

### Interlude: Function Pointers

In C, we can make references to functions (i.e., “function pointers”), but the syntax is a bit wonky. The syntax allows us to pass around functions as values, which feels, in principle, like lambdas in Python and Java. Because the syntax is a bit hairy, we will always typedef away the definitions. A typical function pointer typedef looks like:

typedef RETURN_TYPE (*TYPE_NAME)(ARGUMENTS);

We will use function pointers primarily to generalize functions across types and orderings. Notably, there was a ton of redundancy between ascending_int_sort and descending_int_sort, because they’re effectively the same function. Just like before, we will add an argument to generalize the problem. This time, though, it will be a function pointer. We’ll do this in steps:

1. Introduce a function type to specify how to “compare” ints.
2. Define two functions that meet the type (one for ascending, and one for descending)
3. Write a more general function called int_sort which accepts one of these functions as an extra parameter

### Interlude: comparator_ts

We say a function is a comparator_t if it specifies a total ordering (<) over a type by taking in two arguments of the same type (say, a and b) and returning an int $$X$$ as follows:

• If a < b, then $$X < 0$$
• If a = b, then $$X = 0$$
• If a > b, then $$X > 0$$

It is useful to compare this to Java’s definition of compareTo and compare: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Comparator.html

In contrast, we will define an int_comparator_t as a function pointer in C as follows: typedef int (*int_comparator_t)(int a, int b).

## Conclusion 2: Abstraction by Functional Interfaces

One way of reducing duplicated code or redundancy is identifying functional parameterizations of the problem that allow us to generalize. That is, adding the right functions (as arguments) can allow us to solve more general problems with approximately the same code.

## Part 3: Writing Even More Sorts

### Interlude: void *

C does not have generics like Java does, but it does have a “generic pointer type” (that is, a pointer that points to an unspecified type) called void *. We can use (abuse?) this to get a mediocre substitute for generics (that is, abstraction over types). We’ll need to do two things to incorporate void *:

1. Generalize our idea of int_comparator_t and string_comparator_t to a single typedef for comparator_t that takes two void *’s instead of specific types.
2. Write a more general function called sort which accepts both a comparator_t argument as well as an array of void *’s.

## Conclusion 3: Abstraction by Types

One way of reducing duplicated code or redundancy is identifying type parameterizations of the problem that allow us to generalize. That is, using generic types can allow us to solve more general problems with approximately the same code. This is particularly important when implementing data structures, because we don’t want to write code for each type we want a list for.

# Getting Checked Off

Labs will be due the following Tuesday from when they are assigned, at 11:30 PST. You will need to get manually checked off for most labs, as we will not be using totally automated tests. To get checked off, make a ticket saying you are done, and we will check you off as soon as possible. Please include the link to your repo in the ticket.