Velocity Reviews > Dennis Ritchie -- An Appreciation

# Dennis Ritchie -- An Appreciation

Alan Curry
Guest
Posts: n/a

 11-02-2011
In article <(E-Mail Removed)>,
Malcolm McLean <(E-Mail Removed)> wrote:
>
>we can represent the data like this
>
>typedef struct
>{
> char name[64];
> int id;
> float salary;
>} EMPLOYEE;
>
>EMPLOYEE employees[10];
>or like this
>
>typedef struct
>{
> char name[10][64];
> int id[10];
> float salary[10];
>} EMPLOYEES;
>
>EMPLOYEES employees;

When this program grows up it'll use malloc/realloc to create and grow the
array, and the second version will need a separate realloc for every field
while the first has one realloc for all.

How do you imagine that problem might be fixed?

--
Alan Curry

nroberts
Guest
Posts: n/a

 11-02-2011
On Nov 2, 1:11*pm, jameskuyper <(E-Mail Removed)> wrote:
> nroberts wrote:
> > On Nov 2, 10:14*am, Malcolm McLean <(E-Mail Removed)>
> > wrote:

> ...
> > > We've got ten employees, each with name, payroll id, and salary.

>
> > > we can represent the data like this

>
> > > typedef struct
> > > {
> > > * char name[64];
> > > * int id;
> > > * float salary;

>
> > > } EMPLOYEE;

>
> > > EMPLOYEE employees[10];
> > > or like this

>
> > > typedef struct
> > > {
> > > * char name[10][64];
> > > * int id[10];
> > > * float salary[10];

>
> > > } EMPLOYEES;

>
> > > EMPLOYEES employees;

>
> > > The two methods hold the same data, and have the same access
> > > characteristics - iterating through the list is done in O(N) time,
> > > random access is in O(constant) time, searching for the maximum salary
> > > takes O(N) time, etc. Theya are logically equivalent.

>
> > I thought nobody was saying that!!!!

>
> No, the assertion that no one was making was that they were
> interchangeable.

LOL!

I think that pretty clearly lays out why it's pointless to continue,
at least with you.

nroberts
Guest
Posts: n/a

 11-02-2011
On Nov 2, 3:11*pm, (E-Mail Removed) (Richard Harter) wrote:
> On Wed, 2 Nov 2011 13:11:27 -0700 (PDT), jameskuyper
>
> <(E-Mail Removed)> wrote:
>
> snip]
>
>
>
> >Well, yes - the point is, in C, one method is supported directly, and
> >the other way requires "writing custom functions to serve as binder
> >expressions". That's precisely the bias he's talking about. I can't
> >say its a very important bias, but it's a real one. It doesn't deserve
> >the amount of attention it's received so far, but that amount of
> >attention has been due almost entirely to the challenges you've made
> >against it.

>
> There is another bias. *It is customary to define a struct with the
> actual fields. *Thus
>
> typedef struct
> {
> * char name[64];
> * int id;
> * float salary;
>
> } EMPLOYEE;
>
> The definition does not impact how the array is allocated. *Thus
>
> * * EMPLOYEE employees[10]; /*and */
>
> * * EMPLOYEE *employees;
> * * employees = malloc(10 * sizeof(*employees));
>
> both work. *However if we are doing struct of arrays we need different
> definitions for the declared arrays case and for the allocated arrays
> case. *Thus
>
> typedef struct
> {
> * char name[10][64];
> * int id[10];
> * float salary[10];
>
> } EMPLOYEES;
>
> EMPLOYEES employees;
>
> vs
>
> typedef struct
> {
> * char name[][64]; */* declaration probably wrong */
> * int *id;
> * float *salary;
>
> } EMPLOYEES;
>
> EMPLOYEES employees;
>
> with the further inconvenience that every field must be malloced
> separately. *On the other hand we now have room for the number of
> employees in the struct.

Again though, none of that has anything to do with syntax. In a
language with the abstractions of "array" and "structure" or "record"
that also provides the other features you are talking about such as
dynamic allocation, etc... you are going to have the exact same
issues. The logical structure of your program data directly effects
the complexity level of its algorithms. The wrong logical structure
for the wrong kind of operation is going to result in a very complex
algorithm.

Even if you implemented your program in direct machine code, if you
used the conceptual abstractions of "array" and "structure" the
operations you need to perform on your data is going to dictate what
contains what.

