Quali sono le implicazioni pratiche della teoria del tipo di omotopia nella programmazione?

10

Sto appena iniziando ad imparare Haskell, dopo essere venuto dai mondi JavaScript / Ruby. Ho trovato link e il omotopia Type Theory book , che sono molto desideroso di leggere.

Tuttavia, imparerò i concetti di matematica e teoria del tipo mentre vado, quindi sembra che ci vorrà molto tempo prima di capire quale teoria del tipo di omotopia significherà per un programmatore professionista.

Potresti descrivere quale impatto avrà la teoria del tipo di omotopia sulla programmazione in pratica, per un laico? Ad esempio, renderà alcune cose più facili da scrivere più facilmente? Se sì, quali cose? O ti permetterà di fare cose nuove in programmazione che prima non erano possibili? Se sì, quali cose?

Grazie, non vedo l'ora di abbracciarlo a un livello più basilare.

    
posta Lance Pollard 10.11.2014 - 23:53
fonte

1 risposta

11

Uno dei potenti compilatori di cose che sono in grado di fare durante la loro ottimizzazione fase è di scambiare rappresentazioni inefficienti per quelle equivalenti. Per Ad esempio, in Haskell puoi usare una lista pigra per calcolare una somma di numeri, ma il compilatore GHC Haskell riconoscerà che questo è equivalente all'utilizzo iterazione con una variabile temporanea. In questo modo, puoi programmare contro a astrazione semplice che è facile ragionare, mentre il tuo eseguibile prende vantaggio di una rappresentazione più adatta alla piattaforma hardware (e quella sembra essere molto più difficile ragionare su scala).

Tuttavia, le equivalenze conosciute dal compilatore sono per lo più limitate al bene strutture di dati noti e ricercati, come la fusione del flusso per gli elenchi. Potresti definisci le tue equivalenze nel codice sorgente (usando una coppia di conversioni funzioni che compongono l'identità in entrambe le direzioni), ma dovresti farlo applicali manualmente, e può essere difficile scegliere il tipo giusto da usare tutti i posti al fine di evitare conversioni eccessive.

Ora immaginiamo un mondo in cui tu possa definire "tipi induttivi più alti", dì una mappa di ricerca canonica. Questo tipo ha diversi costruttori per i vari tipi di mappe: ricerca binaria, AVL, rosso-nero, Trie, Patricia, ecc. Insieme a i tipici costruttori di dati, si definisce anche una cattura di tipo di equivalenza forse più conversioni tra queste rappresentazioni, dove diverse le conversioni offrono diverse dimensioni di efficienza (ad es. tempo e memoria).

Che cosa succede se il compilatore è stato in grado di utilizzare questa nozione per riscrivere in modo trasparente la mappa rappresentazioni, allo stesso modo che può fare oggi con la fusione delle liste? Nel frattempo a il tuo codice si arriva a lavorare con la costruzione che è più semplice da ragionare circa (e rende più facile la dimostrazione del lavoro, se ci si trova in un simile ambiente). Questo può sembrare un'interfaccia astratta con molteplici implementazioni, ma include la libertà di scegliere qualsiasi implementazione e avere il compilatore sostituirlo in modo trasparente secondo necessità, senza influire sul significato di il programma.

HoTT ci fornisce una base teorica di tipo per giustificare questa riscrittura di fantasia meccanismo e questi tipi ben definiti, perché promuove la nozione di equivalenza ad essere equivalente all'uguaglianza. Resta da vedere come questo si svolgerà in pratica, ma ci fornisce il quadro teorico su cui basare il lavoro futuro.

    
risposta data 17.05.2015 - 20:35
fonte

Leggi altre domande sui tag