Crea il tuo forum GRATIS su GlobalFreeForum.com.

Progettiamo e implementiamo un interprete

In questa sezione avverranno le discussioni sulla scienza e sulle arti. Si possono chiedere pareri e spiegazioni o postare i propri pensieri a riguardo di un argomento. Qui potete postare spiegazioni su un qualsiasi argomento: matematica, chimica, lingue etc...

Moderatori: Gruppo Admin, Gruppo Mod

Progettiamo e implementiamo un interprete

Messaggioda Flame_Alchemist » 18/07/2012 - 19:01

(Tutto il codice è qui: https://github.com/mbal/tripping-archer)

In questi giorni sul forum si è parlato di linguaggi di programmazione e in particolare dell'implementazione di uno. Siccome ho visto un esempio abbastanza brutto (e un po' di idee non perfettamente chiare), ho pensato di scrivere un minitutorial sull'argomento. Ne approfitto anche per allenarmi in scrittura cieca, quindi se vedete errori che sono sfuggiti al correttore, è perché sto facendo pratica.

Allora, implementeremo un linguaggio disegnato per l'occasione, ispirato a LISP, quindi un linguaggio funzionale basato su liste, in notazione prefissa. Ho deciso che si chiamerà Turing, visto che quest'anno è il centesimo anniversario dalla sua nascita. L'interprete sarà scritto in Python, ma con non troppa difficoltà si sarebbe potuto usare C, Java o qualunque altra cosa.

Un po' di motivazione
O: tanto non scriverò mai un interprete
Prima di cominciare a disegnare il nostro linguaggio, parliamo un po' degli interpreti: a cosa servono? Sicuramente il loro scopo principale è eseguire dei linguaggi di programmazione, ma si possono pensare altri scenari in cui sono utili?

Alcuni scenari
    1. Si deve riformattare il codice per seguire delle linee guida differenti. Per risolvere questo problema ci sono tre alternative: o si rinizia a scrivere tutto a mano, osservando le convenzioni, o si scrive un piccolo interprete che lo fa per te, o ancora si ricatta chi decide le convenzioni per ritornare alla vecchia.
    2. Estrarre i commenti da del codice, ma il programma che lo fa dà problemi sul 50% del tuo codice. Anche qua tre alternative: lasci perdere tutto, oppure scrivi al programmatore del programma originario, sperando che lo risolva in poco tempo, o ancora lo sistemi te. Se decidi di aggiustarlo te, beh, stai scrivendo un interprete.
    3. Convertire un documento. Questo testo è stato scritto tutto in VIM, aggiungendo poche informazioni su dimensione testo, grassetti e corsivi utilizzando un piccolo linguaggio di markup; quando avrò finito lo passerò attraverso un correttore e l'interprete di questo linguaggio, ottenendo del codice html (o bbcode per il forum). Molto più veloce che convertire a mano e più semplice che scrivere direttamente in html.

Da questo piccolo elenco possiamo identificare cos'è un inteprete. Il problema è che siamo davanti ad una struttura molto generale: ha poco a che fare con i linguaggi di programmazione! Quindi, in prima approssimazione un interprete è un programma che prende un testo, lo elabora e fa qualcosa in base a quello che legge.
Possiamo immaginarlo diviso in due fasi: parsing e esecuzione.

Parsing
Il componente che si occupa del parsing riceve come input il programma, in forma di testo, verifica che soddisfi le regole sintattiche del linguaggio e lo traduce in una rappresentazione interna.
Woohh, stop!
Lo so, tante parole difficili per una frase. Quindi, proviamo a spiegare.
Le regole sintattiche sono un insieme di regole da rispettare per produrre codice valido, ma non necessariamente corretto. Proprio come in matematica l'espressione 2x+*5=0 non è valida, anche certi programmi non sono validi.
Con rappresentazione interna invece intendiamo un modo speciale per scrivere un programma che può essere capito facilmente nelle fasi successive.

