Transcript on Abstract Data Types (pptx)

COMP 40: Machine Structure
and
Assembly Language Programming (Fall 2016)
More on Abstract Data Types
Noah Mendelsohn and Mark Sheldon
Tufts University
Email: [email protected]
Web: http://www.cs.tufts.edu/~noah
Last time we covered
 How data and pointers are stored in the computer’s memory
 Abstraction, modularity, reuse, information hiding
 Generalizing over values and types
 The special role of void * and incomplete structures
Today
 Generalizing over computation
 Function pointers
 Iteration and mapping in a functional style
 Boxed and unboxed data structures
2
© 2010 Noah Mendelsohn
Quick Review
© 2010 Noah Mendelsohn
Software structures model real world objects and concepts
 Integers
 Students
 Bank statements
 Photographic images
The course materials refer to these
as being in the “World of Ideas”
 Sound recordings
 Etc.
We build data structures that model them
5
© 2010 Noah Mendelsohn
E.g. methods in Hanson table.h
Interfaces
Interface
Client
Implementation
E.g. your fgroups program
E.g. implementation of
Hanson Table_T
7
© 2010 Noah Mendelsohn
Interfaces
The implementation chooses a
representation … NOT visible to
the client
8
Interface
Client
Implementation
© 2010 Noah Mendelsohn
E.g. methods in Hanson table.h
Interfaces
Q. What can Table_new return?
Client
Interface
My_table = Table_new(…
… …)
Implementation
Last time we showed you two ways of doing this
E.g. your fgroups program
E.g. implementation of
Hanson Table_T
9
© 2010 Noah Mendelsohn
Hanson does this with incomplete structs
struct Table_T *table_ptr;
struct Table_t *table_ptr;
Client has
incomplete
declaration of the
struct
Interface
Client
Struct Table_t {
…data declartions…
Implementation
}
my_table = Table_new(…
Table_put(my_table, …)
13
… …)
© 2010 Noah Mendelsohn
By the way, this is exactly what languages like C++ do
class Myclass
{
int some_method(int a) {…};
}
Myclass my_object = new Myclass();
my_object -> some_method(5);
Under the covers, C++ implements this as:
some_method(my_object, 5);
14
© 2010 Noah Mendelsohn
Generalization
© 2010 Noah Mendelsohn
You’ve already seen some generalization
int square3()
{
return 3 * 3;
}
We don’t do this
int square(int n)
{
return n * n;
}
We do this!
Generalize over input value
Can we generalize over the type of information?
16
© 2010 Noah Mendelsohn
We need to generalize over types
List_of_students_new(…);
List_of_cars_new(…);
List_of_bank_stmts_new(…);
List_new(…);
We want this!
We don’t want this
Can we generalize over the type of information?
How do we declare the input to List_push()?
(after all, its type could be anything)
17
© 2010 Noah Mendelsohn
How do we declare List_push?
void List_push(List_T list, void *x);
Hanson’s declaration for List_push
struct Car {char *brand; int weight};
typedef struct Car Car;
Car mycar = {“ford”, 2000};
Car *retrieved_car;
mylist = List_list(NULL);
List_push(mylist, &mycar);
18
/* create empty list */
/* put my car on the list */
© 2010 Noah Mendelsohn
Void * allows us to generalize over types
The list will remember a pointer to
anything.
void List_push(List_T list, void *x);
Hanson’s declaration for List_push
struct Car {char *brand; int weight};
typedef struct Car Car;
Car mycar = {“ford”, 2000};
Car *retrieved_car;
mylist = List_list(NULL);
List_push(mylist, &mycar);
19
Any pointer can be passed
to a void * parameter
/* create empty list */
/* put my car on the list */
© 2010 Noah Mendelsohn
Void * allows us to generalize over types
void List_push(List_T list, void *x);
This generalization is known as
universal
polymorphism
Hanson’s
declaration
for List_push
struct Car {char *brand; int weight};
typedef struct Car Car;
Car mycar = {“ford”, 2000};
Car *retrieved_car_p;
mylist = List_list(NULL);
List_push(mylist, &mycar);
/* create empty list */
/* put my car on the list */
List_pop(mylist, &retrieved_car_p);
20
/* get back mycar */
© 2010 Noah Mendelsohn
Void * allows us to generalize over types
void List_push(List_T list, void *x);
Hanson’s
declaration for List_push
IMPORTANT:
Retrieved_car_p is already a pointer.
Why do we have to pass the address
struct Car {char *brand; int weight};
of retrieved_car_p?
typedef struct Car Car;
Car mycar = {“ford”, 2000};
Car *retrieved_car_p;
mylist = List_list(NULL);
List_push(mylist, &mycar);
/* create empty list */
/* put my car on the list */
List_pop(mylist, &retrieved_car_p);
21
/* get back mycar */
© 2010 Noah Mendelsohn
Aside: how can a function modify
arguments passed to it?
© 2010 Noah Mendelsohn
Can a function change its argument?
void doubleit(int n)
{
n = n * 2;
return;
}
void doubleit(int *np)
{
*np = *np * 2;
return;
}
int x = 3;
doubleit(x);
printf(“x = %d\n”, x);
int x = 3;
doubleit(&x);
printf(“x = %d\n”, x);
This won’t work
Prints:
23
x = 3
This will work
Prints:
x = 6
© 2010 Noah Mendelsohn
What if the variable to be changed is already a pointer?
void getstring(char **stringpp)
{
*stringpp = ...;
return;
}
char *myString;
getstring(&myString);
Does this remind you of
24
readaline?
© 2010 Noah Mendelsohn
Generalizing Over
Computation
© 2010 Noah Mendelsohn
Three ways of generalizing
 Parameters generalize values
 To generalize over types (of pointers) in C, we
use void pointers (other languages have more
direct ways of doing this)
26
© 2010 Noah Mendelsohn
Three ways of generalizing
 Parameters generalize values
 To generalize over types (of pointers) in C, we
use void pointers (other languages have more
direct ways of doing this)
 To generalize over computations, use function
pointers
27
© 2010 Noah Mendelsohn
Why generalize over function?
 We’ve already generalized types…sometimes we need
different code to work on each type
– Classic example: we’re building a sort routine that can sort anything…
– …the rules for sorting different types of things are different
 Mapping: do the same operation on each entry in a
collection
 Providing or overriding behavior in a common
implementation
– Overriding default output format
– Overriding data source for some input routine
– Etc.
28
© 2010 Noah Mendelsohn
Function pointers in C
 We know the code is living in memory
 Can we take the address of code? Yes!
Syntax
int square(int n)
{
return n * n;
}
int (*somefunc)(int n);
somefunc = □
printf(“3 squared is %d\n”, (*somefunc)(3));
29
© 2010 Noah Mendelsohn
Function pointers in C
 We know the code is living in memory
 Can we take the address of code? Yes!
Syntax
int square(int n)
{
return n * n;
}
int (*somefunc)(int n);
somefunc = □
printf(“3 squared is %d\n”, (*somefunc)(3));
30
© 2010 Noah Mendelsohn
Function pointers in C
 We know the code is living in memory
 Can we take the address of code? Yes!
Syntax
int square(int n)
{
return n * n;
}
int (*somefunc)(int n);
somefunc = □
printf(“3 squared is %d\n”, (*somefunc)(3));
31
© 2010 Noah Mendelsohn
Function pointers in C
 We know the code is living in memory
 Can we take the address of code? Yes!
Syntax
int square(int n)
{
return n * n;
}
int (*somefunc)(int n);
somefunc = □
printf(“3 squared is %d\n”, (*somefunc)(3));
32
© 2010 Noah Mendelsohn
Be sure you understand why this works!
int square(int n)
{
return n * n ;
}
int cube(int n)
{
return n * n * n ;
}
int main(int argc, char *argv[])
{
int (*somefunc)(int n);
somefunc = □
printf("3 squared is %d\n", (*somefunc)(3));
somefunc = &cube;
printf("3 cubed is %d\n", (*somefunc)(3));
return EXIT_SUCCESS;
}
33
© 2010 Noah Mendelsohn
Be sure you understand why this works!
int square(int n)
{
return n * n;
}
int cube(int n)
{
return n * n * n;
}
int main(int argc, char *argv[])
{
int (*somefunc)(int n);
The “*” is optional…
…modern versions of C provide it for
you if you leave it out.
somefunc = □
printf("3 squared is %d\n", (somefunc)(3));
somefunc = &cube;
printf("3 cubed is %d\n", (*somefunc)(3));
return EXIT_SUCCESS;
}
34
© 2010 Noah Mendelsohn
Using function pointers
 You’ve seen a simple example
 We often pass function pointers as arguments to other
functions
 This allows us to generalize over functionals/computations
 Examples from Hanson:
– cmp and hash routines for tables
– apply() functions for mapping
35
© 2010 Noah Mendelsohn
Computing on Collections
© 2010 Noah Mendelsohn
One option: loops
/* NOT how Hanson usually does it */
tab = Table_new(…):
…add some data here..
for (i = 0; i < Table_length(tab); ++i) {
upcase(Table_getnext(tab, NEXT));
}
This is pseudo-code: some details just to show the idea.
Hanson doesn’t do it this way anyway.
37
© 2010 Noah Mendelsohn
The functional (Hanson) way
void upcasefunction(void *key, void **value,
void *cl) {
…can uppercase **value here..
}
tab= Table_new(…):
…add some data here..
Table_map(tab, upcasefunction, ??);
38
© 2010 Noah Mendelsohn
The functional (Hanson) way
void upcasefunction(void *key, void **value,
void *cl) {
…can uppercase **value here..
}
Passing pointer to
function
tab= Table_new(…):
…add some data here..
Table_map(tab, upcasefunction, ??);
The map Table_map function loops calling upcasefunction
repeatedly, once for each entry
39
© 2010 Noah Mendelsohn
The closure: shared data for the mapping
void upcasefunction(void *key, void **value,
void *cl) {
…can uppercase **value here..
}
struct cl mycl {…shared data here..};
tab= Table_new(…):
…add some data here..
Table_map(tab, upcasefunction, &mycl);
The data in mycl is passed in from the caller…
…can be seen and updated in upcasefunction
40
© 2010 Noah Mendelsohn
Mapping vs loops
 Map advantages:
– Clean, easy to reason about
– Often less code to write
– Automatically gets the iteration right (e.g. length)
 Disadvantages
– Less flexible: what if we want to iterate in unusual order?
– Less obvious how to iterate multiple structures at once (there are ways)
– Getting closures right can be tricky
 Mapping is a classic functional programming construct
41
© 2010 Noah Mendelsohn
Unboxed Data
Generalizing to Collections of
Objects that Aren’t Pointers
© 2010 Noah Mendelsohn
Boxed and unboxed collections
 The collections you’ve seen so far are boxed
List_push(mylist, &data); /* list stores a pointer */
 Problem: we want an array of 1 million characters
– A character is 1 byte, but a pointer to a character is 8 bytes
– Even for bigger types, chasing pointers takes time, and allocating memory can
be expensive
– Sometimes, we get arrays from or provide arrays to other code
 Unboxed collections: store the actual data, not a pointer!
/* array of 1000000 chars */
my_array = UArray_new(1000000, sizeof(char));

/* set the char at offset 500 to ‘X’ */
char *mychar = UArray_at(my_array, 500);
*mychar = ‘X’;
43
© 2010 Noah Mendelsohn
Boxed and unboxed collections
Space for 1000000 characters is
 allocated
The collections
you’ve
seen so far are boxed
in the Hanson
uarray…we
List_push(mylist,
&data); /* list stores a pointer */
could
use sizeof(struct
SomeBigStruct) and that would
 work
Problem:
too! we want an array of 1 million characters
– A character is 1 byte
– A pointer to a character is 8 bytes
– Even for bigger types, chasing pointers takes time, and allocating memory can
be expensive
 Unboxed collections: store the actual data, not a pointer!
/* array of 1000000 chars */
my_array = UArray_new(1000000, sizeof(char));

/* set the char at offset 500 to ‘X’ */
char *mychar = UArray_at(my_array, 500);
*mychar = ‘X’;
44
© 2010 Noah Mendelsohn
Boxed and unboxed collections
 The collections you’ve seen so far are boxed
List_push(mylist, &data); /* list stores a pointer */

Uarray_at returns a pointer directly
intoarray
the data
that’s
inside the
Problem: we want an
of 1array
million
characters
Hanson implementation…that’s its
– A character is 1 byte contract.
– A pointer to a character is 8 bytes
– Even for bigger types, chasing pointers takes time, and allocating memory can
be expensive
 Unboxed collections: store the actual data, not a pointer!
/* array of 1000000 chars */
my_array = UArray_new(1000000, sizeof(char));

/* set the char at offset 500 to ‘X’ */
char *mychar = UArray_at(my_array, 500);
*mychar = ‘X’;
45
© 2010 Noah Mendelsohn
Wrapap
© 2010 Noah Mendelsohn
Summary
 Generalization over computation with function pointers
– E.g. comparison routine for polymorphic sorting
– Apply function for mapping…see below
 Aside on changing caller data by passing pointers
 Mapping: a well-structured functional way to:
– Iterate over a data structure
– Apply some specified function to each element
 Closures:
– Maintain context/state while calling out to functions
– Hanson-style: build it by hand
– Models what many modern programming languages do for you
 Boxed vs. unboxed collections
47
© 2010 Noah Mendelsohn