typedef, 2D arrays, design: question

[gdotone]

I am reading "A Book on C" forth edition.

In chapter 6, the author discusses "The Use of typedef". The following is the examples given in the book:

#define N 3

typedef double scalar;
typedef scalar vector[N];
typedef scalar matrix[N][N];

The author explains that typedef is a mechanism to create new types. typedef, according to the author, increases the self-documenting ability of the program and using typedef is helpful when conceptually appropriate.

The author gives the following example of what could have been written instead of the other.

typedef vector matrix[N]; /* instead of the one below */

typedef scalar matrix[N][N];

My question:

In the statement: typedef vector matrix[N]; being that vector is typedef as a scalar array, this statement says the matrix[N] is an array of the array vector?

design question:
An example function is given which adds vectors, three actually in the book,

void add ( vector x, vector y, vector )
{
int i;

for ( i = 0; i < N; i++ )
x = y + z;
}

When a variable is declared to be of type vector, as in vector x, x is an array holding scalar values?

The idea to define or think in terms of vector(s) is because of the problemdomain?

So, if one were writing a chess game, one could say something like:

int N 8;
typedef int position;
typedef postion boardLocation[N]N];

I'm not chess player so forgive for not being more creative with the names of the variable, I think of a chess board containing squares which have a position and will hold a piece, like a king, queen, knight, etc. I have not gotten to enumerations in the book yet, so, I'll say that those pieces willhave a number associated with its kind.

First am I abstracting that correctly? I'm I think about it correctly, it doesn't seem so.
So, maybe all I have written is doesn't fit the problem correctly.

perhaps its enough to say:

typedef int position[N][N];

because that's what I think of when looking at a chess board. I mean that is what happens in the early code, but that code doesn't seem to fit the problem domain. position typed as an int? No, right. Because when you think ofthe position on a chess board its like and (row, column) thought, right?

I'm trying to follow the idea that one should leave the detail off until later in a program. (so to speak, write)

If this example doesn't lend itself well to discuss abstraction, please give another. I'll try to follow the example that you give.

Thanks a lot everyone.

 

[Ben Bacarisse]

I am reading "A Book on C" forth edition.

In chapter 6, the author discusses "The Use of typedef". The following
is the examples given in the book:

#define N 3

typedef double scalar;
typedef scalar vector[N];
typedef scalar matrix[N][N];

The author explains that typedef is a mechanism to create new types.

That can be considered confusing. typedef only gives a name to the type
-- in effect it's the name that's new, not the type. Some other
languages, which have a similar mechanism, have chosen to make the type
itself "new". The effect being that 'double' and 'scalar' would be
considered different. That's not what C does. 'scalar' is now just
another name for 'double'.

typedef, according to the author, increases the
self-documenting ability of the program and using typedef is helpful
when conceptually appropriate.

The author gives the following example of what could have been written
instead of the other.

typedef vector matrix[N]; /* instead of the one below */

typedef scalar matrix[N][N];

My question:

In the statement: typedef vector matrix[N]; being that vector is
typedef as a scalar array, this statement says the matrix[N] is an
array of the array vector?

Yes, though you need to be careful about using a subscript. It says
that the type matrix (no subscript) is an array of N vector.

design question:
An example function is given which adds vectors, three actually in the
book,

void add ( vector x, vector y, vector )

(z missing)

{
int i;

for ( i = 0; i < N; i++ )
x = y + z;
}

When a variable is declared to be of type vector, as in vector x, x is
an array holding scalar values?

Not when it's a parameter! These two do different things:

vector v; // v is an array of N scalar, i.e. double

void function(vector v) // v is a pointer to scalar

In C, you can't pass arrays to functions. Writing what looks like an
array type in function header declares that parameter to be a pointer to
the array's element type. In your example, x, y and z are all pointers.

This is one of the big problems with typedefs. You need to know how the
name is defined to really know what's going on. Had vector been defined
like this:

typedef struct { scalar x, y, z; };

then you'd have been correct. A vector argument really would be passed
as a vector.

The idea to define or think in terms of vector(s) is because of the
problem domain?

Yes, but C is not particularly good at that, especially where arrays are
concerned. It would be nice to be able to ignore how it's actually
defined, but you can't always do that. You need a little voice in your
head telling you, every now and then, that vector is really an array.

So, if one were writing a chess game, one could say something like:

int N 8;

missing = (unless this code is from the 1970s!)

typedef int position;
typedef postion boardLocation[N]N];

