Quali sono i problemi principali nella progettazione di un interprete per un linguaggio funzionale?

Question

Supponiamo che io voglia implementare un interprete per un linguaggio funzionale. Mi piacerebbe capire le questioni coinvolte nel fare ciò e la letteratura adeguata disponibile. Questo è un nuovo linguaggio che è nelle prime fasi di progettazione, ecco perché la domanda ha una portata ampia.

Ai fini di questa discussione possiamo supporre che lo scopo del linguaggio non sia importante e che le sue caratteristiche funzionali possano essere modificate (anche drasticamente) se fa una differenza significativa nella facilità di scrittura di un interprete.

Il sito web del MIT ha una copia online di Struttura e interpretazione dei programmi per computer nonché video del Lezioni del MIT 6.001 con Scheme, registrate ad HP nel 1986. Queste sono un'ottima introduzione al design del linguaggio.

Answer 1

Consiglio vivamente Struttura e interpretazione dei programmi per computer (SICP) come punto di partenza. Questo libro introdurrà l'idea di cosa significhi scrivere un interprete (e un compilatore) ed è generalmente una lettura obbligata per chiunque progetta linguaggi.

L'implementazione di un interprete per un linguaggio funzionale non è probabilmente molto diversa dall'implementazione di un interprete per qualsiasi altro linguaggio di uso generale. C'è analisi lessicale, analisi, costruzione AST, analisi semantica, oltre all'esecuzione (per un puro interprete) o generazione e ottimizzazione del codice (per un compilatore, anche compilando in bytecode come Java / Perl / Python). SICP introdurrà la differenza tra "ordine applicativo" e "ordine normale" valutazione, che può essere importante per te in un contesto funzionale puro.

Answer 2

Per quasi qualsiasi interprete o compilatore di lingue, i problemi principali sono gli stessi, penso.

Devi decidere alcune caratteristiche di base del linguaggio (semantica, non sintassi), e la maggior parte del design della cosa segue da ciò.

• Ad esempio, la tua lingua ha un sistema di tipo? Se è così, che tipo di tipi ha? Sarà digitato staticamente, digitato dinamicamente, anatra-digitato?

• Che tipo di espressioni sei hai intenzione di supportare? Hai bisogno di definire un ordine di operazioni? Volontà hai anche operatori?

• Cosa utilizzerai come runtime rappresentazione del programma? Volontà converti il ??testo in un codice byte rappresentazione, o un AST, o a forma tokenizzata del testo sorgente?

Ci sono toolkit disponibili per aiutare a rimuovere parte del tedio dall'analisi effettiva del testo (ANTLR e Bison, per nominarne due), ma non conosco nulla che aiuti la parte dell'interpretazione effettiva del compito. Sono sicuro che qualcuno suggerirà qualcosa.

Answer 3

Il problema principale è avere una semantica per la lingua che stai implementando - con ciò, l'implementazione diventa semplice. Altrimenti, questa domanda è incredibilmente ampia e di difficile risposta.

Answer 4

Consiglierei Essentials of Programming Languages ??come un buon complemento di SICP, in particolare se sei interessato agli interpreti: sito ufficiale EOPL. Potresti voler dare un'occhiata alla terza edizione - - il sito non è stato ancora aggiornato per questo.

Modifica: la prevenzione dello spam mi sta facendo scegliere tra i collegamenti, quindi la pagina ufficiale non è riscaldata. È facilmente in grado di Google, tuttavia.