유형 추론

형식 추론은 형식 언어에서 표현의 유형을 자동으로 감지하는 것을 말합니다.여기에는 프로그래밍 언어 및 수학 유형 시스템뿐만 아니라 컴퓨터 과학 및 언어학의 일부 분야에서의 자연 언어도 포함됩니다.

비기술적 설명

가장 일반적인 뷰의 유형은 해당 유형의 개체에 대해 가능한 활동을 제안하고 제한하는 지정된 용도와 연관될 수 있습니다.언어의 많은 명사가 그러한 용도를 명기한다.예를 들어, 목줄이라는 단어는 워드선과 다른 용도를 나타냅니다.어떤 것을 테이블이라고 부르는 것은 그것을 땔감이라고 부르는 것과는 다른 호칭을 나타내지만, 실질적으로는 같은 것일 수도 있다.그 물질적 특성은 어떤 목적을 위해 사물을 사용할 수 있게 만들지만, 또한 특정한 명칭의 대상이기도 합니다.이것은 특히 추상적인 분야, 즉 수학과 컴퓨터 과학에서 그 소재가 마침내 비트나 공식에 불과한 경우에 해당된다.

바람직하지 않지만 실질적으로 가능한 사용을 배제하기 위해 유형의 개념을 정의하고 여러 가지 변형으로 적용합니다.수학에서 러셀의 역설은 초기 버전의 유형 이론을 촉발시켰다.프로그래밍 언어에서 전형적인 예는 "유형 오류"입니다. 예를 들어, 컴퓨터가 숫자가 아닌 값을 합산하도록 지시하는 것입니다.물질적으로는 가능하지만, 그 결과는 더 이상 의미가 없고 전체 프로세스에 치명적일 수 있습니다.

타이핑에서 표현식은 타입과 반대된다.예를 들어$,$ 4(\$displaystyle$$4{\displaystyle \mathrm{}),}$ $+$$2{\displaystyle \mathrm{}}$(\$displaystyle 2$$+$2) ${\displaystyle \mathrm{및}}$ 2$(\displaystyle$2\$cdot$ 2)는 모두 자연수의 ${\displaystyle \mathrm{유형}}$ n$(\displaystyle \mathrm${nat$})$과 다른 용어입니다.일반적으로 이 표현식 뒤에는${\displaystyle }$2 : ${\displaystyle \mathrm{n}}$a t \ $displaystyle$2 : \$mathrm${ nat$$} 와 $같은{\displaystyle \mathrm{}}$ 콜론과 그 타입이 계속됩니다.$,$ 값 2(\$displaystyle{\displaystyle }$$$2)는$$ ${\displaystyle \mathrm{t타입}}$ $(\${$nat})$입니다.이 형식은 새로운 이름을 선언할 때도 사용됩니다($예$: n${\displaystyle :}$ n: n: n$:$ n:$tisplaystyle {mathstyle}).$예를 들어 "detective decker"라는 단어로 장면에 새로운 캐릭터를 소개하는 것과 같습니다.

지정이 서서히 전개되는 이야기와는 반대로, 정식 언어의 오브젝트는 종종 처음부터 그 타입으로 정의되어야 합니다.또한 표현이 애매한 경우 의도한 용도를 명확히 하기 위해 유형이 필요할 수 있습니다.예를 들어 식$2{\displaystyle \mathrm{}}$ {$displaystyle$ 2$}$의 $유형$은$$(\$displaystyle \mathrm {nat})$이지만 유리수 또는 실수, 일반 텍스트로도 읽을 수 있습니다.

