CS323 Lecture: Data Types Last Revised 1/26/09Objectives1. To explore what is meant by a "data type"2. To introduce the notions of static and dynamic typing, and strong and weaktype checking.3. To define type equivalence, type compatibility, type inferrence,type conversion and type cast4. To introduce key issues concerning array, record and pointer typesIntroduction------------A. Thus far, we have dealt in rather general terms with notions of syntaxand semantics. We now want to spend a rather large amount of time lookingat different facets of programming languages in general terms - consideringwhat options the language designer has before him/her when designing a newlanguage. We begin our study by looking at features for declaring datatypes and objects; then we move to different kinds of executablestatements.B. One of the most important discoveries that has been made through work insoftware engineering is that, in solving a given problem, the mostimportant step is NOT the development of an algorithm. Rather, the mostimportant step is developing a representation for the problem's DATA.Frederick Brooks puts it this way in his book, The Mythical Man-Month,under the heading "Representation is the Essence of Programming":"Much more often, strategic breakthroughs will come from redoing therepresentation of the data or tables. This is where the heart of theprogram lies. Show me your flowcharts and conceal your tables, and Ishall continue to be mystified. Show me your tables, and I won'tusually need your flowcharts; they'll be obvious."C. We will consider a number of topics under this heading:1. What do we mean by a "data type"?2. What do we mean by "a type system"?, including key issues:a. Strong versus weak typing.b. Static versus dynamic typing.c. Type equivalence.d. Type compability.e. Type inference.3. The array structure.4. The record structure5. Pointers and referencesI. What Do We Mean by a Data Type?- ---- -- -- ---- -- - ---- -----A. At the hardware level, there is support for a limited number of data types- all built around the most basic type of all, the bit. This supporttakes the form of hardware instructions that support basic operations onthose types.1. Integers - typically of several different sizes (e.g. 8, 16, 32,maybe 64 bit), and with the standard arithmetic operations pluscomparisons typically supported.Many machines also support logical operations on integers regarded asvectors of bits - e.g. bitwise logical and, or, not, maybe xor.2. Reals - typically of two different sizes (e.g. IEEE Float, IEEE Double)and with the standard arithmetic operations plus comparisons typicallysupported.3. Characters - typically manipulated in the CPU/memory as 8 or 16 bitintegers, but handled as characters by various IO devices.4. Memory addresses (pointers/references) - typically using the samestorage representation as an integer (32 or perhaps 64 bits).5. Most programming languages include primitive data types that mapdirectly to the first four of these (e.g. Java byte, short, int, long,real, double, and char.)6. Many programming languages also support a boolean type that is actuallyimplemented by using a small integer with false being 0 and true being1; the hardware bit vector operations can be used on these, with allbut the rightmost bit being ignored.B. What do we mean by a data type in a higher-level language?ASK1. The book suggested that there are three different - but related - waysof looking at this question:a. Denotationally - a type denotes a set of values- Example: the set of values of the type boolean is false, true- Example: the set of values of the programming language type charin languages like C++ is a set that includes 52 letters, 10 digits,32 punctuation marks/special characters, the space, and 33 controlcharacters.- Example: the set of values of the type "int" is actually a finitesubset of the mathematical integers (e.g. in most languagesthe subrange -2,147,483,648 .. 2,147,483,647b. Constructively - a type is either one of a set of primitive types,or it is constructed from other types using type constructorslike array, record/struct/class etc.c. Abstractly - a type is an interface consisting of a set ofoperations.2. Another way of looking at it sees a type as being characterized bytwo sets:a. A set of values that instances of that type may assume.b. A set of operations on instances of that type.Example: The Java type intValues = { X | X is in the subrange of the mathematical integers:-2,147,483,648 .. 2,147,483,647 }Operations = { unary +, binary +, unary -, binary -, *, /, %,<<, >>, >>>, ++, --, ~, &, |, ^,==, !=, <, <=, >, >= }Example: Java array typesValues = { sequences of instances of some base type, numbered 0 ..some specified maximum }Operations = { [] |3. Data types may be classified as:a. Primitive types: types that are built in to the language andcorrespond directly to hardware data types.Examples: boolean, char, int ... (in Java, 8 in all)b. Ordinal types: scalar types whose instances are drawn from a fixedset of possible values, such that a one-to-onecorrespondence can be established with some integertypeExamples: most primitive types - but _not_ reals, enumerations,subranges of an ordinal typec. Scalar types: types whose instances are atomic and cannot be takenapart into smaller pieces.Examples: ordinal types plus realsd. Structured types: the value of an instance of a structured type isa composite of components of other, simplertypes. Different languages support differentways of constucting structured types- arrays (almost all languages)- records/structs/classes (most languages)- lists (a few languages)- maps (very few languages)- sets (very few languages)- files (treated as a kind of data type in a few languages)e. Pointer/reference types: the value of an instance of a pointer orreference type is the memory address ofan instance of some other type.4. An important issue is the notion of a named type versus an anonymoustype.1. A number of languages have a construct that allows the declarationof a named data type (e.g C/C++: typedef; Pacal, Ada and others:type).Examples (I will use Pascal throughout, but many have analoguesin other languages):typeintarray = array[1..10] of integer - is an array of 10 integersperson = recordstring name; - assume string already definedstring address;end; - person is a structure with 2 fieldstemperature = -20 .. 120; - temperature is a subrange of theintegersgender = (male, female); - gender is an enumerationletter_set =