상위 질문
타임라인
채팅
관점

자료형 추론

위키백과, 무료 백과사전

Remove ads

자료형 추론(資料型推論, Type inference) 또는 자료형 재구성(type reconstruction)[1](pp. 320)형식 언어에서 식의 자료형을 자동으로 감지하는 것을 의미한다. 여기에는 프로그래밍 언어와 수학적 자료형 체계뿐만 아니라 컴퓨터 과학언어학의 일부 분야에서 자연어도 포함된다.

자료형 가능성(Typeability)은 때때로 자료형 추론과 거의 동의어로 사용되지만, 일부 저자는 예/아니오 답변을 가지는 결정 문제로서의 자료형 가능성과 항에 대한 실제 자료형을 계산하는 자료형 추론을 구별한다.[2]

비기술적 설명

요약
관점

유형화된 언어에서 용어의 자료형은 해당 언어에서 용어가 사용될 수 있는 방식과 사용될 수 없는 방식을 결정한다. 예를 들어, 영어와 "노래하다 _"라는 구문에서 빈칸을 채울 수 있는 용어를 생각해 보자. "노래"라는 용어는 노래할 수 있는 자료형이므로 빈칸에 넣어 의미 있는 구문인 "노래를 부르다"를 형성할 수 있다. 반면에 "친구"라는 용어는 노래할 수 있는 자료형이 아니므로 "친구를 노래하다"는 무의미하다. 기껏해야 은유일 수 있으며, 자료형 규칙을 구부리는 것은 시적 언어의 특징이다.

용어의 자료형은 해당 용어가 포함된 연산의 해석에도 영향을 미칠 수 있다. 예를 들어, "노래"는 구성 가능한 자료형이므로 "노래를 쓰다"라는 구문에서 생성되는 것으로 해석한다. 반면에 "친구"는 수령자 자료형이므로 "친구에게 쓰다"라는 구문에서 받는 사람으로 해석한다. 일반적인 언어에서 "노래를 쓰다"가 노래에 편지를 보내는 것을 의미하거나 "친구에게 쓰다"가 종이에 친구를 스케치하는 것을 의미한다면 우리는 놀랄 것이다.

서로 다른 자료형을 가진 용어라도 실질적으로 동일한 것을 지칭할 수 있다. 예를 들어, "빨랫줄을 걸다"는 그것을 사용하는 것으로 해석하지만, "목줄을 걸다"는 그것을 치우는 것으로 해석할 수 있다. 비록 문맥상 "빨랫줄"과 "목줄"이 다른 시점에 같은 밧줄을 지칭할 수 있더라도 말이다.

자료형은 종종 개체가 너무 일반적으로 고려되는 것을 방지하기 위해 사용된다. 예를 들어, 자료형 시스템이 모든 숫자를 동일하게 취급한다면, 프로그래머가 실수로 `4`가 "4초"를 의미해야 하지만 "4미터"로 해석되는 코드를 작성하면 런타임에 문제가 발생할 때까지 실수에 대한 경고를 받지 못할 것이다. 측정 단위를 자료형 시스템에 통합함으로써 이러한 실수를 훨씬 일찍 감지할 수 있다. 다른 예로, 러셀의 역설은 모든 것이 집합의 원소가 될 수 있고 모든 술어가 집합을 정의할 수 있을 때 발생하지만, 더 신중한 자료형 지정은 역설을 해결하는 여러 가지 방법을 제공한다. 사실 러셀의 역설은 자료형 이론의 초기 버전을 촉발시켰다.

용어가 자료형을 얻는 몇 가지 방법이 있다:

  • 자료형은 구절 외부의 어딘가에서 제공될 수 있다. 예를 들어, 화자가 영어로 "a song"이라고 언급할 때, 일반적으로 청자에게 "a song"이 노래할 수 있고 구성할 수 있다는 것을 말할 필요가 없다. 그 정보는 공유된 배경 지식의 일부이다.
  • 자료형은 명시적으로 선언될 수 있다. 예를 들어, 프로그래머는 코드에 `delay: seconds := 4`와 같은 문을 작성할 수 있다. 여기서 콜론은 용어에 자료형을 표시하는 관습적인 수학적 기호이다. 즉, 이 문은 `delay`를 값 `4`로 설정할 뿐만 아니라, `delay: seconds` 부분은 `delay`의 자료형이 초 단위의 시간량임을 나타낸다.
  • 자료형은 문맥에서 추론될 수 있다. 예를 들어, "I bought it for a song"이라는 구문에서 "a song"이라는 용어에 "노래할 수 있는" 및 "구성 가능한"과 같은 자료형을 부여하려고 하면 무의미해지는 반면, "통화량"이라는 자료형은 작동한다는 것을 알 수 있다. 따라서 우리는 굳이 들을 필요 없이 여기에서 "song"이 영어 관용구인 "for a song"에서처럼 "거의 아무것도 아님"을 의미하며, "가사가 있는 음악 작품"을 의미하지 않는다고 결론 내린다.