그 결과, 프로그램이나 증명은 타입에 매우 지장을 받을 수 있기 때문에, 문맥으로부터 그것들을 추론하는 것이 바람직하다.이것은, 타입이 없는 식(정의되지 않은 이름 포함)의 용도를 수집하면 가능합니다.$예$를 들어 아직 ${\displaystyle \mathrm{정의}}$되지 않은 이름n이$식n$ + 2$(\displaystyle$ n+$2$에서 사용되는 경우 n은 적어도 숫자라고 결론지을 수 있습니다.표현식과 그 문맥에서 유형을 추론하는 과정은 유형 추론입니다.

일반적으로 객체뿐만 아니라 활동에도 유형이 있으며 단순히 그 용도에 따라 도입될 수 있습니다.스타트렉의 스토리에 있어서, 그러한 미지의 활동은, 이야기의 흐름을 위해서 실행되었을 뿐, 정식으로 소개된 적이 없는 「빛난다」일 수 있다.그렇지만, 그 타입(트랜스포트)에 대해서는, 그 후에 추리할 수 있습니다.또한 오브젝트와 액티비티 모두 각 파트에서 구성할 수 있습니다.이러한 설정에서 유형 추론은 더 복잡해질 뿐만 아니라, 충돌하거나 의도하지 않은 사용을 감지하면서 합성된 장면의 모든 것에 대한 완전한 설명을 수집할 수 있기 때문에 더욱 유용합니다.

유형 확인 vs. 유형 추정

타이핑에서 표현식 E는 형식적으로 E : T로 표기된 타입 T와 반대됩니다.보통 타이핑은 일부 컨텍스트 내에서만 의미가 있습니다.여기서는 생략합니다.

이 설정에서는, 다음의 질문이 특히 중요합니다.

1. E : T? 이 경우 식 E와 유형 T가 모두 지정됩니다.E는 정말 T일까?이 시나리오는 타입 체크라고 불립니다.
2. 여기에서는 표현만 알려져 있습니다.만약 E에 대한 유형을 도출하는 방법이 있다면, 우리는 유형 추론을 달성한 것이다.
3. - T? - 반대야유형만 지정하면 해당 유형에 대한 표현식이 있습니까, 아니면 값이 없습니까?T의 예가 있나요?

단순하게 유형화된 람다 미적분은 세 문제 모두 해결이 가능합니다.좀 더 표현력이 풍부한 활자가 허용되면 상황은 그만큼 편치 않다.

프로그래밍 언어의 유형

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2020년 11월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍에 대해 알아보기)

유형은 강력한 정적 유형의 언어에서 나타나는 기능입니다.이는 일반적으로 기능성 프로그래밍 언어의 특징인 경우가 많습니다.타입 추론을 포함한 언어에는 C++11,^[1] C#(버전 3.0 이후), Chapel, Clean, Crystal, D, F#,^[2] FreeB 등이 있습니다.ASIC, Go, Haskell, Java(버전 10 이후), ^[3]Julia, Kotlin,^[4] ML, Nim, OCaml, Opa, Q#, RPython, Rust,^[5] Scala,^{[6] [7]}Swift, TypeScript,^[8] Vala,^{[9] [10]}Dart 및 Visual^[11] Basic(버전 9.0 이후).이들 중 대부분은 단순한 형태의 유형 추론을 사용한다. 힌들리-밀너 유형 시스템은 보다 완벽한 유형 추론을 제공할 수 있다.유형을 추론할 수 있는 기능은 많은 프로그래밍 작업을 자동으로 쉽게 만들어 주므로 프로그래머는 유형 확인을 허용하면서도 유형 주석을 자유롭게 생략할 수 있습니다.

일부 프로그래밍 언어에서는 모든 값이 컴파일 시 명시적으로 선언된 데이터 유형을 가지며, 런타임에 특정 식이 취할 수 있는 값을 제한합니다.저스트 인 타임 컴파일은 실행 시간과 컴파일 시간의 구분을 모호하게 합니다.단, 과거에는 값의 유형이 런타임에만 알려진 경우 이러한 언어는 동적으로 입력됩니다.다른 언어에서는 식 유형을 컴파일 시에만 알 수 있습니다.이러한 언어들은 정적으로 입력됩니다.대부분의 정적 유형 언어에서 함수 및 로컬 변수의 입력 및 출력 유형은 일반적으로 유형 주석을 통해 명시적으로 제공되어야 합니다.예를 들어, C:

인트 add_1(인트 x) {     인트 결과; /* 정수 결과 */ 선언      결과 = x + 1;     돌아가다 결과; } 

이 함수 정의의 시그니처,int add_one(int x)라고 선언합니다.add_one는 1개의 인수(정수)를 사용하여 정수를 반환하는 함수입니다. int result;로컬 변수가 이 명령어를 선언합니다.result는 정수입니다.가상 언어 지원 유형 추론에서는 대신 다음과 같이 코드가 작성될 수 있습니다.

add_1(x) {     변화하다 결과;  /* 유추형 변수 결과 */     변화하다 결과 2; /* 유추형 변수 결과 #2 */      결과 = x + 1;     결과 2 = x + 1.0;  /* 이 행은 (제안된 언어로) 작동하지 않습니다.*/     돌아가다 결과; } 

이것은 Dart 언어로 코드가 기술되는 방식과 동일하지만 아래에 설명된 몇 가지 추가 제약 조건이 적용됩니다.컴파일 시 모든 변수의 유형을 추론할 수 있습니다.위의 예에서 컴파일러는 다음과 같이 추론합니다.result그리고.x상수 이후 타입 정수를 가지다1type integer이기 때문에add_one함수입니다.int -> int. 변수result2합법적으로 사용되지 않기 때문에 유형이 없을 것입니다.

