CS101 학생이 이해할 수있는 방식으로 Damas-Milner 유형 추론을 설명하십시오.

Question

Hindley-Milner는 잘 알려진 기능적 프로그래밍 언어의 유형 시스템의 기초 인 유형 시스템입니다. Damas-Milner는 Hindley-Milner 유형 시스템에서 유형을 유도하는 알고리즘입니다.

위키 백과 내가 알 수있는 한 "통일"라는 단어에 해당하는 알고리즘에 대한 설명을 제공합니다. 그게 전부입니까? 그렇다면 흥미로운 부분은 유형 시스템 자체가 유형 추론 시스템이 아니라는 것을 의미합니다.

Damas-Milner가 통일 이상이라면 간단한 예제와 이상적으로는 일부 코드를 포함하는 Damas-Milner에 대한 설명을 원합니다.

또한이 알고리즘은 종종 유형의 추론을하는 것으로 알려져 있습니다. 실제로 추론 시스템입니까? 나는 그것이 유형을 추론한다고 생각했다.

관련 질문 :

• Hindley Miller는 무엇입니까?
• 통일 문제에 대한 유도

Answer 1

Damas Milner는 통일의 구조적 사용 일뿐입니다.

람다 표현식으로 되풀이되면 새로운 변수 이름을 구성합니다. 하위 기간 동안 주어진 유형이 필요한 방식으로 사용 된 변수를 찾으면 해당 변수의 통일과 해당 유형의 통일을 기록합니다. 개별 변수가 int와 a-> b의 함수라고 말하는 것과 같이 말이되지 않는 두 가지 유형을 통일하려고한다면 나쁜 일을 해준 것에 대해 소리칩니다.

또한이 알고리즘은 종종 유형의 추론을하는 것으로 알려져 있습니다. 실제로 추론 시스템입니까? 나는 그것이 유형을 추론한다고 생각했다.

유형을 추론하는 것은 유형의 추론입니다. 주어진 항에 대해 유형 주석이 유효한 것을 확인하는 것이 유형 확인입니다. 그들은 다른 문제입니다.

그렇다면 흥미로운 부분은 유형 시스템 자체가 유형 추론 시스템이 아니라는 것을 의미합니다.

일반적으로 Hindley-Milner 스타일 유형 시스템은 CUSP에서 균형을 이룹니다. 훨씬 더 많은 기능을 추가하면 유형을 추론하는 것이 불가능 해집니다. 따라서 추론 속성을 파괴하지 않고 Hindley-Milner 스타일 유형 시스템 위에 계층화 할 수있는 시스템 확장은 실제로 현대 기능 언어의 흥미로운 부분입니다. 경우에 따라, 우리는 유형 추론과 유형 검사를 혼합합니다. 예를 들어 Haskell에서는 많은 최신 확장을 추론 할 수는 없지만 점검 할 수 있으므로 다형성 재귀와 같은 고급 기능에 대한 유형 주석이 필요합니다.

Answer 2

Wikipedia는 내가 알 수있는 한 "통일"라는 단어에 해당하는 알고리즘에 대한 설명을 제공합니다. 그게 전부입니까? 그렇다면 흥미로운 부분은 유형 시스템 자체가 유형 추론 시스템이 아니라는 것을 의미합니다.

IIRC, Damas-Milner 유형 추론 알고리즘 W의 흥미로운 부분은 가장 일반적인 유형을 유추한다는 것입니다.