Construcció d'un compilador per a un llenguatge funcional

T reba ll F i de G rau

GRAU D’ENGINYERIA INFORMÀTICA

Construcció d’un compilador per a un llenguatge funcional

NICOLÁS GONZÁLEZ MUNAR

Tutor

Esperança Amengual

Escola Politècnica Superior

Universitat de les Illes Balears

Aquest projecte ha estat possible gràcies a Albert Llemosí Cases, qui em va inspirar, em va motivar, i m’ha guiat i ajudat sempre que he necessitat (fins i tot quan no tenia per què fer-ho). Gràcies també a la meva tutora, Esperança Amengual Alcover, per la seva paciència i efectivitat.

S ^UMARI

Sumari iii

Acrònims vii

Resum ix

1 Introducció 1

2 Llenguatges Funcionals 3

2.1 Funcions matemàtiques i les seves propietats . . . 3

2.2 Característiques d’un llenguatge funcional . . . 5

2.2.1 Definint una funció . . . 5

2.2.2 Tuples . . . 7

2.2.3 Definicions de tipus . . . 8

2.2.4 Funcions d’Ordre Superior . . . 9

2.3 Lambda Càlcul . . . 11

2.3.1 Sintaxi del lambda càlcul . . . 11

2.3.2 Reduccions . . . 13

2.3.3 Supercombinadors . . . 15

2.4 Dificultats de compilar un llenguatge funcional . . . 16

3 Disseny del compilador 17 3.1 Disseny general . . . 17

3.1.1 Eines utilitzades . . . 19

4 Anàlisi Lèxica 21 4.1 Lèxic del llenguatgeFun . . . 21

4.2 Construcció l’analitzador . . . 22

4.3 Taula de noms . . . 23

5 Anàlisi Sintàctica 25 5.1 Fitxer de la gramàtica . . . 25

5.2 Construcció de l’arbre sintàctic . . . 26

5.3 La gramàtica deFun . . . 26

6 Anàlisi Semàntica: Comprovació de tipus 29 6.1 Estructures de dades auxiliars . . . 29

6.1.1 Taula de símbols . . . 29

6.1.2 Taula devartypes . . . 30

6.2 Tipus predefinits . . . 31

6.3 Comprovacions realitzades . . . 31

6.3.1 Definicions de funcions (tc_func_decl) . . . 31

6.3.2 Equacions . . . 32

7 Generació de codi Lambda-Càlcul 37 7.1 L’arbre lambda càlcul . . . 37

7.1.1 Transformació de funcions a Lambda Càlcul (LC) . . . 40

7.1.2 Arbre de reconeixement . . . 40

7.2 PM Tree . . . 42

7.3 Solució enAda . . . 42

8 Elevació de Lambdes 47 8.1 Funció Lift . . . 47

8.1.1 Funció FV . . . 48

8.1.2 Funció A . . . 48

8.2 Implementació de Lift . . . 49

9 Generació de codi FPM 51 9.1 La màquina FPM . . . 51

9.2 Regles de traducció . . . 52

9.3 Implementació de la traducció . . . 54

10 Generació de codi Assemblador 57 10.1 La màquina Functional Programming Machine (FPM) ambIntel x86 . . 57

10.2 Implementació de la traducció . . . 58

10.2.1 Operadors predefinits . . . 59

10.2.2 Label . . . 59

10.2.3 Goto . . . 60

10.2.4 CASE-n . . . 60

10.2.5 INDEX . . . 60

10.2.6 APPLY n . . . 60

10.2.7 PACK n . . . 61

10.2.8 CALL i RTN . . . 61

10.2.9 Push . . . 62

10.2.10 DROP n . . . 62

10.2.11 Comparadors . . . 62

10.3 Operació de visualització:Writer . . . 63

11 Conclusions 65 A fun.l (Lèxic) 67 B fun.y (Gramàtica) 71 C Codi del compilador 77 C.1 fun.adb . . . 77

SUMARI v

C.2 semantic.ads . . . 78

C.3 semantic.adb . . . 79

C.4 semantic.messages.adb . . . 80

C.5 semantic.messages.ads . . . 87

C.6 fun_token.ads . . . 88

C.7 decls.d_names_table.ads . . . 88

C.8 decls.d_names_table.adb . . . 89

C.9 decls.d_tree.ads . . . 92

C.10 semantic.c_tree.ads . . . 96

C.11 semantic.c_tree.adb . . . 98

C.12 decls.d_description.ads . . . 109

C.13 decls.d_symbol_table.ads . . . 110

C.14 decls.d_symbol_table.adb . . . 111

C.15 semantic.type_checking.ads . . . 114

C.16 semantic.type_checking.adb . . . 114

C.17 decls.d_vtype_table.ads . . . 143

C.18 decls.d_vtype_table.adb . . . 143

C.19 semantic.c_lc_tree.ads . . . 144

C.20 semantic.c_lc_tree.adb . . . 145

C.21 decls.d_lc_tree.ads . . . 170

C.22 decls-d_pm_tree.ads . . . 171

C.23 decls-d_pm_tree.adb . . . 172

C.24 semantic.lambda_lifting.ads . . . 173

C.25 semantic.lambda_lifting.adb . . . 173

C.26 decls.d_function_table.ads . . . 177

C.27 decls.d_function_table.adb . . . 178

C.28 decls.d_fpm.ads . . . 179

C.29 decls.d_stack.ads . . . 180

C.30 decls.d_stack.adb . . . 180

C.31 semantic.g_fpm.ads . . . 181

C.32 semantic.g_fpm.adb . . . 182

C.33 semantic.g_assembly.ads . . . 194

C.34 semantic.g_assembly.adb . . . 195

C.35 writer.ads . . . 205

C.36 writer.adb . . . 205

C.37 stdio.ads . . . 208

Bibliografia 209

A ^CRÒNIMS

TFG Treball Final de Grau

POO Programació Orientada a Objectes PF Programació Funcional

FPM Functional Programming Machine LC Lambda Càlcul

WHNF Weak Head Normal Form AFD Autòmat Finit Determinista CAF Constant Applicative Form TDF Taula De Funcions

R ^ESUM

Els llenguatges de programació funcional son uns grans desconeguts. Molts programa- dors actualment els utilitzen, si bé moltes vegades ni tan sols en són conscients. A més, actualment alguns mecanismes propis d’aquests llenguatges han estat heretats per llenguatges d’altres tipus (com els imperatius), així com també s’han anant introduïnt a altres paradigmes de programació (per exemple JavaScript en la seva Programació Orientada a Objectes (POO)).

Conèixer, per tant, quines eines ens poden aportar els llenguatges funcionals, així com també la seva aplicació, és el que farem a aquest Treball Final de Grau (TFG), i no hi ha millor manera de fer-ho que creant un llenguatge propi i construïr-ne el seu compilador. Així entrarem plenament en les problemàtiques que es plantejen, sobretot tenint en compte que els llenguatges funcionals es basen en el principi delambda- càlcul(LC) i que, per tant, estan més enfora de la màquina de Von Neumann que els llenguatges declaratius.

Per poder entendre millor les diferències que hi apareixen, el compilador es desen- voluparà amb les mateixes tecnologies que el desenvolupat a l’assignatura deCom- piladors, és a dir, enAdai emprant les einesaflexyayacccom a generadors de lèxic i d’autòmats finits deterministes respectivament, de tal forma que les úniques preocupa- cions que puguin aparèixer seran produïdes per la naturalesa inherent dels llenguatges funcionals.

Veurem que, com que tot gira al voltant dellambda-càlcul, la generació de codi es redueix en aplicar les seves propietats. Això ens marca el camí, però també és important comprendre en profunditat ellambda-càlculi les seves propietats per tal de poder comprendre que els camins que emprenem són correctes.

C

1

I ^NTRODUCCIÓ

Els llenguatges funcionals tenen molt de potencial degut al seu caire matemàtic. A més, estan guanyant terreny, ja que són cada vegada més utilitzats així. També altres paradig- mes estan adoptant mecanismes propis dels llenguatges funcionals. Un exemple clar és el deJavaScript: un llenguatge POO que incorpora mecanismes com la declaració anònima de funcions, així com les funcionsmapireduce, (funcions molt utilitzades en la Programació Funcional (PF)). Això ho fa possible tractant les funcions com a objectes que per herència sempre tindran les 2 funcions esmentades.

El problema és que els programadors, per herència de la màquina de Von Neumann i ineludiblement del llenguatgeassemblador, hem tingut sempre més a prop els llen- guatges imperatius. Això fa que pensar en altres paradigmes de programació ens sigui estrany i fins i tot difícil, la qual cosa implica que la major part dels programadors no saben com funcionen realment, ni quins avantatges i mecanismes ens poden aportar.

És sabut també que un gran exercici per entendre els mecanismes d’un llenguatge, és fer un exercici d’immersió, i entrar a les entranyes del mateix llenguatge i del seu compilador/intérpret. Aquest exercici ens permet comprendre com es tractarà el codi que escrivim i quins impactes i conseqüències portarà. Així doncs, el que sa fet a aquest TFG és construir un llenguatge funcional bàsic, amb un recull d’eines suficientment interessant, i construir un compilador que arriba fins al llenguatge assemblador, tot passant pel llenguatge de la nomenada FPM, una màquina de pila simple que ens facilitarà la conversió a codi assemblador.

Per tant, els objectius d’aquest TFG es poden enumerar en els següents:

• Revisió de les tècniques que incorporen nadivament els llenguatges funcionals – Anàlisi d’alguns llenguatges existents

• Definició d’un llenguatge funcional propi

• Disseny i implementació d’un compilador pel llenguatge definit

Al capítol 2 (“Llenguatges Funcionals”) farem una repassada de les tècniques més importants que incorporen nadivament els llenguatges funcionals, tot entrant en anàlisi de llenguatges existents tals comHopeoMiranda. Una vegada vists, estarem preparats per definir el nostre llenguatge de programacióFun.

Després, al capítol 3 discutirem el disseny del compilador. Veurem les diferents parts que componen el compilador, repassant les particularitats que apareixen per estar tractant amb un llenguatge funcional, tot de forma esquemàtica i sense entrar en detalls, ja que aquests els veurem en els capítols 4 fins a 10, on entrarem en els detalls de la implementació.

Per acabar, al capítol 11 analitzarem la feina feta, veurem quins coneixements hem obtingut, algunes dificultats que han aparegut durant el procés d’elaboració, i quines millores ens hem deixat al tinter.

En quant a la planificació d’aquest projecte, com que es podria considerar més bé un projecte "d’exploració", no es va fer una bona planificació. L’única fita important era la data límit d’entrega del projecte, la qual, degut a les dificultats sorgides, va ser superada el curs passat. Després, la data límit es va allargar fins a la data límit d’entrega d’aquest curs.

C

2

L ^LENGUATGES F ^UNCIONALS

Abans d’entrar a construir el nostre llenguatge de programació, és evident que primer necessitarem entendre bé com funcionen els llenguatges funcionals. Pot semblar trivial quan es tracta de llenguatges imperatius, ja que els tenim molt per mà, però tot i així, hi hauria aspectes que se’ns passarien per alt.

El cas dels llenguatges funcionals és ben diferent. Sí és cert que alguns llenguatges poden adoptar estructures molt imperatives, sobretot a llenguatges moderns, com per exempleHaskell, però en el cas d’aquests llenguatges, l’estructura imperativa dels programes és poc natural i sens dubte no és l’habitual. A més de tot això, cal destacar que els llenguatges funcionals es basen en el sistema formal conegut com aLambda Càlcul(LC), el qual explicarem en profunditat en la secció 2.3.

Aquest capítol ve inspirat en la seva estructura pels capítols 2 i 3 del llibre que ha servit com a referència principal d’aquest treball, elFunctional Programmingde Anthony J.Field i Peter G. Harrison [1].

Per ara, comencem per una definició senzilla: una funció matemàtica. Aquest és el concepte més bàsic i fonamental, el principal component d’un llenguatge funcional.

2.1 Funcions matemàtiques i les seves propietats

Definició 1. Una funció matemàtica és una relació entre uns valors d’entrada (domini) i uns resultats (codomini).

Aquesta definició principalment extreta de [2] pot semblar vaga i/o poc explicativa, però és vital per entendre els principis bàsics de la programació funcional: una funció és una descripció d’un comportament que ve determinat pels elements que rebi.

Un exemple de funció bàsica seria la funciódoble, una funció que donat un nombre realRqualsevol, retornarà el seu doble (notem que el seu domini i codomini són clars:

el conjuntRen ambdós casos). Una manera dedefiniraquesta funció podria ser donant tots els casos:

...

doble(-1) = 1 doble(0) = 0 doble(1) = 2 doble(2) = 4 doble(3) = 6

...

És evident que aquesta manera de definir una funció és clara, però poc pràctica, ja que hauríem de definir els casos per a tots els elements deR. Per tant, la forma més pràctica de definir una funció és donant una clara definició del seucomportament:

doble:R→R doble(x) = x + x

El primer que veiem és la definició del seu domini i codomini. Després, la definició del seu comportament, és a dir, unaequacióque ens diu que donat unparàmetre formalx, retornaremx+x.

A més, és important remarcar que aquestes definicions vinculen cada element del seu domini a un únic resultat. És per aquesta raó que diem que les funcions són deterministes.

Però evidentment, hi pot haver funcions més complexes. Per exemple, si ens anem al cas de la implicació lògica (=⇒), veiem que tot i que ens trobam a un domini booleà, necessitam més d’una equació per poder definir-la:

i mpl i c a(a,b)=

(vertader si b és vertader

a si b és fals

Així obtenim una funciótotal, perquè està definida per a tots els casos que poden donar-se pel seu domini (quebsigui vertader o fals). Altrament, diríem que la funció és parcial.

Un altre concepte important i que utilitzarem moltes vegades és el concepte d’aplicació:

Definició 2. Diem que una funció és aplicada quan se li proporciona un argument.

D’aquesta manera, per al cas

doble(3)

Diem qued obl eestà sent aplicada a 3. També podem dir que aquesta expressió avaluaa 6, i ho podem expressar de la següent forma

doble(3)→6

Ara es pot fer una observació important: podem encadenar funcions per fer defini- cions més complexes, com per exemple

quadruple(a) = doble(a) + doble(a)

2.2. Característiques d’un llenguatge funcional

Això és el que es coneix com acomposicióde funcions. De fet, si analitzam a fons les funcions definides abans, podem veure que en realitat, la estem utilitzant des del principi, ja que per la definició de la funciód obl ehem utilitzat la funció+, la definició de la qual hem donat per suposada. Aquestes funcions simples són les que anomenarem predefinides(built-in) òprimitives.

I amb aquests conceptes queda clar que amb funcions matemàtiques podem cons- truir programes. Un llenguatge basat en funcions matemàtiques és el que es coneix com allenguatge funcional.

Abans de passar a analitzar els llenguatges funcionals ens queda per definir una propietat important que compleixen les funcions matemàtiques: Transparència refe- rencial.

Definició 3. La transparència referencial és una propietat que compleixen les funcions per la qual el valor d’una funció serà sempre el mateix.

Això ve a dir que, si a una composició, substituïm una funció pel seu valor, no veurem pas cap variació al resultat final.

És important nomenar aquesta propietat ja que no es dóna en la major part de llenguatges actuals, sobre tot els que tenen mecanismes d’entrada/sortida. De fet, els llenguatges imperatius son inherentment referencialment opacs.

Però, un llenguatge funcional pur, com que està basat en funcions matemàtiques, sí manté la transparència referencial. Això es veurà més clar quan vegem el LC.

2.2 Característiques d’un llenguatge funcional

Ara que entenem els conceptes principals de les funcions matemàtiques, podem entrar a veure amb deteniment les característiques dels llenguatges funcionals. Per això, primer de tot analitzarem el llenguatgeHope.

Hopeés un llenguatge funcional desenvolupat als anys 70. És un llenguatge funcio- nal pur bastant simple, però que recull moltes característiques importants, convertint-lo en el predecessor de llenguatges posteriors tals comMirandaiHaskell, llenguatges àmpliament reconeguts i utilitzats en la actualitat, i la base dels quals és essencial- mentHope. La seva simplicitat i completitut el converteix en un candidat perfecte per la nostra missió: podrem analitzar-lo per veure les seves característiques, i després comparar-lo amb altres llenguatges per complementar les idees adquirides.

2.2.1 Definint una funció

El primer que veiem quan definiem una funció matemàtica és que aquesta està vin- culada a un domini i un codomini.Hopeés un llenguatge fortament tipat i per aquest motiu és important, a l’hora de declarar una funció, donar el seu domini i codomini (o, en el seu equivalent informàtic, els tipus dels seusargumentsivalors de retorn). Per seguir el cas de la funciódoble, aHopela declararíem de la següent manera:

dec doble : num −> num;

Aquí ens trobam la paraula reservadadec. AHope, aquesta paraula indica l’inici d’una declaració de tipus seguida del seu nom i la declaració en sí. El símbol->ens

indica, a la seva esquerra un domini, i a la seva dreta un codomini. D’aquesta manera, aquesta declaració ens està declarant la funciódoble, que rep unnum, i ens retornarà unnum(noti’s quenumés un tipus predefinit deHopeequivalent a uninteger(E).

Evidentment els tipus de les funcions poden ser més complexes, però això ho anirem veient.

Ara que ja hem declarat la funció amb el seu domini i codomini, hem de passar a definir-la, és a dir, descriure el seu comportament. AHope, la funciódoblees definiria de la següent manera:

−−−doble ( x ) <= x + x ;

Com es pot observar, la definició és molt similar a la donada anteriorment. AHope, indicam que el que ve a continuació de—és la definició d’una funció, que estarà seguida del nom de la funció que està definint, precedint un llistat corresponent al nom que rebran els paràmetres formals a aquesta definició. Tot seguit, després del símbol

<=, trobem la definició per se.

En aquest cas, la definició involucra una funció predefinida, la funció+. Cal ob- servar que, en aquest cas, la funció es troba entre els dos paràmetres. Això és perquè les funcions predefinides aHopees consideren funcions d’infix. És important aquest aclariment perquè molts llenguatges funcionals, de igual forma que el LC, no permeten aquesta sintaxi, i només admeten funcions de prefix, per exemple:

+ x x

Hopeté mecanismes per indicar si les funcions son d’infix o prefix, així com la prioritat d’aplicació, però no entrarem a analitzar-ho.

És important observar que, a diferència dels llenguatges imperatius, als funcionals no se sol veure la paraula reservadareturn. Això és per què es redundant, si hem definit funciócom una relació entre uns elements d’entrada i uns de sortida, està clar que una funció matemàticasempreretornarà un valor. Si per exemple volguéssim definir una funció que ens digués si un valor és positiu, podríem fer ús de l’expressió condicional de la següent forma:

dec e s P o s i t i u : num −> t r u v a l ;

−−−e s P o s i t i u ( x ) <= i f x > 0 then true e l s e f a l s e ;

Ontruvalfa referència al tipus predefinit equivalent al booleà (t r ue,f al se).

Recordem ara el concepte decomposició. AHopehem vist que és possible fer crides a funcions predefinides però també ho és per funcions definides per l’usuari. De fet, tot i que als exemples anteriors hem fet les definicions just després de les declaracions, no és pas necessari. Podem declarar una funció i definir-la més endavant. Això ens permet declarar funcions que tenguin referències creuades. Per exemple, podríem definir un parell de funcions que plegades calculin el vectorial d’un nombre n:

dec f a c t o r i a l 0 : num −> num;

dec f a c t o r i a l 1 : num −> num;

−−−f a c t o r i a l 0 (n) <= i f n == 1 then 1 e l s e n * f a c t o r i a l 1 (n−1);

−−−f a c t o r i a l 1 (n) <= i f n == 1 then 1 e l s e n * f a c t o r i a l 0 (n−1);

Si per exemple aplicamf ac t or i al0 a 4, la seqüencia d’execució seria:

2.2. Característiques d’un llenguatge funcional

factorial0(4)

→4 * factorial1(3)

→4 * 3 * factorial0(2)

→4 * 3 * 2 * factorial1(1)

→4 * 3 * 2 * 1

→24

Aquest exemple treu a relluir un concepte vital als llenguatges funcionals, el con- cepte derecursivitat. El problema anterior es resoldria de forma molt més senzilla:

dec f a c t o r i a l : num −> num;

−−−f a c t o r i a l (n) <= i f n == 1 then 1 e l s e n * f a c t o r i a l (n−1);

I no només és possible la recursivitat aHope, sinó que és un recurs vital per els llenguatges funcionals. Tant és així queHopeno té instruccions de repetició, sinó que confia plenament en la recursivitat. El primer que pot pensar un usuari habitual de llenguatges imperatius que senti això ésstack overflow, però en el cas dels llenguatges funcionals no és pas així, i és degut al LC i les operacions que es poden fer damunt ell.

Ho veurem a la secció 2.3.

2.2.2 Tuples

Un element fonamental en els llenguatges funcionals són lestuples. Tant és així que bona part dels llenguatges funcionals giren en torn a aquest element. Ho entendrem millor quan vegem com les aprofitaHope. Podríem començar definint la nostra segona funció:implica.

dec implica : t r u v a l # t r u v a l −> t r u v a l ;

−−−implica ( a , b ) <= i f b then true e l s e a ;

A la declaració de la funció podem apreciar l’aparició d’un símbol nou:#. AHope aquest símbol denota elproducte cartesiàde tipus. Per aquest cas veiem que el que ens està indicant la declaració és que la funció agafarà dos elements de tipustruval, i en re- tornarà un altre. És comú, sobre tot venint dels llenguatges imperatius, interpretar això comuna funció que reb dos arguments, però en el cas deHope, aquesta interpretació seria inexacta. Concretament, la funciórep una tupla de dos elements truval i retorna un element truval.

Però no només podem trobar tuples com a entrades d’una funció; també les hi podem trobar com a sortida. Per exemple, podem tenir una funcióanalitzaque analitzi un nombreRi retorni:

1. Un caràcter ’+’ ò ’-’ indicant si el nombre és major que 0.0 o no respectivament, 2. untruvalque ens digui si el nombre es troba entre -1.0 i 1.0 inclosos i,

3. el nombreEmés proper.

La seva definició aHopepodria ser:

dec a n a l i t z a : r e a l −> char # t r u v a l # num;

−−−a n a l i t z a ( r ) <= (i f r <0 then ’−’ e l s e ’ + ’ ,

( r >= −1.0) and ( r <= 1 . 0 ) , round ( r ) ) ;

Si apliquemanalitzaa−3.4, el que obtindríem és (’-’, false, -3). Noti’s que això és possible perquè les tuples poden contenir elements de qualsevol tipus, però l’ordre és important, de manera que, per exemple,t r uv al#num6≡num#t r uv al.

2.2.3 Definicions de tipus

Fins ara, als exemples vists, només hem treballat amb tipus predefinits. Però el llen- guatge estaria molt limitat si no ens donés mitjans per poder definir els nostres tipus.

Estem molt acostumats a poder definir els nostres tipus, es pot fer en pràcticament qualsevol llenguatge. Uns exemples serien elsrecordsaAda, elsstructsa C o lesclasses als llenguatges orientats a objectes comC#.

AHopeaixò és diferent. Quan definim un tipus composat d’altres tipus tals com unrecord, aHopeho podem fer de manera senzilla simplement definint una tupla.

Això permet centrar-se encom ésl’estructura de dades en lloc decom la representem (records, classes, structs, etc).

El mateix passa si el que volem és definir una estructura de dades. Podem prendre per exemple l’estructura de dades fonamental de pràcticament qualsevol llenguatge funcional: les llistes. Com que no ens hem d’aturar a pensar en com representar la llista, és suficient que pensem en què és: una estructura de dades recursiva. Una llista de nombres no es més que el buit ò un nombre continuat d’una altre llista:

data l i s t == n i l ++ cons (num # l i s t )

Quan posam la paraula claudataestam indicant que anam a definir un tipus de dada. Aquests tipus son una concatenació deconstructors de dades, en aquest casnili cons. D’aquesta manera podem definir de manera recursiva llistes de qualsevol mida.

cons(5, nil)→[5]

cons(5, cons(3, nil))→[5, cons(3, nil)]→[5, 3]

AHope, quan un nom apareix com a constructor, ja no pot aparèixer a cap altre constructor (és clar, quan el compilador troba unnull, ha de poder inferir que l’element és unllistat d’entersi no, per exemple, uncotxe). Això ens planteja d’inmmediat el concepte degenèricso, més freqüentment utilitzatpolimorfisme.

Hopeens permet donar paràmetres a les definicions de dades per poder dotar-les de polimorfisme (dades amb diferents formes). Si per exemple, volguèssim definir la nostra estructurallistade forma polimòrfica, ho podríem fer de la següent forma:

typevar alpha

data l i s t ( alpha ) == n i l ++ cons ( alpha # l i s t a ( alpha ) )

Amb la paraula reservadatypevardefinim una variable de tipus, és a dir, definim un identificador que denotarà un tipus. D’aquesta forma es pot definir una estructura de dades on els paràmetres formals s’entenen com a tipus. El polimorfisme, doncs, permet encapsular el concepte de llista i així poder tenir el mateix concepte per qualsevol tipus.

Hope, com altres llenguatges funcionals, inclou aquesta definició de forma interna, permetent l’ús del tipuslist. De fet, també hi té definit un operador, l’operador ::, que fa els efectes del constructorcons. Així, per exemple:

2.2. Característiques d’un llenguatge funcional

5 :: nil→[5]

5 :: (3 :: nil)→[5, (3 :: nil)]→[5, 3]

Un altre mecanisme que aportaHopeés el de poder posar nom a tipus ja existents o a tuples, permetent utilitzar aquests noms. Per exemple:

type Sentencies == t r u v a l # t r u v a l ; dec implica : Sentencies −> t r u v a l ;

−−−implica ( a , b ) <= i f b then true e l s e a ;

Després podríem definir les funcionsand,or, etc. utilitzant el tipusSentenciadefinit.

2.2.4 Funcions d’Ordre Superior

Els exemples de funcions que hem vist fins ara erenfuncions de primer ordre. Però als llenguatges funcionals és comú poder definirfuncions d’ordre superior.

Definició 4. Una funció d’ordre superior és aquella que pot rebre funcions com a parà- metres formals i/o les pot retornar.

Com sempre, serà millor il·lustrar amb un exemple. Suposem que volem definir una funció que, en funció d’un paràmetre, apliqui una funció que rebi també per paràmetre, o una altre.

typevar alpha ;

dec aplicaFoG : t r u v a l # alpha # ( alpha −> alpha ) # ( alpha −> alpha ) −> alpha

−−−aplicaFoG ( t , x , f , g ) <= i f t then f ( x ) e l s e g ( x )

D’aquesta manera es poden encadenar aplicacions de funcions que es reben per paràmetre de manera molt intuïtiva. Basta que, en el moment de declarar la funció, es- pecifiquem quins paràmetres seran funcions. Podem veure quins són funcions perquè tenen el símbol− >, en aquest cas la funcióaplicaFoGespera rebre un booleà, un valor de tipusal pha, i dues funcions que donat un valor de tipus alpha, retornaran un valor de tipus alpha.

De fet, això ho podríem fer d’una altra forma: aplicant la funció que obtinguem com a resultat d’una funció. Vegem com seria:

typevar alpha ;

dec aplicaFoG : t r u v a l # ( alpha −> alpha ) # ( alpha −> alpha ) −> ( alpha −> alpha )

−−−aplicaFoG ( t , x , f , g ) <= i f t then f e l s e g

dec t r a c t a : num # (num −> num) # (num −> num) −> num;

−−−t r a c t a ( x , f , g ) <= aplicaFoG ( x < 0 , f , g ) ( x )

En aquest cas, la funcióaplicaFoGno rep el valor sobre el que aplicar la funció rebuda per paràmetre, sinó que directament retornarà la funció. A la funciótractament veiem com s’aplicaf og. D’aquesta manera, l’expressióapl i c aF oG(x<0,f,g)(x) es podria llegir com "aplica la funció que retorni aplicaFoG a x". Per tant, si per exemple decidim aplicart r ac t aa (3,f,g), el resultat que obtindrem és l’equivalent a aplicarga 3.

Per veure un exemple més clar de com les funcions d’ordre superior ens poden ser de gran ajuda, caldria veure la funciómap, una funció molt utilitzada a llenguatges fun- cionals (tant és així que alguns la hi tenen predefinida, comHaskell). Però abans d’això, cal entrar en el concepte decomprovació de patrons, un concepte importantíssim per als llenguatges funcionals.

Hem vist que quan definim una funció, especificam els paràmetres formals. La comprovació de patrons dóna una passa més endavant i ens permet especificar certes característiques dels paràmetres, obtenint així dos grans avantatges.

1. Poder definir diferentsequacionsen funció dels paràmetres, és a dir, dotar a la funció de diferents comportaments en funció de les característiques dels paràmetres.

2. Poder donar nom als diferents components d’un paràmetre per poder utilitzar-los de forma aïllada.

Posem per exemple una funció que faci un recorregut damunt una llista i sumi 1 a tots els seus valors (un llistat de comptadors).

dec recorregut : l i s t (num) −> l i s t (num) ;

−−−recorregut ( x : : l ) <= x + 1 : : recorregut ( l ) ;

−−−recorregut ( n i l ) <= n i l ;

En aquest exemple es pot apreciar un aprofitament dels 2 avantatges anteriorment esmentats: per a la primera equació hem pogut donar un nom al primer element de la llista (x), i a la cua de la llista (la resta d’elements després del primer (l)), de manera que podem retornar una llista nova composta d’un primer element incrementat en 1 concatenat amb la resta d’elements (als que recursivament se’ls anirà sumant 1). Si aquesta fos la única equació declarada, veuríem que la funció no seriacompl et ai estariai nd e f i ni d apel cas que la llista estigui buida. És per a aquest motiu que es fa necessari definir una equació per a aquest cas, retornant unni l, i permetent així la correcta execució de les crides recursives ar ecor r eg ut.

Ara ja podem veure la funciómap, on es podrà apreciar un exemple de funcions d’ordre superior amb comprovació de patrons:

typevar alpha ;

dec map: ( alpha −> alpha ) # l i s t ( alpha ) −> l i s t ( alpha ) ;

−−−map( f , x : : l ) <= f ( x ) : : map( f , l ) ;

−−−map( f , n i l ) <= n i l ;

D’aquesta forma tan elegant definim una funció que ens permet aplicar una funció qualsevolf a tots i cada un dels elements d’una llista. Segueix el mateix patró que la funciór ecor r eg ut, però en lloc de sumar 1 a cada element, aplica una funcióf que ha rebut per paràmetre.

Les funcions d’ordre superior plantegen un problema: si puc cridar a una funció amb un valor literal com 3, per que no puc passar una funció com a paràmetre també d’aquesta manera? Sí se pot: és el que es coneix amb el concepte defunció anònima olambda. Suposem que volem cridar a la funciót r ac t adefinida anteriorment, de manera quef sigui una funció que suma 1 a l’element, iguna funció que en resta 1.

L’aplicació de la funció seria:

2.3. Lambda Càlcul

def main : num −> num;

−−−main ( x ) <= t r a c t a ( x , (lambda x => x + 1 ) , (lambda x => x − 1 ) ) Amb la paraulalambda, indiquem l’inici d’una expressió lambda. El que ve a con- tinuació és un llistat de paràmetres, i després del=>, definim el comportament de la funció. D’aquesta manera, l’expressiól ambd ax=>x+1 es pot interpretar com una funció que, donat un valorx, retornax+1.

Aquest mecanisme de funcions anònimes es troba de forma freqüent en llenguatges funcionals i ha estat adoptat per moltíssims llenguatges imperatius tals comC#oJava, degut a la comoditat que ens aporta (tot i que no és més que una facilitat, ja que bé podríem definir les funcions i passar-les com a paràmetre).

2.3 Lambda Càlcul

ElLambda Càlculno és més que una manera de representar funcions matemàtiques introduïda per Alonzo Church al 1941 i que ens permet una representació en base a regles. El que es pretenia era dotar de formalisme als programes i poder explicar- los sense tenir en compte la màquina damunt la que treballen. D’aquesta manera, el LC ens aporta unes convencions sintàctiques molt simples i un seguit de regles i transformacions que s’hi poden aplicar.

Tot llenguatge funcional pot traduir-se a LC i ens aprofitarem d’això per a, en el pro- cés de compilació, traduir el nostre codi a LC, i aplicar les transformacions pertinents.

Sense més preàmbul, anem a veure en què consisteix.

2.3.1 Sintaxi del lambda càlcul

El primer que podem dir damunt la sintaxi del LC és que es basa en definir funcions anònimes (tal com les veiem a la secció anterior). D’aquesta manera, per a la nostra funciódoble, la seva equivalència a LC seria:

λx.+x x

Que si comparam amb com seria si la definim de forma anònima aHope:

lambda x => x + x

Podem només observar dues diferències: On aHopes’utilitza un=>per distingir els argument de la definició (comunament anomenadacos), a LC s’utilitza un ., i que al LC els operadors sempre són de prefix (és a dir, aniran davant dels arguments). A les expressions d’aquesta forma les anomenemabstraccions lambda.

Si el que volem és definir una funció que tingui més d’un argument, ho haurem de fer de forma niada. Per exemple:

λx.λy.∗(+x y) 2

Que es podria llegir com “la funció dexque retorna la funció dey que retorna (x+y)∗2”. Definim les variables que apareixen tot seguit d’unaλcomvariables lligades, corresponents al concepte de paràmetres formals. Com que cada abstracció té un i

només un argument, això ens assegura un currying¹no redundant ja que, si posam parèntesis per il·lustrar l’ordre d’aplicació seria, per exemple:

(...(((λx1.λx2...λxn.E)x1)x2)...xn)

Ara que entenem millor com funciona, podem veure la definició formal de la seva gramàtica:

E X P :=λi d.E X P|i d|E X P E X P|(E X P)|CON S CON S :=const ant

Cal dir que el conjunt deconstantsés arbitrari. La gramàtica es pot simplificar si ens oblidem del símbolCONS, però afegir-lo ens farà més senzill treballar amb LC, ja que ho farà tot més llegible. Un recull de les constants que utilitzarem al llarg del desenvolupament del TFG és el següent:

• El conjuntE.

• El conjunt d’operadors aritmètics (+,-,*,...).

• El conjunt de comparadors (=,6=,<,...).

• CON D: Condicional (equivalent a uni f).

CON D x y z≡i f x t hen y el se z

• C ASE−n: Funció equivalent a unsw i t ch.

C ASE−3k x y z≡

i f k==1t hen x el si f k==2y el si f k==3z

• T U P LE−n: Funció que construeix una tupla denelements.

T U P LE−3x y z≡(x,y,z)

• I N DE X: Selector (tuple indexing function).

I N DE X−2T U P LE−3x y x≡(x,y,z)[1]≡y

1

« La idea de tractar una funció de n arguments com una concatenació de n funcions d’un argument([1])».

Concepte definit perHaskell Curry

2.3. Lambda Càlcul 2.3.2 Reduccions

Damunt expressions LC es poden aplicar certes regles per avaluar-les, comunament anomenadesreduccions. En veurem tres, lesδ-reduccions, lesβ-reduccionsi lesα- reduccions.

Com hem vist a la gramàtica anterior, les mínimes expressions que es poden trobar al LC són les constants. Aquestes expressions són mínimes, irreductibles, i contenen significat per si mateixes. La reducció més elemental que es pot fer és l’aplicació d’a- quests operadors, la que es coneix comδ-reducció. Podem denotar una reducció amb el símbol→indicant de quin tipus de reducció es tracta; en aquest cas−→

δ. Un exemple seria:

∗(+1 2)(−4 1)

−

→δ ∗(+1 2) 3

−→

δ ∗3 3

−

→δ 9

La segona reducció que ens interessa és la que descriu com aplicar abstraccions: la β-reducció. Aquesta reducció es basa en el concepte de substitució. Per entendre com funciona, el millor és que ho vegem amb un exemple:

(λx.+x x) 3−→

β (+3 3)−→

δ 6 Com podem observar amb el símbol−→

β , l’efecte de laβ-reducció és substituir totes les aparicions de la variable lligada definida a l’abstracció, al seu cos, per l’expressió que aparegui com argument. En realitat, com hem dit, aquest és l’efecte d’aplicarla funció.

Però, amb lesβ-reduccions hi pot aparèixer un problema quan una variable lliure té el nom d’una variable lligada. En aquest cas podria passar que substituïm la variable lliure en lloc de la lligada.

λx.(λx.x)(+1x)

Per arreglar aquest problema el que hem de fer és renombrar la variable lligada i les seves aparicions, de manera que no hi ha confusions possibles. Aquest canvi de nom és el que es coneix comα-reducció. D’aquesta manera:

λx.(λx.x)(+1x) 3

−→_α λx. (λx⁰.x⁰) (+1x) 3

−→

β λx. (+1x) 3

−→

β (+1 3)

−

→δ 4

Ara que podem jugar amb les reduccions, val la pena definir el concepteredex.

Definició 5. Diem que una expressió lambda és un redex quan s’hi poden aplicar reduc- cions (REDuctible EXpression).

Juntament amb aquest concepte ens apareix el concepte d’expressió enforma normal.

Definició 6. Una expressió es troba en forma normal quan no presenta cap redex (és a dir, no es pot reduir més).

És important destacar que la forma en la que seleccionem els redexs sobre els quals aplicar reduccions és important, ja que pot variar el resultat. Això es pot apreciar, per exemple si a l’expressió hi ha variables lliures amb el mateix nom que alguna variable lligada. En aquest cas, l’ordre en que seleccionam els redexs ens podria dur a una expressió incorrecta. Suposem la següent definició:

(λx.(λy.λx.+x y)x)

Aquí tenim 2 camins. El primer és aplicar unaβ-reducció, i el segon és primer aplicar unaα-reducció. Mentre que amb la primera opció arribam a una expressió incorrecta, amb el segon hi arribam a una vàlida.

(λx.(λy.λx.+x y)x)

−→_α (λx.(λy.λz.+z y)x)

−→

β (λx.(λy.λz.+z y)) C or r ec t e

−→

β (λx.(λx.+x x)) I ncor r ec t e

Per solucionar aquest problema, el que farem és primer convertir l’expressió aWeak Head Normal Form (WHNF).

Definició 7. Diem que una expressió E es troba en WHNF si:

1. E és una constant,

2. E és una expressió de la formaλx.E’ per a qualsevol E’,

3. E és de la forma PE1E2, ...,Enper a qualsevol constant P d’aritat k>n.

El que farem és no aplicar reduccions damunt expressions en WHNF. Com es pot observar, una expressió amb arguments on l’operador no és constant sí que es podria avaluar. Per exemple:

(λx.(λy.λx.+x y)x) 4

−→

β (λy.λx.+y x) 4

−→

β λx.+4x

2.3. Lambda Càlcul 2.3.3 Supercombinadors

Ara que sabem operar amb les expressions lambda-càlcul, podem passar a veure com solucionem alguns problemes o feim algunes simplificacions mitjançantsupercombi- nadors.

El primer que un pot pensar és: val, sabem com definir expressions equivalents a funcions en LC, però un programa no és més que un recull de funcions que es criden entre elles. Com plantejam aquest escenari? Aquest és l’escenari que es coneix com recursivitat mútua, i per poder-lo solucionar, definirem el supercombinadorT. Però anem pas per pas.

El primer plantejament és el de unificar totes les funcions transformades a LC dins unatupla. És a dir:

T U P LE−n E1E2, ...,En

On cadaE es correspon a la traducció LC de cada una de les funcionsHopeon, les crides a altres funcions, es deixen com a tals. D’aquesta manera, si el que volem és fer una crida a una funciókqualsevol, hem d’utilitzar la constantINDEX:

I N DE X−k T U P LE−n E₁E₂, ...,En

Ara és quan podem definir el supercombinadorT, que prendrà per valor:

T =T U P LE−n E1E2, ...,En

Per fer efectiva, doncs, la crida a funcions dintre d’altres funcions, el que cal fer ara és substituir totes les crides a funcions f_k per:

I N DE X−k T Per tant, el resultat final serà

T = T U P LE−n E₁⁰ E₂⁰, ...,E_n⁰ ∀ E⁰=E_{(fk→I N DE X−k T)}

Hem resolt el problema de les referències entre funcions, però no el de la recursivitat.

Recordem la funciófactorial:

−−−f a c t o r i a l (n) <= i f n == 1 then 1 e l s e n * f a c t o r i a l (n−1);

Que, per obtenir el seu valor LC, s’hauria d’afegir un paràmetre perquè la funció pugui passar-se a si mateixa. Quedaria:

F AC T = λa.λn.CON D(= n1) 1 (∗n(a(−n1)))

És clar que amb aquesta definició, si aplicamF AC T aF AC T i 3, obtindrem el factorial de 3, és a dir, 6, i ho haurem fet de forma recursiva. Podem aconseguir aquest mateix efecte si empram el supercombinadorY, també conegut com acombinador de punt fix. Aquest es defineix com:

Y f = f(Y f)

La definició és prou clara. Si l’aplicam a l’exempleF AC T:

Y F AC T = (λa.λn.CON D (= n1) 1 (∗n(a(−n1))))

→ (λa.λn.CON D(= n1) 1 (∗n(a(−n1))))(Y F AC T)

→ (λn.CON D(= n1) 1 (∗n((Y F AC T)(−n1))))

Així doncs, si combinamY ambT, ja podem representar un programa que suporti la recursivitat mutua. El resultat seria:

Y(λT.T U P LE−n E₁⁰E₂⁰, ...,E_n⁰ ∀ E⁰=E(f_k→I N DE X−k T)

Així doncs, amb aquests conceptes, ja estam preparats per definir el que serà el nostre llenguatge: el llenguatgeFun, així com poder comprendre les dificultats que sens presentaran a l’hora de construir el compilador.

2.4 Dificultats de compilar un llenguatge funcional

Com hem pogut veure, el paradigma de la PF és ben diferent dels paradigmes imperatius.

Això ens presenta algunes dificultats no afrontades quan compilàvem un llenguatge imperatiu:

• Comprovació de tipus. És bastant diferent de la que veiem als llenguatges impe- ratius. Té un caire recursiu degut a que el que avaluem sempre són expressions amb un valor de retorn, ja que als llenguatges funcionals no tenen sentit les assignacions. Per altra banda, com que podem rebre funcions com a paràmetre o retornar-les, és necessari comprovar que encaixen amb el que s’espera. I, el més important, hem de fer inferències de tipus: degut a la possibilitat de definir funcions amb tipus genèrics (typevar). Sens dubte, aquest és el major repte que se’ns presenta.

• Generació de codi intermig. La forma més senzilla és, com ja s’ha esmentat, generar codi LC, per poder, posteriorment, convertir-lo a codi per a la màquina FPM. Aquest camí és completament nou i requerirà els coneixements tant del funcionament d’aquesta màquina com del LC.

• Generació de codi assemblador. Amb un codi imperatiu, el codi intermig generat era un codi a cavall entre l’assemblador i el codi font. Això era bastant natural ja que els llenguatges imperatius provenen de la màquina deVon Neumann. En canvi, per a llenguatges funcionals caldrà fer una petita reinterpretació per poder aprofitar els recursos que ens brinden els processadorsInteli poder adaptar la màquina FPM a aquests.

• Entrada-Sortida. Vinculat amb el punt anterior, el fet d’haver emulat la nostra màquina pròpia dins el processador comú fa que les opcions clàssiques d’entrada- sortida no ens serveixin.

C

3

D ISSENY DEL COMPIL ADOR

3.1 Disseny general

Un compilador té diferents propòsits i veurem que el podem separar en parts per poder aplicar el patró dedivide & conquer(tot i que veurem que les diferents parts estaran comunicades). Això és vital per un projecte gran com és aquest. Els objectius del compiladors a gran escala són:

1. Verificar que el codi que es compila éscorrecte.

2. Generar codi assemblador que faci el que el programador volia fer.

Aquests dos grans punts encara els podem desgranar més. El que primer hauríem de veure és què consideram un codicorrecte. Com a un llenguatge natural, la correctesa d’un llenguatge de programació es pot comprovar si assegurem què:

1. El programa éslèxicamentcorrecte (és a dir, les paraules que hi apareixen són correctes).

2. El programa éssintàcticamentcorrecte (és a dir, les paraules apareixen en se- qüencies correctes).

3. El programa éssemànticamentcorrecte (és a dir, les seqüències de paraules tenen sentit).

Per tant, el primer serà definir les regles lèxiques del nostre llenguatge i construir un analitzador lèxic que ens digui quines paraules han aparegut i en quin ordre, de manera que després, damunt això, puguem passar a l’anàlisi sintàctica. Per aquest motiu, també necessitarem tenir definida la gramàtica del nostre llenguatge, mitjançant la qual, podrem realitzar l’anàlisi sintàctica i construir un arbre que pugui utilitzar l’anàlisi semàntica. Aquesta darrera etapa de comprovacions és també coneguda com

comprovació de tipus, i bàsicament tractarà d’assegurar que el programa és consistent en quant als tipus, una feina que, ja veurem, no ha estat senzilla.

Una vegada sabem que el programa és correcte, guanyam la comoditat de que podem suposar com serà l’entrada que rebem. En aquest cas es tracta de reaprofitar l’arbre sintàctic construït a l’anàlisi sintàctica. Aquesta etapa de traducció de codi també es pot desgranar en parts més petites:

1. Generació de codi lambda càlcul 2. Aplicació de supercombinadors 3. Elevació de lambdes

4. Generació de codi FPM

5. Generació de codi assemblador

Normalment, els processos de traducció de codi dels compiladors passen per gene- rar un pseudo-codi proper a l’assemblador conegut com acodi intermig, de manera que la traducció es fa en dues passes i és més controlada i senzilla. Aquest model del dis- seny d’un compilador és el que es presenta a [3], pràcticament el llibre més important referent a la construcció d’un compilador.

El cas dels llenguatges funcionals és una mica diferent tot i que parteix de la mateixa idea. El nostre codi intermig serà elcodi FPM(Functional Programming Machine), és a dir, una màquina de pila que té la capacitat d’executar codi lambda càlcul. La traducció de la FPM a l’assemblador és molt senzilla, el veritable repte es troba en convertir el codi deFuna lambda càlcul. Però veurem que, fent-ho així, aplicant supercombinadors i elevació de lambdes obtindrem un codi molt més reduït.

Finalment, s’ha dissenyat un programaAdaencarregat de visualitzar el resultat de l’execució del programaFunque es compila (com ja s’ha esmentat al capítol anterior).

Així doncs, per executar l’assemblador general, s’hauria de muntar amb el compilat del programa d’escriptura a fi de poder visualitzar el resultat.

Per veure clarament les parts involucrades en el compilador, es pot mirar el fitxer fun.adb(apèndix C.1) que és la funció principal del projecte on se fan les crides a cadascuna de les diferents etapes, tot comprovant que no hi aparèixen errors.

Val la pena mencionar altres fitxers d’ús general com

• semantic.ads/semantic.adb, que es poden trobar als apèndixs C.2 i C.3. Conte- nen variables d’àmbit global (com la taula de variables, variable d’error, etc).

Declarades al fitxer .ad s, i algunes d’elles inicialitzades al .ad b. També conté la funcionalitat d’us generalTrim, que lleva els espais en blanc d’un string (que aparèixen quan es fa una conversió de int/enumerat a string).

• C.5/C.4 (apèndixs C.5 i C.4) encarregats de la impressió de missatges del compi- lador (en la seva majoria missatges d’error).

3.1. Disseny general 3.1.1 Eines utilitzades

Com ja hem dit abans, el compilador s’ha fet en el llenguatgeAda. El motiu que impulsa aquesta decisió és el seu fort tipat que permet mantenir un control dels tipus molt exhaustius. Aquest avantatge, per a un projecte relativament gran com aquest i on hi ha una certa comunicació entre diferents etapes del desenvolupament, serà vital per garantir-nos una millor llegibilitat del codi, així com fer la depuració molt més senzilla.

L’elecció del llenguatge amb que es va fer el compilador va condicionar l’elecció de l’entorn de treball així com les eines de generació de codi per l’anàlisi lèxica i sintàctica:

• L’entorn de programació utilitzat ha estat elGPS(GNAT Programming Studio), l’I- DE predilecte per treballar en Ada. Tot i que elgnatper sí mateix és suficientment bo, per fer feina damunt un projecte gran i sobretot, com a eina de depuració grà- fica, elGPSens aporta tot un recull de funcionalitats que el fan ideal per aquesta tasca.

• Per a la generació de codi per l’anàlisi lèxica s’ha utilitzat l’einaaflex, que és la coneguda adaptació de l’einaflexperAda.

• L’eina utilitzada per a la generació de codi per l’anàlisi sintàctica ha estatayacc què, igual queaflex, és una adaptació deyaccper aAda.

• Githa estat l’eina amb la que hem dut a terme el control de versions, juntament amb la pàgina GitHub.

• Com ja s’ha esmentat, la solució s’ha desenvolupat per a processadorsIntelamb el seu assemblador x86 (sistemes de 32b), per tal de tenir un major abast del codi generat pel compilador.

• Destacar també l’ajuda que ens ha donat el compiladorgcc, que ens ha permés compilar les diferents parts (compilador + I/O) i muntar-les.

Entrarem en més detall damunt la utilitat de l’aflexi l’ayaccen els capíols 4 i 5 respectivament.

C

4

A ^NÀLISI L ^ÈXICA

La primera passa per construir el compilador ha estat definir el lèxic del llenguatgeFun i la seva anàlisi.

Tota aquesta fase gira entorn al concepte detoken. Anomenaremtokena les unitats mínimes que es poden trobar a un llenguatge i que tenen una funcionalitat per si mateixes. D’aquesta manera, a la següent línia

vartype alpha ;

hi trobam 3 tokens:vartype, una paraula reservada que indica el començament d’una declaració de variable de tipus,alpha, un identificador, i;, que indica el final de línia.

El que haurà de fer l’anàlisi lèxica és, en primer lloc, comprovar que els tokens que apareixen són correctes (per exemple, un identificador no pot començar amb un símbol), en segon lloc enregistrar tots els tokens que apareixen de forma que es faciliti la feina a l’analitzador sintàctic (qui revisarà que els tokens apareixen en l’ordre adequat), i en tercer lloc, enregistrar els noms d’identificadors a lataula de noms(de la qual xerrarem més endavant).

Per això necessitarem passar el nostre lèxic per l’einaaflex, la qual generarà el codi necessari per fer les comprovacions, vinculant cada token que troba amb la crida a una funció que indiquem (la qual s’encarregarà d’enregistrar el token i, si procedeix, l’identificador). Anem a veure, doncs, cada una de les parts que hi intervenen.

4.1 Lèxic del llenguatge Fun

Com s’ha esmentat abans, a l’apèndix A es pot trobar el fitxerfun.lque especifica el lèxic del llenguatgeFun. El que es pot trobar a aquest fitxer són 3 parts separades pel símbol %%:

• Declaració d’expressions regulars constants: A aquesta regió es defineixen expres- sions regulars que s’utilitzaran més endavant:LE T T E Rque defineix el conjunt

de caràcters,D IG I T que defineix el conjunt de dígits,RE PC H ARque defineix el conjunt de símbols, iRE PC H AR NOQUOque representa el mateix conjunt, però sense el símbol ".

• Declaració de tokens: A aquesta regió es troben definits, en forma d’expresions regulars, cada un dels tokens que reconeixerà el llenguatge fun, seguit d’una seqüència de codiAdaque s’executarà cada vegada que es trobi un token situat entre claus ({ i }).

• CodiAdaauxiliar per al generador de l’analitzador.

Per definir les expressions regulars se segueixen les següents normes:

• {}: Representa un conjunt de opcions

• "": Utilitzat per envoltar símbols

• -: Representació d’un rang (p.e. A-Z vol dirdesde A fins a Z)

• *: Estrella de Kleene

• |: ClàusulaOR

• ˆ: ClàusulaNOT

• ?: Seguit d’una expressió, indica que dita expressió pot no aparèixer.

Com es pot apreciar, el lèxic no és idèntic al deHope, sinó que, per gusts personals, s’han triat alguns tokens d’altres llenguatges, principalmentHaskell:

• :=, equivalent al<=de Hope

• && i|com a operadors lògics

• % per a l’operaciómòdul(aHopeés la paraula claumod)

El lector observador haurà vist que no hi ha cap símbol ni paraula clau per definir expressions lambda (funcions anònmies). Això és degut a que la introducció d’aquest element afegiria certes dificultats, sobre tot a l’hora de generar codi, que desviarien una mica l’atenció del problema principal. Tanmateix, com s’ha esmentat, no afegeix funcionalitat, sinó que és una comoditat (és equivalent a definir una funció i passar-la com a paràmetre).

4.2 Construcció l’analitzador

Per a construir el nostre analitzador lèxic hem fet servir l’einaaflex. Aquesta eina llegeix el lèxic definit a un fitxer d’extensió .l i genera el codiAdaequivalent a l’autòmat que pot analitzar les expressions regulars corresponents als tokens definits al fitxer. Aquest autòmat té la particularitat que no és un autòmat acceptador/rebutjador, sinó que ha de determinar de quin token es tracta i executar el codi que se li hagi indicat al fitxer .l.

El codi que es podet trobar al fitxer .l corresponent a cada token és el que s’ha anomenat com arutines lèxiques. El que fan és construir un arbre on els nodes tenen un

4.3. Taula de noms

tipus que defineix de quin token es tracta i, en algunes ocasions, contenint informacions addicionals (tipus d’operador en el cas de operadors aritmètics o lògics, els valors en cas de literals, o el seuiden cas d’un identificador). Aquests nodes s’agrupen en forma d’arbre per tal que l’analitzador sintàctic el pugui recórrer fàcilment i mantenint el seu ordre d’aparició. Es pot veure el llistat de tipus de tokens que l’analitzador utilitzarà per a classificar al fitxerd_tokens.adb(apèndix C.6).

El recull de rutines lèxiques que preparen l’arbre de tokens es pot trobar als apèndixs C.10 i C.11 (c_tree.adsic_tree.adbrespectivament). En ells es poden trobar també les rutines sintàctiques, de les quals xerrarem al capítol següent, i que es poden distingir pel seu prefixe (lrper a les rutines lèxiques isrper a les sintàctiques).

4.3 Taula de noms

Aquesta estructura de dades, extreta de [4], ens permetrà tenir enregistrats els identi- ficadors de manera única gestionant tan sols un codi identificatiu. És evident que la implementació d’aquesta estructura de dades és la de un Hashing, ja que ens permetrà fer consultes amb un cost d’O(1). Concretament, es tractarà d’un hashing tancat on la taula de dispersió apuntarà a un array on s’aniran emmagatzemant tots els noms de identificadors. D’aquesta manera, només emmagatzemarem el nom una vegada. Els detalls d’aquesta estructura de dades es poden veure als apèndixs C.7 (namestable.ads) i C.8(namestable.adb).

C

5

A ^NÀLISI S ^INTÀCTICA

Una vegada que tenim construït un arbre amb els tokens que han aparegut, és hora d’avaluar si han aparegut en un ordre vàlid, és a dir, si el programa éssintàcticament correcte.

El concepte principal de l’anàlisi sintàctica és el deunitat lèxica. Aquest concepte fa referència a un conjunt de tokens que entre ells conformen una unitat amb significat, i serà objectiu de l’anàlisi semàntica determinar si aquestes unitats tenen un significat vàlid.

Per dur a terme la generació del codi d’anàlisi sintàctica es descriurà la gramàtica del llenguatge a un fitxer d’extensió .y amb el qual es construirà un Autòmat Finit Determinista (AFD) que analitzarà que els tokens apareixin en un ordre adequat. A la vegada que es fa l’anàlisi, s’haurà de construir un nou arbre amb l’objectiu d’agrupar tots els tokens d’una mateixa unitat sintàctica. Això facilitarà tractaments posteriors com l’anàlisi semàntica i la construcció de l’arbre lambda-càlcul.

5.1 Fitxer de la gramàtica

De manera similar al que hem vist per al lèxic, aquí s’ha definit un fitxer d’extensió .y que es pot trobar a l’apèndix B d’aquesta memòria. Quan el fitxer s’ha passat per l’einaayacc, ha generat codiAdaequivalent a l’AFD que verificarà que el programa introduït és sintàcticament correcte. A més, també de manera similar, quan identifiqui una unitat sintàctica executarà el codi que es trobi entre claus.

En aquest cas, el fitxer també es troba dividit en tres seccions diferenciades pel símbol %%:

• Definició dels tokens que apareixen a la gramàtica. Aquests tokens han d’estar definits al fitxer C.6. Es defineixen amb la paraula reservada%tokeni es pot fer referència a la seva associativitat amb les paraules%left,%right i%nonassoc per tal que l’analitzador pugui actuar d’una manera o una altre quan troba un

d’aquests tokens. En aquesta secció també s’ha d’incloure una referència a l’arbre lèxic generat a l’anàlisi lèxica amb la paraula%with.

• Definició de la gramàtica. A aquesta regió es defineixen les produccions que conformen la gramàtica del nostre llenguatge. La sintaxi serà el nom del símbol seguit de :, seguit de les diferents derivacions que hi pot tenir, separades pel símbol|. A més, de igual forma que succeïa amb el lèxic, aquí podem indicar una seqüència d’instruccions enAdaque s’han d’executar quan aquella regla s’aplica.

• La darrera secció contindrà un bloc de codiAdaque envoltarà el codi de l’AFD.

Concretament, el codi de l’AFD serà introduït on es trobi la marca ##.

5.2 Construcció de l’arbre sintàctic

Per entendre com es construeix l’arbre sintàctic, val la pena tornar a les seqüències de codiAdaque es poden posar devora de cada derivació. Amb el símbol $$ indicaríem el node corresponent a la derivació, i amb $xindicaríem la posició d’un símbol. Així, per exemple, amb la següent derivació,

P ROG: DEC LS E sr_pr og($$, $1, $2);

estaríem dient que quan s’executi, s’haurà de cridar a la funciósr_progpassant-li com a argument el node corresponent a la reducció ($$), el node corresponent al símbol DEC LSi el node corresponent al símbolE. D’aquesta forma, es podrà construir l’arbre sintàctic, ja que el que farem és penjar els nodesDEC LSiEdeP ROG.

Les rutines que s’encarreguen de la construcció de l’arbre sintàctic es poden trobar al mateixos fitxers que les rutines de construcció de l’arbre lèxic (veure apèndixs C.10 i C.11 d’aquesta memòria).. Aquests fitxers es complementen amb el fitxerd_tree.ads (apèndix C.9), que conté la definició del tipusnode, tipus del qual es composa l’arbre sintàctic. Allà es poden veure tots els tipus de nodes que hi poden aparèixer i de què es composen. El resultat final, per tant, és un arbre denodesque tenen un tipus i que tenen diferents fills en funció d’aquest. Així doncs, recórrer aquest arbre per interpretar el significat del programa introduït queda reduït a un simple recorregut a un arbre.

5.3 La gramàtica de Fun

Així com amb el lèxic només s’han explicat les diferències (ja que el fitxer .l és bastant explicatiu per si mateix), amb la gramàtica val la pena aturar-se a fer una explicació més detallada. Per tant, a continuació, s’explicaran les regles més importants i/o confuses de la gramàtica.

El primer a comentar és l’estructura principal d’un programa enFun:

PROG:

DECLS E { sr_prog ( $$ , $1 , $2 ) ; }

;

Aquesta producció ens vol dir que un programaFuncomençarà amb les declaraci- ons i definicions necessàries per, finalment, poder executar l’expressió introduída al final del codi.

5.3. La gramàtica deFun

Però, quines declaracions ens podem trobar aFun? Si bé a un llenguatge declaratiu, són molts els tipus de sentències que hi apareixen (definició de funció, assignació, declaració de variable, condicional, bucle, etc.), aFuntenim un recull molt petit d’a- questes:

DECL:

TYPEVAR_DECL { sr_typevar_decl ( $$ , $1 ) ; }

| TYPE_DECL { sr_type_decl ( $$ , $1 ) ; }

| DATA_DECL { sr_data_decl ( $$ , $1 ) ; }

| FUNC_DECL { sr_func_decl ( $$ , $1 ) ; }

| EQUATION { sr_eq_decl ( $$ , $1 ) ; }

;

O el que és el mateix: declaració de variable de tipus (typevar), declaració de tipus (type), declaració de dada (data), declaració de funció (dec), i equació (− − −f(x) :=...).

Les produccions corresponents a aquestes sentències son trivials en la seva majoria.

No obstant això, sí val la pena comentar algunes produccions que es poden trobar a nivells inferiors. Un exemple és el deT U P LETY PE, que defineix la gramàtica per a les definicions de tipus que podem trobar a una declaració de funció o tipus:

TUPLE_TYPE :

TUPLE_TYPE cart_prod C_TUPLE_TYPE { sr_tuple_type ( $$ , $1 , $3 ) ; }

| C_TUPLE_TYPE { sr_tuple_type ( $$ , $1 ) ; }

;

C_TUPLE_TYPE :

FCALL { sr_c_tuple_type ( $$ , $1 ) ; }

| o_par TUPLE_TYPE arrow TUPLE_TYPE c_par { sr_c_tuple_type ( $$ , $2 , $4 ) ; }

;

Es pot observar el caràcter recursiu d’aquesta definició. La funció deT U P LE_T Y PE és la de definir tuples d’infinita mida. Recordem que qualsevol element d’una tupla pot ser una funció, i aquí és on entra en lloc la segona derivació deC_T U P LE_T Y PE. És important observar que aquesta reducció fa ús dels parèntesi, els quals permeten distingir les definicions de tipus funció i evitar ambigüitats. Ja que ha aparegut,F C ALL no és més que la producció encarregada de definir les crides a funcions (no val la pena entrar en més detall).

L’altre producció important és la d’una expressió E. Aquesta la podem trobar a les equacions (tant en el reconeixement de patrons com a la definició de l’equació), als paràmetres d’una crida a funció, a les expressions condicionals, i a les tuples.

E :

o_par E c_par { sr_e ( $$ , $2 ) ; }

| E plus E { sr_plus ( $$ , $1 , $3 ) ; }

| E sub E { sr_sub ( $$ , $1 , $3 ) ; }

| E prod E { sr_prod ( $$ , $1 , $3 ) ; }

| E div E { s r _ d i v ( $$ , $1 , $3 ) ; }

| E mod_op E { sr_mod ( $$ , $1 , $3 ) ; }

| E and_s E { sr_and ( $$ , $1 , $3 ) ; }

| E or_s E { sr_or ( $$ , $1 , $3 ) ; }

| E relop E { s r _ r e l o p ( $$ , $1 , $2 , $3 ) ; }

| E conc E { sr_econc ( $$ , $1 , $3 ) ; }

| not_s E { sr_not ( $$ , $2 ) ; }

| sub E { sr_usub ( $$ , $2 ) ; }

| COND { sr_econd ( $$ , $1 ) ; }

| LIST_E { s r _ e l i s t ( $$ , $1 ) ; }

| TUPLE { s r _ t u p l e ( $$ , $1 ) ; }

| LITERAL { s r _ e l i t ( $$ , $1 ) ; }

| FCALL { s r _ e f c a l l ( $$ , $1 ) ; }

;

És important destacar el fet que la sentència condicional, que correspon a la pro- duccióCON D, es troba com a reducció de E ja que, com a tota expressió, retorna un valor, i per tant pot encaixar en quasi tots els àmbits on pot encaixar una expressió.

C

6

A ^NÀLISI S ^EMÀNTICA : C OMPROVACIÓ DE TIPUS

La darrera passa per verificar que el programaFunque s’intenta compilar és correcta és l’anàlisi semàntica. Aquesta etapa és la que s’encarrega de validar que el programa té un significat vàlid, el que és equivalent a dir que el programa és consistent en els tipus utilitzats. Per aquest motiu, aquesta etapa es coneix també com acomprovació de tipus.

Per fer aquesta anàlisi es farà ús d’una estructura de dades anomenadataula de símbols, la qual s’exposa a la secció 6.1.1. Aquesta estructura permet emmagatzemar noms amb la seva descripció per tal de poder fes consultes a la taula cada vegada que ens trobem un símbol i poder detectar així incongruències.

Val la pena entendre bé com funciona la taula de símbols abans d’explicar les com- provacions de tipus que es duen a terme. No s’entraran en detalls del codiAdaja que és un codi amb poca complexitat lògica, però molt dens degut al fort caràcter recursiu de la gramàtica. Això fa que les funcions de validació tenen diferent comportament depenent d’on ve aquest element. Un exemple és el de l’analitzador deE. No és el mateix analitzar una expressió que defineix una funció, que una expressió que apareix a la zona de reconeixement de patrons. Per a qualsevol consulta, el codi es pot trobar als apèndixs C.15 i C.16 d’aquesta memòria.

6.1 Estructures de dades auxiliars

6.1.1 Taula de símbols

A fi de tenir moltes facilitats durant la comprovació de tipus, podem fer ús de laTaula de símbols. La seva definició completa es pot trobar al fitxerdecls-d_symbol_table.ads (apèndix C.13) i la seva implementació aldecls-d_symbol_table.adb(apèndix C.14).

La taula de símbols és una estructura de dades que ens permet emmagatzemar informació referent a un identificador. És necessària per la raó òbvia de no haver de