마지막 예가 쓰여진 가상 언어에서, 컴파일러는 반대로 정보가 없을 때, 다음과 같이 가정할 것이다.+는 2개의 정수를 취하여 1개의 정수를 반환합니다.(예를 들어 OCaml에서는 이렇게 동작합니다).이것으로부터, 타입인컨퍼런스서는, 타입이 다음과 같이 추론할 수 있습니다.x + 1정수입니다. 즉,result이 값은 정수이므로 반환값의 값입니다.add_one는 정수입니다.마찬가지로, 그 이후로+는 양쪽 인수가 같은 타입이어야 합니다.x정수여야 합니다.따라서add_one는 1개의 정수를 인수로 받아들입니다.

단, 다음 행에서는 result2가 10진수를 더하여 계산됩니다.1.0부동소수점 산술로 사용 시 경합을 일으킨다.x정수 표현과 부동 소수점 표현 모두에 사용됩니다.이러한 상황에 대한 올바른 유형 추론 알고리즘은 1958년부터 알려져 왔으며 1982년부터 올바른 것으로 알려져 있다.이전 추론을 다시 살펴보고 처음부터 가장 일반적인 유형(이 경우 부동소수점)을 사용합니다.그러나 이는 부정적인 영향을 미칠 수 있습니다.예를 들어 처음부터 부동소수를 사용하면 정수형으로는 존재하지 않는 정밀도 문제가 발생할 수 있습니다.

단, 이러한 상황에서는 역추적할 수 없고 대신 오류 메시지를 생성할 수 없는 퇴화형 추론 알고리즘이 자주 사용됩니다.이전 부동소수점 정밀도 문제에서 알 수 있듯이 유형 추론이 알고리즘적으로 항상 중립인 것은 아니기 때문에 이 동작이 바람직할 수 있습니다.

중간 일반 알고리즘은 result2를 부동소수점 변수로 암묵적으로 선언하고 덧셈은 암묵적으로 변환한다.x부동소수점까지.이는 콜 컨텍스트가 부동소수점 인수를 제공하지 않는 경우에 해당될 수 있습니다.이러한 상황은 유형 변환을 수반하지 않는 유형 추론과 종종 제한 없이 데이터를 다른 데이터 유형으로 강제하는 암묵적 유형 변환의 차이를 보여준다.

마지막으로, 복잡한 유형 추론 알고리즘의 중요한 단점은 결과 유형 추론 해결이 (특히 역추적 때문에) 인간에게 명백하지 않을 것이라는 것이다. 이는 코드가 주로 인간에게 이해되도록 의도되어 있기 때문에 해로울 수 있다.

최근의 저스트 인 타임 컴파일의 출현에 의해, 다양한 콜링 컨텍스트에 의해서 제공되는 인수의 타입이 컴파일시에 알려진 하이브리드 어프로치가 가능하게 되어, 같은 함수의 다수의 컴파일 버전을 생성할 수 있습니다.그런 다음 컴파일된 각 버전을 다른 유형 집합에 맞게 최적화할 수 있습니다.예를 들어 JIT 컴파일을 사용하면 add_one의 컴파일 버전이 적어도2개 있어요

정수 입력을 받아들여 암묵적 유형 변환을 사용하는 버전입니다.

부동소수점 숫자를 입력으로 받아들여 부동소수점 명령을 사용하는 버전입니다.

기술 설명

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

식 유형을 추론하기 위해 필요한 정보를 얻기 위해 컴파일러는 이 정보를 그 하위 식에 주어진 유형 주석의 집계 및 후속 축소로 수집하거나 다양한 원자 값의 유형을 암묵적으로 이해합니다(예: Bool; 42: 정수; 3.14159: Real; 등).암묵적으로 입력된 원자값에 대한 표현식의 궁극적인 축소를 인식함으로써 언어를 추론하는 유형의 컴파일러는 유형 주석 없이 프로그램을 완전히 컴파일할 수 있다.

복잡한 형태의 고차 프로그래밍과 다형성에서는 컴파일러가 항상 많은 것을 추론할 수 있는 것은 아니며, 때때로 형 주석은 명확화를 위해 필요하다.예를 들어, 다형 재귀가 있는 유형 추론은 판별할 수 없는 것으로 알려져 있다.게다가 명시적 타입 어노테이션은 컴파일러가 ^[12]추론한 것보다 더 구체적인(빠른/작은) 타입을 사용하도록 강요함으로써 코드를 최적화하기 위해 사용될 수 있다.

유형 추론을 위한 몇 가지 방법은 제약 만족도^[13] 또는 만족도 모듈로 ^[14]이론에 기초한다.