La funzione che fa il parsing si chiamerà, con molta fantasia, parse.
Questa fase possiamo, per semplicità, pensarla ancora divisa in 2 parti: la fase di tokenizzazione e la fase di analisi vera e propria.
Nella prima fase spezziamo la stringa nei suoi pezzi fondamentali, mentre nella seconda avverà la traduzione in rappresentazione interna.

Esecuzione
Qui è già più facile. In fase di esecuzione il nostro interprete legge la rappresentazione interna e decide cosa fare. Chiameremo la funzione che si occupa dell'esecuzione evaluate.

E i compilatori?
In via puramente teorica non c'è grande differenza tra interpreti e compilatori. La definizione formale di compilatore è: programma che converte un programma scritto in linguaggio L in un secondo programma scritto in linguaggio M.
Ok, quindi nel nostro caso L sarebbe Turing, e M? M è un linguaggio che può essere eseguito da una macchina. Una macchina è tutto ciò che può portare avanti computazione: il PC è una macchina, Python è una macchina, VIM è una macchina. Se potessi dimostrare che la macchina per fare il caffè può effettuare computazione (gli informatici amano dire è Turing-completa) potrei scrivere un compilatore per essa.
Ok, ho un po' divagato: più avanti vedremo che linguaggio sarà M.

Bene. La fase di teoria preliminare è finita, possiamo iniziare a preoccuparci realmente del linguaggio.

7 assiomi
Come LISP anche Turing avrà un core abbastanza minimale, con poche primitive (o assiomi, come amano chiamarli). Queste funzioni vengono dette primitive perché non possono essere implementate nel linguaggio. Ci servono i lacci degli scarponi da cui tirarlo su. Per il momento ne ho trovate 7, anche se 3 potrebbero essere eliminate e implementate più avanti, direttamente nel nostro linguaggio (quali sono?, in fondo troverete la risposta).
    1. (atomo? x) ritorna vero se l'elemento x è un atomo (cioè non è una lista).
    2. (crea x) è semplicemente una funzione che ritorna x. Detta così non sembra molto utile. In realtà servirà perché dobbiamo introdurre un modo per distinguere i dati dal codice. Noi lo useremo per creare liste, principalmente.
    3. (eq? x y) ritorna vero se x e y sono lo stesso atomo. Non funziona sulle liste.
    4. (primo x) se x è una lista, ne ritorna il primo elemento.
    5. (resto x) ritorna tutta la lista x privata del primo elemento.
    6. (costruisci x y) aggiunge x a y, creando una lista. y deve già essere una lista.
    7. (cond (p-1 e-1) (p-2 e-2)... (p-n e-n)) è una espressione condizionale. Ritorna e-k se p-k è vero. Esiste la condizione speciale else che viene sempre valutata vera.

E il resto?
Cos'altro ci serve in un linguaggio di programmazione? Ricordiamo che vogliamo un linguaggio molto piccolo, quindi dobbiamo aggiungere caratteristiche con molta parsimonia.
Direi che per il momento serve ancora: un modo per assegnare un valore alle variabili e le funzioni. Possiamo evitare for e while? Probabilmente ce la possiamo cavare con la ricorsione; è una rinuncia abbastanza pesante, ma faremmo di tutto pur di non introdurre ulteriore complessità nel nostro interprete. In generale non perdiamo nulla in termini di capacità, solo che siamo meno abituati ad usare la ricorsione.
Introduciamo quindi l'istruzione (define x y) che assegna ad x il valore y e l'istruzione (lambda (x y z ...) (body)) che crea una funzione, senza nome, che accetta come argomenti x, y, z eccetera e fa le cose definite in (body).
Una cosa piuttosto interessante è che non c'è modo, all'interno di Turing, di distinguere funzioni da variabili definite. Possiamo pensare ad una variabile come ad una funzione senza argomenti.

