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