Risoluzione del caso del modulo Haskell Importazioni ed esportazioni

Question

Sto scrivendo un piccolo compilatore Haskell e voglio implementare il maggior numero possibile di Haskell 2010. Il mio compilatore può analizzare un modulo, ma il completamento di moduli per un programma sembra essere un compito non banale. Ho fatto alcuni esempi di, ma, moduli Haskell forse validi difficili:

module F(G.x) where 
    import F as G 
    x = 2 

Qui il modulo F esportazioni G.x, ma G.x è lo stesso di F.x, quindi modulo F esportazioni x se, e solo se, esporta x.

module A(a) where 
    import B(a) 
    a = 2 

module B(a) where 
    import A(a) 

In questo esempio, per risolvere le esportazioni del modulo A compilatore deve verificare se a importato dalla B è la stessa della dichiarata a = 2, ma B esportazioni a se, e solo se, A esportazioni a.

module A(f) where 
    import B(f) 

module B(f) where 
    import A(f) 

Durante modulo A risolvere, il may've compilatore presume che f importato da B esiste, il che implica che le esportazioni Af, quindi B possono importare ed esportare A(f)f. L'unico problema è che non esiste uno f definito :).

module A(module X) where 
    import A as X 
    import B as X 
    import C as X 
    a = 2 

module B(module C, C.b) where 
    import C 
    b = 3 

module C(module C) 
    import B as C 
    c = 4 

Qui, le esportazioni module causa che le liste di esportazione sono dipendenti l'uno dall'altro e su se stessi.

Tutti questi esempi devono essere Haskell validi, come definito dalle specifiche Haskell 2010.

Voglio chiedere se c'è qualche idea su come implementare correttamente e completamente i moduli Haskell?

Si supponga che un modulo contiene solo (semplici) variabile binding, import s (possibilmente con as o qualified), e l'elenco delle esportazioni di variabili eventualmente qualificati e module ... abbreviazioni. L'algoritmo deve essere in grado di:

• calcolo lista finito di variabili esportate di ogni modulo
• collegamento ogni variabile esportati in suo legame
• collegamento ogni variabile (forse qualificato) utilizzato in ogni modulo per il suo legame

Answer 1

Potresti essere interessato a A Formal Specification for the Haskell 98 Module System.

Sto anche coprendo alcuni casi limite interessanti in una serie di post di blog, di cui solo il first one è pubblicato fino ad ora.

Infine, sto lavorando proprio su questo - una libreria che gestisce i moduli Haskell. Si chiama haskell-names.

A seconda dei tuoi obiettivi, puoi semplicemente usarlo nel tuo compilatore, studiare il codice sorgente o contribuire. (I tuoi esempi costituiranno casi di test eccellenti.)

---

Per rispondere alla tua domanda: i moduli ricorsivi vengono gestiti calcolando un punto fisso.

Si inizia con un componente fortemente collegato nel grafico del modulo. Per ogni modulo in questo componente, si inizia con l'assunto che non esporta nulla. Quindi rivisita questi moduli e calcola nuovi elenchi di esportazione in base alle nuove informazioni. Puoi dimostrare che questo processo è monotono, ogni volta che la lista di esportazione cresce (o, almeno, non si riduce). Prima o poi smette di crescere - quindi hai raggiunto il punto fisso.

È possibile ottimizzare questo algoritmo prendendo in prestito alcune idee dall'analisi statica (che la community è molto brava a calcolare i punti fissi), ma il mio pacchetto implementa attualmente l'algoritmo naive (code).