Kowalski EasyProgramma per la traduzione automatica di codice Stips-Like in codice Prolog, in accordo con la formualzione di Kowalski

Facoltà di Ingegneria – Università di BolognaAA 2011/2012

Linguaggi e Modelli Computazionali LMProf. Enrico Denti

Chiara Gandolfi

Schema dell’applicazione

File Strips-Like

File Prolog

AST

Parser ToProlog

ToStrips-Like

ToJTree

Esempio di file di partenza

INITIAL_STATE:

in(carico1,carrello1), at(carrello1,milano),

connected(milano,bologna), connected(bologna,roma)

OPERATION: load(Oggetto,Carrello,Location)

PREC: at(Oggetto,Location), at(Carrello,Location)

DELETE: at(Oggetto,Location)

ADD: in(Oggetto,Carrello)

OPERATION: drive(Carrello,Location1,Location2)

PREC:at(Carrello,Location1), connected(Location1,Location2)

DELETE: at(Carrello,Location1)

ADD: at(Carrello,Location2)

OPERATION: unload(Oggetto,Carrello,Location)

PREC:at(Carrello,Location), in(Oggetto,Carrello)

DELETE: in(Oggetto,Carrello), at(Oggetto,Location)

ADD: at(Oggetto,Location), at(Oggetto,Location)

Grammatica (versione 1)

Start ::= State Actions

State ::= "INITIAL_STATE:" Conditions

Actions ::= Action ( Actions )?

Action ::= Name Precondition NegativeEffect PositiveEffect

Name ::= "OPERATION:" Operation

Operation ::= Literal ( "(" TermList ")" )?

Precondition ::= "PREC:" Conditions

NegativeEffect ::= "DELETE:" Conditions

PositiveEffect ::= "ADD:" Conditions

Conditions ::= Condition ( "," Conditions )?

Condition ::= Literal ( "(" ( TermList )? ")" )?

Literal ::= <IDENTIFIER>

TermList ::= Term ( "," TermList )?

Term ::= <IDENTIFIER>

| <INTEGER_LITERAL>

Grammatica e Linguaggio

Le regole sono nella forma A α con α : V* Secondo la classificazione di Chomsky, è una

grammatica di TIPO 2 (context free)

Non sono presenti self-embedding, ne consegue che linguaggio generato è di TIPO 3 (regolare)

Formulazione di Kowalski

Stato iniziale

condizioni

Elenco di azioni

Stato iniziale

condizioni

Elenco di azioni

Codice Strips-like Traduzione relativa

INITIAL_STATE: cond1, cond2

poss(s0).

poss( do( U,S ) ):-poss( S ), pact( U, S ).

holds(cond1, s0)

holds(cond2, s0).

Formulazione di Kowalski

Azione

Precondizioni

Effetti negativi

Effetti positivi

Azione

Precondizioni

Effetti negativi

Effetti positivi

Codice Strips-like Traduzione relativa

OPERATION: operation

pack(operation, S):- holds(pre1, S), holds(pre2, S).

PREC: pre1, pre2

DELETE: del1, del2

ADD: add1, add2

holds(V, do(operation, S)):- holds(V,S), V\=del1, V\=del2.

holds(add1, do(operation, S)).

holds(add2, do(operation, S)).

Problemi con la grammatica attuale

Problema: Necessità di portare alle foglie dell’albero la loro posizione nell’albero

per capire la funzione che devono svolgere: ad esempio un nodo “Condition” sotto il nodo “Precondition” deve agire diversamente da un nodo “Condition” sotto al nodo “NegativeEffect”.

Possibili soluzioni: Creare la gerarchia di classi a mano

AST più pulito possibile Eventuali modifiche nella grammatica sono riportare manualmente nelle

classi implementate Uso di regole (e metasimboli) diverse(i) date le diverse funzioni delle

condizioni e utilizzo di strumenti per la generazione automatica di codice

Grammatica (versione 2)

Vengono differenziate le liste di condizioni, le quali diventano anche OPZIONALI (di fatto questa è stata una modifica avvenuta in un secondo momento, ma grazie ai generatori automatici, non vi sono stati ulteriori modifiche all’interno del codice dell’applicazione già realizzato)

Start ::= ( State )? ( Actions )?

State ::= "INITIAL_STATE:" ConditionsState

Actions ::= Action ( Actions )?

Action ::= Name Precondition NegativeEffect PositiveEffect

Name ::= "OPERATION:" Operation

Operation ::= Literal ( "(" TermList ")" )?

Precondition ::= "PREC:" ( ConditionsPre )?

NegativeEffect ::= "DELETE:" ( ConditionsDel )?

PositiveEffect ::= "ADD:" ( ConditionsAdd )?

Grammatica (versione 2)

Di fatto le regole ConditionsX (e analogamente ConditionX) sono tra loro uguali, la differenza infatti non è sintattica, ma di semantica.

ConditionsState ::= ConditionState ( "," ConditionsState )?

ConditionState ::= Literal ( "(" ( TermList )? ")" )?

ConditionsPre ::= ConditionPre ( "," ConditionsPre )?

ConditionPre ::= Literal ( "(" ( TermList )? ")" )?

ConditionsDel ::= ConditionDel ( "," ConditionsDel )?

ConditionDel ::= Literal ( "(" ( TermList )? ")" )?

ConditionsAdd ::= ConditionAdd ( "," ConditionsAdd )?

ConditionAdd ::= Literal ( "(" ( TermList )? ")" )?

Literal ::= <IDENTIFIER>

TermList ::= Term ( "," TermList )?

Term ::= <IDENTIFIER>

| <INTEGER_LITERAL>

Divisione in package

Visitor per la generazione di codice

FromAstToProlog

FromASTToStripsLike

public String visit( NegativeEffect n, String argu) { //n.f0.accept(this, argu); //"DELETE:" String nRes = "holds( V, do( "+argu+ ", S)) :- holds(V,S)"; String body = n.f1.accept(this, argu); if (!body.equals("")) nRes = nRes +", " + body +".\r\n"; else nRes = nRes + ".\r\n"; return nRes;}

public String visit( Name n) { String nRes = ""; nRes += n.f0.accept(this); nRes += " "; nRes += n.f1.accept(this); return nRes;}

Visitor per visualizzare l’AST

JTreeVisitor

È possibile modificare l’AST da grafica, questa funzionalità non è mappata su un visitor in quanto non è una caratteristica dei singoli nodi.

public String visit(Precondition n, DefaultMutableTreeNode argu) { DefaultMutableTreeNode node = new DefaultMutableTreeNode( n.f0.accept(this, argu)); argu.add(node); n.f1.accept(this, node); return "";}…public String visit(ConditionsPre n, DefaultMutableTreeNode argu) { String nRes = ""; nRes += n.f0.accept(this, argu); nRes += n.f1.accept(this, argu); return nRes;}

Integrazione Java e Prolog

Viene integrato l’uso di Prolog all’interno dell’applicazione Java grazie al plugin tuprolog.jar//Creo la teoria grazie al visitor FromAstToPrologVisitorFromAstToPrologVisitor v = new FromAstToPrologVisitor();String prologCode = getRoot().accept(v, null);

//Recupero il motore Prolog e setto la teoriaProlog engine = new Prolog();Theory t = new Theory(prologCode);engine.setTheory(t);

//Creo la query String queryProlog = string;ByteArrayInputStream sbis = new ByteArrayInputStream(queryProlog.getBytes());AP ap2 = new AP(sbis); Goal goal = ap2.Goal();String inputString = goal.accept(v, null);Term queryStrips = Term.createTerm(inputString);

Integrazione Java e Prolog

Viene integrato l’uso di Prolog all’interno dell’applicazione Java grazie al plugin tuProlog

// In un thread a parte effettuo la ricerca della soluzioneSolveInfo info = engine.solve(queryStrips);

//in caso di successo recupero la rispostaif (info.isSuccess()) { String ris = "Soluzione: "+ info.getTerm("S").toString();}

Goal

Si è scelto di richiedere il goal all’utente sempre in formato Strips-Like

Diventa necessario tradurre anche il goal secondo la formulazione di Kowalski Nuova grammatica con scopo “Goal” Molte affinità con la grammatica precedentemente

analizzataSi è deciso di scrivere la grammatica nello stesso file e

raccogliere la logica di trasformazione negli stessi visitor. Le produzioni sono utilizzate a partire da scopi diversi, a

secondo del fine che si vuole raggiungere (teoria/goal)

Grammatica Goal (part i aggiunte)

La sintassi e la semantica dei nodi “Literal” e “TermList” è la stessa presentata nelle versioni precedenti della grammatica, si è quindi deciso di realizzare uno stesso file per descrivere la grammatica ed estendere gli stessi visitor. Le produzioni sono interpellate a partire da nodi-scopo diversi.

Goal ::= ConditionsGoal

ConditionsGoal ::= ConditionGoal ( "," ConditionsGoal )?

ConditionGoal ::= Literal ( "(" ( TermList )? ")" )?

Formulazione di Kowalski (Goal)

Goal Goal

Codice Strips-like Traduzione relativa

goal1, goal2. poss(S), holds(goal1, S), holds(goal2, S).

Demo

Possibili sviluppi futuri

Estendere la grammatica per accettare tutti i termini effettivamente riconoscibili da Prolog. In questa prima fase si sono considerati solo termini con arietà 0, in realtà i termini possono essere composti, come ad esempio f(t1,t2,…,tk) , dove t1..k sono a loro volta altre termini. Questo produrrebbe, nello strato più basso della grammatica, un self-embedding, portando il linguaggio generato ad essere di TIPO 2.

TermList ::= Term ( "," TermList )?

Term ::= <IDENTIFIER>

| <INTEGER_LITERAL>

| <IDENTIFIER> “(“ TermList “)”

Kowaski EasyProgramma per la traduzione automatica di codice Stips-Like in codice Prolog, in accordo alla formualzione di Kowaski

Facoltà di Ingengeria – Università di BolognaAA 2011/2012

Linguaggi e Modelli Computazionali MProf. Enrico Denti

Chiara Gandolfi