Descrivere il tipo di inferenza Damas-Milner in un modo che uno studente può capire CS101

Question

Hindley-Milner è un sistema di tipo che è alla base dei sistemi di tipo di molti ben noti linguaggi di programmazione funzionale. Damas-Milner è un algoritmo che inferisce tipi (deduce?) In un sistema di tipo Hindley-Milner.

Wikipedia dà una descrizione dell'algoritmo che, come per quanto posso dire, equivale ad una sola parola: "unificazione" È che tutto quello che c'è ad esso? Se è così, questo significa che la parte interessante è il tipo non sistema stesso sistema di inferenza.

Se Damas-Milner è più di unificazione, vorrei una descrizione di Damas-Milner che include un semplice esempio e, idealmente, un certo codice.

Inoltre, questo algoritmo è spesso detto di fare inferenza di tipo. E 'davvero un sistema di inferenza? Ho pensato che fosse deducendo solo i tipi.

Domande correlate:

• cosa è Hindley Miller?
• inferenza di tipo di problema dell'unificazione

Answer 1

Damas Milner è solo un uso strutturato di unificazione.

Quando si recurses in un'espressione lambda che costituisce un nuovo nome di variabile. Quando, in un sub-termine, trova che variabile utilizzata in un modo che richiederebbe un determinato tipo, registra l'unificazione di tale variabile e che tipo. Se mai tenta di unificare due tipi che non hanno senso, come dire che una variabile individuo è sia un Int e una funzione da un -.> B, allora ti urla per aver fatto qualcosa di male

  

Inoltre, questo algoritmo è spesso detto di fare inferenza di tipo. E 'davvero un sistema di inferenza? Ho pensato che fosse deducendo solo i tipi.

dedurre la tipi è l'inferenza dei tipi. Controllo per vedere che annotazioni di tipo sono validi per un determinato periodo è di tipo controllo. Sono problemi diversi.

  

Se è così, questo significa che la parte interessante è il tipo non sistema stesso sistema di inferenza.

Si dice comunemente che i sistemi di tipo stile Hindley-Milner sono in equilibrio su una cuspide. Se si aggiunge molto di più funzionalità diventa impossibile dedurre le tipologie. Quindi digitare le estensioni di sistema che si può strato sulla cima di un sistema di tipo di stile Hindley-Milner senza distruggere le sue proprietà di inferenza sono davvero le parti interessanti di moderni linguaggi funzionali. In alcuni casi, mescoliamo inferenza di tipo e il tipo di controllo, per esempio in Haskell un sacco di estensioni moderne non si può dedurre, ma possono essere controllati, quindi hanno bisogno di annotazioni di tipo per le funzioni avanzate, come la ricorsione polimorfico.

Answer 2

  

Wikipedia dà una descrizione dell'algoritmo che, per quanto ne so, è pari a una sola parola: "unificazione". È che tutto quello che c'è ad esso? Se è così, questo significa che la parte interessante è il tipo non sistema stesso sistema di inferenza.

IIRC, la parte interessante del tipo inferenza Damas-Milner Algoritmo W è di dedurre i tipi più generale possibile.