Chapter 5 Data Types SANGJI University KO Kwangman () 1. Introduction o Type supports abstraction Real World 유한성 (finite) 추상화 (abstraction) Programming Language concrete representation Programming Language Implementation Natural Numbers int data 2's complement binary digits in sizeof(int) bytes Real Numbers double data IEEE754 binary digits in sizeof(int) bytes 2 o 타입 (type) ~ 값의집합과그값들에대한연산의집합. ~ 정수타입 값 :..., -2, -1, 0, 1, 2,... 연산 : +, -, *, /, <,... 로구성 ~ 불타입 값 : true, false 연산 : Ù, Ú, Ø 3 1
5.1 자료형오류 o 컴퓨터에저장된데이터 ~ 자료형정보를가지고있지않다. ~ 기본적으로비트들의열 (sequence) 을저장 예 : 0100 0000 0101 1000 0000 0000 0000 0000 o 비트열의가능한해석 ~ 부동소수점수 3.375 32 비트정수 1,079,508,992. 두개의 16 비트정수 16472 와 0 네개의 ASCII 문자열 @ X NUL NUL 4 o 타입오류 (type error) ~ 어떤연산을해당하지않는타입의값에적용함으로써발생하는오류 ~ 어셈블리프로그램작성시에자주발생 ~ 고급언어의경우에는컴파일러와실행시간시스템이타입오류를검사및추출 ~ 타입체계 (type system) 는타입오류를검출하기위한기반을제공 5 5.2 정적및동적타입결정 o 타입체계 ~ 덧셈에사용되는값은숫자여야한다는것과같은제약을보장 ~ EBNF 를사용하여문법적으로표현할수없음. o 자료형검사 ~ 컴파일시간에타입검사수행 C 언어 ~ 실행시간에타입검사수행 Perl 언어 ~ 두가지방법을다사용하기도한다. Java 언어 6 2
o statically typed ~ 변수의타입이컴파일시간에선언에의하여고정 ~ 정적으로타입이결정 (statically typed) 되는언어 o dynamically typed ~ 변수의타입이저장되는값에따라실행중에볂하 ~ 동적으로타입이결정 (dynamically typed ) 되는언어 7 o strongly typed 언어 ~ 타입체계가컴파일중이나실행중에모든타입오류를찾아낼수있을언어 ~ 동적타입결정또는정적타입결정. ~ 유니온 (union) 타입 많은언어들에서타입체계의허점의원인 ~ 동적으로타입이결정되는언어는각각의값에타입을함께저장 8 5.3 기본타입 o 현재 32-bit 컴퓨터에서사용되는용어 ~ Nibble: 4 bits ~ Byte: 8 bits ~ Half-word: 16 bits ~ Word: 32 bits ~ Double word: 64 bits ~ Quad word: 128 bits o 대부분의언어에서숫자타입은유한한크기 ~ a + b, Overflow 가능성 ~ 수학과의차이점존재 : a + (b + c) ¹ (a + b) + c 3
o 중복 (overloaded) ~ 함수나연산자가인수의타입에따라그의미가달라지는것 ~ a + b in Java 정수덧셈 부동소수점수덧셈 문자열접합 (concatenation) ~ 혼합모드 하나는정수이고다른인수는부동소수점수인경우 o 자료형변환 ~ narrowing 변환 원래값보다더적은수의비트열을결과로생성하는타입변환 ~ widening ~ 묵시적변환이허용되지않는이유? 11 5.4 사용자정의자료형 o 열거형 (Enumeration) : enum day {Mon, Tue, Wed, Thu, Fri, Sat, Sun}; enum day myday = Wednesday; ~ C/C++ 에서위타입들의값은 0,..., 6 이사용된다. ~ Java 는더강력한구조가사용 for (day d : day.values()) Sytem.out.println(d); 12 4
Pointer o 포인터 (pointer) ~ 다른변수의주소를가지고있는변수 char a='a'; char *p; p = &a; 26 주소 26 A 포인터 p 변수 a ~ 포인터가가리키는내용의변경 : * 연산자사용 *p= 'B'; 13 o 포인터연산자 ~ & 연산자 변수의주소를추출 ~ * 연산자 포인터가가리키는곳의내용을추출 *p 26 포인터 p 주소 26 A 변수 a &a 14 o 포인터의사용 struct Node { int key; struct Node* next; }; struct Node* head; 15 5
o 포인터사용에서발생될수있는문제 ~ 신뢰성있는소프트웨어의개발을방해. ~ 오류가생기기쉽다 ~ 버퍼넘침 (Buffer overflow), 메모리누출 (memory leaks) ~ 특히 C 에서문제가많이발생함 16 Array, List o 배열 (array) ~ 동일자료형 (same type) 의자료들이순서 (linear) 있게구성된집합 ~ 연속된기억공간차지 ~ 유한한개수의자료가저장됨 ~ 직접접근 (direct access) 기준위치에대한상대적위치를나타내는인덱스 (index) 를사용하여가능 시작주소 (base) A[0] A[1] A[9] 인덱스 ( 첨자 ) 배열이름 : 기억장소의시작위치 ( 주소 ) 17 o Java 에서의배열 ~ 선언 (declaration) 생성될배열시작위치저장 int dsint [] ; 1) int dsint [] 3) 생성된배열의 ~ 생성 (creation) 힙메모리에서배열크기만큼의기억공간을할당한후시작주소를배정 시작주소전달 2) dsint = new int[3] dsint = new int[3] ; dsint[0] dsint[1] dsint[2] 18 6
o Homeworks ~ 연결리스트 ~ 구조체 ~ 유니온 ~ 문자열 ~ 부분범위형 19 명시적자료형 (Explicit Typing) o 정적자료형검사 (static type checking) ~ static type checking is still controversial. ~ 유연성 (flexibility) 자료형결정및검사를느슨또는반대 ~ 신뢰성 (reliability) 또는보안 (security) 최대한제약성 (restrictiveness) 엄격한번역시간자료형검사 Flexibility type-less language still controversial Reliability (security) strongly typed language 20 정적자료형검사의이유 1. 수행효율성 (execution efficiency) ~ no need to run-time type checking ~ 효율적인메모리할당 ~ 효율적인목적기계코드생성 2. 번역효율성 (Translation Efficiency) ~ 분리컴파일 (separate compilation) 가능 ~ 재컴파일시컴파일되는코드의양을줄일수있음 3. 작성용이성 (writability, Coding Efficiency) ~ 번역시에타입에러를조기에발견 21 7
4. 보안과신뢰성 (security & reliability) ~ 실행시발생될수있는에러를사전차단 5. 판독성 (readability) ~ 명시적자료형선언은자료형설계를문서화 ~ good for documentation 6. 모호성제거 (remove ambiguity) ~ 다중적재된명칭 (overloaded names) 에대한모호성해결 (resolving) 7. 22 자료형정의 o 정의 _1 ~ a set of values ~ ex) the data type int in Java ~ V int = { x x Z, ~ -2,147,483,648 x 2,147,483,647 } o 정의 _2 ~ a set of values with a set of operations ~ ex) the data type int in Java V int = { x x Z, -2,147,483,648 x 2,147,483,647 } with the following set of operations F int = { +, -, *, } 23 자료형검사, 자료형추론 o 자료형검사 (type checking) ~ 번역기가프로그램내에자료형정보에문제가없는지검사한과정 ~ 연산자 ( 서브프로그램 ) 과피연산자 ( 매개변수 ) 사이에자료형의일관성 (type consistency) 을검사한과정 o 자료형추론 (type inference) ~ 수식에자료형부착 (attaching) 시키는동작 ~ z=x/y 에서 z 의자료형을결정하기위해서? x, y 의의자료형이결정되어야함. o 상호의존족 ~ 자료형검사와자료형추론은상호의존적 24 8
Constructing Types o 자료형구성자 (type constructors) ~ 기본자료형으로부터새로운자료형을구성 ~ Derived types are parameterized type constructors. Basic Types (primitive types) int, double, type constructors 사용자-정의자료형 (user-defined data type) Derived Types array, structures, type constructors 25 o 자료형선언 (type declaration) ~ 새로운자료형에이름부여 (In C example) typedef int int10[10]; 26 자료형시스템 (type system) o 자료형동등성 (type equivalence) 알고리즘 ~ 두개의자료형이일치하는지여부를결정하는알고리즘 ~ 방법? o 자료형시스템 (type system) ~ 자료형구성방법 ~ 자료형동등성알고리즘 ~ 자료형검사, 자료형추론 ~ 27 9
Typing o 엄격한자료형 (strongly-typed) 언어 ~ 모든자료형에러가번역시간에발견 ~ 가능한가장이른시점에프로그램내의모든에러발견 ~ 예외 (exception) 검사 실행도중에만검사할수있는오류 s. ~ 불안전한프로그램은대부분번역시간에거부 ~ 너무엄격해서적법한프로그램까지거부 ~ 적적한자료형정보를프로그래머가명시적으로제공 ~ Ada, Haskell, Pascal, 28 o 느스한자료형 (weakly-typed) 언어 ~ the languages which detect type errors during translation time but allow a few loopholes o 타입결여 (untyped) 언어 ~ 정적자료형시스템을지원하지않는언어 ~ 데이터안전성에관한검사가실행시간에이루어짐. ~ Scheme, LISP, Smalltalk, Perl, 29 Safe Programs o Every well-typed programs are safe but not vice versa. contain datacorrupting Executable Programs errors Legal Programs (Safe Programs) Unsafe Well-Typed Programs Programs 30 10
단순타입 (Simple Types) o 단순타입 ~ atomic types ~ the types which contain no other type substructures o 단순타입의분류 Simple Types Predefined Simple Types User-Defined Ordinal Types Defined Operators: successor predecessor comparison Enumeration Types Subrange Types 31 Ordinal Type Example o Enumerated Type in C enum Color { Red, Green, Blue }; o Enumerated Type in Ada type Color_Type is (Red, Green, Blue); o Enumerated Type in ML datatype Color_Type = Red Green Blue; o Java does not have enumerated types. o Subrange Type in Ada type Digit_Type is range 0..9; 32 Some Notes on Simple Types o 순서타입 (ordinal type) ~ 비교연산자를항상지원하지않음 ~ ex) Subrange of floating-point numbers in Ada. type Unit_Interval is range 0.0..1.0; o 부분범위타입 (subrange type) type Digit_Type is range 0.. 9; ~ 효과? o 단순자료형은하드웨어상에서직접구현 ~ 하드웨어효율성중시 33 11
Type Constructors o 타입 ~ 집합 (set) ~ 집합연산이기존의타입에서새로운타입을구성하는데사용 o 타입구성자 (type constructor) ~ 집합연산이타입에적용 ~ 데카르트곱, 합집합, 멱집합, 함수집합, 부분집합. 34 데카르트곱 (cartesian product) o Cartesian product ~ a set of pairs ~ 두집합 U, V 에대한모든원소들의순서쌍 (ordered pair) U ⅹ V = { (u, v) u U and v V } p 1 : U ⅹ V U p 2 : U ⅹ V V with projection functions p 1 and p 2 : p 1 ((u, v)) = u p 2 ((u, v)) = v o corresponding to the Cartesian products ~ record (structure) constructors 35 Example: Structure Types in C struct IntReal // IntReal = int ⅹ double { int i; double r; }; struct IntReal x = {1, 2.5}; // x = (1, 2.5) IntReal x.i // p 1 (x) x.r // p 2 (x) component selector operation (structure member operation) 36 12
합집합 (union) o 합집합종류 ~ 비구별합집합 (undiscriminated union) normal set union ~ 구별합집합 (discriminated union) 원소를구별하기위한태그 (tag) 가첨부 37 o Example: Union in C ~ undiscriminated union: a union itself ~ discriminated union: a union embedded in a structure union IntOrReal { int i; double r; }; enum Disc {IsInt,IsReal}; struct IntOrReal { enum Disc which; union { int i; double r; } val; }; 38 More Safe Union o Variant Records in Ada ~ the discriminant and the value should be assigned at once type Disc is (IsInt, IsReal); type IntOrReal (which: Disc) is record case which is when IsInt => i:integer; when IsReal => r:float; end case; end record;... x: IntOrReal := (IsReal,2.3); o Datatype in ML ~ enumerators may include data fields ~ pattern matching using case expressions datatype IntOrReal = IsInt of int IsReal of real;... fun printintorreal x = case x of IsInt(i) => printint i IsReal(r) =>printreal r ; 39 13
부분집합 (subset) o 부분집합 ~ supported by subtypes( 부분자료형 ). o In Ada ~ subtypes and subrange types are different: ~ subtype subtype IntDigit_Type is integer range 0..9; ~ new type (that is a subrange of an existing type) type Digit_Type is range 0..9; ~ fixing the variant part of a variant record type subtype IRInt is IntOrReal(IsInt); subtype IRReal is IntOrReal(IsReal); 40 Arrays and Functions o Consider a function f: U V If U is an ordinal type, f corresponds to an array: U: index type, V: component type f(i) V which i U o Array Size Problem ~ the size of an array may be or may not be the part of an array 41 Array Example: C/C++ o The size of an array is not part of the array. ~ When passing array parameters, the sizes of the arrays may have to be passed as separate parameters. int array_max (int a[], int size); ~ In a formal parameter, the array notation = pointer. o Difference between C and C++. ~ 교재가틀렸다. const int Size = 5; int x[size]; /* illegal C, ok in C++ */ int x[size*size]; /* illegal C, ok in C++ */ 42 14
Array Example: Java, Ada o In Java, ~ the size of an array is the part of the array ~ array can be dynamically allocated o Unconstrained Array in Ada ~ dynamically sized array ~ 배열선언시크기결정 // a part of Figure 6.3... int [] x = new int[u] ; // Dynamic array allocation for (int i = 0; i < x.length; i++) x[i] = i;... type IntToInt is array (INTEGER range <>) of INTEGER;... declare x: IntToInt(1..size); begin for i in x'range loop x(i) := i; 43 Multidimensional Array o Supporting Multidimensional Array ~ Multidimensional array may be simulated by arrays of arrays (C, C++, Java) o 기억장소할당 (memory allocation) ~ Row-Major : natural way for arrays of arrays ~ Column-Major : FORTRAN ~ 특정원소접근공식? Row-Major: 1 2 3 Column-Major: 1 3 5 4 5 6 2 4 6 44 Passing Multidimensional Array o 배열을매개변수로전달 ~ 배열의크기가배열의일부로간주 there is no problem of array parameters. ~ 배열의크기가배열의일부로간주되지않는경우 매개변수전달시배열의크기를전달 o passing 2-dimensional array in C/C++. ~ When the both dimensions are known ~ When the 1 st dimension should be passed ~ When the both dimensions should be passed 45 15
Passing no Dimensions #include <iostream> using namespace std; const int R = 3, C = 3; int sum(int a[r][c]) { int sum = 0; for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) sum += a[i][j]; return sum; } main() { int a[r][c] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; cout << "1+2+..+9 = " << sum(a) << endl; } 46 Passing the 1 st Dimension #include <iostream> using namespace std; const int R = 3, C = 3; int sum(int a[][c], int row) { int sum = 0; for (int i = 0; i < row; ++i) for (int j = 0; j < C; ++j) sum += a[i][j]; return sum; } main() { int a[r][c] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; cout << "1+2+..+9 = " << sum(a, R) << endl; } 47 Passing the Both Dimensions #include <iostream> using namespace std; int sum(int a[], int row, int col) { int sum = 0; for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) sum += a[i*col+j]; return sum; } const int R = 3, C = 3; main() { int a[r][c] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; cout << "1+2+..+9 = " << sum(&(a[0][0]), R, C) << endl; } 48 16
Some Notes on 2-Dimensional Array o Equivalences and Differences ~ for a constant N int a[n] int a[] int *a ~ for constants M and N int a[m][n] int a[][n] int (*a)[n] ~ beware that int a[][n] int **a o Declarations of C/C++ ~ declarations implies the usages int *a[n]; int (*a)[n]; 49 Pointer(Reference) Types o Pointer(Reference) Type ~ 집합연산에대응되지않는타입구성자 ~ 지정된자료형을지칭 ( 참조 ) 하는모든주소들의집합 ~ 자동쓰레기수집에허용되는언어에서포인턴묵시적 Java, ML, Scheme o 참조 vs. 포인터 ~ 참조 : 시스템제어하에있는객체의주소 값으로사용및연산이가해질수없음. ~ 포인터 값으로사용및연산이가해질수있음. double r = 2.3, &s = r; 50 o In C and C++, arrays are constant pointers int a[] = {1,2,3,4,5}; int* p = a; printf( %d \n, *p); printf( %d \n, *(p+2) ); printf( %d \n, *(a+2) ); printf( %d \n, 2[a]); a[2] *(a + 2) 2[a] // Wow! 51 17
Recursive Types o 순환타입 (recursive types) ~ a type that uses itself in its declaration ~ pointers are useful for recursive types o The Size Problem of Recursive Types ~ require that the maximum size of a data type should be determined at translation time. 52 struct CharList { char data; struct CharList next; }; /* illegal! */ union CharList { enum { nothing } empty; struct { char data; union CharList next; } charlistnode; }; /* still, illegal! */ struct CharListNode { char data; struct CharListNode* next; }; typedef struct CharListNode* CharList; /* Now, legal */ 53 Data Types and the Environment Fully Dynamic Environment Traditional Environment (stack & heap) Recursive Types General Function Types Recursive types and function types are implemented by pointers Functional Languages Algol-style Languages 54 18
The Type Structure of C 55 The Type Structure of Java 56 Simplified Type Structure of Ada 57 19
타입동등성 (Type Equivalence) o 타입동등성이란? ~ 두개의타입이어느때같은 (= 일치 = 동등 ) 한가! ~ 종류 구조적동치 (structural equivalence) 이름동치 (name equivalence) 선언동치 (declaration equivalence) o 구조적동치 ~ 두개의타입이동일한구조 (same structure) ~ 동일한구조 the same type constructor and the same component types. ~ 교재 PP.258 58 o 이름동치 ~ 두개의타입은공일한이름을가질때에만동등 o Declaration Equivalence ~ Two types are equivalent if they are derived from the same name. 59 Complicating Factors o Array Size ~ 배열의크기를배열의한부분으로간주? o Field Names of Record Types ~ The following RecA and RecB should be structurally equivalent (char ⅹ int) but not in practice because of the field names. struct RecA { char x; int y; }; struct RecB { char a; int b; }; 60 20
Language Example: Ada o Ada ~ pure name equivalence the variables a and b in a, b: array (1..10) of integer; are not type equivalent because the above declaration is considered as a shorthand for a: array (1..10) of integer; b: array (1..10) of integer; ~ the new types and the subtypes are different each other new type type Age is new integer; subtype: compatible to the original type subtype Age is integer; 61 Language Examples: Others o Pascal ~ every type constructors introduce a new type ~ new type names for existing type names are equivalent o Java ~ no typedef constructs ~ class and interface declarations introduce a new type name ~ inheritance hierarchy (subtype) ~ structural equivalence for arrays 62 타입검사 (Type Checking) o 타입검사종류 (categories) ~ Dynamic Type Checking 타입정보를실행시간에유지하고검사 ~ Static Type Checking 느슨한 (weakly) 자료형검사언어 Strongly-Typed Languages o Unspecified whether dynamic or static typing is to be used 63 21
Type Checking Examples o C/C++ ~ static type checking ~ no a strongly typed language: type conversion o Scheme ~ dynamic type checking but rigorous ~ predefined type test functions: number?, symbol?, o Ada ~ a strongly typed language ~ array bound checks are performed during runtime: exceptions 64 Type Checking and Type Inference o 타입추론 (inference) ~ the process to infer the type of an expression from the types of its subexpressions o Type Checking and Type Inference ~ Type checking rules and type inference rules are intermingled e 1 + e 2 ~ Type checking rules are type inference rules are closely related with the type equivalence algorithm ~ Explicit declarations are helpful for type checking but not mandatory 65 Type Compatibility o Relaxing the type correctness Type Equivalence e 1 + e 2 Type Compatibility e 1 and e 2 should be e 1 and e 2 should be of equivalent types. of compatible types. For assignment compatibility, information preservation is an important requirement. o Language Examples ~ Ada: subrange types of a base type are compatible ~ C, Java: numeric types are compatible 66 22
Implicit Types o Implicit Types ~ The types of entities are not explicitly declared but inferred implicitly o Examples ~ C: the types of variables and functions are implicitly int x; /* implicitly int */ f(int x) { return x + 1; } /* returns int */ ~ Pascal: constants are implicitly typed from the literals const PI = 3.14159; (* implicitly real *) 67 Type Conversion o Classifying Type Conversions ~ According to the notation Implicit Conversions (coercion) Explicit Conversions (casting) ~ According to the sizes of the types involved Widening Conversions Narrowing Conversions: may involve a loss of data o C Example int x = 3; x = 2.3 + x / 2; 68 int double double int promotion (widening) assignment conversion (narrowing) Notes on Type Conversions o Advantages of Explicit Conversions ~ Type conversions are documented precisely. ~ Make it easier for the translator to resolve overloading. double max(int, double); // max #1 double max(double, int); // max #2... max(2, 3); // calls what? max(2, (double)3); // calls max #1 o Structure Casting ~ The sizes of the structure types should be identical. ~ The translation merely reinterprets the memory 69 23
포괄 (generic) Pointers o Generic pointers may point anything. ~ anonymous pointers (void* in C) char * int *... conversion 1 conversion 2 void * ~ C allows the both conversion to be implicit. ~ In C++, the conversion 1 is implicit but the conversion 2 should be explicit. 70 Library Functions for Conversions o Ada Example ~ attribute functions of the character type character'pos('a') -- returns 97 character'val(97) -- returns 'a' o Java Example ~ conversion functions of the Integer class String s = Integer.toString(12345); int i = Integer.parseInt("54321"); 71 24