Re: What's in a type?

[Alf P. Steinbach]

On 23.12.2016 01:33, Stefan Ram wrote:
> Dan Sacks asked (in the context of C and C++), »What's a data
> type?«.
>
> (Maybe you want to pause here and think about it yourself
> for a moment.)
>
> He later gave his answer. From his slide:
>
> A data type is a bundle of compile-time properties
> for an object:
>
> o size and alignment
> o set of valid values
> o set of permitted operations
>

In C++ one might consider the type `void`. It has no size or alignment,
no values, and no permitted operations. One can define an unlimited
number of similar types.

So I think he's attacking the problem of definition from the wrong end.

Instead of trying an all out definition of type one can say, hey, this
is the basic core concept of a data type. This other thingy is also
considered a type; it's similar in the following respects: [...]. And
then we have ..., which is..., and so on; this list is not complete.


> Well, if he would have asked me this question, I would have
> started to stutter and said some drivel. Later, when I would
> have time to think about it, I might think the best answer
> would be to ask him whether he refers to a specific
> programming language, and, if so, to which programming
> language, and then whether I may now take some time (an
> hour?) to thing about my answer.
>
> But I am not sure whether I would deem his slide to be a
> satisfying answer! One reason would be this:
>
> struct A { int x; };
> struct B { int x; };
>
> A and B now agree in everything on his slide, yet they are
> different types!

As I recall they would be considered identical in original K&R C.

Not entirely sure.


> An abstract data types can hide its »values« up to the
> point where they are not a known determined set anymore.
>
> And when I define a function, say
>
> unsigned successor( unsigned const i ){ return i + 1u; }
>
> have I now added a »new permitted operation« to the type
> »unsigned« and thereby changed it into a different (new)
> type?

Oh, Scott Meyers went on and on about that.

Worth googling up, I think.


> I might post a followup later with an attempt to give
> an answer to his question.

:)


Cheers!,

- Alf

[Manfred]

On 12/23/2016 01:55 AM, Alf P. Steinbach wrote:
> On 23.12.2016 01:33, Stefan Ram wrote:
>> Dan Sacks asked (in the context of C and C++), »What's a data
>> type?«.
>>
>> (Maybe you want to pause here and think about it yourself
>> for a moment.)
>>
>> He later gave his answer. From his slide:
>>
>> A data type is a bundle of compile-time properties
>> for an object:
>>
>> o size and alignment
>> o set of valid values
>> o set of permitted operations
>>
>
> In C++ one might consider the type `void`. It has no size or alignment,
> no values, and no permitted operations. One can define an unlimited
> number of similar types.

Even more, one might consider a forward declaration:
struct A;

It introduces a type A in a scope, yet incomplete, but that exists so
that it can be used to some extent:
A* p;

although it has no size (not even zero size) yet.

>
> So I think he's attacking the problem of definition from the wrong end.

I think this too.

>
> Instead of trying an all out definition of type one can say, hey, this
> is the basic core concept of a data type. This other thingy is also
> considered a type; it's similar in the following respects: [...]. And
> then we have ..., which is..., and so on; this list is not complete.
>
>

I believe (at least in modern C and more in C++) a type is a fundamental
concept the language is built upon. As such, it is hardly defined in
terms of the categories of the language itself.
To me, a type is strictly coupled with the the concepts of
representation and semantics:
Representation is a broader concept than "contents", which would be the
second of the properties above.
Semantics is a broader concept than the third property above.

>> Well, if he would have asked me this question, I would have
>> started to stutter and said some drivel. Later, when I would
>> have time to think about it, I might think the best answer
>> would be to ask him whether he refers to a specific
>> programming language, and, if so, to which programming
>> language, and then whether I may now take some time (an
>> hour?) to thing about my answer.
>>
>> But I am not sure whether I would deem his slide to be a
>> satisfying answer! One reason would be this:
>>
>> struct A { int x; };
>> struct B { int x; };
>>
>> A and B now agree in everything on his slide, yet they are
>> different types!

Even more:
typedef int A;
typedef int B;

Strictly speaking, to me these are two different types (otherwise I
would not define two of them).

[Manfred]

On 12/23/2016 1:55 AM, Alf P. Steinbach wrote:
>>
>> struct A { int x; };
>> struct B { int x; };
>>
>> A and B now agree in everything on his slide, yet they are
>> different types!
>
> As I recall they would be considered identical in original K&R C.
>
> Not entirely sure.

I am not sure about K&R C, but this post refers to the 1974 Dennis
Ritchie's C reference manual from Bell Labs that does exactly what you
are saying:

https://groups.google.com/d/msg/comp.lang.c/FzfjDCD3VY4/cJMNLRKlBwAJ

From supercat's post:
https://www.bell-labs.com/usr/dmr/www/cman.pdf
paying particular attention to 7.1.7 and 7.1.8

>
>
> Cheers!,
>
> - Alf
>
>

[Scott Lurndal]

Manfred <non...@invalid.add> writes:
>On 12/23/2016 1:55 AM, Alf P. Steinbach wrote:
>>>
>>> struct A { int x; };
>>> struct B { int x; };
>>>
>>> A and B now agree in everything on his slide, yet they are
>>> different types!
>>
>> As I recall they would be considered identical in original K&R C.
>>
>> Not entirely sure.
>
>I am not sure about K&R C, but this post refers to the 1974 Dennis
>Ritchie's C reference manual from Bell Labs that does exactly what you
>are saying:

In the V6 C compiler, all MoS (Members of structure) were top-level
symbol table entries (thus they needed to be unique program-wide). This
is one reason that unix structs (e.g. struct stat) use prefixes on
the MoS names (e.g. st_size).

Since they were top-level symbol table items, one could use
the member names with any pointer, regardless of the pointer type
IIRC.

[Tim Rentsch]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> Dan Sacks asked (in the context of C and C++), >>What's a data

> type?<<. [...]

The word type is used to refer to two related but distinct
ideas in computer programming. Historically these ideas
were not distinguished (in Fortran, for example), so a lot
of people still confuse the two meanings. It's important
to understand the difference because, one, what makes sense
for one meaning sometimes doesn't for the other, and two,
the essence of OOP lies in realizing the distinction and
maximizing the gulf between the two different kinds of
"type". Let me try to illustrate.

The earliest understanding of "type" has to do with layout,
structure, or representation. If we have a variable of type
'int', the bits that make up the value will be positioned in
a particular way, so that what is stored in memory can be
interpreted as an abstract numeric value. I will refer to
this meaning of "type" as /structure/.

The other meaning of "type" has to do with what is expected,
or allowed, for a programmatic entity (eg, a variable or an
expression), when the program is being compiled. In the early
days of computing the only kind of thing that was expected is
what structure the variable or expression would have at runtime,
which explains why people used to think of the two ideas as the
same thing.

Let's look at a couple of examples. Consider these two variable
declarations:

static int i = 4;
static const int ci = 4;

The structure of these two variables is exactly the same: if we
looked at the bits, we would find the same pattern of zeros and
ones in both variables.

But what is expected (or allowed) for the two variables is /not/
the same. The variable 'i' is changeable, eg, with an assignment
statement. The variable 'ci' may not be changed via assignment.
Furthermore, even though it may be possible to change 'ci' by means
of some language or extra-linguistic trickery (eg, assembly), the
compiler may assume its value will /not/ change. In this case the
"type" of a variable is more specific than its structure.

For another example, consider this printf() call:

printf( "%.8x", 127 );

A %x conversion specifier expects an argument of type unsigned
int, but we have given for the actual argument a value of type
int. The printf() call still works, because 'int' and 'unsigned
int' are guaranteed to have the same representation for values in
the non-negative range of int. In some sense the "type" expected
is less specific than the structure information of the actual
argument value.

In C++ a good example illustrating the distinction between the
two aspects is a parameter of type Base*, where in a particular
call the argument value supplied is of type Derived*. The
structure of the object pointed to at runtime may not be the same
as what the compile-time pointer type nominally implies.

A note on terminology: the two kinds of "type" are sometimes
referred to as "dynamic type" or "run-time type", for the
layout/structure/representation aspect, and "compile-time type"
or often just plain "type", for the what-is-expected-or-allowed
aspect. I prefer the terms "structure" and "type", respectively,
for these two distinct aspects, but the important thing is to
understand the distinction (assuming of course that what terms
one uses for the two different aspects is made clear).

The essential idea in OOP is to decouple these two aspects as
much as possible. In Smalltalk, every value is an object
pointer, and that's it. What can we do with an object pointer?
Pass it as a value, store it in a variable, or send it a message
(and importantly, any message). All of those are true no matter
what class the object being pointed to belongs. In other words
the type -- ie, what is expected or allowed in terms of language
usage -- is completely decoupled from the class, or structure,
of what the object is at runtime. Obviously some of those things
will be nonsensical (eg, will result in "Message not understood"
popups), but the principle involved is at the heart of OOP and
OOD. (Historical note: in its early usage "object-oriented
programming" was understood to include what is now called design
or "object-oriented design", OOD/A, etc.)

A more complete explanation of the difference between "type"
and "structure" may be found in this paper:

A Type Declaration and Inference System for Smalltalk
http://dl.acm.org/citation.cfm?id=582168

Does my explanation help illuminate what "type" means in its
several aspects?

[Jens Müller]

On 23.12.2016 01:33, Stefan Ram wrote:
> A data type is a bundle of compile-time properties
> for an object:
>
> o size and alignment
> o set of valid values
> o set of permitted operations
>

[...]

>
> But I am not sure whether I would deem his slide to be a
> satisfying answer! One reason would be this:
>

> struct A { int x; };
> struct B { int x; };
>
> A and B now agree in everything on his slide,

No, they don't. The permitted operations are different. It's just not
very visible because the different operations are compiler-generated.

[Mr Flibble]

On 23/12/2016 00:33, Stefan Ram wrote:
> Dan Sacks asked (in the context of C and C++), »What's a data
> type?«.

Simple question, simple answer: in C++ a type is that which an object is
an instance of; an object doesn't have to be an instance of a class
type: an 'int' variable is also an object.

/Flibble

[Tim Rentsch]

This answer conflates the two different notions of type, as
explained in my other posting. For example a variable of
type 'int' and a variable of type 'const int' are both
instances of the 'int' representation, but they have
different types (ie, in the sense of what is checked at
compile time).

[Tim Rentsch]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> r...@zedat.fu-berlin.de (Stefan Ram) writes:
>> Dan Sacks asked (in the context of C and C++), >>What's a data
>> type?<<.
>

> ~~~

>
>> A data type is a bundle of compile-time properties
>> for an object:
>> o size and alignment
>> o set of valid values
>> o set of permitted operations
>

> ~~

>
>> I might post a followup later with an attempt to give
>> an answer to his question.
>

> I like Dan's first part because it uses >>properties<<. The
> term >>property<< is more abstract and therefore might still
> apply, even when the more concrete categories given later do
> not apply.
>
> But then he also uses the vague term >>bundle<<. We know that
> two sets are equal when all their members are equal, but
> when are two >>bundles<< equal? Because of this vagueness,
> the sentence possibly cannot be used as a definition.
>
> [...]

All these ideas have been explored in the literature 20, 30,
or 40 years ago. A good starting point is the paper by
James Morris, "Types are not Sets":

http://dl.acm.org/citation.cfm?id=582168

[Ben Bacarisse]

Tim Rentsch <t...@alumni.caltech.edu> writes:
<snip>

> All these ideas have been explored in the literature 20, 30,
> or 40 years ago. A good starting point is the paper by
> James Morris, "Types are not Sets":
>
> http://dl.acm.org/citation.cfm?id=582168

That seems to be the wrong link. I find it at:

http://dl.acm.org/citation.cfm?doid=512927.512938

--
Ben.

[Tim Rentsch]

Yes, thank you, that's the link I meant. Somehow I mistakenly
copied the wrong link from my clipboard.