[haskell] Haskell의 기존 유형에 대한 설명

Haskell의 기존 유형을 이해하려고하는데 PDF를 발견했습니다. http://www.ii.uni.wroc.pl/~dabi/courses/ZPF15/rlasocha/prezentacja.pdf를 .

지금까지 이해 한 내용을 아래에서 수정하십시오.

  • 존재 유형은 포함하는 유형에 관심이없는 것처럼 보이지만 패턴 일치는 일부 유형이 있으며 유형 지정 또는 데이터를 사용하지 않는 한 유형이 무엇인지 알 수 없습니다.
  • 유형을 숨기고 싶을 때 (예 : 이기종 목록의 경우) 또는 컴파일 타임에 유형이 무엇인지 실제로 알지 못합니다.
  • GADT의 암시 제공함으로써 실존 적 유형을 사용하여 코드에 맑은 및 더 나은 구문을 제공 foralls ‘을 (를)

내 의심

  • 위 PDF의 20 페이지에서 함수가 특정 버퍼를 요구하는 것은 불가능하다는 코드 아래에 언급되어 있습니다. 왜 그래야만하지? 함수를 작성할 때 어떤 종류의 버퍼를 사용할 것인지 정확히 알고 있지만 어떤 데이터를 넣을지 모르겠습니다. 데에 어떤 문제가 :: Worker MemoryBuffer Int그들이 정말로 그들이 합계 유형을 가질 수 있습니다 버퍼를 통해 추상화하려는 경우 data Buffer = MemoryBuffer | NetBuffer | RandomBuffer와 유형 등이있다:: Worker Buffer Int
data Worker x = forall b. Buffer b => Worker {buffer :: b, input :: x}
data MemoryBuffer = MemoryBuffer

memoryWorker = Worker MemoryBuffer (1 :: Int)
memoryWorker :: Worker Int
  • Haskell은 C와 같은 Full Type Erasure 언어이므로 런타임에 호출 할 함수를 어떻게 알 수 있습니까? 정보를 거의 유지하지 않고 거대한 V- 테이블 함수를 전달하고 런타임에 V- 테이블에서 알아낼 수 있습니까? 그렇다면 어떤 종류의 정보를 저장할 것인가?


답변

GADT는 암시 적 forall의

GADT 구문이 더 낫다는 일반적인 동의가 있다고 생각합니다. GADT가 모든 것을 암시 적으로 제공하기 때문이 아니라 ExistentialQuantification확장 기능을 사용하는 원래 구문 이 혼란스럽고 오해의 소지 가 있기 때문 입니다. 물론이 구문은 다음과 같습니다.

data SomeType = forall a. SomeType a

또는 제약 조건이있는 경우 :

data SomeShowableType = forall a. Show a => SomeShowableType a

그리고 나는 forall여기 에 키워드 를 사용하면 유형이 완전히 다른 유형과 쉽게 혼동 될 수 있다고 생각합니다 .

data AnyType = AnyType (forall a. a)    -- need RankNTypes extension

더 나은 구문은 별도의 exists키워드를 사용했을 수 있으므로 다음과 같이 작성하십시오.

data SomeType = SomeType (exists a. a)   -- not valid GHC syntax

암시 적이든 명시 적이든 GADT 구문 forall은 이러한 유형에서 더 균일하며 이해하기 쉽습니다. 명시 적 forall인 경우에도 다음 정의는 모든 유형의 값을 가져 와서 a단형 안에 넣을 수 있다는 아이디어를 얻 습니다 SomeType'.

data SomeType' where
    SomeType' :: forall a. (a -> SomeType')   -- parentheses optional

그리고 그 유형과 다음의 차이점을 쉽게보고 이해할 수 있습니다.

data AnyType' where
    AnyType' :: (forall a. a) -> AnyType'

존재 유형은 포함하는 유형에 관심이없는 것처럼 보이지만 패턴 일치는 일부 유형이 있으며 유형 지정 또는 데이터를 사용하지 않는 한 유형이 무엇인지 알 수 없습니다.

유형을 숨기고 싶을 때 (예 : 이기종 목록의 경우) 또는 컴파일 타임에 유형이 무엇인지 실제로 알지 못합니다.

나는 존재하지 않는 유형 을 사용 Typeable하거나 사용할 필요는 없지만 이것들은 너무 멀지 않은 것 같습니다 Data. 필자는 실존 유형이 지정되지 않은 유형 주위에 잘 유형화 된 “상자”를 제공한다고 말하는 것이 더 정확하다고 생각합니다. 상자는 유형을 어떤 의미로 “숨겨”서, 상자에 포함 된 유형을 무시하고 이기종 목록을 만들 수 있습니다. SomeType'위와 같이 제한되지 않은 실재 는 쓸모가 없지만 제약 유형입니다.

data SomeShowableType' where
    SomeShowableType' :: forall a. (Show a) => a -> SomeShowableType'

“상자”내부를 들여다 볼 수 있도록 패턴 일치를 만들고 유형 클래스 기능을 사용할 수 있습니다.

