Re: What is a type?

From: Keith Thompson (kst-u_at_mib.org)
Date: 10/07/04 

Date: Wed, 06 Oct 2004 22:39:47 GMT

jacob navia <jacob@jacob.remcomp.fr> writes:
> Keith Thompson wrote:
>> jacob navia <jacob@jacob.remcomp.fr> writes:
[...]
>> This makes it sound like an enumeration type and type "int" are
>> fundamentally different things, that an enumeration type exists at
>> compilation time, but type "int" exists at run time. This is
>> misleading. The type "int", like an enumeration type, exists only at
>> compilation time.
>
> Surely not. A glance at the instruction set of a common circuit
> for instance (x86) will reveal that the circuit supports integer
> operations in hardware. The type int is perfectly supported by
> almost all CPUs around.
>
> Types (and type associated concepts) exist in the hardware itself.
>
> C allows for a clear mapping of those hardware types into language
> types, but it is obvious that in all processors the type int is
> supported...

You probably won't find the term "int" in a CPU reference manual.
"int" is a C type, not a machine-level concept. The corresponding
CPU-level concept is probably something like a "word".

Yes, of course the CPU supports integer operations (note the
relatively generic term "integer" rather than the C-specific term
"int"). It happens that C's type "int" is very likely to be mapped
almost directly to a machine "word", but they're still two different
concepts that exist in two different contexts. In C, "int" and "long"
are two distinct types, even if they're both the same size; in the
CPU, that distinction no longer exists.

> Floating point can exist at run time too, obviously, and many
> CPUs support the type double, float and long double.
>
> These types exist in hardware.

They exist *as types* only in a C program, either in source or during
compilation. They are mapped onto operations in the hardware. (And
some CPUs don't directly support floating point, but emulate it in
software.)

[...]

>> As a rule of thumb, anything having to do with the C language exists
>> only in your source program or at compilation time, not at run time.
>> (That's not completely true, since a lot of the names overlap.)
>>
>
> The task of the compiler is just to translate the instructions written
> by the programmer as faithfully as possible into machine instructions
> that do exactly what was written.

The task of the compiler is to *map* what the programmer wrote into
machine instructions. The nature of that mapping varies from one
compiler to another, and from one CPU to another. Types are a
high-level language concept. Pretending that the CPU-level concepts
are the "types" in the same sense as int and long is misleading.

> Most types (fortunately) *exist* at run time in a quite real manner.
> C exists at run time sorry. For instance when you specify:
>
> float d = (float) a;
> and a was a double, the machine will shed precision by writing the
> number into memory as a float and re-reading it.

Unless float and double are the same size (which is perfectly legal).

Or the CPU manual might refer to single-precision and double-precision
reals. Yes, the C types are most likely mapped directly to certain
machine-level representations, but the *types* float and double exist
only on the C side of that mapping.

[...]

>> In my opinion, it's best to use the term "type" only for things that
>> are types in C, not for entities like machine words that exist at run
>> time.
>
> I have to disagree here. The machine should follow exactly the type
> description specified in the source program.

If it followed it exactly, wouldn't there be distinct machine-level
"types" for int and long?

>>>Hardware is represented in C as a sequential space of
>>>addreses, where are stored the data and the preprogrammed
>>>(compiled) instructions sequences, that act with those
>>>data and maybe further inputs.
>>
>>
>> That assumes a particular runtime model, one not required by the C
>> standard. There isn't necessarily a single sequential address space.
>
> Some times.
[snip]

Yes, sometimes there is, sometimes there isn't. I'm not sure what
point you're trying to make; my point is that asserting that "Hardware
is represented in C as a sequential space of addreses" is misleading.

[...]

> What is an object?

The term is defined in the standard.

> Is a character in a character string an object?

Yes, and it happens to be a component of another object.

> Can we
> imagine a character string where each character resides
> in a different address space?

No. Or rather, we can imagine it, but it wouldn't be legal in C.

To use a concrete example:

    char s[6] = "hello";

s[1] and s[2] are both objects of type char. s is an object of type
char[6]. Since the object s has to be in a locally linear address
space (which it may or may not share with other objects), it follows
that s[1] and s[2] must be in the same address space. Thus it's legal,
for example, to compute (&s[2] - &s[1]).

Given:

    char t[6] = "fubar";

s and t could be in distinct address spaces, and computing (&t[2] -
&s[1]) invokes undefined behavior.

> > A function address could be anything that allows the
>> function to be called; it could easily be an index into a system table
>> rather than a machine-level address.
>
> In C
> (FnTable[index])(arg1,arg2)
> is different from
> fnptr(arg1,arg2)
>
> A function expression must resolve to a machine address. This way
> it can be passed around as an integer very efficiently. Most of
> the power of C comes from this facility, functions as simple integers.
>
> An efficient way of passing a *lot* of context.

I meant that a function pointer could be implemented as an index into
a system table. On many implementations, a function pointer is
implemented as a machine address, which looks like an integer index
into the entire address space (either of the machine or of the current
process). But an implementation that represented function pointers as
indices could be conforming.

The C implementation on the AS/400 represents function pointers as
some kind of large descriptor, not as a machine address.

All this is equally true for object pointers. Any pointer can be
represented in nearly any way the implementation chooses, as long as
the semantics are implemented consistently. Implementing pointers as
machine addresses happens to result in more efficient code on most
machines, but the C standard specifically doesn't require it.

>>>In C you can at any moment change your mind and start
>>>interpreting the same bits in another way. You make a
>>>cast operation, i.e. you apply to some address a new
>>>type.
>>
>>
>> A cast operator specifies a type conversion. Not all such conversions
>> are simple reinterpretations of the bits. Conversions between integer
>> and floating-point types almost certainly do more than just copying
>> the bits; conversions between pointer types may or may not do so.
>> What you're talking about is type punning; converting addresses is one
>> of several ways to achieve that.
>>
>
> True, I was speaking about re-interpreting because I wanted to emphasize
> that memory is interpreted by the program. With this I am introducing
> the discussion about strongly typed/weakly typed languages, that I hope
> to come later on. This facility of re-interpreting memory is absent or
> much more difficult in several other languages. As everything this can
> be handy if well used, or a nightmare if abused.

My objection was to the reference to a cast operator. Not all casts
just re-interpret their operands, and not all type punning is done via
cast operators.

>>>There are even types that you can't figure out at all:
>>>opaque types. This type is, for instance:
>>>
>>>struct unknown *bn;
>>>
>>>and struct "unknown" is nowhere defined. Or even worst:
>>>
>>>void *bn;
>>>
>>>A pointer that points to an unknown object.
>>>You can do only one thing with this pointer:
>>>pass it around.
>>
>>
>> These are called incomplete types; it's best to keep your terminology
>> consistent with standard usage.
>>
>
> struct unknown * is incomplete, void * not. To a beginner, an
> expression like void * must be utterly strange. I will explain
> this more later on.

Neither "struct unknown *" nor "void *" is an incomplete type; they're
pointers, possibly to incomplete types. "struct unknown" is an
incomplete type if there's no definition for the complete type.
"void" is an incomplete type that cannot be completed.

>> Incomplete types and opaque types are two different things, and an
>> opaque type needn't be an incomplete type. For example, the type FILE
>> in <stdio.h> is opaque as far as the programmer is concerned (the
>> standard says nothing about its contents), but I can see what's in it
>> (in many implementations) by viewing the appropriate header file.
>
> If you can see the contents, then its not opaque. Of course, any
> non-opaque structure can be converted in an opaque one if you refuse
> to look into it, but this would be playing with words. Normally, since
> it is not specified in the standard it is better not to mess with it,
> I agree with that, but with real opaque structures like void * that
> is no longer possible. You can't use them, they enforce themselves
> by definition.

The type FILE is an odd case. It's intended to act like an opaque
type, in the sense that the user isn't supposed to look inside it --
and a conforming implementation probably could make it a genuine
incomplete type, hiding the actual definition inside the library
implementation.

> Thanks for your feedback.

You're welcome. 

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Relevant Pages

  • Re: Vertical Text with TextOut()
    ... actually put some conditional compilation around it; then when I moved it to my laptop I'd ... I've got to update the Font Explorer (that was also on my ToDo List for the San Diego ... afx_msg void OnPaint; ... afx_msg void OnSize(UINT nType, int cx, int cy); ...
    (microsoft.public.vc.mfc)
  • Re: C Compilers
    ... int main ... Chars read: 190,Total compilation time = 0.003 sec. ... Ok, not a conformance issue. ...
    (comp.lang.c)
  • Re: simple question
    ... declaring the prototype of a function earlier and defining it later ... Doesn't having a function prototype also add type checking on the ... compilation unit and can ... void foo(int i, int n); ...
    (comp.lang.c)
  • Re: Why no compilation error.
    ... int a = 10. ... on compilation, now i got multiple definition error. ... can't have any expectations under the C language standard. ... Your program produces undefined behavior by having more than one ...
    (comp.lang.c)
  • Re: huge array
    ... or do you know a CPU which can handle something like "FOR I = 1 TO ... The dot net JIT compilers *do* interpret pseudo code (or whatever ... parsing and execution are two separate steps. ... compilation happens in two phases ...
    (microsoft.public.vb.general.discussion)