Questi non sono assiomi, ma perché?
Una risposta a questa domanda è piuttosto complicata, perché per arrivare a capire veramente la motivazione si dovrebbe introdurre il concetto di macro di LISP, che ricordano le macro in C, ma sono molto più potenti. Per questo articolo ci accontenteremo di una definizione molto semplice: sono funzioni particolari che possono modificare il codice durante l'esecuzione.
In questo caso è necessario che queste funzioni modifichino il codice perché devono aggiungere o una funzione o una espressione generica (rispettivamente nel caso di lambda o define) nel nostro interprete. Se riguardate le definizioni degli assiomi vedete che nessuno di essi fa una cosa del genere.
(A dir la verità anche cond potrebbe essere considerata una macro -- e in generale lo è --, e il vero punto 7 dovrebbe diventare if, ma cond risulta spesso più utile, inoltre è in accordo con le specifiche originarie di LISP).

Inoltre aggiungeremo una parola chiave, (blocco (istr-1) (istr-2) ... (istr-n)) per indicare i blocchi del programma. Ogni programma dovrà essere scritto all'interno di un blocco. Questa istruzione provoca l'esecuzione di tutte le istruzioni, ma ritorna solo il valore dell'ultima.

Ok, per ora non ci viene in mente niente altro, quindi fermiamo la fase progettuale e vediamo se riusciamo a scrivere un po' di codice, cercando di arrivare ad avere un interprete che fa tutto quello descritto finora.

La sintassi
Purtroppo ci siamo scontrati nuovamente con qualcosa da definire: la sintassi. Per fortuna è piuttosto semplice. Organizzeremo i nostri programmi in liste di istruzioni, dove il primo elemento sarà una funzione, e gli altri saranno gli argomenti. Anche un solo elemento, un atomo, è un programma valido.
8 è valido.
(+ 8 4) è un programma sintatticamente valido
(8 4 1) no.
(definisci ottuplica (lambda (x) (* x 8))) è valido: definisce ottuplica come una funzione che prende un solo argomento e ritorna il prodotto per 8.
Come si intuisce dall'ultimo esempio le istruzioni possono essere arbitrariamente innestate.

Visto che la nostra sintassi è molto semplice anche la funzione parse sarà facile. La rappresentazione interna è anche semplice, infatti tradurremo liste di Turing in liste di Python.
Il nostro M di cui parlavamo prima è quindi un linguaggio intermedio che assomiglia a qualcosa del genere:
Codice: Seleziona tutto
[/ [+ [* 8 2] [- 7 5] 3]]

Naturalmente sono possibili più o meno infinite rappresentazioni, questa è la più semplice, un'altra molto usata è la codifica ad albero, che risulta più difficile da costruire ma rimane tutto sommato semplice in esecuzione (o traduzione, se consideriamo un compilatore).

Finalmente programmiamo
Parsing
Possiamo finalmente iniziare a scrivere il codice che si occupa del parsing. Nella maggior parte dei linguaggi di programmazione la fase di parsing è spesso molto complicata, fortunatamente, nel nostro caso, la sintassi non ha casi particolari, quindi diventa facile.
Codice: Seleziona tutto
def tokenize(expr):
    expr = expr.replace('(', ' ( ').replace(')', ' ) ')
    return expr.split()

def rep(tokens):
    return t(tokens, 0)

def t(tokens, k):
    if len(tokens) == k:
        raise SyntaxError("Errore! Incontrato EOF")
    tok = tokens[k]
    if tok == '(':
        i = k = k+1
        l = []
        while tokens[i] != ')':
            res, n = t(tokens, i) #analizzo ogni token in cui è divisa la stringa
            l.append(res)         #ritorna: una rappresentazione del token e la sua lunghezza
            i = n
        return l, i+1
    elif tok == ')':
        raise SyntaxError(") non attesa")
    else:
        return parse_atom(tok), k+1

def parse_atom(t):
    try:
        return int(t)
    except ValueError:
        try: return float(t)
        except ValueError: return t

Un paio di esempi di conversione:
Codice: Seleziona tutto
(+ 8 4) = ['+', 8, 4]
(+ (* 8 2) 4) = ['+', ['*', 8, 2], 4]