특히 프로그래밍 언어에서는 컴퓨터에 사용할 수 있는 공유된 배경 지식이 많지 않을 수 있다. 명시적으로 자료형이 지정된 언어에서는 대부분의 자료형을 명시적으로 선언해야 한다는 것을 의미한다. 자료형 추론은 이러한 부담을 덜어주어, 컴퓨터가 문맥에서 추론할 수 있어야 하는 자료형을 저자가 선언하지 않아도 되게 한다.

Remove ads

자료형 검사 대 자료형 추론

자료형 지정에서 표현식 E는 자료형 T와 대립되며, 형식적으로 E : T로 작성된다. 일반적으로 자료형 지정은 어떤 맥락 내에서만 의미가 있으며, 여기서는 생략한다.

이러한 설정에서 다음 질문들이 특히 중요하다:

  1. E : T? 이 경우 표현식 E와 자료형 T가 모두 주어진다. 이제 E가 정말 T인가? 이 시나리오는 자료형 검사로 알려져 있다.
  2. E : _? 여기서는 표현식만 알려져 있다. E에 대한 자료형을 파생시킬 방법이 있다면 자료형 추론을 완료한 것이다.
  3. _ : T? 반대의 경우이다. 자료형만 주어졌을 때, 그것에 대한 어떤 표현식이 있는가 아니면 자료형에 값이 없는가? T의 어떤 예시가 있는가? 이것은 자료형 거주성으로 알려져 있다.

단순형 람다 대수의 경우, 세 가지 질문 모두 결정가능하다. 그러나 더 표현력이 뛰어난 자료형이 허용될 때는 상황이 그리 편안하지 않다.

Remove ads

프로그래밍 언어의 자료형

요약
관점

자료형은 일부 강력한 정적 자료형 지정 언어에 존재하는 기능이다. 일반적으로 함수형 프로그래밍 언어의 특징인 경우가 많다. 자료형 추론을 포함하는 언어로는 C (C23부터),[3] C++ (C++11부터),[4] C# (버전 3.0부터), 채플, 클린, 크리스탈, D, 다트,[5] F#,[6] 프리베이직, Go, 하스켈, 자바 (버전 10부터), 줄리아,[7] 코틀린,[8] ML, , OCaml, 오파, Q#, RPython, 러스트,[9] 스칼라,[10] 스위프트,[11] 타입스크립트,[12] 발라,[13] Zig, 그리고 비주얼 베이직[14] (버전 9.0부터) 등이 있다. 대부분의 언어는 단순한 형태의 자료형 추론을 사용한다. 힌들리-밀너 자료형 체계는 더 완전한 자료형 추론을 제공할 수 있다. 자료형을 자동으로 추론하는 기능은 많은 프로그래밍 작업을 더 쉽게 만들며, 프로그래머가 자료형 주석을 생략하면서도 자료형 검사를 허용한다.

일부 프로그래밍 언어에서는 모든 값이 컴파일 타임에 명시적으로 선언된 자료형을 가지며, 특정 표현식이 런타임에 취할 수 있는 값을 제한한다. 점점 더 JIT 컴파일은 런타임과 컴파일 타임의 구분을 모호하게 만든다. 그러나 역사적으로 값의 자료형이 런타임에만 알려져 있다면 이러한 언어는 동적 자료형이다. 다른 언어에서는 표현식의 자료형이 컴파일 타임에만 알려져 있다. 이러한 언어는 정적 자료형이다. 대부분의 정적 자료형 언어에서는 함수의 입력 및 출력 자료형과 지역 변수의 자료형을 일반적으로 자료형 주석으로 명시적으로 제공해야 한다. 예를 들어, ANSI C에서는 다음과 같다:

int add_one(int x) {
    int result; /* 정수형 결과 선언 */

    result = x + 1;
    return result;
}

이 함수 정의의 시그니처인 `int add_one(int x)`는 `add_one`이 하나의 인수인 정수형을 취하고 정수를 반환하는 함수임을 선언한다. `int result;`는 지역 변수 `result`가 정수임을 선언한다. 자료형 추론을 지원하는 가상의 언어에서는 코드가 대신 다음과 같이 작성될 수 있다:

add_one(x) {
    var result;  /* 추론된 자료형 변수 result */
    var result2; /* 추론된 자료형 변수 result #2 */

    result = x + 1;
    result2 = x + 1.0;  /* 이 줄은 (제안된 언어에서) 작동하지 않는다 */
    return result;
}

이것은 언어 다트에서 코드가 작성되는 방식과 동일하지만, 아래에 설명된 몇 가지 추가 제약이 적용된다. 컴파일 타임에 모든 변수의 자료형을 추론하는 것이 가능하다. 위 예제에서 컴파일러는 상수 `1`이 정수 자료형이므로 `result`와 `x`가 정수 자료형임을 추론할 것이며, 따라서 `add_one`은 `int -> int` 함수가 된다. 변수 `result2`는 유효한 방식으로 사용되지 않으므로 자료형이 없을 것이다.

마지막 예제가 작성된 가상의 언어에서 컴파일러는 반대되는 정보가 없는 한 `+`가 두 개의 정수를 받아 하나의 정수를 반환한다고 가정할 것이다. (이것은 예를 들어 OCaml에서 작동하는 방식이다.) 여기에서 자료형 추론기는 `x + 1`의 자료형이 정수임을 추론할 수 있으며, 이는 `result`가 정수이고 따라서 `add_one`의 반환 값이 정수임을 의미한다. 마찬가지로 `+`는 두 인수가 동일한 자료형이어야 하므로 `x`는 정수여야 하며, 따라서 `add_one`은 하나의 정수를 인수로 받는다.

그러나 다음 줄에서 result2는 십진수 `1.0`을 부동소수점 연산으로 더하여 계산되는데, 이는 정수 및 부동소수점 표현식 모두에 `x`를 사용하는 데 충돌을 일으킨다. 이러한 상황에 대한 올바른 자료형 추론 알고리즘은 1958년부터 알려져 있었고, 1982년부터 정확하다는 것이 알려져 있었다. 이 알고리즘은 이전 추론을 재검토하고 처음부터 가장 일반적인 자료형을 사용한다. 이 경우 부동소수점 자료형이다. 그러나 이는 처음부터 부동소수점을 사용하면 정수 자료형에서는 존재하지 않았을 정밀도 문제를 야기할 수 있다는 등 해로운 영향을 미칠 수 있다.

그러나 종종 이러한 상황에서 역추적할 수 없고 대신 오류 메시지를 생성하는 퇴행적 자료형 추론 알고리즘이 사용된다. 자료형 추론이 항상 알고리즘적으로 중립적이지 않을 수 있기 때문에 이 동작이 더 바람직할 수 있다. 이는 이전의 부동소수점 정밀도 문제에서 알 수 있다.

중간 정도의 일반성을 가진 알고리즘은 result2를 부동소수점 변수로 암시적으로 선언하고, 덧셈은 `x`를 부동소수점으로 암시적으로 변환한다. 이는 호출 컨텍스트에서 부동소수점 인수를 제공하지 않는 경우 올바를 수 있다. 이러한 상황은 형 변환을 포함하지 않는 자료형 추론과, 종종 제한 없이 데이터를 다른 자료형으로 강제 변환하는 암시적 형 변환 간의 차이를 보여준다.

마지막으로, 복잡한 자료형 추론 알고리즘의 중요한 단점은 결과적인 자료형 추론 해결책이 사람에게 명확하지 않을 수 있다는 점이다(특히 역추적 때문에). 이는 코드가 주로 사람이 이해할 수 있도록 의도되었기 때문에 해로울 수 있다.

최근 JIT 컴파일의 등장으로 다양한 호출 컨텍스트에서 제공되는 인수의 자료형이 컴파일 타임에 알려져 동일한 함수의 많은 컴파일된 버전을 생성할 수 있는 하이브리드 접근 방식이 가능해졌다. 각 컴파일된 버전은 서로 다른 자료형 세트에 최적화될 수 있다. 예를 들어, JIT 컴파일은 add_one의 컴파일된 버전을 최소 두 개 이상 가질 수 있도록 한다:

  • 정수 입력을 받아 암시적 자료형 변환을 사용하는 버전.
  • 부동소수점 숫자를 입력으로 받아 부동소수점 명령을 전반적으로 사용하는 버전.
Remove ads

기술적 설명

자료형 추론은 컴파일 시점에 표현식의 자료형을 부분적으로 또는 완전히 자동으로 추론하는 기능이다. 컴파일러는 명시적인 자료형 주석이 주어지지 않아도 변수의 자료형이나 함수의 자료형 시그니처를 종종 추론할 수 있다. 자료형 추론 시스템이 충분히 강력하거나 프로그램이나 언어가 충분히 단순하다면 많은 경우 프로그램에서 자료형 주석을 완전히 생략하는 것이 가능하다.

표현식의 자료형을 추론하는 데 필요한 정보를 얻기 위해 컴파일러는 하위 표현식에 주어진 자료형 주석을 집계하고 후속적으로 축소하거나, 다양한 원자 값의 자료형(예: true : Bool; 42 : Integer; 3.14159 : Real; 등)을 암시적으로 이해함으로써 이 정보를 수집한다. 컴파일러는 표현식이 암시적으로 자료형이 지정된 원자 값으로 최종적으로 축소되는 것을 인식함으로써 자료형 추론 언어용 컴파일러가 자료형 주석 없이 프로그램을 완전히 컴파일할 수 있다.

고차 프로그래밍다형성의 복잡한 형태에서는 컴파일러가 그만큼 많이 추론하는 것이 항상 가능하지 않으며, 모호성을 해소하기 위해 때때로 자료형 주석이 필요하다. 예를 들어, 다형적 재귀를 사용한 자료형 추론은 결정 불가능한 것으로 알려져 있다. 또한 명시적인 자료형 주석은 컴파일러가 추론했던 것보다 더 구체적인(더 빠르거나 더 작은) 자료형을 사용하도록 강제함으로써 코드를 최적화하는 데 사용될 수 있다.[15]

일부 자료형 추론 방법은 제약 충족[16] 또는 이론 모듈로 만족 가능성을 기반으로 한다.[17]

Remove ads

고수준 예제

예를 들어, 하스켈 함수 map은 리스트의 각 요소에 함수를 적용하며 다음과 같이 정의될 수 있다.

map f [] = []
map f (first:rest) = f first : map f rest

(하스켈에서 :Cons를 나타내며, 머리 요소와 리스트 꼬리를 더 큰 리스트로 구조화하거나 비어있지 않은 리스트를 머리 요소와 꼬리로 분해한다. 이는 수학이나 이 문서의 다른 곳에서처럼 "자료형이 ~이다"를 의미하지 않는다. 하스켈에서는 "자료형이 ~이다" 연산자를 대신 ::로 작성한다.)

map 함수에 대한 자료형 추론은 다음과 같이 진행된다. map은 두 개의 인수를 받는 함수이므로 자료형은 a -> b -> c 형태여야 한다. 하스켈에서 [](first:rest) 패턴은 항상 리스트와 일치하므로 두 번째 인수는 리스트 자료형이어야 한다: 일부 자료형 d에 대해 b = [d]. 첫 번째 인수 ffirst 인수에 적용되며, 이 인수는 리스트 인수의 자료형에 해당하는 자료형 d를 가져야 하므로 일부 자료형 e에 대해 f :: d -> e (::는 "자료형이 ~이다"를 의미한다). 마지막으로 map f의 반환 값은 f가 생성하는 것의 리스트이므로 [e]이다.

이러한 부분을 조합하면 map :: (d -> e) -> [d] -> [e]가 된다. 자료형 변수에 특별한 것은 없으므로 다음과 같이 재지정할 수 있다.

map :: (a -> b) -> [a] -> [b]