예

예를 들어, Haskell 함수는map는 목록의 각 요소에 함수를 적용하여 다음과 같이 정의할 수 있습니다.

지도 f [] = [] 지도 f (첫번째:쉬다) = f 첫번째 : 지도 f 쉬다 

에 대한 형식 추론map함수는 다음과 같이 진행됩니다. map2개의 인수의 함수이므로 그 타입은 다음과 같이 제한됩니다.a → b → c해스켈의 패턴은[]그리고.(first:rest)두 번째 인수는 목록 유형이어야 합니다.b = [d]어떤 종류에서는d첫 번째 논쟁f인수에 적용됩니다.first(타입이 필요합니다).dlist 인수의 타입에 대응하고 있습니다.f :: d → e(::일부 유형에 대해서는 "유형"을 의미합니다.e의 반환값map f마지막으로, 그 리스트는f생산하기 때문에[e].

부품을 조립하면map :: (d → e) → [d] → [e]. 유형 변수에는 특별한 것이 없기 때문에 다음과 같이 다시 레이블이 붙을 수 있습니다.

지도 :: (a → b) → [a] → [b] 

더 이상의 제약이 적용되지 않기 때문에 이 또한 가장 일반적인 유형으로 판명되었습니다.의 추정 유형으로서mapparametric polymorphic은 인수 및 결과의 유형입니다.f유추되지 않고 유형 변수로 남습니다.map는, 실제의 타입이 각 호출에 일치하고 있는 한, 다양한 타입의 기능이나 리스트에 적용할 수 있습니다.

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

형식 추론을 수행하기 위해 처음 사용된 알고리즘은 현재 비공식적으로 힌들리-밀너 알고리즘이라고 불리지만, 알고리즘은 다마스와 ^[15]밀너에게 적절히 귀속되어야 한다.

이 알고리즘의 기원은 1958년 ^{[citation needed]}해스켈 커리와 로버트 페이스가 고안한 단순형 람다 미적분의 유형 추론 알고리즘이다.1969년에 J. Roger Hindley는 이 연구를 확장했고 그들의 알고리즘이 항상 가장 일반적인 유형을 추론한다는 것을 증명했다.1978년 로빈 밀너는 ^[16]힌들리의 연구와는 독립적으로 동등한 알고리즘인 알고리즘 W를 제공하였다.1982년 Luis^[15] Damas는 마침내 Milner의 알고리즘이 완전하다는 것을 증명하고 다형 레퍼런스를 가진 시스템을 지원하도록 확장했습니다.

가장 일반적인 유형의 사용으로 인한 부작용

설계상 유형 추론, 특히 올바른(역추적) 유형 추론은 가장 일반적인 유형의 사용을 도입하지만, 일반적인 유형이 항상 알고리즘적으로 중립적이지는 않을 수 있기 때문에 다음과 같은 경우에 영향을 미칠 수 있다.

• 부동소수는 일반적인 정수형으로 간주되는 반면 부동소수는 정밀도 문제를 일으킨다.
• 다른 유형의 일반적인 유형으로 간주되는 변형/동적 유형은 다른 유형의 캐스팅 규칙과 비교를 도입합니다. 예를 들어 이러한 유형은 숫자 추가와 문자열 연결 모두에 대해 '+' 연산자를 사용하지만, 어떤 연산이 수행되는지 정적이 아닌 동적으로 결정됩니다.

자연어에 대한 유형 추론

유형 추론 알고리즘은 프로그래밍 ^[17][18][19]언어뿐만 아니라 자연 언어도 분석하기 위해 사용되어 왔습니다.유형 추론 알고리즘은 자연어를 ^[22]위한 일부 문법 유도^[20][21] 및 제약 기반 문법 시스템에서도 사용됩니다.

레퍼런스

외부 링크

• Roger Hindley의 아카이브된 이메일 메시지 유형 추론의 이력을 설명합니다.
• Michael Schwartzbach의 Polymorphic Type Inference는 Polymorphic Type 추론의 개요를 제공한다.
• Luca Cardelli에 의한 기본적인 타입 체크 페이퍼, 알고리즘을 설명하고 Modula-2에서의 실장을 포함한다.
• Andrew Forrest에 의한 Scala에서의 힌들리 밀너 유형 추론 구현(2009년 7월 30일 회수)
• Nikita Borisov가 Wayback Machine에 Hindley-Milner를 Perl 5에 구현(2007년 2월 18일 아카이브 완료)
• 힌들리 밀너가 뭐죠? (그리고 왜 멋있어?)힌들리 밀너 설명, 스칼라 예시