Quando si scrive un interprete, come dovrebbe l'algoritmo di inferenza del tipo cambiare l'AST analizzato? Dovrebbe?

4

Durante la scrittura di un interprete, in che modo l'algoritmo di inferenza del tipo può modificare l'AST analizzato? Dovrebbe? O l'analisi e l'inferenza sono fatti necessariamente simultaneamente?

Ho implementato un interprete di linguaggio funzionale strongmente tipizzato, in cui ciascuna funzione può essere dichiarata una sola volta (cioè senza varianti di firma). Non appena il parser dell'implementazione non tipizzato è stato concluso e funzionante, ho scritto l'algoritmo di inferenza del tipo, alimentato dall'AST risultante del parser.

Hindley- Damas -Milner funziona come un incantesimo, ma il programma lo usa e se il controllo del tipo passa, dimentica l'argomento e passa l'AST all'interprete. Al momento, la "lingua di destinazione" (cioè quella in cui è scritto l'interprete) ha soddisfatto le esigenze del tipo di interprete, ma Mi chiedo se questo approccio è usuale: scartare tutti i frutti di inferenza di tipo dopo un "ok" risultato.

Inoltre, scrivere un compilatore invece di un interprete può fare la differenza in questo senso?

    
posta viyps 19.06.2013 - 07:35
fonte

1 risposta

6

No, non è certo il solito buttare via buoni risultati di analisi. Per una netta differenza potresti voler controllare il compilatore di Scala. Si basa sulle fasi di esecuzione e puoi aggiungere plugin che verranno eseguiti dopo determinate fasi. È particolarmente interessante posizionare il tuo plug-in dopo la fase di digitazione, perché questo ti dà tutti i tipi dedotti in un modo molto pratico.

L'AST, tuttavia, non è tanto modificato quanto annotato . La struttura di base delle tue affermazioni, espressioni, definizioni di funzioni, ecc., Che sono contenute nel tuo AST, rimangono ovviamente invariate. Quello che realmente fai durante l'inferenza di tipo è annotare i nodi dell'albero con i loro rispettivi tipi.

Ad esempio, prima di digitare l'inferenza eseguita avresti un AST con un nodo funzione per la funzione f , che si trova da qualche parte all'interno dell'AST e ha alcuni nodi figli, che assomigliano a argomenti ed espressioni / espressioni. Durante l'inferenza di tipo si determinano i tipi di questi nodi figli, cioè delle istruzioni / espressioni, e da essi si determina il tipo della funzione f . Ora potresti essere soddisfatto nel rilevare che f restituisce un int e viene sempre e solo utilizzato in luoghi, dove viene utilizzato int , ma non vi è alcun motivo per perdere queste informazioni.

Per quanto riguarda l'interprete vs il compilatore, ci sono enormi vantaggi dall'avere annotato i tipi sul tuo AST, che vanno ben oltre. Prendiamo ad esempio gli IDE. Gli autori di plugin sono molto grati per avere un AST con annotazione di tipo disponibile. È molto più efficiente semplicemente sapere che f restituisce un int , quando si desidera implementare il completamento del codice, invece di dover eseguire nuovamente l'inferenza di tipo.

Potresti voler estendere la tua lingua in un punto. Se l'estensione è ovunque oltre l'inferenza del tipo, in genere è necessario fare affidamento sui suoi risultati. Ad esempio, prendi in considerazione l'aggiunta di macro di tipo sicuro o qualche tipo di controllo semantico.

In sintesi: digitare le informazioni in una lingua strongmente tipizzata è così importante, che assomiglia alla bestemmia se si esegue l'inferenza di tipo solo per buttare via i suoi risultati. Rapisci te stesso e gli altri di informazioni che sono entrambe, estremamente potenti quando disponibili e piuttosto costose da generare.

    
risposta data 19.06.2013 - 08:02
fonte

Leggi altre domande sui tag