카테고리 보관물: cs

cs

타입 추론 + 과부하 하나이므로 내

개발중인 언어에 대한 형식 유추 알고리즘을 찾고 있지만 일반적으로 다음 중 하나이므로 내 요구에 맞는 것을 찾을 수 없습니다.

  • La Haskell, 다형성, 임시 과부하 없음
  • a-임시 오버로드가 있지만 기능이 단일 한 C ++ (자동)

특히 내 유형 시스템은 (단순화)입니다 (저는 Haskellish 구문을 사용하고 있지만 언어에 구애받지 않습니다).

data Type = Int | Double | Matrix Type | Function Type Type

그리고 나는 꽤 많은 과부하가있는 연산자를 가지고 있습니다 :

Int -> Int -> Int
(Function Int Int) -> Int -> Int
Int -> (Function Int Int) -> (Function Int Int)
(Function Int Int) -> (Function Int Int) -> (Function Int Int)
Int -> Matrix Int -> Matrix Int
Matrix Int -> Matrix Int -> Matrix Int
(Function (Matrix Int) (Matrix Int)) -> Matrix Int -> Matrix Int

기타…

그리고 가능한 유형을 추론하고 싶습니다

(2*(x => 2*x))*6
(2*(x => 2*x))*{{1,2},{3,4}}

첫 번째는 Int두 번째 Matrix Int입니다.

예 (작동하지 않음) :

{-# LANGUAGE OverlappingInstances, MultiParamTypeClasses,
  FunctionalDependencies, FlexibleContexts,
  FlexibleInstances, UndecidableInstances #-}

import qualified Prelude
import Prelude hiding ((+), (*))
import qualified Prelude

newtype WInt = WInt { unwrap :: Int }

liftW f a b = WInt $ f (unwrap a) (unwrap b)

class Times a b c | a b -> c where
(*) :: a -> b -> c

instance Times WInt WInt WInt where
(*) = liftW (Prelude.*)

instance (Times a b c) => Times a (r -> b) (r -> c) where
x * g = \v -> x * g v

instance Times (a -> b) a b where
f * y = f y

two = WInt 2
six = WInt 6

test :: WInt
test = (two*(\x -> two*x))*six

main = undefined

답변

내가 볼 것을 제안합니다 Geoffrey Seward Smith의 논문을

이미 알고 있듯이 일반적인 형식 유추 알고리즘이 작동하는 방식은 구문 트리를 통과하고 모든 하위 식에 대해 형식 제약 조건을 생성하는 것입니다. 그런 다음이 제약 조건을 취하고 이들 사이의 연결을 가정하고 해결합니다 (일반적으로 가장 일반적인 솔루션 찾기).

오버로딩이있을 때 오버로드 된 연산자를 분석 할 때 오버로드가 제한되는 경우 하나의 유형 대신 여러 유형 제약 조건을 생성하고 이들 사이의 분리를 가정합니다. 연산자가 본질적으로“이것 또는 이것 또는 그 유형 ”을 가질 수 있다고 말하고 있기 때문에 제한이 없다면 다형성 유형과 마찬가지로 보편적 인 수량화에 의존해야하지만 실제 제약 조건을 제한하는 추가 제약 조건이 필요합니다 오버로드 유형 : 내가 참조하는 논문은 이러한 주제를보다 깊이 다루고 있습니다.

답변

이상하게도 Haskell 자체는 귀하의 모범을 거의 완벽하게 수행 할 수 있습니다. Hindley-Milner는 잘 묶여있는 한 오버로드로 완전히 괜찮습니다.

{-# LANGUAGE OverlappingInstances, MultiParamTypeClasses,
             FunctionalDependencies, FlexibleContexts,
             FlexibleInstances #-}
import Prelude hiding ((*))

class Times a b c | a b -> c where
    (*) :: a -> b -> c

instance Times Int Int Int where
    (*) = (Prelude.*)

instance Times Double Double Double where
    (*) = (Prelude.*)

instance (Times a b c) => Times (r -> a) (r -> b) (r -> c) where
    f * g = \v -> f v * g v

instance (Times a b c) => Times a (r -> b) (r -> c) where
    x * g = \v -> x * g v

instance (Times a b c) => Times (r -> a) b (r -> c) where
    f * y = \v -> f v * y

type Matrix a = (Int, Int) -> a

끝났습니다! 글쎄, 당신은 기본 설정이 필요하다는 것을 제외하고. 귀하의 언어가 Times클래스를 기본으로 설정 Int한 다음 ( Double) 으로 허용하면 예제가 명시된대로 작동합니다. 다른 방법은 물론, 자동으로 홍보하지 않는 것입니다 해결하기 Int에 Double, 또는 때 즉시 필요한 경우에만하는 것은 그것을 및 사용에 Int같은 리터럴 Int(경우에만 즉시 필요한 홍보, 다시) 만; 이 솔루션도 작동합니다.

답변