PARSER in PROLOG

[prolog]

Sto imparando il PROLOG e spero di essere nella sezione giusta.
Ho creato un semplice database PROLOG con fatti e regole:

Codice: Seleziona tutto

possibile_coppia(X,Y):-ragazzo(X),ragazza(Y).
ragazzo(luca).
ragazzo(carlo).
ragazzo(luigi).
ragazza(romy).
ragazza(sonia).


Ora vorrei capire come fare a creare un PARSER ed una grammatica in PROLOG che permetta al programma sopra di rispondere in linguaggio naturale in italiano,
Ad esempio io chiedo "Chi è sonia" e lui mi risponde "Una ragazza" etc...
Non cerco la pappa pronta ma datemi per lo meno un esempio di codice di un PARSER così mi studio il codice
per capire come funziona.
Grazie in anticipo

[fairyvilje]

Le interrogazioni che poni in prolog non sono esposte in linguaggio naturale, ma hanno un formato di query estremamente specifico.

Fare quello che chiedi è tremendamente difficile perché il processing del linguaggio naturale è immensamente più complicato di quello che il tuo corso (e probabilmente il tuo tempo libero) può effettivamente chiederti. E di sicuro non lo implementi in prolog .

A livello logico poi c'è un problema di fondo secondo me. Non hai specificato la semantica di ragazzo e ragazza ed il fatto che possano rispondere come attributi ad un interrogazione di un predicato "chi è".

[prolog]

OK capisco, però sono riusciti ad implementare una cosa del genere allo stato dell'arte.
Ad esempio alcuni modelli di mercedes hanno una cosa del genere a bordo detta AI.
Cosa mi consigli di fare per imparare ad implemntare una cosa che si avvicini solo lontanamente a quello che ho chiesto sopra?
Intendo fargli capire delle domande semplici non complicate.
Potete darmi un esempio di codice di un PARSER magari in altri linguaggi?

[fairyvilje]

Si esatto, stato dell'arte. In ambito aereospaziale questa cosa esiste almeno dagli anni 80 credo e fa uso di un linguaggio super-semplifcato basato sull'inglese per interrogare database circa voli, tratte e via dicendo.
È lo sforzo congiunto di centinaia di persone che ci hanno lavorato attivamente per decenni, capisci bene che farlo da sé può essere abbastanza complicato senza il corretto background.

In generale nel gestire i linguaggi naturali ci sono due approcci, uno basato sulle grammatiche formali ed uno su varie tecniche di machine learning.
Quello che vuoi fare te è più probabilmente legato alle prime.
Ti consiglio un libro per iniziare: Heim & Kratzer: Semantics in Generative Grammars.
Ti da le basi modellistiche minime per affrontare il problema di modellare un linguaggio naturale in modo sensato, specialmente se dominio-specifico come vorresti te.
A livello più operativo prova a cercarti le slides di qualche corso di computational linguistics.

Per poi implementare il tutto ci sono un botto di librerie e frameworks che ti semplificano parte del lavoro, ma quello dipende anche dal linguaggio che usi e dal fatto che tu abbia padroneggiato i principi di base della materia.

[rugweri]

Potete darmi un esempio di codice di un PARSER magari in altri linguaggi?

Il sempre gentilissimo fairyvilje te l'ha suggerito implicitamente, ma io quando leggo queste domande ho come l'impressione che a volte il messaggio non sia chiaro: realizzare un interprete del linguaggio naturale (che non è un parser, ma qualcosa di molto più complesso) è un compito che richiede moltissimo tempo e soprattutto delle competenze tutt'altro che banali. Già solo la scrittura di un interprete per "little languages" è qualcosa che può richiedere mesi a un programmatore non doverosamente preparato, quindi non credo di esagerare se affermo che per fare un interprete per un linguaggio naturale potrebbe non bastarti tutta la vita che hai davanti.

Giusto per essere chiari, le basi minime che devi studiare per poter anche solo tentare l'impresa sono le seguenti:

- Un buon linguaggio di programmazione come ad esempio il C... e attenzione, quando dico che devi studiarlo non intendo che devi imparare a scriverci dei programmini: intendo che se nella libreria standard c'è un punto in cui viene definita una macro invece che una funzione vera e propria tu lo devi sapere. Tempo di apprendimento stimato: circa 2-3 anni se programmi ogni giorno e ti cimenti nella scrittura di codice quanto più variegato possibile.
- MATEMATICA, e non lo scrivo in maiuscolo per caso: contrariamente a quanto molti smanettoni credono, l'informatica è prima di tutto matematica: dall'algebra di base alla teoria degli automi basata sui semigruppi passando per la teoria dei grafi e persino per l'analisi funzionale, se vuoi davvero capire cosa stai facendo (e se vuoi maneggiare le semantiche formali - perché di questo si parla quando si parla di interpretare un linguaggio naturale - lo devi capire per forza) devi conoscere quanto più possibile. Tempo di apprendimento stimato: 4-5 anni se impari a velocità supersonica.
- Algoritmica generale con cenni di teoria della complessità (la vedrai meglio dopo): strutture dati fondamentali (liste, tabelle di hash, grafi, code con e senza priorità...) con relativi algoritmi (dei quali, avendo studiato prima la matematica, riuscirai a capire il senso) e loro complessità, programmazione ricorsiva e dinamica (passando per gli algoritmi greedy, che è sempre bene conoscere perché in molti casi ti salvano) e quant'altro. Tempo di apprendimento stimato: 1 anno per avere almeno un'idea di base e aver imparato a pensare come qualcuno che capisce davvero il codice che scrive, probabilmente 2-3 per capire davvero.
- Teoria dei linguaggi formali: cosa sono le grammatiche formali, quali sono e che caratteristiche matematiche hanno gli interpreti per i linguaggi dei vari livelli della gerarchia di Chomsky (e qui capirai perché la teoria dei semigruppi è fondamentale), caratteristiche fondamentali degli automi per linguaggi a lunghezza infinita, differenze tra i vari tipi di macchina di Turing e modelli alternativi (uno tra tutti la macchina di Lambek, ma di modelli ce ne sono tantissimi), collegamento con la teoria della complessità e con i limiti della computazione. Tempo di apprendimento stimato: diciamo 2 anni per essere molto ottimisti, personalmente ritengo che per capire davvero potrebbe volerci molto di più.
- Logiche formali: almeno la logica proposizionale e la logica predicativa vanno conosciute alla perfezione e non meno vanno conosciuti gli algoritmi di minimizzazione e analisi quali ad esempio l'algoritmo DPLL, il vecchio algoritmo di Quine-McCluskey e almeno due versioni di ESPRESSO (l'algoritmo esatto e una delle varie versioni euristiche, per dire). Per completezza andrebbero studiate anche le basi delle logiche modali, ma facciamo finta di niente... Tempo stimato: 6-9 mesi di studio a medio-alto livello di concentrazione, anche perché è fondamentale che ogni spunto di riflessione e approfondimento sia colto e sviluppato.
- Teoria dei linguaggi di programmazione: si tratta probabilmente dell'unico modo sensato per farti vedere delle semantiche formali senza farti fare un frontale contro le difficoltà del linguaggio naturale, per cui è ovviamente necessario che tu sfrutti questa "palestra" nel modo migliore e dunque che impari come si deve cosa sono i linguaggi di programmazione, che caratteristiche hanno e come si definiscono e manipolano le loro sintassi e semantiche, ponendo particolare attenzione ai vari tipi di semantica dinamica e alle differenze tra loro. Fatto ciò, è fortemente raccomandato lo studio della teoria di base dei compilatori come trattata ad esempio nell'Aho-Lam-Sethi-Ulmann, così magari capisci perché quello che vuoi fare non è un semplice parser. Tempo di apprendimento stimato: a mio avviso per le basi minime dell'argomento non meno di 1 anno di studio assistito (e cioè con l'assistenza di un docente), anche perché trovare libri di livello non troppo alto che spieghino bene le semantiche formali non è facilissimo.
- Teoria del linguaggio naturale: cosa sono i linguaggi naturali in termini formali, come vengono modellati e trattati, quali sono gli strumenti per la loro manipolazione algoritmica e come vengono usati davvero. Tempo di apprendimento stimato: se te la cavi in meno di 1 anno (di studio assistito) ti faccio un applauso, personalmente stimo che 2 anni siano il minimo sindacale per avere il tempo di capire e applicare almeno i concetti fondamentali.

Questa è la storia, senza mezzi termini. Stando così le cose, a te la scelta: vuoi dedicare i prossimi 10-15 anni a studiare per questo progetto - scelta nobilissima e rispettabile che ti porterà a imparare tantissime cose interessanti e sconosciute anche alla stragrande maggioranza degli informatici - oppure ti aspettavi di potercela fare semplicemente leggendo il codice di un interprete (che è molto più di un parser, lo ribadisco) e quindi ora vuoi mollare?


Una nota a margine: esistono, come ti è già stato detto, librerie che semplificano la scrittura del codice e ti nascondono molti dei dettagli tecnici delle operazioni svolte... questo però non vuol dire che tu non debba sapere esattamente cos'è che non stai programmando esplicitamente, quindi non ti sognare neanche per sbaglio di poter tagliare i tempi di studio. Non mi piace essere il "cattivo" della discussione, perché il mio interesse è motivare le persone a studiare e non farle scappare via, ma è bene non dimenticare mai qual è la realtà delle cose.

[prolog]

OK ho capito mollo!!
Non voglio passare il resto della mia vita a studiare logica formale etc...

[DarwinNE]

Implementare qualcosa in grado di comprendere il linguaggio naturale scritto è un'impresa mostruosa, come molto ben descritto da fairyvilje e rugweri.

E' invece abbastanza semplice scrivere un limitatissimo parser capace di interpretare semplici comandi come:

ACCENDI LA LAMPADA
CHIEDI A MARIO DI LUISA
APRI LA PORTA CON LA CHIAVE

Posso proporre una versione molto semplice, che è quella che ho usata per alcuni giochi di avventura testuale.

Sono infatti tutte frasi composte da due o tre termini che possono essere messi in un dizionario. Nel dizionario viene memorizzata la categoria di ogni termine. Per esempio, ACCENDI, CHIEDI e APRI sono dei verbi, LAMPADA, PORTA e CHIAVE sono oggetti, MARIO e LUISA sono persone.
Per capire il "senso" del comando, basta:
- scandire la frase e riconoscere il verbo e quali oggetti si applica, ignorando tutto il resto.
- eseguire l'operazione in questione, sempre se ha senso.

Ovviamente tutto questo permette solo di ottenere una versione alquanto stereotipata della lingua corrente, ma ciò basta in un certo numero di situazioni simpatiche. Guarda per esempio questo giochino che ho scritto in inglese:

[rugweri]

Approfitto dell'ottima proposta di DarwinNE per farti notare alcune cose, prolog, che ritengo sia importante mostrarti per farti capire perché ho scritto che un interprete per un linguaggio naturale è davvero complesso e richiede competenze non banali e tantissimo lavoro.

1) Se osservi attentamente l'interprete del gioco proposto, puoi notare che lavora praticamente sempre con frasi a struttura fissa (verbo + complemento oggetto con eventuale specificazione + eventuale complemento di mezzo); nel linguaggio naturale, invece, una struttura fissa non è garantita: nulla (se non il contesto del discorso, ulteriore complicazione) rende "Un caffé è ciò che voglio" meno sensato di "Io voglio un caffé". La struttura fissa prevista per le frasi interpretate nel gioco non è casuale: verbo+complemento è letteralmente l'equivalente della struttura "azione da compiere + entità su cui lavorare" che sta alla base delle istruzioni in praticamente qualsiasi linguaggio di programmazione procedurale (e anche nei linguaggi orientati agli oggetti, se aggiungi come ulteriore elemento la possibilità di avere un oggetto "proprietario" dell'azione da compiere).
2) La semantica dei comandi (perché questo sono) impartiti all'interprete integrato nel gioco è sempre ben chiara e del tutto indipendente dal contesto: non ci sono ad esempio casi in cui un verbo è usato in senso figurato o una parola "imperfetta" è usata per sostituire la denominazione esatta di un oggetto o si fa ricorso a figure retoriche o si compongono delle parole del vocabolario per formarne delle altre, tutte cose che invece sono normali ed estremamente frequenti nei linguaggi naturali. Non starò qui a spiegarti la teoria dietro a tutto questo: se ti interessa segui il percorso che ho indicato fino ad arrivare ai linguaggi formali.; quel che mi interessa che tu capisca è che di base l'interprete del gioco lavora come se avesse una "tabella" che mappa univocamente ogni parola sul relativo significato, cosa che nei linguaggi naturali non è quasi mai possibile (soprattutto se consideri, come già accennato prima, che i linguaggi naturali sono dipendenti dal contesto).
3) Date le semplificazioni spiegate nei precedenti punti e dati gli ovvi limiti del linguaggio del gioco (che potrà contenere... diciamo 200 parole?), l'interprete di DarwinNE può essere implementato anche ignorando del tutto la teoria dei linguaggi formali e dunque non costruendo esplicitamente (implicitamente lo si fa lo stesso, ma non è necessario saperlo) una grammatica formale e a maggior ragione una semantica formale. Prova a fare la stessa cosa con un linguaggio naturale, che di parole ne ha a migliaia (senza tener conto della possibilità di creare neologismi), non obbliga a un ordine preciso delle parole nella costruzione delle frasi, ammette proposizioni subordinate e coordinate, permette di inserire in una frase un riferimento a qualcosa che potrebbe non solo non essere nella stessa frase ma addirittura neanche nello stesso periodo, ha una grammatica relativamente complessa da formalizzare (e comunque dipendente dal contesto in molti casi) e non ha una semantica univoca...

[prolog]

[...]

Il tuo interprete può essere realizzato pure con un linguaggio procedurale tipo il python?
So che python ha una librareria che si chiama NLTK e può suddividere la frase in soggetto, verbo e complemento, giusto?

[Max2433BO]

rugweri, fairyvilje