추가 제약이 적용되지 않으므로 이것이 가장 일반적인 자료형임이 밝혀졌다. map의 추론된 자료형은 매개변수적으로 다형성이므로, f의 인수 및 결과의 자료형은 추론되지 않고 자료형 변수로 남는다. 따라서 map은 호출할 때마다 실제 자료형이 일치하는 한 다양한 자료형의 함수와 리스트에 적용될 수 있다.

Remove ads

상세 예제

요약
관점

컴파일러와 같은 프로그램이 사용하는 알고리즘은 위에 비공식적으로 구조화된 추론과 동등하지만, 약간 더 장황하고 체계적이다. 정확한 세부 사항은 선택된 추론 알고리즘에 따라 다르지만(가장 잘 알려진 알고리즘은 다음 섹션 참조), 아래 예제는 일반적인 아이디어를 제공한다. 다시 map의 정의로 시작한다.

map f [] = []
map f (first:rest) = f first : map f rest

(다시 말하지만, 여기서 :는 하스켈 리스트 생성자이며, 하스켈에서 ::로 표기되는 "자료형이 ~이다" 연산자가 아님을 기억하라.)

먼저, 각 개별 항에 대해 새로운 자료형 변수를 만든다:

  • α는 우리가 추론하고자 하는 map의 자료형을 나타낸다.
  • β는 첫 번째 방정식에서 f의 자료형을 나타낸다.
  • [γ]는 첫 번째 방정식 왼쪽의 []의 자료형을 나타낸다.
  • [δ]는 첫 번째 방정식 오른쪽의 []의 자료형을 나타낸다.
  • ε는 두 번째 방정식에서 f의 자료형을 나타낸다.
  • ζ -> [ζ] -> [ζ]는 첫 번째 방정식 왼쪽의 :의 자료형을 나타낸다. (이 패턴은 정의에서 알려져 있다.)
  • ηfirst의 자료형을 나타낸다.
  • θrest의 자료형을 나타낸다.
  • ι -> [ι] -> [ι]는 첫 번째 방정식 오른쪽의 :의 자료형을 나타낸다.

그런 다음 이러한 항으로 구성된 하위 표현식에 대해 새로운 자료형 변수를 만들고, 호출되는 함수의 자료형을 그에 따라 제한한다:

  • κmap f []의 자료형을 나타낸다. 우리는 `α ~ β -> [γ] -> κ`라고 결론을 내린다. 여기서 "유사한" 기호 `~`는 "통합된다"를 의미한다. 즉, `map`의 자료형인 `α`는 `β`와 `γ`의 리스트를 받아 `κ`를 반환하는 함수의 자료형과 호환되어야 한다는 것이다.
  • λ(first:rest)의 자료형을 나타낸다. 우리는 `ζ -> [ζ] -> [ζ] ~ η -> θ -> λ`라고 결론을 내린다.
  • μmap f (first:rest)의 자료형을 나타낸다. 우리는 `α ~ ε -> λ -> μ`라고 결론을 내린다.
  • νf first의 자료형을 나타낸다. 우리는 `ε ~ η -> ν`라고 결론을 내린다.
  • ξmap f rest의 자료형을 나타낸다. 우리는 `α ~ ε -> θ -> ξ`라고 결론을 내린다.
  • οf first : map f rest의 자료형을 나타낸다. 우리는 `ι -> [ι] -> [ι] ~ ν -> ξ -> ο`라고 결론을 내린다.

또한 각 방정식의 왼쪽과 오른쪽이 서로 통합되도록 제한한다: `κ ~ [δ]` 및 `μ ~ ο`. 통합 시스템을 모두 풀면 다음과 같다:

α ~ β -> [γ] -> κ
ζ -> [ζ] -> [ζ] ~ η -> θ -> λ
α ~ ε -> λ -> μ
ε ~ η -> ν
α ~ ε -> θ -> ξ
ι -> [ι] -> [ι] ~ ν -> ξ -> ο
κ ~ [δ]
μ ~ ο

그런 다음 더 이상 변수를 제거할 수 없을 때까지 대입한다. 정확한 순서는 중요하지 않다. 코드가 자료형 검사를 통과하면 어떤 순서든 동일한 최종 형식으로 이어진다. `ο`를 `μ`로, `[δ]`를 `κ`로 대입하는 것부터 시작해 보자:

α ~ β -> [γ] -> [δ]
ζ -> [ζ] -> [ζ] ~ η -> θ -> λ
α ~ ε -> λ -> ο
ε ~ η -> ν
α ~ ε -> θ -> ξ
ι -> [ι] -> [ι] ~ ν -> ξ -> ο

`ζ`를 `η`로, `[ζ]`를 `θ`와 `λ`로, `ι`를 `ν`로, `[ι]`를 `ξ`와 `ο`로 대입한다. · -> ·와 같은 자료형 생성자는 인수에 대해 역변환 가능하므로 이 모든 대입이 가능하다:

α ~ β -> [γ] -> [δ]
α ~ ε -> [ζ] -> [ι]
ε ~ ζ -> ι

`ε`에 `ζ -> ι`를, `α`에 `β -> [γ] -> [δ]`를 대입하고, 마지막에 `α`를 복구할 수 있도록 두 번째 제약을 유지한다.

α ~ (ζ -> ι) -> [ζ] -> [ι]
β -> [γ] -> [δ] ~ (ζ -> ι) -> [ζ] -> [ι]

그리고 마침내 [·]와 같은 자료형 생성자는 역변환 가능하므로 `β`에 `(ζ -> ι)`를, `γ`에 `ζ`를, `δ`에 `ι`를 대입하면 두 번째 제약에 특정한 모든 변수가 제거된다.

α ~ (ζ -> ι) -> [ζ] -> [ι]

더 이상 대입할 수 없으며, 자료형을 재지정하면 map :: (a -> b) -> [a] -> [b]가 된다. 이는 이 세부 사항에 들어가지 않고 찾았던 것과 동일하다.

Remove ads

힌들리-밀너 자료형 추론 알고리즘

자료형 추론을 수행하는 데 처음 사용된 알고리즘은 현재 비공식적으로 힌들리-밀너 알고리즘이라고 불리지만, 이 알고리즘은 다마스와 밀너에게 제대로 귀속되어야 한다.[18] 또한 전통적으로 자료형 재구성이라고도 불린다.[1](pp. 320) 항이 힌들리-밀너 자료형 지정 규칙에 따라 올바르게 자료형이 지정되면 규칙은 해당 항에 대한 주된 자료형 지정을 생성한다. 이 주된 자료형 지정을 찾는 과정이 "재구성" 과정이다.

이 알고리즘의 기원은 1958년 해스켈 커리로버트 페이스가 고안한 단순형 람다 대수의 자료형 추론 알고리즘이다. 1969년 J. 로저 힌들리는 이 작업을 확장하여 그들의 알고리즘이 항상 가장 일반적인 자료형을 추론한다는 것을 증명했다. 1978년 로빈 밀너[19] 힌들리의 작업과는 독립적으로 동등한 알고리즘인 알고리즘 W를 제공했다. 1982년 루이스 다마스[18]는 마침내 밀너의 알고리즘이 완전함을 증명하고 다형 참조를 지원하는 시스템으로 확장했다.

Remove ads

가장 일반적인 자료형 사용의 부작용

설계상 자료형 추론은 적절한 가장 일반적인 자료형을 추론한다. 그러나 많은 언어, 특히 오래된 프로그래밍 언어는 약간 불완전한 자료형 시스템을 가지고 있어 더 일반적인 자료형을 사용하는 것이 항상 알고리즘적으로 중립적이지 않을 수 있다. 일반적인 사례는 다음과 같다:

  • 부동소수점 자료형이 정수 자료형의 일반화로 간주되는 경우. 실제로 부동소수점 연산은 정수와 다른 정밀도 및 오버플로 문제가 있다.
  • 변형/동적 자료형이 연산자 오버로드 선택에 영향을 미치는 경우 다른 자료형의 일반화로 간주되는 경우. 예를 들어, `+` 연산자는 정수를 더할 수 있지만, 해당 변형이 정수를 담고 있더라도 변형을 문자열로 연결할 수 있다.

자연어 자료형 추론

자료형 추론 알고리즘은 프로그래밍 언어뿐만 아니라 자연어를 분석하는 데에도 사용되었다.[20][21][22] 자료형 추론 알고리즘은 일부 문법 귀납[23][24] 및 자연어용 제약 기반 문법 시스템에도 사용된다.[25]

각주

외부 링크

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads