Quale dizionario sceglie GHC quando ne sono presenti più di uno?

Question

consideri il seguente esempio:

import Data.Constraint 

class Bar a where 
    bar :: a -> a 

foo :: (Bar a) => Dict (Bar a) -> a -> a 
foo Dict = bar 

GHC ha due scelte per il dizionario da utilizzare quando si seleziona un'istanza Bar in foo: si potrebbe utilizzare il dizionario dal vincolo Bar a su foo, o potrebbe usare il runtime Dict per ottenere un dizionario Vedere this question per un esempio in cui i dizionari corrispondono a diverse istanze.

Quale dizionario usa GHC e perché è la scelta "corretta"?

Answer 1

GHC solo sceglie uno, e questa è la scelta giusta Ogni due dizionari per lo stesso vincolo dovrebbero essere uguali

OverlappingInstances e IncoherentInstances sono sostanzialmente equivalenti al potere distruttivo. Entrambi perdono istanza coerenza per progetto (eventuali due vincoli uguali nel tuo programma sono soddisfatti dallo stesso dizionario). Sovrapposizione Le istanze ti danno un po 'più di capacità di capire quali istanze saranno utilizzate caso per caso, ma non è così utile quando arrivi al punto di passare a Dicts come valori di prima classe e così via. Prenderò in considerazione l'uso di OverlappingInstances solo se considero le istanze sovrapposte estensionalmente equivalenti (es., un'implementazione più efficiente ma altrimenti uguale per un tipo specifico come Int), ma anche in questo caso, se mi interessa abbastanza le prestazioni per scrivere quell'implementazione specializzata, non è un bug di prestazioni se non viene utilizzato quando potrebbe essere ?

In breve, se si utilizza OverlappingInstances, si ha il diritto di porre la domanda su quale dizionario verrà selezionato qui.

Ora è vero che è possibile rompere la coerenza dell'istanza senza Sovrapposizioni. In effetti puoi farlo senza orfani e senza estensioni diverse da FlexibleInstances (probabilmente il problema è che la definizione di "orfano" è sbagliata quando FlexibleInstances è abilitato). Questo è un bug di GHC di lunga data, che non è stato risolto in parte perché (a) in realtà non può causare arresti anomali direttamente come nessuno sembra sapere, e (b) potrebbero esserci molti programmi che in realtà si basa sull'avere più istanze per lo stesso vincolo in parti separate del programma e potrebbe essere difficile da evitare.

Tornando all'argomento principale, in linea di principio è importante che GHC possa selezionare qualsiasi dizionario che è disponibile per soddisfare un vincolo, perché anche se si suppone che siano uguali, GHC potrebbe avere più informazioni statiche su alcuni di essi di altri. Il tuo esempio è un po 'troppo semplice per essere illustrativo ma immagina di aver passato un argomento a bar; in generale GHC non sa nulla del dizionario passato via Dict quindi deve considerarlo come una chiamata a una funzione sconosciuta, ma hai chiamato foo a un tipo specifico T per il quale c'era un'istanza Bar T in ambito, quindi GHC saprebbe che il bar dal dizionario dei vincoli Bar a è stato T di bar e potrebbe generare una chiamata a una funzione conosciuta e potenzialmente in linea T di bar ed eseguire di conseguenza più ottimizzazioni.

In pratica, GHC al momento non è così intelligente e utilizza solo il dizionario più interno disponibile. Probabilmente sarebbe già meglio usare sempre il dizionario più esterno. Ma casi come questo in cui ci sono più dizionari disponibili non sono molto comuni, quindi non abbiamo buoni benchmark su cui testare.

Answer 2

Ne basta uno. Questa non è la scelta corretta; è una verruca abbastanza conosciuta. È possibile causare arresti in questo modo, quindi è un pessimo stato di cose. Ecco un breve esempio utilizzando nient'altro che GADTs che dimostra che è possibile avere due differenti istanze nel campo di applicazione in una sola volta:

-- file Class.hs 
{-# LANGUAGE GADTs #-} 
module Class where 

data Dict a where 
    Dict :: C a => Dict a 

class C a where 
    test :: a -> Bool 

-- file A.hs 
module A where 

import Class 

instance C Int where 
    test _ = True 

v :: Dict Int 
v = Dict 

-- file B.hs 
module B where 

import Class 

instance C Int where 
    test _ = False 

f :: Dict Int -> Bool 
f Dict = test (0 :: Int) 

-- file Main.hs 
import TestA 
import TestB 

main = print (f v) 

Troverete che Main.hs compila bene, e anche corre. Stampa True sulla mia macchina con GHC 7.10.1, ma non è un risultato stabile. Trasformare questo in un incidente è lasciato al lettore.

Answer 3

Ecco un test:

{-# LANGUAGE FlexibleInstances, OverlappingInstances, IncoherentInstances #-} 
import Data.Constraint 

class C a where foo :: a -> String 
instance C [a] where foo _ = "[a]" 
instance C [()] where foo _ = "[()]" 

aDict :: Dict (C [a]) 
aDict = Dict 

bDict :: Dict (C [()]) 
bDict = Dict 

bar1 :: String 
bar1 = case (bDict, aDict :: Dict (C [()])) of 
     (Dict,Dict) -> foo [()]    -- output: "[a]" 

bar2 :: String 
bar2 = case (aDict :: Dict (C [()]), bDict) of 
     (Dict,Dict) -> foo [()]    -- output: "[()]" 

GHC sopra capita di usare il dizionario "ultimi" che è stato portato in ambito. Non mi affiderei a questo, però.

Se ci si limita a istanze sovrapposte, solo, quindi non si sarà in grado di portare due dizionari diversi per lo stesso tipo (per quanto posso vedere), e tutto dovrebbe andare bene dato che il la scelta del dizionario diventa irrilevante.

Tuttavia, istanze incoerenti sono un'altra bestia, poiché consentono di eseguire il commit su un'istanza generica e quindi di utilizzarla in un tipo con un'istanza più specifica. Questo rende molto difficile capire quale istanza verrà utilizzata.

In breve, le istanze incoerenti sono malvagie.

---

Aggiornamento: ho eseguito ulteriori test. Utilizzando solo istanze sovrapposte e un'istanza orfana in un modulo separato, è comunque possibile ottenere due dizionari diversi per lo stesso tipo. Quindi, abbiamo bisogno di ulteriori avvertimenti. . :-(