Ora siamo riusciti a fare il parsing di una stringa arbitrariamente innestata di codice. Il prossimo passo è quindi l'esecuzione.

Esecuzione
Dato un programma in rappresentazione interna ci basta:
    1. vedere che operazione compiere in base all'operatore in prima posizione nella lista.
    2. estrarre il primo argomento, se necessario valutarlo (in maniera ricorsiva)
    3. estrarre il secondo argomento, valutare anch'esso (anche qui, con ricorsione)
    4. effettuare l'operazione
Tornando sulla definizione dei compilatori data sopra: anche questa funzione è una macchina.

Gestione variabili
Fino a qui è tutto abbastanza semplice, possiamo fare tutto con degli if nella funzione evaluate. Una cosa più complicata da fare è gestire le variabili. Dobbiamo quindi pensare a che struttura dati utilizzare e come gestire i vari ambienti: ci sarà un solo ambiente per tutto? oppure conviene creare un ambiente nuovo per ogni funzione?
La maggior parte dei linguaggi di programmazione usa la seconda opzione, anche perché scegliendo la prima si incontrano diversi problemi.
Python mette a disposizione una struttura dati, chiamata dizionari (o hash-table) che fa proprio quello che fa al caso nostro: permette di associare un nome a un valore.
Ci sarà il dizionario di livello massimo, cioè l'insieme delle variabili e funzioni globali, e ogni funzione ne avrà uno suo, che invece conterrà tutte le cose definite nel blocco della funzione stessa. Si avrà una gerarchia, quindi ognuno potrà accedere ai dizionari più elevati, ma non si potrà mai scendere. Quando una funzione vuole una variabile per prima cosa cercherà nel suo dizionario, e se non trova, sale di un livello, per cercare nel dizionario dell'ambiente in cui è definita.
Per esempio, quindi
Codice: Seleziona tutto
(define h 10)
(define area (lambda (b h) (* b h)))
(define area2 (lambda (b) (* b h)))
(area 2 3)

Ritornerà 6, perchè area troverà la variabile h definita nel proprio dizionario
Codice: Seleziona tutto
(area2 2)

Invece, ritornerà 20, perché, visto che non trova la variabile h nel suo dizionario locale, sale di un livello, e la trova nel dizionario globale, dove è definita a 10.
Con queste considerazioni, si arriva a produrre il codice:
Codice: Seleziona tutto
def evaluate(e, environment):
    if isinstance(e, str):
        return environment.find(e)[e]
    elif not isinstance(e, list):
        return e
    elif e[0] == 'atomo?':
        return atom(evaluate(e[1]), environment)
    elif e[0] == 'crea':
        return e[1]
    elif e[0] == 'eq?':
        op1 = evaluate(e[1], environment)
        op2 = evaluate(e[2], environment)
        return (op1 == op2) and atom(op1)
    elif e[0] == 'primo':
        return evaluate(e[1:], environment)[0]
    elif e[0] == 'resto':
        return evaluate(e[1:], environment)[1:]
    elif e[0] == 'costruisci':
        exp1 = evaluate(e[1], environment)
        exp2 = evaluate(e[2], environment)
        return [exp1] + exp2
    elif e[0] == 'blocco':
        exps = [evaluate(x, environment) for x in e[1:]]
        return exps[-1] #valuta ogni espressione, ma ritorna il valore solo dell'ultima
    elif e[0] == 'null?':
        return evaluate(e[1], environment) == []
    elif e[0] == 'cond':
        for (predicato, expr) in e[1:]:
            if predicato == 'else': #else è sempre vero
                return evaluate(expr, environment)
            if evaluate(predicato, environment):
                return evaluate(expr, environment)
    elif e[0] == 'define':
        name = e[1]
        body = e[2]
        environment[name] = evaluate(body, environment)
    elif e[0] == 'lambda':
        vals = e[1]
        body = e[2]
        return lambda *args: evaluate(body, Env(vals, args, environment)) #siccome lambda crea funzioni, dobbiamo fornirgli un ambiente nuovo.
    elif e[0] == 'tempo':
        start = time.time() 
        r = evaluate(e[1], environment)
        print("%.5f" %(time.time()-start))
        return r
    else:
        exps = [evaluate(exp, environment) for exp in e]
        proc = exps.pop(0)
        try:
            return proc(*exps)
        except TypeError: #questo errore avviene quando proc non è una funzione, ma una lista o un valore booleano.
            return proc


