Qual è il lavoro di una macchina virtuale del linguaggio e ne crea uno [chiuso]

6

Recentemente sono diventato incredibilmente interessato allo sviluppo del linguaggio. Nelle ultime settimane ho scritto molti frontend in lingua (lexer, parser) tra cui un parser di linguaggio / espressione calcolatrice e molto altro. Dopo aver creato tante cose che ho realizzato, DEVE esserci più astrazione tra l'analisi e l'esecuzione del codice rispetto a quello che attualmente ho, il che porta alla mia domanda principale (s).

La mia prima domanda è questa. Che cosa è esattamente il lavoro di una macchina virtuale del linguaggio, come ad esempio la JVM (ovviamente il mio sistema immaginato sarebbe molto, molto più piccolo). Che cosa fa? In realtà, emula l'hardware ed esegue istruzioni di basso livello sull'hardware emulato? O semplicemente fornisce un'astrazione ed esegue istruzioni gestite di livello inferiore sul sistema? (Ho letto questa domanda ma non ha mi ha davvero aiutato a capire)

Seconda domanda. Cosa è esattamente il codice byte? È una sorta di codice macchina per la macchina virtuale? O sono le istruzioni di assembly umano leggibili probabilmente come istruzioni e queste istruzioni sono eseguite direttamente o in qualche modo compilate in codice nativo?

Terza domanda. Come potrei fare per implementare questo? Mi considero un programmatore competente e non ho bisogno di istruzioni passo passo in alcun modo, solo una panoramica di cosa esattamente devo fare, e di quanto è basso questo livello.

Grazie mille per qualsiasi aiuto / suggerimento / spiegazione. Si prega di fare domande se qualcosa che ho dichiarato è stato confuso o avete bisogno di maggiori dettagli su di esso. Grazie ancora!

    
posta APott 02.09.2013 - 23:40
fonte

3 risposte

3

What exactly is the job of a language virtual machine, like for example the JVM? What does it do?

Una macchina virtuale è un programma in grado di eseguire codice macchina non destinato alla piattaforma utilizzata dal computer. Quindi, ad esempio, un computer Windows x86 può eseguire direttamente il codice macchina x86 di Windows, ma non può eseguire il bytecode Java. Ecco a cosa serve la JVM: colmare il divario, in modo che il tuo computer Windows x86 possa eseguire il bytecode Java.

Questo può essere utile se hai molti frontend (Java, Scala, Clojure, Jython, ...) e vuoi usare lo stesso codice per eseguirli (che per esempio significa che puoi scrivere molte ottimizzazioni solo una volta nella VM e usali da una qualsiasi delle lingue supportate).

Un altro buon motivo è se hai più backend (Windows, Linux, Android; x86, ARM, ...) e vuoi eseguire lo stesso (o quasi lo stesso) codice su tutti loro.

Does it actually sort of emulate hardware and execute low level instructions on the emulated hardware?

Tipo di. Non emula hardware specifico, ma emula hardware in grado di eseguire il bytecode.

What exactly is byte code? Is it some sort of machine code for the virtual machine?

Questo è esattamente quello che è.

Or is it the human readable possibly assembly like instructions

Questa è la rappresentazione leggibile dall'uomo del bytecode. La relazione è esattamente la stessa di, ad esempio, per l'assembly x86 e il codice macchina x86.

Quando le persone hanno bisogno di leggere o scrivere sul codice byte, lavorano quasi sempre con il formato leggibile. Ma la macchina virtuale lavora direttamente con il bytecode. Il punto importante è che la traduzione tra i due è 1-a-1: ogni istruzione nel leggibile per l'utente corrisponde esattamente a una singola istruzione nel bytecode.

and are these instructions directly executed or somehow compiled to native code?

Dipende dall'implementazione della macchina virtuale. Le macchine virtuali più semplici (e più lente) interpretano semplicemente il bytecode. VM più avanzate (come JVM o CLR desktop) compilano il bytecode nel codice macchina nativo per la piattaforma corrente e quindi lo eseguono. Ma l'unica differenza tra le due opzioni (o qualsiasi altra implementazione) è la prestazione.

