Chuyển đổi đại diện untyped của một DSL vào biểu gõ

Question

Cho một ngôn ngữ đơn giản, nói

data E where 
    ValE :: Typeable a => a -> E 
    AppE :: E -> E -> E 

là nó sau đó có thể để biến nó thành một đại diện gõ:

data T a where 
    ValT :: Typeable a => a -> T a 
    AppT :: T (a -> b) -> T a -> T b 
    deriving Typeable 

Tôi đã thử các cách tiếp cận khác nhau, ví dụ như sau:

e2t :: Typeable a => E -> Maybe (T a) 
e2t (ValE x) = cast (ValT x) 
e2t (AppE e1 e2) = liftM2 AppT (e2t e1) (e2t e2) 

này không làm việc, và tôi nhận được thông báo lỗi sau:

mơ hồ kiểu biến 'a' trong ràng buộc:
'Typeable một'
phát sinh từ một sử dụng của `e2t' tại ...
sửa chữa dự kiến: thêm một chữ ký kiểu đó sửa chữa các loại biến (s)

Tuy nhiên, nếu tôi làm như

này

e2t :: Typeable a => E -> Maybe (T a) 
e2t (ValE x) = cast (ValT x) 
e2t (AppE e1 e2) = liftM2 AppT (e2t e1) (e2t e2 :: Maybe (T Int)) 

nó biên dịch.

Answer 1

Đúng vậy. Bạn có thể không nhận ra nó, nhưng bạn đang cố gắng suy luận kiểu về ngôn ngữ của bạn. Nếu bạn muốn chuyển đổi biểu thức f x thành GADT đã nhập của bạn, không đủ để biết loại kết quả. Chúng tôi có thể có f :: Bool -> Int với x :: Bool, f :: (Int -> Int) -> Int với x :: Int -> Int, v.v. Và đại diện được đánh máy của bạn tuyên bố rằng, đặc biệt vì nó yêu cầu Typeable trên hằng số của nó (bạn có thể thoát khỏi việc nói dối về việc biết loại đó là gì nếu bạn không làm như vậy t có ràng buộc Typeable).

e2t yêu cầu phải biết loại biểu thức được mong đợi là gì. Bạn cần một số cách để xác định loại đối số của một ứng dụng được mong đợi là gì. Có lẽ bạn có thể nhận được xung quanh cần điều này bằng cách nói điều gì đó khác nhau, cụ thể là:

e2t :: E -> Maybe (exists a. T a) 

Đó là, bạn đang cố gắng để xem nếu E có thể nhận được một loại, nhưng thay vì nói nó loại nó phải được, nó nói với bạn. Đây là suy luận từ dưới lên, thường dễ dàng hơn. Để mã hóa này:

data AnyT where 
    AnyT :: Typeable a => T a -> AnyT 

Hmm, sau khi chơi với điều này trong một thời gian, tôi nhận ra rằng mình chạy vào chính xác cùng một vấn đề trên đường trở lại. Tôi không nghĩ rằng nó có thể làm điều này bằng cách sử dụng chỉ Data.Typeable. Bạn cần phải tạo lại một cái gì đó như dynApp từ Data.Dynamic, nhưng đối với T s thay vì các loại Haskell thông thường. I E. bạn sẽ phải thực hiện một số thao tác trên TypeRep giây và sau đó tại một số điểm, hãy chèn "chỉ tin tưởng tôi" unsafeCoerce khi bạn biết điều đó là an toàn. Nhưng bạn không thể thuyết phục trình biên dịch nó là an toàn, theo như tôi có thể nói.

Điều này có thể thực hiện được trong Agda, vì các phép toán tương đương đã nói trên TypeRep s sẽ được quan sát đối với trình biên dịch. Nó có lẽ sẽ là một bài tập tốt khi học ngôn ngữ đó.