The Artima Developer Community
Sponsored Link

Weblogs Forum
Comp. Sci. 101: Definition of Type

19 replies on 2 pages. Most recent reply: Dec 17, 2004 10:28 AM by Gregg Wonderly

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 19 replies on 2 pages [ 1 2 | » ]
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Comp. Sci. 101: Definition of Type (View in Weblogs)
Posted: Dec 4, 2004 2:29 PM
Reply to this message Reply
Summary
It is a challenge to find definitions for computer science terms, which are understandable, correct and uncontentious. Lately I have needed to come up with a good definition of type.
Advertisement
I am currently writing a detailed reference for the Heron programming language. In so doing, I have found it challenging to find good definitions for basic computer science terminology. The most recent term I am working on is "type". In writing about a type, I needed to be able to answer the question: what exactly is a type?

I wanted a definition which is short, precise and complete. The definition I came up with is:

type: a semantic classification of a set of values
There is little disagreement on the fact that a type is a set of values, but when I proposed this definition previously on the Lambda the Ultimate forums, there was some disagreement on what "semantic" means. The problem is that there is a common intuitive notion of what "meaning" is, which is not precisely correct. Using the Merriam-Websters dictionary online, semantic is defined as "of or relating to meaning in language.". Meaning is defined as "the logical connotation of a word or phrase", which I think can be applied appropriately in this case to a value. Finally connotation is defined by defined as "an essential property or group of properties of a thing named by a term in logic".

I believe that my proposed definition of type is correct and complete. Any thoughts or comments?


Larry O'Brien

Posts: 7
Nickname: lobrien
Registered: Jul, 2003

Re: Comp. Sci. 101: Definition of Type Posted: Dec 4, 2004 4:58 PM
Reply to this message Reply
re. "semantic classification"

I don't think that captures the behavioral nature of a Type. It seems to me that the constraints introduced by a type are its raison d'etre. I might have all sorts of "semantic classifications of a set of values" that are meaningless to a Type system. Compare "negative" and "positive" numbers, which are semantically valid classifications, but which are irrelevant, since the Type issue is whether numbers are "signed" or "unsigned" (since that has a relation to an underlying representation in hardware and its constraints).

Another point is that an enormous amount of the foo-farah about Type derives from the von Neumann architecture's reliance on context to determine the interpretation of binary memory, which shouldn't be conflated with "the way things must be."

Toby Donaldson

Posts: 8
Nickname: tjd
Registered: Jun, 2003

Re: Comp. Sci. 101: Definition of Type Posted: Dec 4, 2004 10:47 PM
Reply to this message Reply
I was the one who posted the oridinal query to Lambda the Ultimate about a CS-101 definition of type. I was a bit surprised by the variety of answers, and ultimately I ended up using a definition that was not given there.

Practically speaking, a term like "semantic" means very little to the average CS-101 student. Many of these students are just learning to program. If you give them a definition of types as you suggest, then I think they would simply memorize it and not really understand the term any better than if there was no definition at all.

So I ended up explaining the need for types in a more humble and concrete way: computer memory is just a long sequence of 32-bit words. A word might represent an integer, or 4 ASCII characters, or something else. You can't tell what it repersents just by looking at the bits. You need some extra information --- the type --- to know how interpret these bits correctly.

This isn't really a definition, but I think it lays the groundwork for the more abstract definitions of types. And I also think it gets CS-101 students to think more about what types are all about than a definition they don't really understand.

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Comp. Sci. 101: Definition of Type Posted: Dec 5, 2004 9:56 AM
Reply to this message Reply
I don't think that traditional notions of type are important practically. If they were there wouldn't be so many conflicting definitions.

On the other hand, I think it is nearly criminal that so many people are able to get through school without a clear understanding of behavioral subtyping. If I were doing early curriculum, I would use behavioral subtyping as the basis for nearly all discussions of type.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 5, 2004 12:30 PM
Reply to this message Reply
> I don't think that captures the behavioral nature of a
> Type. It seems to me that the constraints introduced by a
> type are its raison d'etre.

Two different types can have the same behaviour. It can be useful to differentiate types by some kind of user defined meaning.

> I might have all sorts of
> "semantic classifications of a set of values" that are
> meaningless to a Type system. Compare "negative" and
> "positive" numbers, which are semantically valid
> classifications, but which are irrelevant,

Not every semantic classification of values is a type, but every type is a semantic classification of values. I could easily design a positive number type, or a negative number type, so I don't see how it is irrelevant.

> since the Type
> issue is whether numbers are "signed" or "unsigned" (since
> that has a relation to an underlying representation in
> hardware and its constraints).

In many languages, I can write a type which has multiple underlying representations. Internal representations does not neccessarily distinguish one type from another.

> Another point is that an enormous amount of the foo-farah
> about Type derives from the von Neumann architecture's
> reliance on context to determine the interpretation of
> binary memory, which shouldn't be conflated with "the way
> things must be."

I am sorry, but I don't follow.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 5, 2004 12:54 PM
Reply to this message Reply
> I was the one who posted the oridinal query to Lambda the
> Ultimate about a CS-101 definition of type. I was a bit
> surprised by the variety of answers, and ultimately I
> ended up using a definition that was not given there.
>
> Practically speaking, a term like "semantic" means very
> little to the average CS-101 student. Many of these
> students are just learning to program.

Semantic has a clear meaning in English, which you can provide. "of or relating to meaning". This requires no programming experience. The point is that a type comes with extra information, which distinguishes a particular set of values from another.

> If you give them a
> definition of types as you suggest, then I think they
> would simply memorize it and not really understand the
> term any better than if there was no definition at all.

I agree, that some kind of context is needed. You can't just throw that at someone who is starting out and expect it to stick. You need to explain why types exist, and the various roles they play.

> So I ended up explaining the need for types in a more
> humble and concrete way: computer memory is just a long
> sequence of 32-bit words.

This is true only within the narrow confines of 32 bit Von Neumann architectures. So you have opted to fill your students with misinformation?!

> A word might represent an
> integer, or 4 ASCII characters, or something else. You
> can't tell what it repersents just by looking at the bits.
> You need some extra information --- the type --- to know
> how interpret these bits correctly.
>
> This isn't really a definition, but I think it lays the
> groundwork for the more abstract definitions of types. And
> I also think it gets CS-101 students to think more about
> what types are all about than a definition they don't
> really understand.

I think it is a very bad idea to give a definition of type in a bottom-up manner. Representation is secondary to a type, it is the meaning or behaviour associated with the type which is relevant.

Consider how a C++ "int" is defined. No part of the definition says anything about the bits.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 5, 2004 1:33 PM
Reply to this message Reply
> I don't think that traditional notions of type are
> important practically.

Could you give some examples?

> If they were there wouldn't be so
> many conflicting definitions.

I think the reason for conflicting definitions is because we have miseducation of computer science. For instance, if Toby isn't careful, his students won't learn the following things which conflict with his def'n:

- not all bits have a type
- specific bits at a specific location can be a part of different types at the same time
- types don't neccessarily have bits
- that computers don't have to arrange their memory in a linear sequence of same sized words

> On the other hand, I think it is nearly criminal that so
> many people are able to get through school without a clear
> understanding of behavioral subtyping. If I were doing
> early curriculum, I would use behavioral subtyping as the
> basis for nearly all discussions of type.

Honestly I am unsure of what that means. When I Google "behavioural subtyping" in quotes, I get 835 hits ( I get more for my own name ;-) ) If I attempt to deduce the meaning from the term, I believe you are refering to the mechanism of being able to use one type in place of another so as long as the extensional characteristics are satisfied ( for instance the set of public methods ). Are interface types an example of behavioural subtyping?

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Comp. Sci. 101: Definition of Type Posted: Dec 5, 2004 2:52 PM
Reply to this message Reply
> Honestly I am unsure of what that means. When I Google
> "behavioural subtyping" in quotes, I get 835 hits ( I get
> more for my own name ;-) ) If I attempt to deduce the
> meaning from the term, I believe you are refering to the
> mechanism of being able to use one type in place of
> another so as long as the extensional characteristics are
> satisfied ( for instance the set of public methods ). Are
> interface types an example of behavioural subtyping?

Pretty much.. it is a definition of subtyping given by Liskov and Wing ('behavior' without the 'u' gives closer hits).

Subtype Requirement: Let phi(x) be a property provable about objects x of type T. Then phi(y) should be true for objects y of type S, where S is a subtype of T.

Interfaces can be used to enable this sort of subtyping but satifaction is really determined by the concrete classes that implement them.

The requirement is very tight and there are good reasons to loosen it at times. For instance, the Liskov Substitution Principle loosens it a bit by saying that subtyping depends on how S is used in a context rather than upon inherent properties of S. Regardless, I think that awareness of the concept is very important groundwork for people who will be thinking about programs most of their career. I think it really should be drilled in early.

Vincent O'Sullivan

Posts: 724
Nickname: vincent
Registered: Nov, 2002

Re: Comp. Sci. 101: Definition of Type Posted: Dec 6, 2004 6:23 AM
Reply to this message Reply
> type: a semantic classification of a set of values
> :
> I believe that my proposed definition of type is correct and complete. Any thoughts or comments?

Since you already believe that your own answer is 'correct and complete', what do you want us to add?

> So you have opted to fill your
> students with misinformation?!

Such a sarcastic reply as the one above to someone elses thoughts on the subject isn't exactly going to encourage much feedback, is it.

Vince.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 6, 2004 10:46 AM
Reply to this message Reply
> > type: a semantic classification of a set of
> values

> > :
> > I believe that my proposed definition of type is correct
> and complete. Any thoughts or comments?
>
> Since you already believe that your own answer is 'correct
> and complete', what do you want us to add?

I just want to know whether people agree or disagree, and if they disagree, I would appreciate clear reasons why. Such as by providing counter-examples which demonstrate why the definition is insufficient or overly general. Because I have strong opinion on the subject doesn't mean I am not open to other reasonable and well thought out ideas.

> > So you have opted to fill your
> > students with misinformation?!
>
> Such a sarcastic reply as the one above to someone elses
> thoughts on the subject isn't exactly going to encourage
> much feedback, is it.