This is not a language issue. It's not a C bias, it's a logical one.
It's intrinsic to the definition of "structure" and "array". It's the
same in Pascal, Basic, and any other language that has these
abstractions. It cannot BE any other way.

You can organize your data in different manners, yes. When you have a
bunch of values that are related by a concept, and you want to have a
bunch of values of that concept, the simplest method of dealing with
that data in a language that HAS structures and arrays is to make an
array of structures. The concept is the structure, it has its value
elements, and it's held in an array so you can have many of them.
This is not the most convenient organization for all algorithms but
for most it will be regardless of the syntax you're using.

You can't just organize your data in an inversion of that and expect
things to work the same or as well. Again, this is not a syntatic
issue, it's an issue of equivalence...in that they are not. The
organization is completely different and thus the operations will be
different and some algorithms will be severely complicated by the
change while others will be simplified. This would be true though
whether your blocks are begun with '{' and ended with '}' or if
instead it was 'do' and 'done'.

Similarly you'd have the same issues in a language that only had
lists. Do you keep a list of employees that have names and ids, or do
you keep a list with name and id lists that have entries for each
employee? The choice made here will alter many, many thing and in
general the easiest method is very likely to be the former rather than
the later...be it in C or LISP.

Uncle Steve
Guest
Posts: n/a

 11-02-2011
On Wed, Nov 02, 2011 at 12:09:54PM -0700, nroberts wrote:
> On Nov 2, 10:14*am, Malcolm McLean <(E-Mail Removed)>
> wrote:
> > On Nov 2, 5:22*pm, nroberts <(E-Mail Removed)> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > On Nov 1, 6:35*pm, James Kuyper <(E-Mail Removed)> wrote:

> >
> > > > On 11/01/2011 05:16 PM, nroberts wrote:

> >
> > > > > On Nov 1, 1:46 pm, James Kuyper <(E-Mail Removed)> wrote:
> > > > >> On 11/01/2011 03:59 PM, nroberts wrote:
> > > > >> ...

> >
> > > > >>> and has nothing to do with syntax. Structures and arrays are in no
> > > > >>> way interchangeable whether you are writing in C, C++, BASIC, or
> > > > >>> Brain****.

> >
> > > > >> No one has suggested that they are interchangeable. Only that data which
> > > > >> can be stored as a single array of structures can also be stored as a
> > > > >> single structure by converting each member to an array.

> >
> > > > > 2+2 = 27?

> >
> > > > > Unless you're making a completely pointless statement ...

> >
> > > > Richard Harter's point was precisely that it's significantly more
> > > > complicated iterating through the arrays in a structure than through an
> > > > array of structures.

> >
> > > Because *C* has a bias in that direction. *I was trying to understand
> > > that assertion because it seems like nonsense to me, and now everyone
> > > wants to pretend it was never made. *That's fine. *If you guys want to
> > > make nonsensical assertions and then pretend you were making sense the
> > > whole time it's no problem with me, I'll just remain unconvinced.

> >
> > We've got ten employees, each with name, payroll id, and salary.
> >
> > we can represent the data like this
> >
> > typedef struct
> > {
> > * char name[64];
> > * int id;
> > * float salary;
> >
> > } EMPLOYEE;
> >
> > EMPLOYEE employees[10];
> > or like this
> >
> > typedef struct
> > {
> > * char name[10][64];
> > * int id[10];
> > * float salary[10];
> >
> > } EMPLOYEES;
> >
> > EMPLOYEES employees;
> >
> > The two methods hold the same data, and have the same access
> > characteristics - iterating through the list is done in O(N) time,
> > random access is in O(constant) time, searching for the maximum salary
> > takes O(N) time, etc. Theya are logically equivalent.

>
> I thought nobody was saying that!!!!
>
> The truth is that they are not at all logically equivalent. The
> difference between the two is 100% logical.
>
> > The only
> > difference is the way the employees are laid out in memory.

>
> There could be no difference in how they're laid out in memory, the
> difference is in their *logical* structure--completely the opposite of
> what you're saying. I can write the statements to access a field in
> English and the difference is still there:
>
> Get the N'th employee from the employee's array and access its id
> field.
> Get the ids field from the employees structure and access its N'th
> element.
>
> No matter what syntax I use that is specific enough for talking to a
> computer, I'm still going to have to access the elements in different
> manners.

Talk of computer programming and you talk of "manners"? I must have
died and gone to hell.

