Come viene implementato lo Scoping Lexical?

Question

Un paio di anni fa ho iniziato a scrivere un interprete per un piccolo linguaggio specifico di dominio che includeva funzioni definite dal programmatore.

Inizialmente ho implementato l'ambito variabile utilizzando una semplice pila di tabelle di simboli. Ma ora voglio passare al giusto scope lessicale (con l'opzione delle chiusure). Qualcuno può spiegarmi o indicarmi una buona spiegazione della struttura dei dati e dell'algoritmo alla base dello scope lessicale?

Answer 1

Non esiste un unico modo corretto per farlo. L'importante è dichiarare chiaramente la semantica che stai cercando di fornire, quindi seguiranno le strutture e gli algoritmi di dati.

Answer 2

Per ottenere risultati corretti scoping lessicale e chiusure in un interprete, tutto quello che dovete fare è seguire queste regole:

• Nel vostro interprete, le variabili sono sempre guardato in una tabella di ambiente passata dal chiamante/mantenuto come variabile, non un env-stack globale. Cioè, eval(expression, env) => value.
• Quando il codice interpretato chiama una funzione, l'ambiente è NOT passato a quella funzione. apply(function, arguments) => value.
• Quando viene chiamata una funzione interpretata, l'ambiente in cui viene valutato il corpo è l'ambiente in cui è stata creata la definizione della funzione e non ha assolutamente nulla a che fare con il chiamante. Pertanto, se si dispone di una funzione locale, è una chiusura , ovvero una struttura dati contenente i campi {function definition, env-at-definition-time}.

elaborare tale ultimo bit in Python-ish sintassi:

x = 1 
return lambda y: x + y 

Viene eseguito come se fosse

x = 1 
return makeClosure(<AST for "lambda y: x + y">, {"x": x}) 

dove il secondo dict può essere la corrente-env piuttosto che una struttura dati costruita in quel momento. (D'altra parte, mantenere l'intero env piuttosto che solo le variabili chiuse può causare perdite di memoria.)

Answer 3

Leggi ad esempio The implementation of Lua 5.0.

Answer 4

Esistono molti modi diversi per implementare lo scoping lessicale. Qui ci sono alcuni dei miei preferiti:

• Se non avete bisogno di prestazioni super-veloce, utilizzare una struttura di dati puramente funzionale per implementare le tabelle di simboli, e rappresentano una funzione annidata da una coppia contenente un puntatore al codice e un puntatore alla tabella dei simboli.

• Se sono necessarie velocità del codice nativo, la mia tecnica preferita è descritta in Making a Fast Curry da Simon Marlow e Simon Peyton Jones.

• Se sono necessarie velocità del codice nativo, ma le funzioni non sono così importanti, considerare closure-passing style.

Answer 5

Stroustrup implementato questo in primo compilatore C++ semplicemente con una tabella di simboli al campo di applicazione, e una regola concatenamento seguita ambiti verso l'esterno fino a trovare una definizione.Come funziona esattamente dipende dalla tua semantica precisa. Assicurati di inchiodarli per primi.

Knuth in The Art of Computer Programming, Vol 1, fornisce un algoritmo per una tabella di simboli Cobol in cui l'ambito viene eseguito tramite collegamenti.