Qual è il formalismo per dimostrare le dichiarazioni sull'unicità delle funzioni con certe firme

Question

Supponiamo che voglio una funzione come

f: ((A, B) -> C) -> A -> B -> C

Una dichiarazione che ho visto spesso fatto è che F ha solo un'implementazione, vale a dire la "funzione curry", cioè g => a => b => g(a, b)

Preso al valore nominale Questo non sembra effettivamente essere vero, posso sempre definire F come recitare in modo diverso da questo in casi speciali, ad es.Posso dire che è g => a => b => g(a, b) tranne quando generatodicetagcode e poi lo definisco come A = B.

Nondimeno, è intuitivamente chiaro sufficientemente ciò che si intende per "ha solo un'implementazione".

Vorrei conoscere il corretto formalismo in cui le affermazioni come quanto sopra possono essere dimostrate.

A suppongo che sospetterei che sia una teoria della categoria?Quanto sopra mi sente un po 'come la nozione di una trasformazione naturale, ma non vedo veramente i dettagli.

Answer 1

Sono sicuro che c'è una connessione con la teoria della categoria, ma puoi effettivamente farlo (cosa considero) uno strumento più semplice: Parametricità.

L'idea di base è che, quando una lingua ha la proprietà che i tipi polimorfici fanno esattamente la stessa cosa per ogni tipo che vengono istantanea a (cioè non c'è alcuno costrutto di typecase), possiamo provare proprietà molto potenti sulla lingua, in la forma di una relazione logica.

Questo impedisce esattamente l'implementazione del "caso speciale" che descrivi nella tua domanda. Vale anche la pena ricordare che queste implementazioni sono tutte estensionalmente uguale: potrebbero sembrare diversi ma producono risultati uguali per uguali input. per esempio. È possibile sostituire qualsiasi termine $ T $ con $ (\ lambda x \ ldotp x) t $ e ottenere una funzione equivalente.

Le affermazioni sulle funzioni solo dal loro tipo sono generalmente chiamate teorema libero , dal nome della carta che ha introdotto l'idea: teoremi gratis di Phil Wadler. Se sei interessato a quest'area, consiglio vivamente il documento, dal momento che è una buona introduzione al soggetto.

L'idea alla base di questo va in realtà molto più indietro di quella carta, a John Reynolds lavora con il sistema F e il "teorema dell'astrazione" ma ci è voluto un po 'prima che l'idea sia diventata popolare.

Puoi effettivamente generare teoremi gratuiti a http://free-herems.nomeata.de/, anche se potrebbe richiedere un po 'di massaggio per ottenere informazioni utili dai teoremi che danno lì.

Se sei interessato alla parametricità usata per dimostrare cose diverse dai teoremi liberi, come il tipo sicuro, allora Tesi Amal Ahmed's è la migliore introduzione che abbia mai visto. Fa davvero un buon lavoro di descrizione dei tipi semantici: il tipo di programma è in realtà una proprietà di come funziona e ciò che produce e ciò che chiamiamo "tipi" siamo un'approssimazione sintattica di questi tipi semantici più generali.