nicht typisierten Darstellung eines DSL in getippten Darstellung

Question

eine einfache Sprache gegeben Transforming, sagen

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

ist es dann möglich, sie in eine typisierte Darstellung zu transformieren:

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

ich verschiedene Ansätze versucht haben, z.B die folgenden:

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

Das funktioniert nicht, und ich erhalte die folgende Fehlermeldung:

Mehrdeutige Variable vom Typ 'a' in der Einschränkung:
'typisierbarem eine'
von einem entstehenden Verwendung von `E2T‘ an ...
Wahrscheinliche fix: eine Art Signatur hinzufügen, die diese Variable vom Typ fixiert (s)

wenn ich aber wie diese

tun

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)) 

es kompiliert.

Answer 1

Das stimmt. Sie werden es vielleicht nicht erkennen, aber Sie versuchen, Rückschlüsse auf Ihre Sprache zu treffen. Wenn Sie den Ausdruck f x in Ihre typisierte GADT konvertieren möchten, genügt es nicht, einfach den Ergebnistyp zu kennen. Wir könnten f :: Bool -> Int mit x :: Bool, f :: (Int -> Int) -> Int mit x :: Int -> Int usw. haben. Und Ihre typisierte Darstellung behauptet das zu wissen, vor allem, da sie Typeable auf ihren Konstanten benötigt (Sie können mit Lügen darüber hinwegkommen, zu wissen, welcher Typ es ist, wenn Sie nicht t haben die Typeable Einschränkung).

e2t erfordert Wissen, welcher Typ der Ausdruck erwartet wird. Sie müssen einen Weg finden, um zu bestimmen, welcher Typ das Argument einer Anwendung erwartet. Vielleicht können Sie etwas anderes diese benötigen, indem er sagte, nämlich zu umgehen:

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

Das heißt, Sie sind nur zu sehen, versuchen, wenn E kann eine Art gegeben werden, sondern es zu sagen, welche Art es sein sollte, es sagt Ihnen. Dies ist eine Bottom-up-Schlussfolgerung, die im Allgemeinen einfacher ist. Zu kodieren dies:

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

Hmm, nachdem eine Weile mit diesem zu spielen, ich merke, Sie laufen in genau das gleiche Problem auf dem Weg nach oben zurück. Ich glaube nicht, dass dies nur mit Data.Typeable möglich ist. Sie müssen etwas wie dynApp von Data.Dynamic, aber für T s anstelle von regulären Haskell-Typen neu erstellen. I.e. Sie müssen einige Operationen auf TypeRep s und dann irgendwann einfügen ein "nur mir vertrauen" unsafeCoerce, sobald Sie wissen, dass es sicher ist. Aber Sie können den Compiler nicht davon überzeugen, dass es sicher ist, soweit ich das beurteilen kann.

Dies wäre in Agda möglich, weil die äquivalenten Operationen auf TypeRep s für den Compiler beobachtbar wären. Es wäre wahrscheinlich eine gute Übung, wenn man diese Sprache lernt.