Abbiamo aggiunto alcune cose nella nostra evaluate di cui non avevamo parlato prima, cioè:
    1. tempo. (tempo operazione) misura il tempo che impiega l'operazione ad essere eseguita
    2. (null? x), controlla se x è la lista vuota. Siccome è un predicato molto utile lo aggiungiamo qua.

Veramente finito
Ok, questo è davvero l'ultimo capitolo: lo sfrutterò per tirare un po' le fila lasciate in sospeso qua e là.
Prima di tutto, come forse avete notato, quello inserito finora non è il codice completo, questo perché inserito avrebbe reso troppo lungo il post. Tutto il codice lo potete trovare qua.
Come avete visto disegnare e implementare un linguaggio è un duro lavoro. Nonostante questo la fase di implementazione è stata abbastanza breve, perché:
    1. il nostro linguaggio è abbastanza piccolo, ma ancora più importante
    2. la fase di progettazione di un linguaggio di programmazione deve sempre essere molto lunga, se si vuole qualcosa ben fatto.

Quanto è piccolo/veloce/completo/buono questo linguaggio?
    1. Piccolo: beh, è davvero piccolo. Pochi Kb di sorgente. Certo, il fatto che sia scritto in python aiuta, rifare lo stesso procedimento in Java dà luogo ad un programma lungo circa 5/10 volte tanto.
    2. Veloce. Purtroppo non è velocissimo. Dobbiamo ricordarci che è comunque una VM che viene eseguita da una VM. Comunque per un progetto giocattolo scritto in pochi giorni è più che sufficiente.
    3. Completo. Comparandolo ad un vero linguaggio di programmazione non ne esce troppo bene. Gli mancano commenti, tipi di dato veri, svariate funzioni ormai considerate necessarie, e tante altre cose, ma si possono implementare facilmente (o quasi).
    4. Buono, beh questo dovete deciderlo voi. Credo che per realizzare un breve tutorial abbia servito il suo scopo abbastanza bene.

Possiamo andare oltre?
Certo:
    1. La mia idea base era di implementare un ulteriore livello di astrazione, realizzando un interprete Turing in Turing stesso, realizzando ciò che viene definito meta-circular evaluator, realizzando quasi completamente la famosa pagina 13 del manuale LISP. Non è complicato, in fondo basta reimplementare la funzione evaluate che abbiamo scritto in Python nel nostro linguaggio, ma questo articolo sarebbe diventato molto più lungo.
    2. Si può entrare nel mondo delle ottimizzazioni dell'interprete. Una particolarmente utile nel nostro caso (e in tutti i linguaggi funzionali) è la tail-call optimization, che permette all'interprete di eliminare la ricorsione sotto alcune ipotesi. Solo con questa possiamo giungere ad ottenere delle performance molto migliori e evitare la morte dell'interprete quando si vogliono eseguire un buon numero chiamate ricorsive.
    3. Una altra cosa piuttosto interessante da aggiungere è un buon modo per riportare gli errori, visto che al momento è abbastanza inesistente. Purtroppo non vedo una strada semplice per farlo in modo generale (gli unici errori che si possono segnalare in maniera relativamente facile sono la mancanza di una parentesi e simbolo sconosciuto).
    4. Riuscire ad emettere del codice nativo per una piattaforma, una specie di assembler o un bytecode per JVM, potrebbe essere interessante, ma nemmeno questo è semplicissimo, considerando che nonostante il linguaggio sia molto piccolo è anche moderatamente espressivo.