showIt :: SomeShowableType' -> String
showIt (SomeShowableType' x) = show x

이것은 Typeable또는 모든 유형 클래스에서 작동하지만Data .

슬라이드 데크의 20 페이지에 대한 혼동과 관련하여 필자는 필자는 실존 적 인 기능 특정 인스턴스 Worker를 요구하는 것이 불가능하다고 말합니다 . 다음 과 같은 특정 유형을 사용하여 작성하는 함수를 작성할 수 있습니다 .WorkerBufferWorkerBufferMemoryBuffer

class Buffer b where
  output :: String -> b -> IO ()
data Worker x = forall b. Buffer b => Worker {buffer :: b, input :: x}
data MemoryBuffer = MemoryBuffer
instance Buffer MemoryBuffer

memoryWorker = Worker MemoryBuffer (1 :: Int)
memoryWorker :: Worker Int

그러나 Worker인수로 사용 하는 함수를 작성하는 경우 일반 Buffer유형 클래스 기능 (예 output: function ) 만 사용할 수 있습니다 .

doWork :: Worker Int -> IO ()
doWork (Worker b x) = output (show x) b

b패턴 일치를 통해서도 특정 유형의 버퍼 가 되도록 요구할 수는 없습니다 .

doWorkBroken :: Worker Int -> IO ()
doWorkBroken (Worker b x) = case b of
  MemoryBuffer -> error "try this"       -- type error
  _            -> error "try that"

마지막으로, 존재하는 유형에 대한 런타임 정보는 관련된 유형 클래스에 대한 암시 적 “사전”인수를 통해 사용 가능합니다. Worker버퍼와 입력에 대한 필드를 갖는 것 외에도 위 의 유형에는 Buffer사전 을 가리키는 보이지 않는 암시 적 필드가 있습니다 (v-table과 거의 같지만 적절한 포인터를 포함하기 때문에 거의 크지 않습니다)output 함수에 않습니다).

내부적으로 유형 클래스 Buffer는 함수 필드가있는 데이터 유형으로 표시되며 인스턴스는이 유형의 “사전”입니다.

data Buffer' b = Buffer' { output' :: String -> b -> IO () }

dBuffer_MemoryBuffer :: Buffer' MemoryBuffer
dBuffer_MemoryBuffer = Buffer' { output' = undefined }

실존 유형에는이 사전에 숨겨진 필드가 있습니다.

data Worker' x = forall b. Worker' { dBuffer :: Buffer' b, buffer' :: b, input' :: x }

doWork존재 Worker'값에서 작동하는 것과 같은 기능은 다음과 같이 구현됩니다.

doWork' :: Worker' Int -> IO ()
doWork' (Worker' dBuf b x) = output' dBuf (show x) b

함수가 하나만있는 형식 클래스의 경우 사전은 실제로 새 형식에 최적화되므로이 예에서 실존 Worker형식에는 output버퍼 의 함수에 대한 함수 포인터로 구성된 숨겨진 필드가 포함되며 필요한 런타임 정보입니다. 에 의해 doWork.


답변

위 PDF의 20 페이지에서 함수가 특정 버퍼를 요구하는 것은 불가능하다는 코드 아래에 언급되어 있습니다. 왜 그래야만하지?

왜냐하면 Worker정의 된 바와 같은, 하나의 인자, “입력”필드 (입력 변수의 입력 소요 x). 예 Worker Int를 들어 유형입니다. b대신 type 변수 는의 매개 변수가 Worker아니라 일종의 “로컬 변수”이므로 말입니다. 에서처럼 전달할 수 없습니다Worker Int String형식 오류를 유발하는 .

우리가 대신 정의한 경우 :

data Worker x b = Worker {buffer :: b, input :: x}

그런 다음 Worker Int String작동하지만 유형이 더 이상 존재하지 않습니다. 이제는 항상 버퍼 유형도 전달해야합니다.

Haskell은 C와 같은 Full Type Erasure 언어이므로 런타임에 호출 할 함수를 어떻게 알 수 있습니까? 정보를 거의 유지하지 않고 거대한 V- 테이블 함수를 전달하고 런타임에 V- 테이블에서 알아낼 수 있습니까? 그렇다면 어떤 종류의 정보를 저장할 것인가?

이것은 대략적입니다. 간단히 말해 생성자를 적용 할 때마다 WorkerGHC는 b의 인수 에서 형식을 유추 Worker한 다음 인스턴스를 검색합니다 Buffer b. 이것이 발견되면 GHC는 객체의 인스턴스에 대한 추가 포인터를 포함합니다. 가장 간단한 형태로, 이것은 가상 함수가 존재할 때 OOP의 각 객체에 추가되는 “포인터에서 vtable로”와 크게 다르지 않습니다.

일반적인 경우에는 훨씬 더 복잡 할 수 있습니다. 컴파일러는 코드의 속도를 높이면 다른 표현을 사용하고 단일 포인터 대신 포인터를 더 추가 할 수 있습니다 (예 : 모든 인스턴스 메소드에 포인터를 직접 추가). 또한 때로는 컴파일러가 제약 조건을 충족시키기 위해 여러 인스턴스를 사용해야 할 수도 있습니다. 예를 들어 인스턴스를 저장 해야하는 경우 Eq [Int]하나만 두 개는 없습니다. Int하나는 목록 하나이고 하나는 하나이며 목록에는 하나가 있고 두 개는 결합해야합니다 (런타임에는 최적화 최적화 제외).

각 경우에 GHC가 무엇을하는지 정확하게 추측하기는 어렵습니다. 이는 트리거 될 수도 있고 트리거하지 않을 수있는 수많은 최적화에 따라 다릅니다.

무슨 일이 일어나고 있는지에 대해 더 많이 알기 위해 타입 클래스의 “사전 기반”구현에 대한 인터넷 검색을 시도 할 수 있습니다. 또한 GHC에 내장 최적화 코어를 인쇄하고 -ddump-simpl구성, 저장 및 전달되는 사전을 관찰 하도록 요청할 수 있습니다 . 나는 당신에게 경고해야합니다 : 코어는 다소 저수준이며 처음에는 읽기가 어려울 수 있습니다.


답변