> > The first way is better for C, but that's largely because of C's
> > syntax. We can imagine language x where you can declare arrays of
> > records, and all the fields are contiguous, and this is transparent to
> > the user. You'd use a syntax like field(employees, i, salary) *= 1.1; /
> > * increment employee's salary by 10 % */
> >
> > The second method has certain advantages. For instance, if we want the
> > average salary, we have an array of floats ready to be passed to a
> > generic mean() function.

>
> Not in language X. In language X you're using the field() syntax.
> You've essentially got an array of structures in language X no matter
> what you might want and you're writing your generic mean function to
> use binder expressions like: mean(field(employees, _1, salary)). You
> can do this in C by the way though not at quite that high level
> (you'll be writing custom functions to serve as binder expressions).

The cowardly lion might have a thing or two to say about that.

> > With the first method, ypu've got to either
> > write an special mean_employee_salary() function, use a temporary
> > buffer, or fake up the "field" syntax using a stride, offset, and some
> > pointer jiggery-pokery.

>
> Which is all "language X" is. You could write it in C as a macro and
> then still access the underlying memory. It's all going to depend
> upon the needs of your program.
>
> All you're doing here is arguing for abstractions. You're not showing
> that C's syntax forces you into one form of data expression or
> another, you're saying that it would be nice to be able to manipulate
> your data at a higher level than structures and arrays. There's
> nothing stopping you from doing that in C and there's nothing that
> makes it more or less difficult except perhaps a lack of utility
> functions in the standard library, which is not a syntax issue.

What isn't a syntax issue?

> It is true that there are many languages at higher levels than C that
> support the kind of expressions you're talking about. C++ in fact
> provides much of the functionality you want here, or at least better
> facilities to create it. But when you get to this point you're no
> higher level concepts. I do agree that abstractions can be a
> wonderful thing, but this is clearly not a C specific issue.

values blind you to the truth of this reality. Oh, ****. Did I say
that on the record?

Regards,

Uncle Steve

--
My robot girlfriend can beat up your robot girlfriend.

James Kuyper
Guest
Posts: n/a

 11-03-2011
On 11/02/2011 06:11 PM, Richard Harter wrote:
.....
> typedef struct
> {
> char name[][64]; /* declaration probably wrong */

That would be acceptable if it were the last member of the struct, in
which case it would declare a flexible array member. But if you were to
do that, then the struct object itself would have to be dynamically
allocated. To declare name as a pointer to an array of 64 char, you
would write

char (*name)[64];

> int *id;
> float *salary;
> } EMPLOYEES;
>
> EMPLOYEES employees;
>
> with the further inconvenience that every field must be malloced
> separately. On the other hand we now have room for the number of
> employees in the struct.

In general, any struct containing a pointer to a dynamically allocated
block of memory of variable length should contain a count that indicates
how long that block is.
--
James Kuyper

Kaz Kylheku
Guest
Posts: n/a

 11-03-2011
On 2011-10-30, nroberts <(E-Mail Removed)> wrote:
> On Oct 29, 12:18Â*pm, Markus Wichmann <(E-Mail Removed)> wrote:
>> On 29.10.2011 08:56, Jorgen Grahn wrote:
>>
>> > So do I, and it's definitely workable -- but not having RAII,

>
> Not having scope tied destructors hurts.

Not having scope-tied exit code ("unwind protect") is what hurts!

This hurts even when you have destructors because destructors are
clumsy. They let you run code, but in a remote context somewhere with
its own scope which has no visibility into the scope which is
terminating (i.e. the object that actually needs the clean up).

Uncle Steve
Guest
Posts: n/a

 11-03-2011
On Thu, Nov 03, 2011 at 02:38:55AM +0000, Kaz Kylheku wrote:
> On 2011-10-30, nroberts <(E-Mail Removed)> wrote:
> > On Oct 29, 12:18Â*pm, Markus Wichmann <(E-Mail Removed)> wrote:
> >> On 29.10.2011 08:56, Jorgen Grahn wrote:
> >>
> >> > So do I, and it's definitely workable -- but not having RAII,

> >
> > Not having scope tied destructors hurts.

>
> Not having scope-tied exit code ("unwind protect") is what hurts!
>
> This hurts even when you have destructors because destructors are
> clumsy. They let you run code, but in a remote context somewhere with
> its own scope which has no visibility into the scope which is
> terminating (i.e. the object that actually needs the clean up).
>

Sounds like a pipe dream. HTF are you going to unwind protect Kylie

Regards,

Uncle Steve

--
My robot girlfriend can beat up your robot girlfriend.

Ian Collins
Guest
Posts: n/a

 11-03-2011
On 11/ 3/11 03:38 PM, Kaz Kylheku wrote:
> On 2011-10-30, nroberts<(E-Mail Removed)> wrote:
>> On Oct 29, 12:18 pm, Markus Wichmann<(E-Mail Removed)> wrote:
>>> On 29.10.2011 08:56, Jorgen Grahn wrote:
>>>
>>>> So do I, and it's definitely workable -- but not having RAII,

>>
>> Not having scope tied destructors hurts.

>
> Not having scope-tied exit code ("unwind protect") is what hurts!
>
> This hurts even when you have destructors because destructors are
> clumsy. They let you run code, but in a remote context somewhere with
> its own scope which has no visibility into the scope which is
> terminating (i.e. the object that actually needs the clean up).
>

How would unwind-protect work in cases where you want an object's
destruction to cause the release of a managed resource (a smart pointer
for example)?

--
Ian Collins

Ben Bacarisse
Guest
Posts: n/a

 11-03-2011
http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter) writes:
<snip>
> The big one is that if we have an array of structs
> we can readily form a pointer to a particular struct whereas with a
> struct of arrays we can't. With an array of structs we can do things
> like
>
> func(a[i]) /* pass a pointer to a struct to a function */
> b = a[i]; /* Make a copy of a struct */
>
> With a struct of arrays we can't. The issue here is that our data in
> effect is a two dimensional array with one of the dimensions being the
> fields. In some languages slicing is intrinsic to the language; in C
> it is not.

