제 6 장 데이터 타입 6.1 데이터 타입 및 타입 정보 6.2 타입의 용도 6.3 타입 구성자 6.4 사례 연구 6.5 타입 동등성 6.6 타입 검사

6.1 데이터 타입 및 타입 정보

개 요 기본 타입(Basic type) 유도 타입(Derived type) 타입들의 특성 타입의 용도

기본 타입 및 유도 타입 유도 타입 기본 타입 boolean, char(나열 타입의 하나로 간주할 수 있음); integer; real; 나열 타입(Enumerated type) 부분범위 타입(Subrange) 유도 타입 Array types; Record types; Union types; Set types; Pointer types.

기본 형: 예 나열 타입 부분범위 타입(Ada, Pascal) 부분범위 타입 없음(C, C++, Java) enum Color {Red, Green, Blue}; 부분범위 타입(Ada, Pascal) type digit is range 0 .. 9; 부분범위 타입 없음(C, C++, Java) byte digit; // -128 .. 127 If (digit >9 || digit < 0) thrown new DigitException(); 사전정의 타입은 무엇인가?

데이터 타입의 의미 다음 선언을 생각해보자 int x; 이 변수 선언에서 데이터 타입은 무엇을 의미하는가? 정의 1 그 타입의 변수가 가질 수 있는 값들의 집합 정의 1 A data type is a set of values. 따라서 위 선언의 의미는 x  Integer

데이터 타입의 의미 데이터 타입의 의미 값들의 집합(a set of values) 그 값에 적용 가능한 연산들의 모음(a group of operations) 정의 2 A data type is a set of values, together with a set of operations on those values. 데이터 타입의 수학적 의미 an algebra (S, Op) where S is a set of values and Op is a set of operations on S

6.2 타입의 용도

실세계 대상의 표현 답 1 예: 날짜 표현 실세계 대상 표현 YYMMDD; YYDDD; DDMMYY; DDMMYYYY. 정수들의 배열 Day, month, year 필드를 갖는 레코드

타입을 이용한 메모리 할당 답 2 예 메모리 배치 컴파일러가 변수 선언을 보고 필요한 메모리 양을 계산한다. 타입을 이용한 메모리 할당 답 2 메모리 배치 컴파일러가 변수 선언을 보고 필요한 메모리 양을 계산한다. 예 Array of integer: A[0] A[1] A[2] A[3] A[4] A[5] Record of integer: Day Month Year

타입 검사(Type checking) 답 3 예 올바른 경우 틀린 경우 타입이 올바르게 사용되고 있는지 검사 타입을 중심으로 말이 되는 프로그램인지 검사 예 컴파일러에서 산술 연산이 올바르게 수행되고 있는지 검사 올바른 경우 틀린 경우 int x, y, z int x, y; char z; z = x / y z = x / y

6.3 타입 구성자 (Type Constructors)

타입 구성자란 무엇인가? 기본 타입으로부터 더 복잡한 타입을 구성하는 방법 Array types; Record types; Union types; Set types; Pointer types. 사용자-정의 타입

구조체(레코드) 타입 C의 예 Ada의 예 struct IntCharReal { int i; char c; float r; } type IntCharReal is record i: integer; c: character; r: float; end record;

구조체(레코드) 타입 타입 구성자 struct, record C++의 struct 혹은 class int, char, float로부터 새로운 타입 IntCharReal를 정의한다. struct in C record in Pascal, Ada, ... C++의 struct 혹은 class C의 struct를 확장 데이터뿐 아니라 연산(함수)들을 포함하도록

레코드의 수학적 의미 IntCharReal가 의미하는 값들의 집합은 ? int: Int char: Char float: Real Cartesian Product U  V = { (a,b) | a U, b V } Cartesian product can be extended to more than two sets What is an operation corresponding to the projection ? ML의 예 type IntCharReal = int * char * real;

레코드 타입에 대한 연산들 필드 선택 연산(Field selector operation) x.i Project of x to the integer

레코드을 위한 기억장소 배치 예 정확한 상대위치를 컴파일-시간에 계산할 수 있다. struct IntCharReal x; x.i x.b x.r integer char float x.i x.c x.r

유니온 예(C) union IntOrReal { int i; float r; }; enum Disc {IsInt, IsReal}; struct IntOrReal { enum Disc which; union { int i; } val;

유니온의 종류 구별 유니온(Discriminated union) 비구별 유니온(Undiscriminated union) 구성원을 구별하는 태그 필드(tag field) 존재 Algol, Pascal, Modula의 변이 레코드(variant record) 비구별 유니온(Undiscriminated union) C의 유니온은 태그 필드나 공통 부분이 없다.

구별 유니온: Ada 예 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);

유니온 타입에 관한 잇슈 수학적 의미 합집합 유니온 타입을 위한 메모리 할당 최대값

집합 타입(Set type) What is an element of the power set of a set S ? type digit = 0 .. 9; digitSet = SET OF digit In Pascal, Modula SET OF ordinal type

