Search Results for 'subranges types'

1 POSTS

  1. 2006.10.07 Type Inference와 Subrange Types (Subtypes with Range Constraints)

Pascal에는 subrange type이라는 게 있다. subrange 말이 내포하듯이 정수 타입의 변수에 범위를 주는 것인데, 다음과 같은 형태로 사용할 수 있다.

type Atype = 0..20;
     Btype = 10..20;

var a : Atype;
    b : Btype;

이 경우 변수 a는 0에서 20까지의 값을, 변수 b는 10-20까지의 값만 가질 수 있는 타입이다. 정수의 일부 범위만 사용할 수 있으므로 subrange 타입이라 불린다. Pascal의 type rule은 무척 간단한 편인데, subrange 타입이 들어가면 약간 복잡해진다.

예를 들어 a + b의 타입은 무엇일까? 직관적으로 생각해보면 a + b가 가능한 값은 10에서 40이니깐 10..40 sunbrange 타입이 되어야 할 것이다. 즉 a + b는 a의 타입도 b의 타입도 아닌 새로운 타입이 나오게 된다. 하지만 Pascal에서는 이런 type inference가 복잡하니깐 subrange 타입의 연산은 subrange type의 base type인 integer라고 하고 이 문제를 해결해 버렸다.

만약 a + b의 계산 결과를 새로운 subrange type의 변수 c에 대입(assign) 한다면 컴파일러는 어떻게 해야 할까? 이 경우 보통 dynamic check가 필요하다. 계산 결과가 subrnage type의 범위 내에 들어간다고 보장할 수 없다면 런타임에 검사를 해줘야 하기 때문이다. 물론 위의 예에서 우리가 a + b가 10에서 40을 벗어나지 않는다고 계산했던 것처럼 같은 정보를 컴파일러가 계산해 낸다면, 일부 dynamic check를 성능 향상을 위해 제거할 수 있을 것이다.

이렇게 계산한 값과 c의 subrange를 비교해서 만약 c의 값이 반드시 c의 subrange에 들어가면 dynamic check를 안전하게 제거할 수 있다. 반대로 계산한 값이 항상 c의 subrange를 벗어난다면, dynamic check를 넣는 대신에 컴파일 에러를 발생시켜야 할 것이다.

하지만 항상 이런 식으로 계산 결과의 범위를 예측할 수 있지는 않다. 다음 예제를 살펴보자.


a : integer range 0..20;
b : integer range 10..20;

function foo(i : integer) return integer is ...
...

a := b - foo(10);

이 경우에는 foo(10)이 외부 함수이므로, 이 코드만 봐서는 foo(10)의 범위가 어떻게 될지 예측하기가 어렵다. 결과적으로 b -  foo(10)이 0..20 사이에 포함될 것인지를 결정할 수 없게 된다. 따라서 컴파일러는 실제로는 필요가 없을 수도 있는 dynamic check를 넣어줘야만 한다. 만약 intraprocedural analysis를 통해서 foo(10)의 range를 계산할 수 있었다면 이런 불필요한 dynamic check를 없앨 수도 있었을 것이다.

이 케이스의 교훈은 type inference를 열심히 할수록 불필요한 런타임 오버헤드를 줄일 수 있다는 것이다. 여기서는 subrange type을 예로 들었지만, statically typed language에서도 type inference의 부재 혹은 한계로 인해 불필요한 dynamic check가 들어가 있는 경우가 많이 있다. Java의 배열 경계 검사(array bound checking)도 subrange type과 동일하다. 물론 정확한 계산 값을 얻는 것이 외부적인 요인, 혹은 계산의 복잡성으로 인해 원천적으로 불가능한 경우가 많이 있지만, type inference의 발전은 프로그램의 성능 향상을 가져올 것이다.


참고 문서
1. Programming Languages Pragmatics Michael L Scott p342-343,7.2.4 Type Inference
신고

티스토리 툴바