Digitare l'inferenza con il sovraccarico

Question

Sto lavorando su un sistema di tipo che supporta il sovraccarico. Ho un'idea approssimativa di come il tipo di inferenza è solitamente implementato in uno scenario, ma mi chiedo come è possibile completare l'inferenza del tipo - è possibile scegliere la corretta implementazione di un operatore sovraccarico. O, in altre parole, il modo in cui il tipo di dedotto può essere trasmesso indietro sull'albero della sintassi all'operatore.

Per un piccolo esempio, considera l'espressione (x + y) + 1 dove x :: N | S, y :: a, + :: (N -> N -> N) | (S -> S -> S), 1 :: N. :: Stands per Tipo di e a | b Stand per il tipo a o Tipo b.

La strada, presumo, il tipo di inferenza ora funzionerebbe, è quello di attraversare l'albero della sintassi e per ciascun nodo restituire un vincolo di tipo:

(x + y) + 1 => ((N & (N[a=N] | S[a=S])), (N & N) -> N) | ((S & (N[a=N] | S[a=S])), (S & N) -> S) => N[a=N]
  1         => N
  +         => (N -> N -> N) | (S -> S -> S)
  x + y     => ((N & (N | S)), (N & a) -> N) | ((S & (N | S)), (S & a) -> S) => N[a=N] | S[a=S]
    x       => N | S
    y       => a
    +       => (N -> N -> N) | (S -> S -> S)

.

a & b in questo esempio Stand per Unifying I tipi a e b, [a=T, b=U] è un insieme di vincoli di uguaglianza per le variabili di tipo.

Come previsto il tipo di ritorno dell'espressione specificata è dedotto come N[a=N], cioè N dove si prevede che il tipo di generazione variabile variabile sia a.

Pertanto, delle due implementazioni fornite per l'operatore N (+, N -> N -> N), è necessario utilizzare S -> S -> S. Nell'esempio dato, il tipo risultante è dedotto, ma non il tipo di operatore sovraccarico. La mia domanda è se c'è un modello comune utilizzato per informare il nodo N -> N -> N nell'albero di sintassi dell'implementazione utilizzata.

Answer 1

È possibile organizzare inferenza del tipo come segue.

Supponiamo che la tua sintassi di input abbia digita Input.Definire la sintassi di uscita Output per essere come Input ma con annotazioni di tipo esplicita su tutte le variabili.L'inferenza del tipo avrebbe digitato

infer : Input -> List (Output * Type)

.

cioè, dato un po 'di ingresso e, restituisce un elenco di possibili risposte.Ogni risposta è una coppia (e', t) in cui e' è e con variabili annotate da tipi e t è il tipo di generazione di e.

Puoi vederlo come tutto avvenendo nella monada nonterminismo.Ogni volta che è necessario dedurre il tipo di una variabile x, cerchi i suoi possibili tipi S | T | ... e ramo su ciascuno di essi.In questo modo non devi "passare" qualsiasi informazione alle sotto-espressioni.Invece, ogni sotto-espressioni viene già annotata, in tutti i modi possibili.