Stai imbrogliando, hai usato Python
O, Python è un linguaggio di alto livello, quindi ottieni tanto gratis
Programs must be written for people to read, and only incidentally for machines to execute.

E' vero: mi sono basato abbastanza sulle caratteristiche di Python, primi fra tutti i tipi di dato e il garbage collector. Ma lo scopo principale è mostrare come creare un interprete, e secondo me Python se l'è cavata bene. Non è un caso la citazione aggiunta a questa sezione :)

Ehi, ci devi una risposta
Non l'abbiamo fatto perchè significa introdurre un calo di performance piuttosto importante, ma le tre funzioni sono (costruisci x y), (primo x) e (resto x), e potrebbero essere implementate in Turing in questo modo:

Codice: Seleziona tutto
(define mio-costruisci
  (lambda (x y)
    (lambda (m) (m x y))
    )
  )
(define mio-primo (lambda (x) (x (lambda (p q) p))))
(define mio-resto (lambda (x) (x (lambda (p q) q))))

(define a (mio-costruisci (crea 1) (crea 2))
(mio-primo a) #ritorna 1
(mio-resto a) #ritorna 2


Questa è una costruzione piuttosto avanzata, che non si vede nei normali linguaggi di programmazione, principalmente perché non possiamo ritornare funzioni (o si può con molte limitazioni). In Turing invece, non abbiamo questa restrizione. La funzione costruisci ritorna una funzione che accetta un argomento; e questo argomento è a sua volta una funzione che verrà applicata ai due elementi passati a costruisci.
Con questo ultimo assaggio di linguaggi funzionali penso di aver finito (e credo di non aver detto troppe cose sbagliate); spero vi sia piaciuto e abbiate capito un po' meglio l'argomento linguaggi di programmazione.

Ho implementato alcuni algoritmi classici (un paio di funzioni tipiche della programmazione funzionale, potenza con complessità logaritmica, un algoritmo di bisezione più alcune cose miste): li troverete nel prossimo post, in modo che possiate giocare un po' con l'interprete e vedere la sintassi.
Potete caricare il file dando python turing.py nome_programma.tur, si aprirà un prompt interattivo dove potete chiamare le funzioni definite nel file e definire le vostre, attenti però perché non supporta l'andata a capo, dovete definire una procedura su una singola linea, oppure inserirle in un file.

PS: Talk is cheap, show me the code
Potete trovare tutto il codice sul mio repo git (https://github.com/mbal/tripping-archer), così lo scaricate in fretta.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Progettiamo e implementiamo un interprete

Messaggioda Flame_Alchemist » 18/07/2012 - 19:02

Codice: Seleziona tutto
(blocco
  (define fibonacci
    (lambda (n) (cond ((= n 1) 1)
                      ((= n 2) 1)
                      (else (+ (fibonacci (- n 1)) (fibonacci (- n 2))))
                      )
      )
    )

  (define pow
    (lambda (a b) (cond ((= b 0) 1)
                        ((= (modulo b 2) 0) (square (pow a (/ b 2))))
                        (else (* a (pow a (- b 1))))
                        )
      )
    )

  (define square
    (lambda (a) (* a a)))

  (define abs
    (lambda (x) (cond ((< x 0) (- 0 x))
                      (else x))))

  (define map
    (lambda (f seq) (cond ((null? seq) (crea ()))
                          (else (costruisci (f (primo seq)) (map f (resto seq))))
                          )
      )
    )

  (define filter
    (lambda (pred seq)
                         (cond ((null? seq) (crea ()))
                             ((= (pred (primo seq)) True) (costruisci (primo seq) (filter pred (resto seq))))
                             (else (filter pred (resto seq)))
                             )
      )
    )

  (define range
    (lambda (start stop)
      (cond ((> start stop) (crea ()))
            (else (costruisci start (range (+ 1 start) stop)))
            )
      )
    )

  (define accumulate
    (lambda (op va_iniziale seq) (cond ((null? seq) va_iniziale)
                                       (else (op (primo seq) (accumulate op va_iniziale (resto seq))))
                                       )
      )
    )

  (define fattoriale
    (lambda (n) (accumulate * 1 (range 2 n))))

  (define bisezione
    (lambda (f pos neg e)
            (blocco
              (define midpoint (/ (+ pos neg) 2))
              (cond ((< (abs (f midpoint)) e) midpoint)
                    ((> (f midpoint) 0) (bisezione f midpoint neg e))
                    (else (bisezione f pos midpoint e))
                  )
              )
            )
    )

  (define sqrt
    (lambda (n)
      (bisezione (lambda (x) (- (* x x) n)) n 0.0 0.00000000001)
      )
    )
)

Questo è il codice di prova dell'interprete. Come ho detto nel post sopra, potete caricarlo in Turing e chiamare le funzioni normalmente, usando la sintassi (funzione arg1 arg2...).
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Progettiamo e implementiamo un interprete

Messaggioda Style { HdS619 } » 19/07/2012 - 10:19

Complimenti bellissimo articolo e l'hai spiegato, imho, in modo chiaro! nulla da aggiungere :)

P.s.: A quando un esempio di compilatore? :P
Il mio sito personale

Without freedom of choice there is no creativity.
Without creativity, there is no life.


---
Ogni volta che usi un goto un unicorno muore. - Flame Alchemist
Avatar utente
Style { HdS619 }
Gold Member
Gold Member
 
Messaggi: 3073
Iscritto il: 12/05/2007 - 18:30
Località: Lecce

Re: Progettiamo e implementiamo un interprete

Messaggioda Flame_Alchemist » 20/07/2012 - 11:40

A dir la verità avevo una mezza idea di farlo, ma non posso promettere niente.
Comunque se guardi, quasi ogni libro che parla di LISP come ultimo capitolo presentano un compilatore di LISP scritto in LISP (così su due piedi mi viene in mente il PAIP di Norvig e SICP -- il wizard book)
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Progettiamo e implementiamo un interprete

Messaggioda crap0101 » 27/07/2012 - 00:01

bravo! molto bello! e anche spiegato semplicemente ma senza essere (troppo) superficiale.
btw, Nonostante sia 'solo' un esempio trovo affascinante quello che si può fare (e, divagando, introspezione ecc..) e, in certi casi, con che - apparente - semplicità.
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
Avatar utente
crap0101
Utente
Utente
 
Messaggi: 392
Iscritto il: 02/01/2008 - 03:43
Località: ora sono qua

Re: Progettiamo e implementiamo un interprete

Messaggioda Freedom » 28/07/2012 - 00:19

io ti consiglierei piuttosto di definire in modo più rigoroso la grammatica
e poi affidarti a Flex e Bison per la generazione di parser e compilatore!
Avatar utente
Freedom
Utente
Utente
 
Messaggi: 230
Iscritto il: 06/12/2006 - 19:42

Re: Progettiamo e implementiamo un interprete

Messaggioda Flame_Alchemist » 28/07/2012 - 06:45

In realtà (nemmeno un vero) LISP ha sintassi (oltre alla regola (op arg1 arg2 ...)), quindi c'era poco da usare generatori di parser o altre cose. Nonostante sia molto piccolo, l'interprete lì sopra implementa una buona percentuale di un linguaggio funzionale (le cose principali lasciate fuori sono le monadi, che non servivano siccome non è puro, le macro, che non sono una cosa essenziale, e qualche tipo di dato, che si possono implementare abbastanza semplicemente).


Un piccolo trivia che mi ero dimenticato di aggiungere nel primo post: la rappresentazione funzionale è oggi molto usata (anche) dai compilatori per produrre le varie ottimizzazioni. Cioè, un compilatore fa una cosa del genere:

programma --> analisi sintattica --> conversione in un linguaggio stile LISP --> ottimizzazioni --> compilazione

Siccome i linguaggi funzionali hanno alcune caratteristiche che rendono più facile l'ottimizzazione.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21


Torna a Il Pozzo della conoscenza

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron