Llenguatges de Programació
Fernando López Ostenero i Ana García Serrano
El conegut concurs “Xifres i lletres “proposa als seus participants dos tipus de proves: unaprueba de xifres en la qual han d’aproximar el més possible a un nombre objectiu utilizandooperaciones bàsiques sobre una sèrie de números i una prova de lletres, en la qual han de trobar lapalabra (vàlida) més llarga que sigui possible escriure amb un seguit de lletres.
En aquesta pràctica crearem un programa que resoldrà la segona d’aquestes pruebas.Concretamente el programa rebrà una sèrie de lletres i ‘trobarà tots els paraules válidasque es puguin construir amb elles. Per comprovar si una paraula és vàlida o no, és imprescindibleel ús d’un diccionari.
Per a això, es proporcionarà un fitxer amb el diccionari en forma de llista de 79.517 palabraspertenecientes a el diccionari de la RAE perquè els estudiants puguin provar el seu programa. Paraevitar problemes deguts a la codificació de caràcters, s’han esborrat totes les paraules quecontienen la ñ i s’han eliminat els accents gràfics.
Així doncs, la pràctica es dividirà en dues fases diferents:
- Creació de l’diccionari: es carregarà un fitxer de text que conté les paraules que considerarem vàlides (una paraula per línia) i s’inserirà cadascuna d’elles en una estructura de diccionari sobre la qual s’han de consultar les possibles paraules .
- Cerca de paraules: una vegada es disposi de l’diccionari, el programa preguntarà a l’usuari la seqüència de lletres a analitzar i tornarà totes les possibles paraules vàlides que es puguin construir a partir d’aquestes lletres, ordenades alfabèticament i agrupades per mida de més a menys.
per tal com l’entrada / sortida en el paradigma funcional no és part de l’temari que estudiaen l’assignatura, totes les funcions encarregades de llegir el diccionari des d’un fitxer o de l ainteracción amb l’usuari es donaran programades per als estudiants. En aquest enunciat es donarà unaexplicación de l’funcionament d’aquestes funcions.
Enunciat de la pràctica
La pràctica consisteix a elaborar un programa en Haskell que carregui un fitxer de text conpalabras vàlides i creï un diccionari. Un cop fet això, el programa preguntarà a l’usuariopor diferents seqüències de lletres i retornarà les paraules vàlides (aquelles presents en eldiccionario) que es puguin construir en base a les lletres disponibles.
Exemple 1: el programa busca el fitxer de l’diccionari per paraules (diccionario.txt), construeix el diccionari i espera que l’usuari introdueixi una seqüència de lletres:
* Main > mainCargando llista de paraules des del fitxer diccionario.txt79517 paraules llegides
Introdueix seqüència de lletres:
Exemple 2: amb el diccionari anterior ja carregat, l’usuari introdueix la seqüència de lletres “aosc” i el programa retorna totes les paraules de l’diccionari que poden construir-se utilizandoesas lletres:
Aquí podem veure el diccionari resultant representat gràficament en forma d’arbre. com seindicó prèviament, els nodes intermedis (excepte l’arrel, representada com RN) són els únics quecontienen caràcters. I la concatenació dels caràcters que formen el camí des de l’arrel acualquiera dels nodes fulla (representats com WN) ens indica les paraules presents en eldiccionario.
Per a una millor comprensió de l’estructura de dades a utilitzar, suggerim als estudiants queinviertan un temps recorrent el diccionari mostrat a la Figura 1 per a comprovar quecontiene exactament les onze paraules indicades en la llista que s’ha utilitzat per a crear-lo.
2.2 Estructura de mòduls de la pràctica
La pràctica està dividida en dos mòduls, cadascun en un fitxer independent el nombrecoincide (incloent majúscules i minúscules) amb el nom de la lliçó i l’extensió és .hs:
- mòdul Diccionari : dins d’aquest mòdul es programaran les funcions de construcció i accés a l’diccionari. Inclou, a més, la definició de l’tipus de dades Diccionari.
- Mòdul Main: aquest mòdul conté el programa principal i totes les funcions encarregades de carregar la llista de paraules i interactuar amb l’usuari.
Atès que un estudi més profund dels mòduls en Haskell està fora de l’àmbit de laasignatura, només indicarem que cada mòdul importa una sèrie de mòduls que són necesariospara seu funcionament. En la nostra pràctica el mòdul Main importa (a més de l’móduloDictionary) mòduls addicionals per poder treballar amb la sortida, fitxers i convertir aminúsculas totes les lletres. A més, la llista d’identificadors entre parèntesis que acompanya alnombre de la lliçó Diccionari representa les definicions de tipus i funcions que el móduloexporta.Qualsevol altra definició es considerarà privada, sent només accessible pel mòdul.
Figura 1: Diccionari representat en forma d’arbre
2.3 Tipus de dada Diccionari (mòdul Diccionari)
en aquest apartat anem a escollir el tipus de dades que utilitzarem per emmagatzemar undiccionario en la pràctica. Està definit en la part de la lliçó Diccionari que proporciona elEquipo Docent. Tal com hem vist en l’apartat anterior, un diccionari serà un arbre en elque els nodes intermedis de contenir un caràcter, mentre que els nodes fulla ens donaran lainformación de quines paraules pertanyen a l’diccionari. Així doncs, la definició de l’tipus Dictionaryserá la següent:
data Diccionari = ROOTNODE | LETTERNODE Char | WORDNODE
és a dir, un diccionari és o bé un ROOTNODE (node arrel) que conté una llista de diccionaris, unLETTERNODE (node lletra) que conté un Char i una llista de diccionaris, o bé un WORDNODE (node paraula) que serà un node fulla que ens marcarà que la concatenació de totes les letrascontenidas en els nodes des de l’arrel ( que no conté cap) fins al pare de el node fulla formanuna paraula vàlida de l’diccionari.
Aquest tipus de dades s’afegeix com a instància de la classe Show, per poder visualitzar el contingut deun element de tipus diccionari i així facilitar la tasca de programació de les funcions decreació de l’diccionari.
la representació interna de l’diccionari de la Figura 1 seria la següent:
ROOTNODE]]], LETTERNODE ‘c’], LETTERNODE ‘s’, LETTERNODE ‘c’], LETTERNODE ‘o’]]], LETTERNODE’o ‘]]], LETTERNODE’ o ‘]]]], LETTERNODE’ s ‘] ], LETTERNODE ‘o’]]]]
la qual és una mica més complicada de llegir que la seva representació gràfica.
2.4 Programa principal (mòdul Main)
el mòdul Main conté el programa principal, ja programat per l’equip docent. Hayfunciones que utilitzen mònades i estan escrites utilitzant la “notació do”, que és una notaciónpara facilitar l’escriptura de concatenacions de funcions monádicas. Sense entrar en demasiadodetalle sobre el funcionament de les mònades, anem a explicar els tipus de dades definits i quéhace cada funció .
tipus de Dades
- WordsN: representa una llista de paraules. Utilitzarem aquest tipus per referir-nos a una llista de paraules totes de la mateixa longitud i ordenades alfabèticament.
- Words: representa una llista de WordsN. Utilitzarem aquest tipus per referir-nos a una llista de paraules agrupades en llistes de paraules de la mateixa longitud i ordenades alfabèticament.
Funció insertInTree
El seu tipus seria insertInTree :: String – > Diccionari – > Diccionari. Aquesta funció és la quese s’encarrega d’inserir una paraula en el diccionari però ja pensat com un arbre. el primerparámetro hauria de ser la resta de paraula que encara queda per inserir i el segon paràmetre el nododel arbre a partir de l’quin s’hauria inserir aquesta resta de paraula.
Funció insertChild
De tipus insertChild :: Char – > – > – >. Al primerparámetro rep el primer caràcter de la resta de paraula a inserir, el segon paràmetre la resta dela paraula a inserir (sense aquest primer caràcter), el tercer paràmetre una llista d’elements de tipoDictionary (que seran els fills d’un node). Retorna la llista de fills de el node correctamentemodificada.
Aquesta funció s’encarrega de buscar el fill de el node actual on s’ha de continuar la inserció delos caràcters que encara queden de la paraula actual. En cas que aquest fill no existeixi, la funció lodeberá crear. Un cop localitzat (o creat) el fill correcte, la funció ha de continuar la insercióndel resta de caràcters de la paraula a partir d’aquest fill. En aquest punt suggerim als estudiantescrear “a mà” el diccionari representat a la Figura 1 per a una millor comprensió de l’procesode inserció de paraules al diccionari.
2.6 Consultes a l’diccionari (mòdul Diccionari)
en aquest apartat tractarem sobre les consultes a l’diccionari. el nostre objectiu serà programar la funció search que rep una seqüència de caràcters i un diccionari. Ens retorna la llista depalabras, ordenades alfabèticament, que estan contingudes en el diccionari i que es puedenconstruir amb els caràcters de la seqüència.
search :: String – > Diccionari – >
per exemple, si busquem la seqüència “Cascão” sobre el diccionari representat a la Figura 1, hauríem d’obtenir la següent llista de paraules:
Cal notar que “casos” i “ocàs”, presents al diccionari, no poden formar-se amb les lletres de lasecuencia, ja que aquesta només conté una ‘s’ (i “casos” té dos) i 1 ‘o’ (i “ocàs” té dos).
Com realitzarem la recerca?Anem a suposar que ja hem fet un recorregut previoque ens ha portat a un node de l’arbre (que no és un full). Per tant, tindrem una secuenciade caràcters encara no utilitzats i el començament d’una paraula format pels caràcters presentesen el camí des de l’arrel a el node actual.
Ara analitzem tots els fills de el node actual:
- Si un fill és un WORDNODE, significarà que la paraula que ja tenim formada pertany a l’diccionari, amb la qual cosa, caldrà afegir-la.
- Si un fill és un LETTERNODE, contindrà un caràcter. Únicament si el caràcter pertany a la seqüència encara no explorada (en qualsevol posició, no necessàriament el primer), haurem d’explorar recursivament aquest fill, afegint a la paraula ja formada el caràcter de l’LETTERNODE i eliminant aquest caràcter de la seqüència encara no explorada.
de nou tornem a recomanar que els estudiants inverteixin un temps en realitzar esterecorrido sobre l’arbre de la Figura 1 per a la seqüència “Cascão” i comprovin així que seobtienen exactament les paraules indicades.
a l’igual que en l’apartat anterior, la funció search necessitarà una sèrie de funcionesauxiliares (que tampoc seran visibles des de l’exterior de la lliçó). Les més importants són lasdos següents:
funció searchInTree
El seu tipus seria searchInTree :: String – > String – > Diccionari – >. al primerparámetro rep els caràcters de la seqüència encara no utilitza dues, en el segon rep la palabraque ja s’ha format fins a arribar a el node de l’arbre que es rep com a tercer paràmetre.
Ha de tornar totes les paraules contingudes en el diccionari el començament sigui el contingut delsegundo paràmetre i continuïn a partir d’el node actual (tercer paràmetre) emprant únicamentecaracteres de la seqüència encara no explorada (primer paràmetre).
Funció searchChild
de tipus searchChild :: String – > String – > Diccionari – >. La funció rep-seqüència encara no explorada, el començament de paraula ja construït (basant-se el recorregut empleadopara arribar a aquest node des de l’arrel) i un node (fill de el node que s’està explorant actualment) .Aquesta és la funció que aplicarà l’algoritme explicat anteriorment per tornar la llista depalabras que es poden formar amb el començament ja construït, i amb els caràcters que encara no sehan utilitzat.
Qüestions sobre la pràctica
la resposta a aquestes preguntes és optativa. No obstant això, si l’estudiant no respon a estaspreguntas, la qualificació de la pràctica només podrà arribar a 6 punts sobre 10.
- (1’5 punts). Suposem una implementació de la pràctica en un llenguatge no declaratiu (com Java, Pascal, C …). Comenteu quins avantatges i quins desavantatges tindria enfront de la implementació en Haskell. Relacioni aquests avantatges des del punt de vista de l’eficiència pel que fa a la programació i l’execució. Quin seria el principal punt a favor de la implementació en els llenguatges no declaratius? I el de la implementació en Haskell?
- (1’5 punts). Indiqui, amb les seves paraules, què permet gestionar el predicat predefinit no lògic, tall (!), En Prolog. Com es realitzaria aquest efecte en Java? Justifiqueu la resposta.
- (1 punt). Per als tipus de dades de el problema definits en Haskell (en tots dos mòduls), indiqui quines classes de constructors de tipus s’han utilitzat en cada cas (veure capítol 5 de el llibre de l’assignatura).
Documents a lliurar
Cada estudiant haurà de lliurar la següent documentació al seu tutor de pràctiques: – Codi font en Haskell que resolgui el problema plantejat. Per a això s’hauran de lliurar els fitxers Letras.hs i Diccionario.hs, amb les funcions descrites en aquest enunciat, així com totes les funcions auxiliars que siguin necessàries. – Una memòria amb: – Una petita descripció de les funcions programades. – Les respostes a les qüestions sobre la pràctica.