<snip>
> The syntax favors one choice over another; i.e., it is
> easier to do certain common things (examples above) with one choice
> than the other.

Part of the debate may be caused by your talking of the *syntax*
favouring one rather than the other. Whilst it is true that there is no
syntax for the "sliced" struct access, nor for a pointer to such a
"sliced" struct, the bias (if that is what it is) goes much deeper than
C's syntax.

The purpose of transposing the data structure is to get a different
layout in memory, so, inevitably, the sliced structs in the "struct of
arrays" layout are not objects in the C sense. All the numerous rules
about object representations, sizes, effective types, pointers to
objects and so on can't apply to these. In other words, the syntax of
the language merely represents its fundamental, low-level, view of
objects, types and values.

Of course, these slices need not be objects -- an enhanced C could
introduce a new kind of pointer and a new kind of "thing" to which these
point, but, again, that's a lot more than removing a bias in the syntax.

I accept that it's possible to view all these changes as simply the
consequence of having new syntax that supports slices or transposed data
structures, but, because of C's low level nature and its history of
having very informally defined semantics, most "C people" (I count
myself as one of these) are used to thinking of the underlying concepts
as fundamental, and of the syntax as being a natural (and rather trivial)
consequence of these.

By the way, in such a language one would want to avoid having to repeat
the size (as has been done in the various examples) -- maybe by just
having a "transpose" keyword on a type declaration or an object
definition. That way, such objects could be naturally malloc'd.

<snip>
--
Ben.

Malcolm McLean
Guest
Posts: n/a

 11-03-2011
On Nov 3, 2:51*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
>
> The purpose of transposing the data structure is to get a different
> layout in memory, so, inevitably, the sliced structs in the "struct of
> arrays" layout are not objects in the C sense. *All the numerous rules
> about object representations, sizes, effective types, pointers to
> objects and so on can't apply to these. *In other words, the syntax of
> the language merely represents its fundamental, low-level, view of
> objects, types and values.
>
> Of course, these slices need not be objects -- an enhanced C could
> introduce a new kind of pointer and a new kind of "thing" to which these
> point, but, again, that's a lot more than removing a bias in the syntax.
>

If I have a struct employee, the payroll id and the salary might not
be physically stored on the same memory chip. There's a layer of
electronic wizardry between the memory substrate and the program which
maps maybe several chips into the same address space.
Similarly, at the program level, I need to tie the payroll id to the
salary. The easiest way of doing this is to have the salary directly
and the data is tied that way. To do that in language X, we'd need
something like an "array base" which gave the base addresses for each
element, then we'd have to specify that records can only be accessed
via the array base (So if in C I pass in a struct employee * to
transfer the salary to the bank account referenced by the payroll id,
in language X I pass in an array base *, plus an index, though of
course the fact that I'm passing two values could be hidden by the
syntax).
--
Read Basic Algorithms: learn how to use BMP, GIF, and JPEG files
http://www.malcolmmclean.site11.com/www