How would I go about implementing this?

Come ho già detto, la VM più semplice è solo un interprete: legge le istruzioni del bytecode una alla volta e le esegue immediatamente. Penso che fare questo per qualcosa come il bytecode Java (o almeno un sottoinsieme decente di esso) non sarebbe difficile, anche se penso che sarebbe noioso.

Poiché JVM è basato sullo stack, potresti avere qualcosa come Stack<Object> per rappresentarlo. E istruzioni come incost_2 potrebbero semplicemente manipolare direttamente quella pila. (Ovviamente, le prestazioni di questa VM sarebbero pessime, ma non è questo il punto.)

    
risposta data 03.09.2013 - 00:54
fonte
2

After creating so many things I have realized there MUST be more abstraction between parsing and code execution than what I currently have, which leads to my main question(s).

Non proprio. In una tipica implementazione linguistica ad alte prestazioni di qualità industriale, in genere sono molte altre fasi, ma non è affatto una necessità. Interpreti semplici di tree-walking come MRI Ruby, ad esempio, in realtà solo lex, analizzano, quindi camminano sull'albero di sintassi astratto ed eseguono uno snippet di codice per ogni nodo visitato. Questo è tutto. Anche gli interpreti basati su linee più semplici non creano nemmeno un AST.

My first question is, this. What exactly is the job of a language virtual machine, like for example the JVM […].

La cosa più importante da capire è che una VM non è nulla di speciale. Una macchina virtuale è qualsiasi cosa che estrae completamente un'API da un'API diversa. Questo è tutto. Ad esempio, nella programmazione orientata agli oggetti (almeno nella forma immaginata da Alan Kay), ogni oggetto è una macchina virtuale.

Più specificamente nel contesto delle lingue: ogni lingua è una VM e ogni VM definisce una lingua.

In realtà l'unica differenza tra un linguaggio di programmazione e un set di istruzioni VM è intent : la sintassi di un linguaggio di programmazione è progettata per essere facilmente letta dagli umani, la semantica è progettata per esprimere elegantemente problemi complessi . La sintassi (formato) di un set di istruzioni VM è progettata per essere facilmente analizzata dalle macchine e la sua semantica è progettata per essere facilmente interpretata (o compilata) e anche facile da compilare a .

Ma ancora: un set di istruzioni VM è solo un linguaggio di programmazione come gli altri, ed è eseguito esattamente allo stesso modo di qualsiasi altro linguaggio di programmazione: interpretandolo o compilandolo in un linguaggio diverso che è già possibile interpretare.

What does it do? Does it actually sort of emulate hardware and execute low level instructions on the emulated hardware? Or does it simply provide an abstraction and execute lower level managed instructions on the system?

Dipende da ciò che vuoi che la VM faccia. Il set di istruzioni LLVM, ad esempio, è progettato per essere un codice macchina indipendente dalla macchina, se lo si desidera. Il suo obiettivo è quello di essere facilmente compilato in un codice macchina efficiente. Quindi, cerca di essere il più basso e vicino ai set di istruzioni della corrente principale della CPU (x86, AMD64, IA-64, SPARC, MIPS, ARM, ecc.) Senza legarlo a un set di istruzioni specifico della CPU.

Il set di istruzioni JVML OTOH è stato progettato per essere facilmente interpretato , e come tale è molto più alto del set di istruzioni LLVM. Il set di istruzioni CIL è ugualmente di alto livello come JVML, ma è stato progettato per essere compilato , e quindi fa alcune scelte diverse.

Second question. What exactly is byte code? Is it some sort of machine code for the virtual machine? Or is it the human readable possibly assembly like instructions,

Il codice byte è semplicemente il nome di una lingua in cui le istruzioni sono codificate come byte, anziché come testo. Questo è tutto.

Si noti che molte lingue erroneamente chiamate "codice byte" in realtà non lo sono. Ad esempio, sulla CLI, le istruzioni sono codificate come inte, non come byte, quindi CIL è un codice int, non un codice byte.

and are these instructions directly executed or somehow compiled to native code?

In entrambi. Tutti e due. Tu decidi. Il primo è chiamato "interpretazione", il secondo è chiamato "compilazione". A proposito: non è necessario per compilare codice nativo, puoi compilare qualsiasi cosa per cui hai un interprete o un compilatore. Ad esempio, la Fantom VM compila il proprio set di istruzioni su JVML o CIL, a seconda che venga eseguito sulla piattaforma Java o sulla CLI.

Ogni linguaggio può essere implementato da un compilatore e la lingua ogni può essere implementata da un interprete. I set di istruzioni VM non sono diversi. Ad esempio, ci sono JVM che interpretano il codice byte JVML, ci sono JVM che compongono il codice byte JVML nel codice nativo mentre il programma è in esecuzione, ci sono JVM che compongono il codice byte JVML nel codice nativo prima dell'esecuzione del programma, ci sono JVM che compila codice byte JVML in codice sorgente JavaScript e molti altri ancora. Esistono anche CPU che eseguono direttamente il codice byte JVML (che in realtà è solo un caso speciale della prima opzione, in cui l'interprete è implementato in silicio anziché software).

Third question. How would I go about implementing this? I consider myself a competent programmer and don't need step by step instructions by no means, just an overview of what exactly I need to be doing, and how low level this is exactly.

Un set di istruzioni VM è una lingua come qualsiasi altra lingua. Lo implementa esattamente come qualsiasi altra lingua:

  • l'analisi
  • analisi semantica
  • tipo inferenza
  • verifica del tipo
  • ottimizzazione
  • generazione del codice (per un compilatore) o esecuzione di codice (per un interprete)

La fase di analisi è solitamente banale, poiché i set di istruzioni VM sono progettati per essere facilmente analizzati. L'inferenza del tipo e il controllo del tipo del corso hanno senso solo se il set di istruzioni VM è stato digitato. L'ottimizzazione è facoltativa, se non si desidera creare una macchina virtuale ad alte prestazioni. OTOH, se fai vuoi costruire una macchina virtuale ad alte prestazioni, allora l'ottimizzazione è dove spenderai il 99,999% del tuo sforzo di sviluppo.

    
risposta data 03.09.2013 - 00:37
fonte
2

Riguardo alla terza domanda:

Una macchina virtuale è un programma che esegue un programma. Questo può variare dagli interpreti alle macchine virtuali in compilazione Just In Time.

Per imparare come scrivere una semplice VM, non hai bisogno di molto. La macchina SECD è un modello semplice che puoi adattare. Questo è in realtà un modello matematico che può essere utilizzato per ragionare sui programmi scritti nel calcolo lambda. È molto facile scrivere la tua versione e puoi implementare le chiusure abbastanza facilmente. Tuttavia, dovresti iniziare con una lingua raccolta automaticamente (preferibilmente in modo dinamico) per la tua sanità mentale (ad esempio Python, Perl, Ruby, Go o qualcosa della famiglia ML). Il SECD ha i seguenti stack:

  • S tack - dove si mantengono i valori intermedi
  • E nvironment - dove mantieni le mappature dei valori ID per le variabili
  • C ommand - dove mantieni le istruzioni
  • D ump, talvolta ortografato K ontinuation, di cui hai bisogno come secondo stack per il controllo del flusso.

Il modo in cui implementate le istruzioni dipende da voi: ho usato sia Vtables che il pattern Command con grande successo per le VM giocattolo.

Esiste un altro tipo di dati importante: la chiusura, che è solo una coppia di un ambiente e una lista di istruzioni.

Ora possiamo definire alcune istruzioni. Puoi implementare il set di istruzioni teoriche o uno dei tuoi progetti. Le istruzioni importanti che di solito implementano sono:

  • Const : inserisce un argomento costante nello stack.
  • Manipolazioni dello stack come Dup , Drop e Swap .
  • Aritmetica di base che prende gli argomenti dallo stack.
  • Ricerche variabili (e se sei pragmatico, anche un'operazione set ). Ogni mappa corrisponde a un livello di ambito. Per ricerche basate su stringhe: se non trovi l'ID nella prima mappa sullo stack Env, guarda nel prossimo. Ma spesso vengono utilizzati due numeri interi per identificare ciascuna variabile. Il primo indica l'ambito in cui è stata definita la var, il secondo il numero della variabile definita in tale ambito. Per esempio. in { var x; HERE } , x ha coordinate 0, 0 - prima variabile nello scope più esterno. Ma in { var x; { var y; var z; HERE } } , y ha coordinate 1, 0 - prima variabile nel secondo ambito.
  • Creazione di chiusura - di solito ha un argomento costante e lo combina con un puntatore all'Env corrente. La chiusura risultante viene posta sullo Stack.
  • Call - che accetta una chiusura e un (singolo) argomento dallo stack. Se si utilizzano indicatori di stack, è possibile implementare più argomenti. Ma se conosci il lambda calcolo, sai che non è necessario.

    Per chiamare la funzione, si salva l'ambiente corrente, il comando e lo stack corrente sul dump. Quindi si installa env dalla chiusura come nuovo Env e si spinge un nuovo ambiente vuoto su quello (l'ambito corrente). Installa gli argomenti nell'ambiente. Successivamente si installa una copia dei comandi dalla chiusura come nuovo comando. Infine, crei un nuovo Stack.

  • Return : inserisci un valore di ritorno dello Stack. Quindi, ripristina Command, Env e Stack dal dump. Spingi il valore di ritorno sullo Stack.

  • Le condizioni possono essere implementate facendo scoppiare un booleano e due chiusure dello stack, quindi posizionando di nuovo una chiusura in modo condizionale. Puoi quindi Call di quella chiusura.

Molti di questi possono essere implementati come sequenze di operazioni più piccole, ma le operazioni di cui sopra dovrebbero essere sufficienti per eseguire programmi completi di Turing. Un semplice programma come

fun myadd(x, y) { x + y }
var a = 40
var result = myadd(a, 2)

potrebbe essere tradotto nelle operazioni

Closure(2, [Var(1, 0), Var(1, 1), Add, Return]), Set(0, 0),
Const(40), Set(0, 1),
Var(0, 1), Const(2), Var(0, 0), Call, Set(0, 2)

dove Closure prende un argomento che specifica il numero di argomenti per la funzione da far apparire nello stack.

È molto facile compilare questi Op da una rappresentazione AST.

La VM attuale ora è solo un ciclo che fa apparire Ops dal comando, invoca l'implementazione corretta e si arresta quando il comando è vuoto:

# Perl, using an array for Op implementation lookup
method run {
    while (@$command) {
        $self->display_state if $debug;
        $OPCODES[pop @$command]->($self);
    }
}

// Go, using the Command Pattern, and immutability:
func (secd *Secd) Step() *Secd {
        // spew internal info if verbose
        if secd.Verbose() {
                secd.Report()
        }
        // termination and returns are handled by opcodes
        // pop and evaluate
        return secd.c.Pop().(Command).evaluate(secd)
}

for !secd.Finished() {
    secd = secd.Step()

Una volta che lasci i giocattoli e vuoi prestazioni reali, dovresti guardare probabilmente al LLVM. Mentre un SECD è vicino alla programmazione funzionale, il LLVM è molto vicino al metallo e rende più semplice l'espressione di programmi simili a C. Dopo aver ottenuto un po 'di teoria (modulo di assegnazione singola, nodi phi), puoi seguire il bel tutorial per implementare il caleidoscopio linguaggio giocattolo, che mette in mostra le caratteristiche più elementari. Un interessante linguaggio giovane che si basa sul LLVM per garantire che le prestazioni siano Julia - puoi guardare implementazione su GitHub per l'ispirazione.

    
risposta data 03.09.2013 - 06:33
fonte

Leggi altre domande sui tag