프로그래밍언어론 Chapter 6 타입시스템 나는 발생 가능한 오류의 수를 최소화하고

Presentation on theme: "프로그래밍언어론 Chapter 6 타입시스템 나는 발생 가능한 오류의 수를 최소화하고"— Presentation transcript:

1 프로그래밍언어론 Chapter 6 타입시스템 나는 발생 가능한 오류의 수를 최소화하고
발생하더라도 컴파일 시간에 안전하게 감지할 수 있도록 하는 프로그래밍 표기법을 설계할 필요성을 마침내 가지게 되었다. -토니 호어(C.A.R Hoare)

2 목차 6.1 Clite를 위한 타입시스템 6.2 자동 타입 변환 6.3 Clite 타입시스템의 정형화

3 Motivation: 타입 오류의 감지 컴파일 시간이나 실행 시간에 타입 오류를 감지하는 것을 타입 검사라고 한다.
컴파일 시간이나 실행 시간에 타입 오류를 감지하는 것을 타입 검사라고 한다. 타입오류는 프로그램에서 빈번하게 발생한다. 타입오류는 EBNF로 방지하거나 감지할 수 없다. 감지되지 않은 타입오류는 심각한 실행시간 오류를 일으킨다. 타입 시스템은 타입오류가 발생하기 전에 이를 식별하는 것이다.

4 6.1 CLITE를 위한 타입 시스템 정적 바인딩 단일 함수: main 단일 유효범위: 유효범위 중첩이나 전역변수가 없음.
단일 유효범위: 유효범위 중첩이나 전역변수가 없음. 이름 풀이 오류가 컴파일 시간에 감지됨 선언된 변수는 유일한 명칭을 가져야 한다. 명칭은 키워드가 아니어야 한다.(구문적으로 강제됨) 참조되는 변수는 선언되어 있어야 한다.

5 Clite 예제 프로그램(Fig 6.1) // 정수 n의 계승을 계산하는 함수 void main ( ) {
int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; }

6 타입 시스템의 설계 자연어로 작성된 규칙 집합 V 정적 타입 검사를 용이하게 함. 규칙에 위배되면 예외를 발생하도록 구현됨.
결과값은 true 또는 false 추상 구문을 기반함. 수학 함수로 나타내면: V: AbstractSyntaxClass → Boolean 정적 타입 검사를 용이하게 함. 규칙에 위배되면 예외를 발생하도록 구현됨.

7 타입 규칙 6.1 참조되는 모든 변수는 선언되어 있어야 한다. 타입환경(타입맵)은 순서쌍 집합이다:
E.g., {<n, int>, <i, int>, <result, int>} 해쉬 테이블로 구현할 수 있다. 함수 typing 은 타입 환경을 생성한다. 함수 typeOf 은 변수의 타입을 검색한다: typeOf(id) = type

8 함수 typing은 타입 환경을 생성한다: public static TypeMap typing (Declarations d) { TypeMap map = new TypeMap( ); for (Declaration di : d) { map.put (di.v, di.t); } return map;

9 Type Rule 6.2 모든 변수는 유일한 명칭을 가져야 한다.
public static void V (Declarations d) { for (int i=0; i<d.size() - 1; i++) for (int j=i+1; j<d.size(); j++) { Declaration di = d.get(i); Declaration dj = d.get(j); check( ! (di.v.equals(dj.v)), "duplicate declaration: " + dj.v); }

10 타입규칙 6.2 예제 // compute the factorial of integer n void main ( ) {
int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; } 이것들이 유일해야 한다

11 타입 규칙 6.3 프로그램은 다음을 만족할 때 타당하다: 선언부분이 타당하고
블럭부분이 선언부분에 대한 타입 환경에 의해 타당함. public static void V (Program p) { V (p.decpart); V (p.body, typing (p.decpart)); }

12 타입규칙 6.3 예제 // 정수 n의 계승을 구하는 함수 void main ( ) { int n, i, result;
while (i < n) { i = i + 1; result = result * i; } 이것들이 타당해야 함.

13 타입 규칙 6.4 문장은 다음에 의해 타당하다: Skip 문은 항상 타당하다.
Assignment 는 다음을 만족할 때 타당하다: 변수 Variable 이 선언되었다. 수식 Expression 이 타당하다. 변수 Variable 의 타입이 float이면 수식 Expression 의 타입은 float 이거나 int 이어야 한다. 변수 Variable 의 타입이 int이면 수식 Expression 의 타입은 int 이거나 char 이어야 한다. 그 외에는 변수 Variable 는 수식 Expression와 같은 타입이어야 한다.

14 타입 규칙 6.4 (계속) 조건문 Conditional 은 다음을 만족할 때 타당하다:
조건식 Expression 이 타당하고 bool 타입을 가진다. then 부분과 else 부분의 Statements 가 타당하다. 루프문 Loop 은 다음을 만족할 때 타당하다: 몸체 문장이 타당하다. 블록 Block은 내부의 모든 문장이 타당하면 타당하다.

15 타입규칙 6.4 예제 // 정수 n의 계승을 구하는 함수 void main ( ) { int n, i, result;
while (i < n) { i = i + 1; result = result * i; } 이 저장문은 타당하다 왜냐면: n 이 선언되어 있고, 8 이 타당한 수식이며, 8의 타입이 int 또는 char이다. (n 이 int 타입이기 때문에).

16 타입규칙 6.4 예제 // 정수 n의 계승을 구하는 함수 void main ( ) { int n, i, result;
while (i < n) { i = i + 1; result = result * i; } 이 루프는 타당하다: i < n 이 타당하고, i < n 의 타입이 bool 이며, 루프 몸체가 타당하다.

17 타입 규칙 6.5 수식은 다음에 의해 타당하다: 값 Value 는 무조건 타당하다.
변수 Variable 는 이것이 타입환경에 나올 때 타당하다. 이항 수식 Binary 은 다음이 만족할 때 타당하다: 수식 term1 과 term2 이 타당하다. 연산자 op 가 산술연산이면 피연산자 수식은 모두 int 이거나 float 이어야 한다. 연산자 op 가 관계연산이면 피연산자 수식은 같은 타입이어야 한다. 연산자 op 가 논리연산이면 피연산자 수식은 모두 bool이어야 한다. 단항 수식 Unary 는 다음을 만족할 때 타당하다: 수식 term 이 타당하다. …

18 타입 규칙 6.6 수식 e 의 타입은 다음과 같이 결정된다: 수식 e 가 값이면 그 값의 타입
수식 e 가 이항 연산 op term1 term2 일때 op 가 산술연산자이면 term1 과 term2의 (공통)타입 op 가 관계연산자이거나 논리연산자이면 bool 타입 수식 e 가 단항 연산 op term 일때 op 가 ! 이면 bool 타입 …

19 타입규칙 6.5 와 6.6 예제 // 정수 n의 계승을 구하는 함수 void main ( ) {
타입규칙 6.5 와 6.6 예제 // 정수 n의 계승을 구하는 함수 void main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; } 이 수식은 타당하다. op 는 산술연산자 (*) 이고 i 와 result의 타입이 int이다. 따라서 결과 타입은 int 이다.

20 6.2 자동 타입 변환 Clite의 저장문은 상위타입으로의 자동 타입 변환을 제공한다.
6.2 자동 타입 변환 Clite의 저장문은 상위타입으로의 자동 타입 변환을 제공한다. 추상 구문 트리의 필요한 곳에 수동 타입 변환 함수를 자동으로 삽입할 수 있다. 저장문의 좌변 변수 타입과 우변 수식 타입에 따라서 삽입할 변환 함수를 결정할 수 있다.

21 예제: int 타입을 float 타입에 저장하기
다음의 저장문을 생각해보자. f = i - int(c); (f, i, c는 각각 float, int, char 변수이다.) 추상구문트리는 다음과 같다.

22 예제 (계속) 따라서 트리에 상위타입으로의 타입변환함수가 삽입된다.
따라서 트리에 상위타입으로의 타입변환함수가 삽입된다. 여기서, c2i 는 char에서 int로의 변환함수이고 i2f 는 int 에서 float으로의 변환함수이다. Note: c2i 는 프로그램에서 연산자 int()에 의해서 주어진 변환함수이다.

23 6.3 Clite 타입시스템의 정형화 타입환경: 타입규칙 6.1 (타입환경) 타입규칙 6.2 (선언부 타당성)

24 Clite 프로그램의 타당성 타입규칙 6.3

25 문장의 타당성 타입규칙 6.4, 저장문에 대한 간략화된 규칙

26 수식의 타당성 타입규칙 6.5, 이항연산식과 단항연산식은 부분적으로 생략됨

27 수식의 타입 결정하기 타입규칙 6.6, 부분적으로 생략됨