[CSUSB] >> [CompSci] >> /pool/faculty/dick/cs320/sebesta/06

## CS320 Notes on Data Types

http://www.csci.csusb.edu/dick/cs320/sebesta/06.html

## What is a Data Type?

The book does not define what a data type is  until chapter 11!
But it has lots of examples here instead.
My definition
A data type is a collection of values and operations.
Operations do things to values and produce values as a result.
This defines the Abstract data Type or ADT.
Compare with a C++ class.
Structured objects(values) with functions(operations).
T operator +(T left, T right){.....}

## Primitive Data Types

To describe a data type we need to define both the syntax and the
semantics.  Primitive data is often described by giving the syntax
and an informal mapping into mathematical objects:

Numerical Data Types map into NUMBERS (surprise :-)

Integer              A SUBSET of the integers
...-3,-2,-1,0,+1,+2,+3,...
Reals and doubles	SUBSETS of real numbers
Decimal			A subset of the fractions.

An important property of Numerical data is that
they have arithmetical operations(+*-/...) defined.

Implementation: A finite number of bits.
Axioms: Like arithmetic but approximate and with
risk of overflow.
Denotation: Number theory, Real Analysis.

Question:
Why is decimal arithmetic important?
MONEY

Sebesta does not mention "fixed point number".  Few languages
except COBOL provide it.  Essentially it provides an
efficient way to handle non-integral numbers that have
a fixed range and fixed precision.

point and floating point data types.   The compiler generates
a a new type (with values, syntax, operations, ...) as
needed to fit the ranges and precision that you want.

Good Ada programmers always define the precision and
range that they require for floating point types

There is no reason why you shouldn't have Decimal Floating point.
(except it isn't on most chips...)

Boolean
Two values - true and false
Operations include - and, or, not, ...

Implementation:  A single bit
Assumptions:
http://www.csci.csusb.edu/dick/maths/intro_logic.html
Denotation:	A Boolean Algebra with two elements.

Was available in Algol 60!

Recently added to C++  (and called 'bool')
#include <stdlib.h>

XLISP:   T and NIL
Scheme:  true false (I think?)
Prolog:  true fails (not false!)
Java:    Boolean True False (I think)
SmallTalk:  True and False are special classes of Object
within the class of Boolean. They are
responsible for handling selections and
iterations.

## Character Strings:

Values: zero or more characters
Operations:   Concatenation, substrings, substitution,....
Assumptions: No loss of information when strings concatenated. ...
How does C do strings?
It fakes them.
It fakes them
#include <string>
^no .h!
The faking is hidden behind an abstract data type or interface.

## User Defined Ordinal Types

Values: Chosen by the programmer
Operations: Minimal, predecessor, successor?
ORDERED, like 0,1,2,3,...
Assumptions:  Just like a subset of the non-negative integers.
C++: enum{...}
Danger: A Java Enumeration is not an Ordinal type. Pity.

## Subranges

Adds a run time test to all operations on the type,
unless the compiler can prove that the operation
is safe in some way of other
Not in C. Or C++

In Ada and Pascal subranges (sub types) are used to check
subscripts, as well as the results of arithmetic expressions.

Ada 95.  Takes this idea further to handle coercions and
a kind of polymorphism.

Notice:  The theory of inheritance is that it is a way to
implement subtyping.

## Array types

Values: Each array associates subscript values with elements.
Operations:....
Assumptions:....

## Implementing Arrays.

You need this in C,C++,Java, and CS330...

For example: C/C++ implementation is via pointers,
but the Standard Template Library (STL) will provide safer
arrays.
#include <vector>
For any given type T,
vector<T> my_row_of_Ts;
http://www.csci.csusb.edu/dick/c++std/
http://www.csci.csusb.edu/dick/cs202/stl.html

## Record Types

In essence a record is a primitive object with a minimal
set of methods/functions/operations available for manipulating it.

Can you recode  the books examples in C?
Java doesn't have any 'struct's.  Instead it has ________.
(The answer to this question is the same as every other
Java question...
Objects
)

## Union Types

Can you recode the example in C?  Is it simpler/safer/...

In C++ a kind of union and tag situation is set up whenever
a class has virtual methods and that class has several
classes derived from it.  Figure 5.10 looks at first
glance like a C++ object.

Notice that Object oriented languages replace Union data types
by polymorphic data types.  So in C++
inheritance and virtual functions make unions a bit obsolete.

## Set Types

NOT in C.... Not in Ada
The C++ STL has a <bitset>.
The STL <set> is an ordered set.
See CSCI330.

The logical operations (and,or,not,...) are extended to apply
to small arrays of bits.
C:  &, |, ~

However sets can be implemented in C, C++, Ada, Pascal,.....

Notice that higher level languages have set implementations:
Sets are part of SmallTalk and LISP.
Prolog uses Lists and/or predicates instead.
In Java, we have a HashTable that might be used for sets of objects?

## Pointers.

The goto of data structures.

Lost objects are commonly called GARBAGE.

Do you need them?
yes?
no?
What languages do not have pointers?
Java, Edison, Basic, Algol 60,...

(However in Java every object is accessed as a pointer
and its address can be stored in another object
)

## Reference Variables

Safe and constant pointers!

## Assigned work on Chapter 5.

I do not expect you know anything about the VAX minicomputers(problem 4).