In che modo i linguaggi di programmazione definiscono le funzioni?

28

In che modo i linguaggi di programmazione definiscono e salvano funzioni / metodi? Sto creando un linguaggio di programmazione interpretato in Ruby e sto cercando di capire come implementare la dichiarazione delle funzioni.

La mia prima idea è di salvare il contenuto della dichiarazione in una mappa. Ad esempio, se ho fatto qualcosa di simile

def a() {
    callSomething();
    x += 5;
}

Quindi aggiungerei una voce nella mia mappa:

{
    'a' => 'callSomething(); x += 5;'
}

Il problema con questo è che diventerebbe ricorsivo, perché dovrei chiamare il mio metodo parse sulla stringa, che chiamerebbe di nuovo parse quando ha incontrato doSomething , e quindi avrei finito di stack space alla fine.

Quindi, come gestiscono le lingue interpretate?

    
posta Doorknob 05.09.2013 - 14:57
fonte

4 risposte

31

Sarei corretto nel presupporre che la funzione "parse" non solo analizzi il codice ma lo esegua allo stesso tempo? Se vuoi farlo in questo modo, invece di memorizzare il contenuto di una funzione nella tua mappa, memorizza la posizione della funzione.

Ma c'è un modo migliore. Ci vuole un po 'più di impegno in anticipo, ma produce risultati molto migliori con l'aumentare della complessità: usa un Abstract Syntax Tree.

L'idea di base è che si analizzi il codice una volta sola. Quindi hai un set di tipi di dati che rappresentano operazioni e valori e ne crei un albero, in questo modo:

def a() {
    callSomething();
    x += 5;
}

diventa:

Function Definition: [
   Name: a
   ParamList: []
   Code:[
      Call Operation: [
         Routine: callSomething
         ParamList: []
      ]
      Increment Operation: [
         Operand: x
         Value: 5
      ]
   ]
]

(Questa è solo una rappresentazione testuale della struttura di un ipotetico AST. L'albero attuale probabilmente non sarà in forma di testo.) Comunque, estrai il tuo codice in un AST e poi esegui il tuo interprete sul AST direttamente o usa un secondo ("code generation") pass per trasformare l'AST in qualche forma di output.

Nel caso della tua lingua, ciò che probabilmente faresti è avere una mappa che mappa i nomi di funzioni in funzione AST, invece di nomi di funzioni in stringhe di funzioni.

    
risposta data 05.09.2013 - 15:22
fonte
4

Non dovresti chiamare l'analisi dopo aver visto callSomething() (presumo tu intendessi callSomething piuttosto che doSomething ). La differenza tra a e callSomething è che una è una definizione di metodo mentre l'altra è una chiamata di metodo.

Quando vedi una nuova definizione, ti consigliamo di eseguire controlli correlati per assicurarti di poter aggiungere la definizione, quindi:

  • Verifica se la funzione non esiste già con la stessa firma
  • Assicurati che la dichiarazione del metodo sia eseguita nello scope appropriato (cioè i metodi possono essere dichiarati all'interno di altre dichiarazioni di metodo?)

Supponendo che questi controlli superino, puoi aggiungerlo alla tua mappa e iniziare a controllare il contenuto di quel metodo.

Quando trovi una chiamata al metodo come callSomething() , dovresti eseguire i seguenti controlli:

  • Esiste callSomething nella mappa?
  • Viene chiamato correttamente (il numero di argomenti corrisponde alla firma che hai trovato)?
  • Gli argomenti sono validi (se i nomi delle variabili sono usati, sono dichiarati? possono essere raggiunti in questo ambito?)?
  • È possibile chiamare Qualcosa da cui si chiama (è privato, pubblico, protetto?)?

Se trovi che callSomething() va bene, allora a questo punto ciò che vorresti fare in realtà dipende da come desideri affrontarlo. A rigor di termini, una volta che sai che una tale chiamata è a posto a questo punto, puoi solo salvare il nome del metodo e gli argomenti senza entrare in ulteriori dettagli. Quando esegui il tuo programma, invocherai il metodo con gli argomenti che dovresti avere in fase di runtime.

Se vuoi andare oltre, potresti salvare non solo la stringa ma un link al metodo attuale. Questo sarebbe più efficiente, ma se devi gestire la memoria, può diventare confuso. Ti consiglierei di tenere semplicemente la corda all'inizio. Più tardi puoi provare a ottimizzare.

Si noti che questo è tutto presupponendo che tu abbia scritto il tuo programma, il che significa che hai riconosciuto tutti i token nel tuo programma e sai cosa sono . Questo non vuol dire che tu sai se hanno ancora un senso insieme, che è la fase di analisi. Se non sai ancora quali sono i token, ti suggerisco di concentrarti prima sull'invio di tali informazioni.

Spero che questo aiuti! Benvenuto in Programmers SE!

    
risposta data 05.09.2013 - 15:19
fonte
2

Leggendo il tuo post, ho notato due domande nella tua domanda. Il più importante è come analizzare. Esistono molti tipi di parser (ad es. parser di discesa ricorsivo , LR Parsers , Packrat Parsers ) e generatori di parser (ad esempio GNU bison , ANTLR ) puoi utilizzare per attraversare un programma testuale "ricorsivamente" dato una grammatica (esplicita o implicita).

La seconda domanda riguarda il formato di archiviazione per le funzioni. Quando non stai facendo traduzione diretta alla sintassi , crei una rappresentazione intermedia del tuo programma, che può essere un < a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree"> albero sintattico astratto , o qualche linguaggio intermedio personalizzato, al fine di eseguire ulteriori elaborazioni con esso (compilare, trasformare, eseguire, scrivere su un file, ecc.)

    
risposta data 05.09.2013 - 15:16
fonte
1

Da un punto di vista generico, la definizione di una funzione è poco più di un'etichetta, o un segnalibro, nel codice. La maggior parte degli altri operatori di loop, scope e condizionali sono simili; sono stand-in per un comando base "jump" o "goto" nei livelli più bassi dell'astrazione. Una chiamata di funzione si riduce fondamentalmente ai seguenti comandi del computer di basso livello:

  • Concatena i dati di tutti i parametri, più un puntatore all'istruzione successiva della funzione corrente, in una struttura nota come "frame di stack di chiamate".
  • Spingi questo frame sullo stack di chiamate.
  • Passa all'offset di memoria della prima riga del codice della funzione.

Un'istruzione "return" o simile procederà come segue:

  • Carica il valore da restituire in un registro.
  • Carica il puntatore al chiamante in un registro.
  • Apre il frame dello stack corrente.
  • Vai al puntatore del chiamante.

Le funzioni, quindi, sono semplicemente astrazioni in una specifica del linguaggio di livello superiore, che consente agli esseri umani di organizzare il codice in modo più manutenibile e intuitivo. Quando viene compilato in un assembly o in un linguaggio intermedio (JIL, MSIL, ILX) e sicuramente quando viene eseguito il rendering come codice macchina, quasi tutte queste astrazioni spariscono.

    
risposta data 05.09.2013 - 20:00
fonte