My apolgoies to Toby if I was disrespectful, it was not my intention, but I was not being sarcastic. His explanation of type is misleading, and I thought I gave clear reasons why. In hindsight, I should not have responded in such a manner, I am sorry.

James Pfister

Posts: 1
Nickname: feester
Registered: Dec, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 8, 2004 4:03 PM
Reply to this message Reply
I think it is incorrect to think of 'type' as referring to values, as your definition does. At least in Java, type is something that is said about variables. Class is something that is said about values. I think you will find helpful and interesting chapter 4 on "Type, Values and Variables" in the JAVA LANGUAGE SPECIFICATION 2nd Edition.

http://java.sun.com/docs/books/jls/second_edition/html/typesValues.doc.html#48440

Here is their definition in the first paragraph:

"Types limit the values that a variable (§4.5) can hold or that an expression can produce, limit the operations supported on those values, and determine the meaning of the operations"

Before I went back to the aforementioned chapter and refreshed my memory, this was the definition that I had come up with:

"Type defines or limits a variable's ability to hold some sub-set of all possible values."

Best Regards, feester

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Comp. Sci. 101: Definition of Type Posted: Dec 8, 2004 4:18 PM
Reply to this message Reply
> Here is their definition in the first paragraph:
>
> "Types limit the values that a variable (§4.5) can hold or
> that an expression can produce, limit the operations
> supported on those values, and determine the meaning of
> the operations"
>
> Before I went back to the aforementioned chapter and
> refreshed my memory, this was the definition that I had
> come up with:
>
> "Type defines or limits a variable's ability to hold some
> sub-set of all possible values."

Everyone defines type in a way that is convenient for them. The thing I don't like about that definition is that bowls over the fact that both static and dynamic typing exist. The people who are most concerned with definitions have failed to notice that and as a result we've ended up with many academics categorizing dynamically typed languages as typeless languages. That term doesn't really do them much justice.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 8, 2004 4:33 PM
Reply to this message Reply
Hi Feester,

> I think it is incorrect to think of 'type' as referring to
> values, as your definition does. At least in Java, type
> is something that is said about variables. Class is
> something that is said about values.

Their documentation is misleading. Java is a strongly typed language, every value, variable and expression in Java has a type. The literal <tt>42</tt> is an example of a value with a type. It's type is <tt>int</tt>. Furthermore a class is type, but not all types are classes, at least not in Java anyway.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Comp. Sci. 101: Definition of Type Posted: Dec 8, 2004 4:38 PM
Reply to this message Reply
> Everyone defines type in a way that is convenient for
> them.

Most of the time their definitions are wrong, insufficient or general.

>> "Type defines or limits a variable's ability to hold some
>> sub-set of all possible values."
>
> The thing I don't like about that definition is
> that bowls over the fact that both static and dynamic
> typing exist.

My bigger beef is that it also applies only to variables, and ignores functions, expressions, literals, etc.

> My def'n o
> The people who are most concerned with
> definitions have failed to notice that and as a result
> we've ended up with many academics categorizing
> dynamically typed languages as typeless languages. That
> term doesn't really do them much justice.

Good point, dynamic typing is not typelessnes.

Larry O'Brien

Posts: 7
Nickname: lobrien
Registered: Jul, 2003

Re: Comp. Sci. 101: Definition of Type Posted: Dec 9, 2004 1:20 PM
Reply to this message Reply
> Not every semantic classification of values is a type, but
> every type is a semantic classification of values.

I agree with that statement, but doesn't that mean your definition requires further precision?

>I could
> easily design a positive number type, or a negative
>number
> type, so I don't see how it is irrelevant.

Well, yes, or a "Foo" or a "Bar". If the problem is "What subset of 'semantic classifications of values' is worth defining as the set of types we'll be using in our system," I would argue that the answer comes from determining what constraints / behavior / capacity are important.

In your reply you said both that two types can have identical behavior (I assume you include range of values) and a single type can have multiple underlying representations. I'd submit that you're shifting perspective to argue both sides of the coin. I argue that within a given language, a type is what a type does.

Yes, one can define two types that are identical but which have different type identifiers. C-style enums strike me as the closest common example to 'identical but usefully distinct,' but even enum directions { Left, Right } and enum political_leanings { Left, Right } have different behavior in that they can't be assigned interchangeably: that constraint is imposed by the type system, true, but that's the point -- types constrain behavior. If you create two identical types that have identical behavior (including range of values and assignment compatibility), surely it's fair to say that one of the two is erroneous?

My point about the von Neumann architecture echoes some of the concerns you had about Toby's response, although I think you are too quick to dismiss his perspective. The primacy of types in discussions of computer science is not coincidental to the primacy of the von Neumann architecture.

In your reply to Toby you say "types don't necessarily have bits," which I don't follow.

Flat View: This topic has 19 replies on 2 pages [ 1  2 | » ]
Topic: Excerpt: Beyond Lifestreams, the inevitable demise of the Desktop Metaphor Previous Topic   Next Topic Topic: Pitching a Fit


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us