부분타입(Subtype) Ada의 예 subtype Digit is integer range 0..9; 부분타입의 연산 기반 타입(base type)의 모든 연산을 상속 받는다 기반 타입의 모든 연산을 부분타입에 적용 가능하다. 객체-지향 언어의 상속 자식 클래스는 부모 클래스의 부분타입이다. 왜?

배열 타입 C의 배열 선언 C 언어 Java typedef int DigitToInt[10]; typedef int IntArray []; DigitToInt A; IntArray B[] = {1,2,3,4} C 언어 배열 크기가 정적 결정 Java 배열 크기 동적 결정 배열 크기가 배열의 일부

C 예제 int array_max(int a[], int size) { int temp, i; assert(size > 0); temp = a[0]; for (i = 1; i < size; i++) { if (a[i] > temp) temp = a[i]; } return temp;

Java 예제 class ArrayTest { static int array_max(int[] a) { int temp; temp = a[0]; for (i = 1; i < a.length; i++) { if (a[i] > temp) temp = a[i]; } return temp;

수학적 의미 배열 DigitToInt의 의미 DigitToInt DigitToInt인 배열 A가 나타낼 수 있는 값들의 집합 값들의 연속(Sequence) 혹은 튜플(Tuple) (A[0], A[1], A[2], …, A[9]) 함수 f  Digit  Int 0  A[0] 1  A[1] . . . 9  A[9] DigitToInt the set of all functions from Digit to Int Digit  Int

배열의 메모리 배치 일차원 배열의 배치 A[i]의 주소 = base + i*w base . . . A[0] A[1] A[2] . . . A[0] A[1] A[2] A[8] A[9]

다차원 배열의 메모리 배치 예 행우선 할당(Row-major order allocation) int x[10][20]; /* C 코드 */ int[][] x = new int [10][20]; /* Java 코드 */ 행우선 할당(Row-major order allocation) x[0,0] x[0,1] . . . x[0,19] x[1,0] x[1,1] . . . x[9,19] X[i,j]의 주소 = base + i*n*w+ j*w = base + ( i*n + j)*w 열우선 할당(Column-major order allocation)

포인터 타입 예 질문 포인터 혹은 참조 타입의 의미는 ? typedef int* IntPtr; IntPtr x; 지정된 타입의 모든 가능한 주소들의 집합

순환 타입(Recursive Type) 타입 정의에 자신의 이름을 사용하는 경우 예 struct CharList { char data; struct CharList next; /* C에서 위법 */ }; 이 정의의 문제는 무엇인가?

순환 타입(Recursive Type) 포인터는 순환 타입 정의에 유용하다. 예 struct CharListNode { char data; struct CharListNode* next; /* legal in C */ }; typedef struct CharListNode* CharList;

6.4 사례 연구

C Types Basic Derived void Numeric Pointer Array Function struct union Integral char, int, short, long enum Floating float, double, long double Derived Pointer Array Function struct union

Java Types Primitive Reference boolean Numeric Array class interface Integral byte, char, short, int, long Floating float, double Reference Array class interface

6.5 타입 동등성

타입 동등성이란 ? 타입 동등성 규칙은 무엇인가 ? 타입 동등성은 언제 필요한가? 두 타입이 같은지 결정하는 규칙 매개변수 전달 배정 동등비교(equality operator) …

타입 동등성 규칙의 종류 구조 동등성(Structural equivalence) 이름 동등성(Name equivalence) Algol, FORTRAN, COBOL, Modula-3 C(구조체 및 유니온 제외) Java의 배열 이름 동등성(Name equivalence) Java의 class와 interface C의 구조체 및 유니온 선언 동등성(Declaration equivalence) Pascal

구조 동등성 기본 아이디어 같은 구조 두 타입이 구조 동등하면 그들은 같은 값을 포함하는가 ? 구현 두 타입은 구조가 같으면 같다 같은 구조 같은 단순 타입으로부터 같은 구성자를 사용하여 같은 방식으로 구성되었으면 구조가 같다. 두 타입이 구조 동등하면 그들은 같은 값을 포함하는가 ? 구현 타입을 트리 형태로 표현한다. Check equivalence recursively on subtrees !

예 struct Rec1 { char x; int y; char z[10]; }; struct Rec2 { char x; { char y; int x; char z[10]; };

이름 동등성(Name Equivalence) 기본 아이디어 두 타입은 같은 이름을 가지면 같은 타입이다. 구 변수는 같은 타입 이름을 사용하여 선언되었으면 같은 타입니다. 예 struct RecA { char x; int y; }; typedef struct RecA A struct RecA a; A b; struct RecA c; struct { char x; int y; } d;

선언 동등성 기본 아이디어 두 타입이 일련의 재선언에 의해서 원래 같은 선언에 도달하면 같은 타입으로 간주한다. 기존 타입 이름에 대한 새로운 이름은 기본적으로 같은 타입이다. 두 타입이 일련의 재선언에 의해서 원래 같은 선언에 도달하면 같은 타입으로 간주한다.

예 struct A struct B { char x; { char x; int y; int y; }; }; typedef struct A C; typedef C *P; typedef struct B *Q; tyedef struct A *R; typedef int S[10]; typedef int T[5]; typedef int Age; typedef int (*F)(int); typedef Age (*G)(Age)

6.6 타입 검사 (Type Checking)

왜 타입 검사가 필요한가? 타입 검사란 무엇인가? 실행 전에 프로그램 오류 검사 프로그램의 신뢰성 향상에 기여 프로그램이 말이 되는지 타입을 중심으로 검사하는 것 프로그램에서 타입이 올바르게 사용되고 있는지 검사 실행 전에 프로그램 오류 검사 정적 타입 검사는 프로그램 실행 전 컴파일 시간에 타입이 잘 못 사용된 오류를 검출할 수 있다. 매우 중요한 일 ! 프로그램의 신뢰성 향상에 기여 엄격한 타입 검사는 실행 중에 갑자기 죽는 프로그램 예방

타입 검사 개요 정적 타입 검사(Statically typed) 동적 타입 검사(Dynamically typed) 거의 모든 타입 검사를 컴파일 시간에 한다 Java, Pascal, C++, ML, Haskell 엄격 타입(strongly typed) 언어라고 함 동적 타입 검사(Dynamically typed) 실행 시간에 타입 검사 Lisp, Scheme 타입 검사 안 함 어떤 종류의 타입 검사도 하지 않음(어셈블리어)

타입 및 타입 검사 프로그래머는 식별자의 타입을 선언한다 타입 추론(type inference) 타입 검사 각 식(expression)의 타입을 추론한다. 타입 검사 프로그램에서 타입이 올바르게 사용되고 있는지 검사한다.

타입 규칙(Typing Rule) 정형적 표기법 타입 검사 규칙 정규식(regular expression) – 어휘분석 문맥-자유 문법(CFG) – 구분분석 타입 검사 규칙 논리적 추론 규칙(logical inference rule) “If this expression has this type and that expression has the other type, then this third expression must have another type.” “if X and Y then Z” computations.

영어를 타입 규칙으로 표현 Read “x : T” as “x has type T”. 규칙 예 If e1 has type Int and e2 has type Int, then e1+ e2 has type Int (e1 has type Int e2 has type Int)  e1+ e2 has type Int (e1 :Int  e2:Int)  e1+ e2 : Int

영어를 타입 규칙으로 표현 추론 규칙 예 (e1 :Int  e2:Int)  e1+ e2 : Int 일반적 형태 Hypothesis1  … Hypothesisn  Conclusion 추론 규칙

타입 규칙 예 정수와 + 식에 대한 타입 규칙: 식 2 + 5의 타입은 ?

타입 규칙의 의미 >는 타입 규칙에 의해서 “증명 가능함”을 의미한다. 안전한(sound) 타입 시스템 >e: T일 때마다 e의 계산된 값이 T 타입이어야 한다. 안전한 타입 규칙이 많을 수 있으나 어떤 규칙들이 다른 규칙보다 좋다 혹은 정확하다.

타입 규칙 예 상수를 위한 규칙: new T를 위한 규칙: T 타입의 객체를 생성한다. 배열 사용 a[i]를 위한 규칙 조건식을 위한 규칙 >a: array of int >i: int a[i]: int

타입 규칙 예 배정문 함수 정의 및 타입 함수 호출을 위한 타입 규칙 함수 정의: int f(String x, String y) { … } 함수의 타입 f: String  String  Int 함수 호출을 위한 타입 규칙 실매개변수 타입 = 형식 매개변수 타입 호출 결과 타입 = 함수의 f의 반환 타입

타입 검사 과정 예 (x+y)*z a[i] +i + [] x y z * int + int int int int i int array of int

예제 다음 함수의 타입은 다음 문장에 대한 타입 검사 ? int a, b, c; int max (int x, int y) { return x > y ? X : y;} 다음 문장에 대한 타입 검사 ? int a, b, c; c = c + max(a,b);

타입 검사 과정 타입 검사는 각 식 e에 대해서 e:T라는 것을 증명한다. 각 식 종류에 대해서 하나의 타입 규칙이 있다. 이 증명은 AST와 같은 모양을 갖는다. AST의 각 노드에 대해서 하나의 타입 규칙이 사용된다. 식 e의 노드에서 가정은 e의 부분식들이고 결론은 e의 타입이다. 각 식 종류에 대해서 하나의 타입 규칙이 있다. 타입 검사 과정은 AST에 대한 상향식 패스이다.

사례 연구: C 정적 타입 검사를 한다. 많은 타입 불일치에 대해 오류를 내지 않는다. 자동 타입 변환 그러나 엄격 타입 언어가 아니다 많은 타입 불일치에 대해 오류를 내지 않는다. 자동 타입 변환이 수행된다. 자동 타입 변환 char -> int -> long -> float -> double

6.7 타입 변환 (Type Conversion)

타입 변환 묵시적 변환(implicit conversion) int x = 3; … x = 2.3 + x / 2 명시적 변환(explicit conversion) x = (int) (2.3 + (double) (x /2));