In che modo Lisp può essere sia dinamico sia compilato?

Question

Okay, prima per ottenere questo fuori del modo: Ho letto la seguente risposta:

How is Lisp dynamic and compiled?

ma io non capisco la sua risposta.

In un linguaggio come Python, l'espressione:

x = a + b 

non può davvero essere compilato, come per il "compilatore" sarebbe impossibile conoscere i tipi di A e B (come i tipi sono conosciuti solo in fase di esecuzione), e quindi come aggiungerli.

Questo è ciò che rende impossibile compilare un linguaggio come Python senza dichiarazioni di tipo, corretto? Con le dichiarazioni, il compilatore sa che, ad es. aeb sono numeri interi e quindi sa come aggiungerli e tradurli in codice nativo.

Così come fa:

(setq x 60) 
(setq y 40) 
(+ x y) 

lavoro?

Compilato definito come compilazione nativa in tempo reale.

EDIT

In realtà, la questione è più sul fatto che i linguaggi dinamici senza dichiarazioni di tipo possono essere compilati, e se sì, come?

EDIT 2

Dopo molte ricerche (cioè browsing appassionato Wikipedia) credo di aver capito i seguenti:

• dinamici lingue digitati sono le lingue in cui i tipi sono controllati a run-time
• Le lingue statiche sono lingue in cui i tipi vengono controllati quando il programma è compilato
• dichiarazioni di tipo consentono al compilatore di rendere il codice più efficiente perché e invece di fare chiamate API per tutto il tempo in cui può utilizzare più "funzioni" native (ecco perché è possibile aggiungere dichiarazioni di tipo al codice Cython per accelerarlo, ma non è necessario, perché può ancora chiamare le librerie Python nel codice C)
• non ci sono tipi di dati in Lisp; quindi nessun tipo da controllare (il tipo è i dati stessi)
• Obj-C ha sia dichiarazioni statiche che dinamiche; i primi sono controllati al momento della compilazione, il secondo in fase di esecuzione

Correggimi se ho torto su uno dei punti sopra elencati.

Answer 1

Esempio di codice:

(setq x 60) 
(setq y 40) 
(+ x y) 

esecuzione con un interprete Lisp

In un Lisp basato interprete di cui sopra sarebbe di dati Lisp e l'interprete guarda ogni forma e corre il valutatore. Dal momento che è in esecuzione delle strutture dati Lisp, lo farà ogni volta quando si vede sopra il codice

• ottenere la prima forma
• abbiamo un'espressione
• si tratta di un setq forma speciale
• valutazione 60, il risultato è di 60
• cercare il luogo per la variabile x
• impostare la variabile x al 60
• ottenere la forma successiva ... ...
• abbiamo una chiamata di funzione per +
• valutare x -> 60
• valutare y -> 40
• chiamata la funzione + con 60 e 40 -> 100 ...

Ora + è un pezzo di codice che in realtà scopre cosa fare. Tipicamente Lisp ha diversi tipi di numeri e (quasi) nessun processore ha supporto per tutti quelli: fixnums, bignum, rapporti, complessi, float, ... Quindi la funzione + ha bisogno di scoprire quali tipi hanno gli argomenti e cosa può fare per aggiungili.

esecuzione con un compilatore Lisp

Un compilatore semplicemente emettere codice macchina, che farà le operazioni. Il codice macchina farà tutto ciò che fa l'interprete: controllare le variabili, controllare i tipi, controllare il numero di argomenti, chiamare le funzioni, ...

Se si esegue il codice macchina, è molto più veloce, poiché il Lisp le espressioni non devono essere guardate e interpretate. L'interprete dovrebbe decodificare ogni espressione. Il compilatore ha già fatto questo.

È ancora più lento di un codice C, poiché il compilatore non conosce necessariamente i tipi e emette semplicemente il codice completamente sicuro e flessibile.

Quindi questo codice Lisp compilato è molto più veloce dell'interprete che esegue il codice Lisp originale.

L'utilizzo di un compilatore Lisp ottimizzare

A volte non è abbastanza veloce. Quindi hai bisogno di un compilatore migliore e dì al compilatore Lisp che dovrebbe mettere più lavoro nella compilazione e creare codice ottimizzato.

Il compilatore Lisp potrebbe conoscere i tipi di argomenti e variabili. È quindi possibile indicare al compilatore di omettere i controlli di runtime.Il compilatore può anche supporre che + sia sempre la stessa operazione. Quindi può inline il codice necessario. Dal momento che conosce i tipi, può solo generare il codice per questi tipi: l'aggiunta di interi.

Tuttavia, la semantica di Lisp è diversa dalla C o dalla macchina. A + non si tratta solo di vari tipi di numeri, ma passerà automaticamente da piccoli numeri interi (fixnum) a interi interi (bignum) o errori di segnale su overflow per alcuni tipi. Si può anche dire al compilatore di ometterlo e basta usare una aggiunta intera nativa. Quindi il tuo codice sarà più veloce, ma non così sicuro e flessibile come il codice normale.

Questo è un esempio per il codice completamente ottimizzato, utilizzando l'implementazione 64 bit di LispWorks. Utilizza le dichiarazioni di tipo , dichiarazioni in linea e direttive di ottimizzazione. Si vede che dobbiamo dire al compilatore un po ':

(defun foo-opt (x y) 
    (declare (optimize (speed 3) (safety 0) (debug 0) (fixnum-safety 0)) 
      (inline +)) 
    (declare (fixnum x y)) 
    (the fixnum (+ x y))) 

Il codice (64bit codice macchina Intel) allora è molto piccolo e ottimizzato per quello che abbiamo detto al compilatore:

 0:  4157    push r15 
     2:  55    push rbp 
     3:  4889E5   moveq rbp, rsp 
     6:  4989DF   moveq r15, rbx 
     9:  4803FE   addq rdi, rsi 
     12:  B901000000  move ecx, 1 
     17:  4889EC   moveq rsp, rbp 
     20:  5D    pop rbp 
     21:  415F    pop r15 
     23:  C3    ret 
     24:  90    nop 
     25:  90    nop 
     26:  90    nop 
     27:  90    nop 

Ma tenere a mente al di sopra del codice fa qualcosa di diverso da ciò che l'interprete o il codice di sicurezza avrebbero fatto:

• calcola solo fixnums
• lo fa in silenzio ove rflow
• il risultato è anche un Fixnum
• lo fa senza il controllo degli errori
• non funziona per altri tipi di dati numerici

Ora il codice non ottimizzato:

 0:  49396275   cmpq [r10+75], rsp 
     4:  7741    ja L2 
     6:  4883F902   cmpq rcx, 2 
     10:  753B    jne L2 
     12:  4157    push r15 
     14:  55    push rbp 
     15:  4889E5   moveq rbp, rsp 
     18:  4989DF   moveq r15, rbx 
     21:  4989F9   moveq r9, rdi 
     24:  4C0BCE   orq r9, rsi 
     27:  41F6C107   testb r9b, 7 
     31:  7517    jne L1 
     33:  4989F9   moveq r9, rdi 
     36:  4C03CE   addq r9, rsi 
     39:  700F    jo L1 
     41:  B901000000  move ecx, 1 
     46:  4C89CF   moveq rdi, r9 
     49:  4889EC   moveq rsp, rbp 
     52:  5D    pop rbp 
     53:  415F    pop r15 
     55:  C3    ret 
L1: 56:  4889EC   moveq rsp, rbp 
     59:  5D    pop rbp 
     60:  415F    pop r15 
     62:  498B9E070E0000 moveq rbx, [r14+E07] ; SYSTEM::*%+$ANY-CODE 
     69:  FFE3    jmp rbx 
L2: 71:  41FFA6E7020000 jmp [r14+2E7]  ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB 
    ... 

Si può vedere che chiama una routine di libreria per fare l'aggiunta. Questo codice dovrebbe fare tutto l'Interprete. Ma non ha bisogno di interpretare il codice sorgente Lisp. È già compilato con le istruzioni della macchina corrispondenti.

Perché il codice Lisp compilato è veloce (er)?

Quindi, perché il codice Lisp compilato è veloce? Due situazioni:

• codice Lisp non ottimizzato: il sistema runtime Lisp è ottimizzato per strutture dati dinamiche e codice non deve essere interpretato

• codice Lisp ottimizzato: il compilatore Lisp bisogno di informazioni o inferisce e fa molto lavoro per emettere codice macchina ottimizzato.

Come programmatore Lisp, si consiglia di lavorare con il codice Lisp non ottimizzato, ma compilato, la maggior parte del tempo. È abbastanza veloce e offre molto comfort.

Diverse modalità di esecuzione di offrire scelta

Come programmatore Lisp abbiamo la scelta:

• interpretato codice: lento, ma più semplice per eseguire il debug
• codice compilato: veloce in fase di esecuzione, compilazione veloce, molti controlli del compilatore, leggermente più difficile da eseguire il debug, completamente dinamico
• codice ottimizzato: molto veloce in fase di esecuzione, possibilmente pericoloso in fase di esecuzione, un sacco di rumore compilazione di varie ottimizzazioni, lento compilazione

Tipicamente si ottimizzare solo le porzioni di codice che richiedono la velocità.

Ricorda che ci sono molte situazioni in cui anche un buon compilatore Lisp non può fare miracoli. Un programma orientato agli oggetti completamente generico (che utilizza il Common Lisp Object System) avrà quasi sempre un overhead (dispatching basato su classi di runtime, ...).

dinamicamente tipizzato e dinamico non sono la stessa cosa

Si noti inoltre che dinamicamente tipizzati e dinamica sono diverse proprietà di un linguaggio di programmazione:

• Lisp è dinamicamente tipizzati poiché i controlli di tipo sono eseguiti in fase di esecuzione e le variabili di default possono essere impostate su tutti i tipi di oggetti. Per questo Lisp ha anche bisogno di tipi allegati agli oggetti dati stessi.

• Lisp è dinamica perché sia ​​il Lisp linguaggio di programmazione e il programma stesso possono essere modificate in fase di esecuzione: siamo in grado di aggiungere, modificare e rimuovere le funzioni, possiamo aggiungere, modificare o rimuovere costrutti sintattici, possiamo aggiungere, modificare o rimuovere i tipi di dati (record, classi, ...), possiamo cambiare la sintassi di superficie di Lisp in vari modi, ecc. Aiuta anche Lisp a scrivere dinamicamente per fornire alcune di queste funzionalità.

Interfaccia utente: la compilazione e smontaggio

ANSI Common Lisp fornisce

• due funzioni standard per compilare il codice: compile e compile file
• una funzione standard per caricare sorgente o compilato codice: load
• una funzione standard per smontare il codice: disassemble

Answer 2

La compilazione è una semplice traduzione da una lingua all'altra. Se è possibile esprimere la stessa cosa nella lingua A e nella lingua B, è possibile compilare questa cosa espressa nella lingua A nella stessa cosa nella lingua B.

Una volta espresso l'intento in una lingua, viene eseguito con interpretato. Anche quando si fa C, o qualche altro compilato la lingua, la sua dichiarazione è:

1. Traduzione dal C -> linguaggio Assembly
2. Tradotto dal Assembly -> codice macchina
3. interpretato dalla macchina.

Un computer è in realtà un interprete per un linguaggio di base molto. Dal momento che è così semplice e così difficile da lavorare, le persone hanno trovato altri linguaggi con cui è più facile lavorare e possono essere facilmente tradotti in equivalenti istruzioni in codice macchina (ad esempio C). Quindi, è possibile dirottare la fase di compilazione eseguendo la traduzione "al volo" come fa il compilatore JIT o scrivendo il proprio interprete che esegue l'istruzione direttamente nel proprio linguaggio di alto livello (ad esempio LISP o Python).

Ma si noti che l'interprete è solo una scorciatoia per eseguire direttamente il codice! Se invece di eseguire il codice, l'interprete stampasse la chiamata che avrebbe fatto, avrebbe eseguito il codice, avresti ... un compilatore. Certo, sarebbe un compilatore molto stupido e non userebbe gran parte delle informazioni che ha.

I compilatori effettivi cercheranno di raccogliere quante più informazioni possibile dal programma intero prima di generare il codice. Per esempio, il seguente codice:

const bool dowork = false; 

int main() { 
    if (dowork) { 
     //... lots of code go there ... 
    } 
    return 0; 
} 

Sarà in teoria generare tutto il codice all'interno della filiale if. Ma un compilatore intelligente probabilmente lo considererà irraggiungibile e semplicemente lo ignorerà, facendo uso del fatto che conosce tutto nel programma e sa che dowork sarà sempre false.

In aggiunta a ciò, alcune lingue hanno tipi, che possono aiutare a inviare chiamate di funzione, assicurare alcune cose in fase di compilazione e aiuto per la traduzione al codice macchina. Alcune lingue come C richiedono il programmatore per dichiarare il tipo delle loro variabili. Altri come LISP e Python inferiscono il tipo della variabile quando è impostata, e vanno in panico in fase di runtime se si tenta di utilizzare un valore di un certo tipo se è richiesto un altro tipo (ad esempio se si scrive (car 2) nella maggior parte degli interpreti Lisp, sarà sollevare qualche errore che ti dice che una coppia è prevista). I tipi possono essere utilizzati per allocare la memoria in fase di compilazione (ad esempio, un compilatore C allocherà esattamente 10 * sizeof(int) byte di memoria se è necessario allocare un int[10]), ma questo non è esattamente richiesto. In effetti, la maggior parte dei programmi C usa puntatori per memorizzare array, che sono fondamentalmente dinamici. Quando si ha a che fare con un puntatore, un compilatore genererà/collegherà al codice che, in fase di esecuzione, eseguirà i necessari controlli, riallocazioni, ecc. Ma la linea di fondo è che la dinamica e la compilazione non devono essere contrastate. Gli interpreti Python o Lisp sono programmi compilati, ma possono comunque agire su valori dinamici. In effetti, il linguaggio assembly non è tipizzato, poiché il computer può eseguire qualsiasi operazione su qualsiasi oggetto, poiché tutto ciò che "vede" sono flussi di bit e operazioni su bit.I linguaggi di livello superiore introducono tipi e limiti arbitrari per rendere le cose più leggibili e impedirti di fare cose completamente pazze. Ma questo è solo per aiutarti a, non un requisito assoluto.

Ora che la declamazione filosofica è finita, diamo un'occhiata a tuo esempio:

(setq x 60) 
(setq y 40) 
(+ x y) 

E proviamo a compilare che a un programma C valido. Una volta fatto, i compilatori C abbondano, quindi possiamo tradurre LISP -> C -> linguaggio macchina, o praticamente qualsiasi altra cosa. Tieni presente che la compilazione è solo una traduzione (anche le ottimizzazioni sono interessanti, ma facoltative).

(setq 

Assegna un valore. Ma non sappiamo cosa viene assegnato a cosa. Continuiamo

(setq x 60) 

Ok, stiamo allocando da 60 a x. 60 è un valore letterale intero, quindi il suo tipo C è int. Poiché non v'è alcun motivo di ritenere x è di un altro tipo, questo è equivalente alla C:

int x = 60; 

Analogamente per (setq y 40):

int y = 40; 

Ora abbiamo:

(+ x y) 

+ è una funzione che, a seconda delle implementazioni, può richiedere diversi tipi di argomenti, ma sappiamo che x e y sono numeri interi. I nostri compilatori sa che esiste una dichiarazione C equivalente, che è:

x + y; 

Così abbiamo appena interpretarlo. Il nostro programma C finale:

int x = 60; 
int y = 40; 
x + y; 

Che è un programma C perfettamente valido. Può diventare più difficile di così. Ad esempio, se x e sono molto grandi, la maggior parte dei LISP non permetterà loro di overflow mentre C lo farà, quindi potresti codificare il tuo compilatore in modo che abbia il proprio tipo intero come array di ints (o qualsiasi cosa tu trovi rilevante). Se si è in grado di definire le operazioni più comuni (come +) su questi tipi, il nuovo compilatore sarà forse tradurre il codice precedente in questo, invece:

int* x = newbigint("60"); 
int* y = newbigint("40"); 
addbigints(x, y); 

Con le funzioni newbigint e addbigints definiti altrove, o generati dal compilatore . Sarà ancora valido C, quindi verrà compilato. In effetti, il tuo interprete è probabilmente implementato in un linguaggio di livello inferiore e ha già rappresentazioni per oggetti LISP nella sua stessa implementazione, quindi può utilizzarle direttamente.

Tra l'altro, questo è esattamente ciò che il compilatore Cython fa per il codice Python :)

È possibile definire tipi staticamente in Cython per ottenere po 'di velocità/ottimizzazioni in più, ma non è necessario. Cython può tradurre il tuo codice Python direttamente in C, e poi in codice macchina.

Spero che sia più chiaro!Ricorda:

1. Tutto il codice è interpretato, alla fine
2. compilatori tradurre codice in qualcosa che è più facile/più veloce da interpretare. Spesso eseguono ottimizzazioni lungo il percorso, ma questo non fa parte della definizione