LISP to SECD
Il progetto ha avuto come fine quello di realizzare un compilatore di linguaggio LISP; nello specifico: trasforma il linguaggio LISP in linguaggio per la macchina SECD.
Compilatore scritto interamente in linguaggio ML.
Esempio
Codice LispKit
"let x=5 and y = 6 in IF ( LEQ ( x y ) SUB ( y x ) SUB ( x y ) ) end $"
Lista di tokens prodotta dall’analizzatore lessicale:
[(LET, S "let"), (ID, S "x"), (SYM, S "="), (NM, M(NUM 5)), (AND, S "and"),
(ID, S "y"), (SYM, S "="), (NM, M(NUM 6)), (IN, S "in"), (OP, S "IF"),
(SYM, S "("), (OP, S "LEQ"), (SYM, S "("), (ID, S "x"), (ID, S "y"),
(SYM, S ")"), (OP, S "SUB"), (SYM, S "("), (ID, S "y"), (ID, S "x"),
(SYM, S ")"), (OP, S "SUB"), (SYM, S "("), (ID, S "x"), (ID, S "y"),
(SYM, S ")"), (SYM, S ")"), (END, S ‘‘end’’), (SYM, S "$")]
Sexpr prodotta dall’analizzatore sintattico
Let(If(Op("LEQ", [Var "x", Var "y"]), Op("SUB", [Var "y", Var "x"]),
Op("SUB", [Var "x", Var "y"])), ["x", "y"],
[Quote(NUM 5), Quote(NUM 6)]
Download
Progetto
Compilatore LISP. Trasforma il linguaggio LISP in linguaggio per la macchina SECD attraverso il linguaggio ML.
LISP: (da Wikipedia)
Il Lisp (List Processor) è un linguaggio di programmazione con implementazioni sia compilate che interpretate, spesso usato nei progetti di intelligenza artificiale. È stato ideato nel 1958 da John McCarthy come linguaggio formale, per studiare le equazioni di ricorsione in un modello computazionale. È un linguaggio di programmazione che si basa sul concetto di programma come funzione. Tutte le strutture dati di questo linguaggio sono delle liste chiamate S-expression.
Il primo software libero (free software) con un core lisp è stato emacs, diffuso editor di testo per terminale progettato negli anni 80 da Richard Stallman sulle lisp machine dell'epoca e portato successivamente su tutti i sistemi operativi. Commercialmente, la diffusione più rilevante del linguaggio è avvenuta con la sua integrazione in programmi di uso comune, come nel CAD Autocad (Autodesk inc.) o come nel publisher Interleaf (Interleaf Inc.), che utilizza una versione personalizzata di Lisp e strettamente integrata con le funzioni di programmazione dell'ambiente grafico.
La Symbolics Technology Inc. ha realizzato negli anni '80 delle workstation e server con sistema operativo multitasking e orientato agli oggetti con una potentissima interfaccia grafica di programmazione simbolica, tutto interamente programmato in LISP anche il microcodice del processore LISP: foto.
Le prime LISPM (LISP Machine) erano state implementate al MIT. Anche la Xerox produsse delle macchine LISPM (Dandylion, Dandytiger) come pure la Texas Instrument (TI Explorer).
Questi progetti dimostrano le enormi possibilità di questo linguaggio, talvolta erroneamente considerato solo accademico. Complessi software lisp restano ancora in servizio presso enti governativi, militari, aerospaziali, compagnie aeree, compagnie petrolifere, ecc. per complessi giochi di simulazione e valutazione di strategie operative, dimostrando che i progetti scritti in LISP di Intelligenza Artificiale mediante linguaggio simbolico sono validi e tutt'ora non eguagliati da altri linguaggi.
Data la grande versatilità del linguaggio e quindi la facilità di estensione e personalizzazione da parte del programmatore, sono fioriti molti dialetti di lisp, tra cui, il più diffuso, e quello a cui solitamente ci si riferisce parlando di lisp, è il Common LISP. Altri sono lo Scheme e l'Arc (linguaggio di programmazione).
SECD: (da Wikipedia)
The SECD machine is a highly influential virtual machine intended as a target for functional programming language compilers. The letters stand for Stack, Environment, Code, Dump, the internal registers of the machine. These registers point to linked lists in memory.
The machine was the first to be specifically designed to evaluate lambda calculus expressions. It was originally described by Peter J. Landin as part of his ISWIM programming language definition in 1963. The description published by Landin was fairly abstract, and left many implementation choices open (like an operational semantics). Hence the SECD machine is often presented in a more detailed form, such as Peter Henderson's Lispkit Lisp compiler, which has been distributed since 1980. Since then it has been used as the target for several other experimental compilers.
In 1989 researchers at the University of Calgary worked on a hardware implementation of the machine.
ML: (da Wikipedia)
ML è l'acronimo che identifica un linguaggio di programmazione funzionale general-purpose sviluppato dall'equipe di Robin Milner presso l'Università di Edimburgo alla fine degli anni 70, con una sintassi ispirata ad ISWIM. Storicamente, ML sta per MetaLinguaggio visto che era nato per la verifica formale attraverso il theorem prover LCF (il linguaggio di cui ML rappresentava il livello meta era pplambda, una combinazione di calcolo dei predicati del primo ordine e lambda-calcolo polimorfico debolmente tipizzato). Tra i linguaggi di programmazione funzionali è tra i più noti per il suo utilizzo dell'algoritmo di inferenza dei tipi di Hindley-Milner, che riesce ad inferire quasi tutti i tipi senza bisogno di dichiarazioni.
ML viene definito come linguaggio funzionale impuro, perché a differenza di altri linguaggi funzionali, come ad es. Haskell, consente la programmazione imperativa, e pertanto anche effetti collaterali.
Le caratteristiche principali di ML sono le seguenti: valutazione delle espressioni con chiamata per valore, gestione automatica della memoria attraverso un meccanismo di garbage collection, polimorfismo parametrico, tipizzazione statica, inferenza dei tipi, tipi di dati algebrici, pattern matching e gestione delle eccezioni. La combinazione di tutte queste caratteristiche ha dato vita ad uno dei migliori compilatori disponibili [1].
A differenza di Haskell, ML non usa un meccanismo di valutazione rapido (cortocircuitato): tutte le sottoespressioni componenti una espressione complessa sono sempre valutate. Come conseguenza non si possono utilizzare liste infinite. Tuttavia, la valutazione rapida (lazy evaluation) può essere simulata, e quindi anche le liste infinite, attraverso l'utilizzo di funzioni anonime.
Sono nati diversi linguaggi a partire da ML; tra questi i più popolari sono SML (Standard ML, del 1990) e Ocaml (Objective Caml). ML ha anche influenzato molti altri linguaggi, soprattutto quelli sviluppati in ambito accademico (ad es. F#, Cyclone e Nemerle).
ML è particolarmente adatto alle applicazioni teoriche come il progetto e lo sviluppo di linguaggi (compilatori, analizzatori, dimostratori di teoremi) ma ha trovato applicazione anche in ambito di bioinformatica, analisi finanziarie, ecc.
Specifiche tecniche
Questa grammatica libera da contesto descrive la sintassi dei programmi Lisp Kit:
1 Prog::= let Bind in Exp end | letrec Bind in Exp end
2 Bind::= var = Exp X
3 X :: = and Bind | epsilon
4 Exp ::= Prog | var Y |const | List | op ( Seq_Exp ) | lambda (Seq_Var ) Exp
5 Y :: = ( Seq_Exp ) | epsilon
6 Seq_Exp::= Exp Z
7 Z::= Seq_Exp | epsilon
8 Seq_Var::= var W
9 W :: = Seq_Var | epsilon
10 List :: = [ Const_List ] | nil
11 Const_List ::= const V | List V
12 V :: = ::Const_list | epsilon
FIRST e FOLLOW : Nelle definizioni di FIRST e FOLLOW che seguono abbiamo introdotto dei simboli terminali speciali che chiameremo collettivi. Si tratta dei simboli const , var e op. Il primo sta per ogni costante semplice, il secondo per ogni identificatore e l’ultimo per ogni operatore. Usare questi 3 simboli (al posto delle reali stringhe che essi rappresentano) è una grossa semplificazione e questo è infatti il motivo per cui le abbiamo usate. Un’altra semplificazione che facciamo è quella di considerare le key word come un unico simbolo. Quindi per esempio “let” viene considerato un unico simbolo (d’altronde è racchiusa in un’unica coppia token_lexema).
First(Prog)={let,letrec}
Follow(Prog)={$,end,),in}
First(Bind)= {var}
Follow(Bind)= {in}
First(X)={and, epsilon}
Follow(X)= {in}
First(Exp)={let,letrec,var,const,op,lambda,[,nil}
Follow(Exp)={and, end,),in,let,letrec,var,const,op,lambda,[,nil}
First(Y)={(,epsilon}
Follow(Y)={and, end,),in,let,letrec,var,const,op,lambda,[,nil}
First(Seq_Exp)= First(Exp)={let,letrec,var,cst,op,lambda,[,nil}
Follow(Seq_Exp)={)}
First(Z)={let,letrec,var,const,op,lambda,epsilon,[,nil}
Follow (Z)={)}
First(Seq_Var)={var}
Follow(Seq_Var)={)}
First(W)={var,epsilon}
Follow(W)={)}
First(List) = {[,nil}
Follow(List)={and, end,),in,let,letrec,var,const,op,lambda,[,nil,::,]}
First (Const_List) ={[,nil,const}
Follow(Const_List) ={]}
First(V) = {::, epsilon}
Follow(V) = {]}
Dati di prova
Alcuni dati di input per provare il codice:
Codice LispKit
"let x=5 and y = 6 in IF ( LEQ ( x y ) SUB ( y x ) SUB ( x y ) ) end $"
Lista di tokens prodotta dall’analizzatore lessicale:
[(LET, S "let"), (ID, S "x"), (SYM, S "="), (NM, M(NUM 5)), (AND, S "and"),
(ID, S "y"), (SYM, S "="), (NM, M(NUM 6)), (IN, S "in"), (OP, S "IF"),
(SYM, S "("), (OP, S "LEQ"), (SYM, S "("), (ID, S "x"), (ID, S "y"),
(SYM, S ")"), (OP, S "SUB"), (SYM, S "("), (ID, S "y"), (ID, S "x"),
(SYM, S ")"), (OP, S "SUB"), (SYM, S "("), (ID, S "x"), (ID, S "y"),
(SYM, S ")"), (SYM, S ")"), (END, S ‘‘end’’), (SYM, S "$")]
Sexpr prodotta dall’analizzatore sintattico
Let(If(Op("LEQ", [Var "x", Var "y"]), Op("SUB", [Var "y", Var "x"]),
Op("SUB", [Var "x", Var "y"])), ["x", "y"],
[Quote(NUM 5), Quote(NUM 6)]
Codice LispKit
"let N = 3 and L = LAMBDA ( P Q R ) DIV (ADD (
ADD ( MUL ( P P ) MUL ( Q Q ) ) MUL ( R R ) ) N ) in L ( 2 4 6 ) end $"
Lista di tokens prodotta dall’analizzatore lessicale:
[(LET, S "let"), (ID, S "N"), (SYM, S "="), (NM, M(NUM 3)), (AND, S "and"),
(ID, S "L"), (SYM, S "="), (LAMBDA, S "LAMBDA"), (SYM, S "("),
(ID, S "P"), (ID, S "Q"), (ID, S "R"), (SYM, S ")"), (OP, S "DIV"),
(SYM, S "("), (OP, S "ADD"), (SYM, S "("), (OP, S "ADD"), (SYM, S "("),
(OP, S "MUL"), (SYM, S "("), (ID, S "P"), (ID, S "P"), (SYM, S ")"),
(OP, S "MUL"), (SYM, S "("), (ID, S "Q"), (ID, S "Q"), (SYM, S ")"),
(SYM, S ")"), (OP, S "MUL"), (SYM, S "("), (ID, S "R"), (ID, S "R"),
(SYM, S ")"), (SYM, S ")"), (ID, S "N"), (SYM, S ")"), (IN, S "in"),
(ID, S "L"), (SYM, S "("), (NM, M(NUM 2)), (NM, M(NUM 4)), (NM, M(NUM 6)),
(SYM, S ")"), (END, S "end"), (SYM, S "$")]
Sexpr prodotta dall’analizzatore sintattico
Let(Call(Var "L", [Quote(NUM 2), Quote(NUM 4), Quote(NUM 6)]), ["N", "L"],
[Quote(NUM 3),
Lambda(["P", "Q", "R"],Op("DIV",
[Op("ADD",
[Op("ADD",
[Op("MUL", [Var "P", Var "P"]),
Op("MUL", [Var "Q", Var "Q"])]),
Op("MUL", [Var "R", Var "R"])]), Var "N"]))])
Codice LispKit
"letrec
FACT = LAMBDA ( X ) IF ( EQ ( X 0 ) 1 MUL ( X FACT ( SUB ( X 1 ) ) ) )
and G = LAMBDA ( H L ) IF ( EQ ( L NIL ) L
CONS ( H ( CAR ( L ) ) G ( H CDR ( L ) ) ) )
in G ( FACT [2::3::4::5] ) end $"
Lista di tokens prodotta dall’analizzatore lessicale:
[(LETREC, S "letrec"), (ID, S "FACT"), (SYM, S "="), (LAMBDA, S "LAMBDA"),
(SYM, S "("), (ID, S "X"), (SYM, S ")"), (OP, S "IF"), (SYM, S "("),
(OP, S "EQ"), (SYM, S "("), (ID, S "X"), (NM, M(NUM 0)), (SYM, S ")"),
(NM, M(NUM 1)), (OP, S "MUL"), (SYM, S "("), (ID, S "X"), (ID, S "FACT"),
(SYM, S "("), (OP, S "SUB"), (SYM, S "("), (ID, S "X"), (NM, M(NUM 1)),
(SYM, S ")"), (SYM, S ")"), (SYM, S ")"), (SYM, S ")"), (AND, S "and"),
(ID, S "G"), (SYM, S "="), (LAMBDA, S "LAMBDA"), (SYM, S "("),
(ID, S "H"), (ID, S "L"), (SYM, S ")"), (OP, S "IF"), (SYM, S "("),
(OP, S "EQ"), (SYM, S "("), (ID, S "L"), (Nil, M NIL), (SYM, S ")"),
(ID, S "L"), (OP, S "CONS"), (SYM, S "("), (ID, S "H"), (SYM, S "("),
(OP, S "CAR"), (SYM, S "("), (ID, S "L"), (SYM, S ")"), (SYM, S ")"),
(ID, S "G"), (SYM, S "("), (ID, S "H"), (OP, S "CDR"), (SYM, S "("),
(ID, S "L"), (SYM, S ")"), (SYM, S ")"), (SYM, S ")"), (SYM, S ")"),
(IN, S "in"), (ID, S "G"), (SYM, S "("), (ID, S "FACT"), (SYM, S "["),
(NM, M(NUM 2)), (SYM, S "::"), (NM, M(NUM 3)), (SYM, S "::"),
(NM, M(NUM 4)), (SYM, S "::"), (NM, M(NUM 5)), (SYM, S "]"), (SYM, S ")"),
(END, S "end"), (SYM, S "$")]
Sexpr prodotta dall’analizzatore sintattico
Letrec(Call(Var "G",
[Var "FACT",
Quote(DOT(NUM 2, DOT(NUM 3, DOT(NUM 4, DOT(NUM 5, NIL)))))]),
["FACT", "G"],
[Lambda(["X"],
If(Op("EQ", [Var "X", Quote(NUM 0)]), Quote(NUM 1),
Op("MUL",
[Var "X",
Call(Var "FACT",
[Op("SUB", [Var "X", Quote(NUM 1)])])]))),
Lambda(["H", "L"],
If(Op("EQ", [Var "L", Quote NIL]), Var "L",
Op("CONS",
[Call(Var "H", [Op("CAR", [Var "L"])]),
Call(Var "G",
[Var "H", Op("CDR", [Var "L"])])])))]
Prewiev del codice, codice e specidiche :
Puoi trovare nella sezione FILES sono presenti alcuni PDF con alcune specifiche e il codice.
N.B. : il codice del programma è stato diviso, per comodità, in due parti. La prima parte con nome LispToFS , la seconda parte con nome FSToSECD