missing [

You've used, possibly unwittingly something called a "variably modified
array" (and in a way that won't work, as it happens). For the moment,
stick with arrays where the size is defined by a macro that expands to
a simple literal.

I'm not chess player so forgive for not being more creative with the
names of the variable, I think of a chess board containing squares
which have a position and will hold a piece, like a king, queen,
knight, etc. I have not gotten to enumerations in the book yet, so,
I'll say that those pieces will have a number associated with its
kind.

First am I abstracting that correctly? I'm I think about it
correctly, it doesn't seem so. So, maybe all I have written is
doesn't fit the problem correctly.

Abstraction is not all-or-nothing and it's not possible to say is some
typedef is correct or not. It all depends on how it will be used. If
you are writing a program that can solve all kind of chess-like
problems, this may be way too simple (in a more abstract notion of a
board, it need not be square, for example) but if you are going to try
to write some hyper-efficient chess puzzle solving program, your example
may be too general already.

perhaps its enough to say:

typedef int position[N][N];

because that's what I think of when looking at a chess board. I mean
that is what happens in the early code, but that code doesn't seem to
fit the problem domain. position typed as an int? No, right. Because
when you think of the position on a chess board its like and (row,
column) thought, right?

There are some problems here. 'position' is not typed as an int -- it's
an array of arrays of ints. Also the word "position" means two things
in chess (a) the overall position of the game (and your typedef is fine
for that) and (b) the position of a piece. That is indeed a row and
column and you'd need something else if you wanted to represent such
things directly in your program.

I'm trying to follow the idea that one should leave the detail off
until later in a program. (so to speak, write)

That's a noble aim but C will get in the way of doing that again and
again. It has lots of special cases (about arrays and functions in
particular) but it also has no direct way to represent what programmers
call abstract types. Search for C and opaque structs to find out some
more about how this is sometimes tackled in large C programs.

If this example doesn't lend itself well to discuss abstraction,
please give another. I'll try to follow the example that you give.

Abstraction is about ignoring details, but it takes knowledge of the
purpose to know what details should be "abstracted out". Also, the
language determines how you end up thinking about abstraction, and C is
not strong in that respect. For example, almost every C programs is
lettered with loops because you can't abstract out the idea of running
through an array. This is good (for C) because it allows C compiler to
generate very efficient code, but it's not particularly good if you want
to learn about the role of abstraction in programming.

 

[BartC]

So, if one were writing a chess game, one could say something like:

int N 8;

That would need to be:

#define N 8

to make N a constant suitable to declare the sizes of arrays.

typedef int position;

This sort of typedef is probably not so worthwhile doing in C, as 'position'
is exactly equivalent to an 'int'. The language won't stop you from doing
everything to a position value as you can to an int value. Typedefs are
sometimes used to break down very complex type-specifications which
otherwise are (to my view) near impossible to write (usually involving
pointers, arrays, and function pointers).

typedef postion boardLocation[N]N];

I'm not chess player so forgive for not being more creative with the names
of the variable, I think of a chess board containing squares which have a
position and will hold a piece, like a king, queen, knight, etc. I have
not gotten to enumerations in the book yet, so, I'll say that those pieces
will have a number associated with its kind.

Actually neither 'boardLocation' nor 'position' seem appropriate for what is
to be stored in each square (usually Empty, or the code of a piece).

If this was Ada or Pascal, you could do this properly: a set of enumerations
for the pieces, a matrix of those pieces, and the language stopping you from
taking the square root of the queen at [3][4]!

But being C, an 8x8 matrix of ints or chars seems the simplest to get
started with. (And later you might find that a different representation, or
multiple ones, might be more suited):

char chessboard[8][8] = {0}; /* An empty board */

(I've used char rather than int, because you probably won't need that many
different values. It also limits the range of illegal values that could be
stored in each square! Also I've hardcoded the 8s, because chessboards are
unlikely to be anything other than 8x8. But you should use a #define.

This also assumes that 0 designates an empty square; that's simplest.)

because that's what I think of when looking at a chess board. I mean that
is what happens in the early code, but that code doesn't seem to fit the
problem domain. position typed as an int? No, right. Because when you
think of the position on a chess board its like and (row, column) thought,
right?

Yes, position would be the index that you supply to the matrix, not the
value in each cell.

 

[Eric Sosman]

So, if one were writing a chess game, one could say something like:

int N 8;

That would need to be:

#define N 8

to make N a constant suitable to declare the sizes of arrays.

typedef int position;

This sort of typedef is probably not so worthwhile doing in C, [...][/QUOTE]

One important exception is the use of typedef for range
portability with storage economy, as in

#include <limits.h>
#if INT_MAX >= 1000000
typedef int UpToOneMillion;
#else
typedef long UpToOneMillion;
#endif

struct there_will_be_many_of_these {
UpToOneMillion count;
...
};

This usage became less important with C99's invention of the

Typedefs are
sometimes used to break down very complex type-specifications which
otherwise are (to my view) near impossible to write (usually involving
pointers, arrays, and function pointers).

Many people (myself included) dislike `typedef Thing *Thingp;'
and its brethren, since it tends to obscure the pointer-nature of
a variable declared as `Thingp x;'. I find the code more readable
if pointer-ness is obvious: `Thing *x;' puts it right in my face.

"Very complex" pointer types can overcome my dislike, though.
You mention function pointers, which are often good candidates by
virtue of their verbosity if nothing else, although even there it's
sometimes clearer to typedef the function than the pointer:

// Okay, but ...
typedef int (*comparePtr)(const void*, const void*);
void mySuperSort(void*, size_t, size_t, comparePtr);

// May be clearer:
typedef int compareFunc(const void*, const void*);
void mySuperSort(void*, size_t, size_t, compareFunc*);

 

[Edward Rutherford]

Many people (myself included) dislike `typedef Thing *Thingp;'
and its brethren, since it tends to obscure the pointer-nature of a
variable declared as `Thingp x;'. I find the code more readable if
pointer-ness is obvious: `Thing *x;' puts it right in my face.

I disagree with this.

In Python almost everything is implicitly a void* and it works pretty
well.

 

[Eric Sosman]

I disagree with this.

You disagree that "many people (myself included)" dislike
something? Okay, go ahead: Convince me that I do in fact like it.

In Python almost everything is implicitly a void* and it works pretty
well.

But it works very badly in COBOL, so there!

 

[James Kuyper]

You disagree that "many people (myself included)" dislike
something? Okay, go ahead: Convince me that I do in fact like it.

He could have worded that better - but is should be clear that he was
expressing disagreement with your reasons for disliking such typedefs,
not with your assertion that you dislike them.

 

[Ian Collins]

He could have worded that better - but is should be clear that he was
expressing disagreement with your reasons for disliking such typedefs,
not with your assertion that you dislike them.

It should also have been clear that Eric's tongue was very firmly in his
cheek!

 

[James Kuyper]

It should also have been clear that Eric's tongue was very firmly in his
cheek!

I could tell that Eric was being sarcastic, but since he only addressed
the form of the Edward's objection, and not the content of it, I thought
it important to redirect his attention to the content.

 

[John Bode]

I am reading "A Book on C" forth edition.



In chapter 6, the author discusses "The Use of typedef". The following is the
examples given in the book:

#define N 3

typedef double scalar;
typedef scalar vector[N];
typedef scalar matrix[N][N];

The author explains that typedef is a mechanism to create new types.

Not exactly; it creates a synonym for an existing type. In this case,
"scalar" is a synonym for type "double", "vector" is a synonym for type
"N-element array of scalar", and "matrix" is a synonym for type "N-element
array of N-element array of scalar".

typedef, according to the author, increases the self-documenting ability
of the program and using typedef is helpful when conceptually appropriate.

Honestly? Not so much, at least not in my experience. Typedefs almost always
wind up hiding information that I need to know. The code is more "readable" in that it scans more easily, but it's less *understandable* in that I don't
necessarily know how to *use* objects of that type without chasing down the
typedef. In a large project with several hundred files spread over different
directories, that can be a pain.

For example, what conversion specifier do I use to print a value of type "scalar" (assuming whoever defined the typedef hasn't also provided routines
to read and write such values)? In this case, it's whatever I would use for
a "double" (%f, %g, etc.), but if I don't know what a "scalar" is off the top of
my head, I have to go looking for the typedef.

Or, even better, there's a school of thought that likes to typedef function
pointers, like

typedef void (*Callback)(int, double, double);

so you can write function declarations that look like

void bar(int x, Callback c);

instead of

void bar(int x, void (*c)(int, double, double));

Yeah, the first form scans more easily, but it doesn't tell me anything about what Callback returns, or how many arguments it takes, or what their types are,
or that it's *even a function* (I assume that from the name "Callback", but
not everyone names their typedefs so helpfully). Again, if I don't have the
definition handy, I have to stop and go looking for it. By contrast, the second
form tells me everything I need to know about how to *use* c, right there in
front of me. I know that it's a function that takes 3 parameters of type int,
double, and double, and returns void.

IME, typedefs work best for types that are meant to be truly opaque, where
the programmer *shouldn't* need to know anything about the underlying
representation, such as the FILE typedef. You don't manipulate objects of
FILE type directly, you manipulate them through the interface provided
by stdio.

One of my favorite build breaks resulted from a typedef name hiding the
"pointerness" of a type (this is C++, but you should get the idea):

for(vector<typedef_name>::iterator it = v.begin(); it != v.end(); ++it)
it->foo();

Unfortunately, "typedef_name" was along the lines of

typedef some_class* typedef_name;

where "typedef_name" gave ABSOLUTELY NO CLUE that this was a pointer type, meaning the above code *should* have been written

for(vector<typedef_name>::iterator it = v.begin(); it != v.end(); ++it)
(*it)->foo();

and thanks to g++'s incontinence whenever there's an error involving a
template, it took more than a minute to figure out what the hell was going
on.

Now, it must be said that one area where pointer typedefs do help is preventing bugs like

int* p1, p2;

where someone is under the illusion that both p1 and p2 will have type "pointer to int"; unfortunately, the '*' is bound to the declarator p1, not the type specifier, so only p1 is declared as "pointer to int"; p2 is declared as a plain "int".

If, OTOH, you have

typedef intptr *int;

then

intptr p1, p2;

*would* declare both p1 and p2 as pointers to "int".

The author gives the following example of what could have been written
instead of the other.

typedef vector matrix[N]; /* instead of the one below */

typedef scalar matrix[N][N];

My question:

In the statement: typedef vector matrix[N]; being that vector is typedef as
a scalar array, this statement says the matrix[N] is an array of the array
vector?

Basically, yes: matrix is an N-element array of vector, which in turn is an N-element array of scalar, so you wind up with a type of N-element array of N-element array of scalar.

So, conceptually, is a matrix really an array of vectors, or is it a 2D array
of scalars? Have you cleared things up, or made them muddier?

design question:

An example function is given which adds vectors, three actually in the book,

void add ( vector x, vector y, vector )
{
int i;

for ( i = 0; i < N; i++ )
x = y + z;
}

When a variable is declared to be of type vector, as in vector x, x is an
array holding scalar values?

Except that, in the context of a function parameter declaration, "T a[N]" and "T a[]" are synonymous with "T *a", so instead of x, y, and z being "N-element array of scalar", they're all treated as "pointer to scalar".

The idea to define or think in terms of vector(s) is because of the problem
domain?

Yes, essentially; you're trying to abstract away details that don't matter at
a given level.

But...

At some point you have to translate from the problem domain to the
implementation. The key is the "don't matter" part; again, if the programmer
*has* to be aware of the underlying representation of the object, then you don't
want to hide that object's type behind a typedef.

So, if one were writing a chess game, one could say something like:

int N 8;
typedef int position;
typedef postion boardLocation[N]N];

I'm not chess player so forgive for not being more creative with the names of
the variable, I think of a chess board containing squares which have a
position and will hold a piece, like a king, queen, knight, etc. I have not
gotten to enumerations in the book yet, so, I'll say that those pieces will
have a number associated with its kind.

First am I abstracting that correctly? I'm I think about it correctly, it
doesn't seem so.

So, maybe all I have written is doesn't fit the problem correctly.

perhaps its enough to say:

typedef int position[N][N];

because that's what I think of when looking at a chess board. I mean that
is what happens in the early code, but that code doesn't seem to fit the
problem domain. position typed as an int? No, right. Because when you think
of the position on a chess board its like and (row, column) thought, right?

The row/column aspect is represented by the fact that you're using a 2D array.
The question is, a 2D array of *what*?

Thinking about how you would *use* the array. For example, if you wanted to
move the white king to position 1,4 on the board, you would write something
like

board[0][3] = wking; // C arrays are 0-origin, remember.

So each element of "boardPosition" stores the piece currently at that location.
If you're using an int to represent the different pieces (say, white king = 0, white queen = 1, first white bishop = 2, etc.), then yeah,

typedef int boardPosition[N][N];

works. If you want to create an abstract type for pieces, you could do

typedef int piece;
typedef piece boardPosition[N][N];

boardPosition board;
...
board[j] = currentPiece;

If you want to print out a representation of the board, then at some point you *have* to know the representation of the board and the pieces.

I'm trying to follow the idea that one should leave the detail off until
later in a program. (so to speak, write)

IME, when writing C code, it's better to err on the side of less abstraction; details start to matter early on. Rather than creating a bunch of typedefs, use native types and comment liberally.

If this example doesn't lend itself well to discuss abstraction, please give
another. I'll try to follow the example that you give.

Thanks a lot everyone.

This works well enough.

 

[gdotone]

Thanks very much.

 

[Seungbeom Kim]

Honestly? Not so much, at least not in my experience. Typedefs almost always
wind up hiding information that I need to know. The code is more "readable"
in that it scans more easily, but it's less *understandable* in that I don't
necessarily know how to *use* objects of that type without chasing down the
typedef. In a large project with several hundred files spread over different
directories, that can be a pain.

Information hiding, or abstraction, is an important *feature* of typedef,
I'd rather say. (Of course, it's not perfect...) In a large project,
having to deal with every detail everywhere can be a pain.

For example, what conversion specifier do I use to print a value of type
"scalar" (assuming whoever defined the typedef hasn't also provided routines
to read and write such values)? In this case, it's whatever I would use for
a "double" (%f, %g, etc.), but if I don't know what a "scalar" is off the top of
my head, I have to go looking for the typedef.

True. It's an example of a leaky abstraction, where the information
hiding is not perfect. Sometimes the abstraction can/should provide
a dedicated I/O function (like print_matrix), or a format specifier
macro (like PRIxPTR for uintptr_t), but it's not always done or doable,
unfortunately.

Or, even better, there's a school of thought that likes to typedef function
pointers, like

typedef void (*Callback)(int, double, double);

so you can write function declarations that look like

void bar(int x, Callback c);

instead of

void bar(int x, void (*c)(int, double, double));

Yeah, the first form scans more easily, but it doesn't tell me anything about
what Callback returns, or how many arguments it takes, or what their types are,
or that it's *even a function* (I assume that from the name "Callback", but
not everyone names their typedefs so helpfully). Again, if I don't have the
definition handy, I have to stop and go looking for it. By contrast, the second
form tells me everything I need to know about how to *use* c, right there in
front of me. I know that it's a function that takes 3 parameters of type int,
double, and double, and returns void.

Yes, but you always carry all the details, even when you don't need them
(e.g. when you're merely passing such an argument). It can be a pain to
have to write and understand

void (*bar(int x, void (*c)(int, double, double)))(int, double, double);

instead of

Callback bar(int x, Callback c);

Of course, you'll need the details *at some point*, no matter whether
you use typedef or not.

IME, typedefs work best for types that are meant to be truly opaque, where
the programmer *shouldn't* need to know anything about the underlying
representation, such as the FILE typedef. You don't manipulate objects of
FILE type directly, you manipulate them through the interface provided
by stdio.

Agreed, that's a good example.

One of my favorite build breaks resulted from a typedef name hiding the
"pointerness" of a type (this is C++, but you should get the idea):

for(vector<typedef_name>::iterator it = v.begin(); it != v.end(); ++it)
it->foo();

Unfortunately, "typedef_name" was along the lines of

typedef some_class* typedef_name;

where "typedef_name" gave ABSOLUTELY NO CLUE that this was a pointer type,
meaning the above code *should* have been written

for(vector<typedef_name>::iterator it = v.begin(); it != v.end(); ++it)
(*it)->foo();

and thanks to g++'s incontinence whenever there's an error involving a
template, it took more than a minute to figure out what the hell was going
on.

Just a few minutes? You were so quick. ;-)

So, conceptually, is a matrix really an array of vectors, or is it a 2D array
of scalars?

Both. In mathematics, a matrix of M-by-N scalars, a matrix of M rows of
N row vectors, and a matrix of N columns of M column vectors are all
used interchangeably. So it doesn't matter really.

Yes, essentially; you're trying to abstract away details that don't matter at
a given level.

But...

At some point you have to translate from the problem domain to the
implementation. The key is the "don't matter" part; again, if the programmer
*has* to be aware of the underlying representation of the object, then you don't
want to hide that object's type behind a typedef.

In nearly all cases, the programmer has to be aware of the underlying
representation of the object *at some point*, of course. Does that mean
you don't want typedef in nearly all such cases? I don't think so.

IME, when writing C code, it's better to err on the side of less abstraction;
details start to matter early on. Rather than creating a bunch of typedefs,
use native types and comment liberally.

I see your point here.

I don't agree fully, though. IMHO programming is all about abstraction;
not only typedefs, but macros are also abstractions, functions and
operators are abstractions of the underlying behaviour, and even types
themselves are also abstractions of the underlying bits. Abstraction is
what makes us much more productive writing in C than in assembly or
machine code.

Following your argument could lead to objecting to all such abstractions.
(Yes, I've seen people objecting to C++ because it doesn't reveal every
detail at hand.) In small programs, it may be feasible to forgo many of
them and write with bare literals and put most of the program in main(),
but I'm afraid that way you'll have more trouble with the burden of all
the details. (Or maybe it's just that you'll need a different language
with more powerful abstraction facilities for larger programs anyway,
and that it doesn't really matter in C. ;-))