CSC161 2010F, Class 39: Pointers to Functions

Overview:
* Homework 7
* Function Pointers.
* Lab.

Admin:
* Apologize: Behind in classprep.
* Potential Prospies on Friday.
* EC for G-Tones concert tonight in Loose Lounge.
* EC for RHPS this weekend.
* Two interesting performances by Ethel tonight and tomorrow night.
* Reading for Friday: K&R 7.5-7.7.
* Are there questions on Assignment 7?

Homework 7

* Don't we need to length of the arrays in order to sort?
  * Yes.  Sorry.  Fixed.
* What is merge sort?
  * Top down recursive version
    * Divide in half
    * Sort both halves with merge sort
    * Merge the two sorted halves.
 * Bottom-up merge sort
   * Merge neighbors into sorted lists of length two.
   * Merge neighbors into sorted arrays of length four.
   * Merge neighbors into sorted arrays of length eight
   * ...
   * Merge neighbors into a sorted array of length n.
 * For the generic merge sorts, quick sorts, etc. we need a way to
   compare elements generically

For ints
#define MAY_PRECEDE(x,y) x <= y
For doubles
#define MAY_PRECEDE(x,y) x <= y
For strings
#define MAY_PRECEDE(x,y) strcmp(x,y) <= 0

* How is "a" sorted vs. "ab"
  * I *believe* "a" comes before "ab" because '\0' comes before 'b'.
  * But you can accept whatever strcmp tells you.

Today's reading was on pointers to functions
* C lets you treat "function" as
  * parameter
  * something you assign to variables
  * something you can call
* One important difference: These functions are typed:
  * Something that returns an int should not be used in place of
    something that returns a double
  * Something that expects an int should not be used in place of
    something that expects a double

The type looks like this

RETURN_TYPE (*NAME)(PARAM_TYPES)

For example, fun is a function from integers to doubles

  double (*fun)(int x);

Now, suppose we'd written isqrt

  double isqrt(int x)

We can now write

  fun = isqrt;

More importantly, we can make functions parameters to other functions.

int sort(int vals[], int size, int (*may_precede)(int, int));

int ile(int x, int y)
{
  return x <= y;
}

int ige(int x, int y)
{
  return x >= y;
}

int c2z(int x, int y)
{
  return abs(x) <= abs(y);
}

sort (grades, 12, ile); // Sort my array of grades from smallest to largest
sort (grades, 12, ige); // Sort my array of grades from largest to smallest
sort (temps, 365, c2z); // Sort my array of numbers by closest to zero

How does this use of functions as parammeters differ from what we did in
Scheme (other than the use of types)?
* In Scheme, the symbol <= might have sufficed.
* In Scheme, we can use lambda expressions to build anonymous functions.
  In C, there are not anonymous functions.  (Okay, there weren't the
  last time I checked.)
* Higher-order functions?
  map
void
imap(int vals[], int size, int (*fun)(int))
{
  int i;
  for (i = 0; i < size; i++)
    vals[i] = (*fun)(vals[i]);
} // imap
void
PREFIX(map)(TYPE vals[], int size, TYPE (*fun)(TYPE))
{
  int i;
  for (i = 0; i < size; i++)
    vals[i] = (*fun)(vals[i]);
} // map
  keep: Given an array and a predicate, keep the elements that meet
    the predicate.
    * Hard in C b/c we don't have dynamic arrays (yet) in C.
  compose
(define compose
  (lambda (f g)
    ; Return a newly constructed function
    (lambda (x)
      (f (g x)))))
  It turns out that you can't write compose as a HOF in C.

Why did I say "I'm a Stooge" when I wrote a function called "Iggy"?
Is it because I have my TV Eye on you?  Is it because I want my
classroom to be a Fun House?  Is it in tribute to a dying (perhaps
dead) city?


Lab!

cp -r /home/rebelsky/public_html/Courses/CSC161/2010F/Examples/FunctionPoitners/* HERE