Presentazione di
Enrico Siboni
Sistemi Autonomi – 2018/2019
In modalità slide premere ESC per la mappa
tuProlog è un motore per l'esecuzione di programmi Prolog, realizzato con l'intento di essere minimale, altamente configurabile anche dinamicamente.
Esso è stato realizzato in Java adottando dunque il paradigma ad oggetti.
Il Prolog è un linguaggio di programmazione che adotta il paradigma della programmazione logica
Un programma Prolog è una sequenza di clausole di Horn nella forma A :- B1, ..., Bn
A
è detta testa:-
simboleggia l'implicazione logicaB1, ..., Bn
sono una congiunzione di termini, costituente il corpo della clausolaL'esecuzione di un programma Prolog è comparabile alla dimostrazione di un teorema, mediante la regola di inferenza detta risoluzione
Il cuore di tuProlog è il motore inferenziale di risoluzione costituito da una macchina a stati finiti
Il processo di risoluzione adottatto è SLD (Selective Linear Definite resolution)
Il database delle clausole contiene l'insieme delle clausole che formano la teoria (il programma) Prolog che potrà essere eseguito sottomettendo un input al motore inferenziale.
Esso viene consultato durante il processo di risoluzione per determinare la veridicità di fatti applicando regole, al fine di dimostrare l'input iniziale.
La consultazione rapida è coadiuvata da funzionalità di:
a(b, c)
ha indicatore a/2
)Le principali classi che realizzano il Database delle clausole sono: ClauseDatabase
, FamilyClauseList
, FamilyClauseIndex
e ClauseInfo
ClauseDatabase
: Realizza il database delle clausole vero e proprio, sotto forma di HashMap
FamilyClauseList
: E' la stuttura dati "lista linkata" su cui ClauseDatabase si poggia, che realizza una momorizzazione indicizzata delle clausole tramite FamilyClauseIndexFamilyClauseIndex
: E' un indice Red-Black-Tree specializzato nella memorizzazione delle clausoleClauseInfo
: E' una classe che mantiene le informazioni fondamentali su ogni clausolaLe librerie sono teorie Prolog che contengono funzionalità di base utili alla costruzione di altri programmi Prolog
In tuProlog ad esempio abbiamo di base le seguenti:
BasicLibrary
che definisce predicati di base standard, ad eccezione di quelli di I/OIOLibrary
definisce i predicati di Input-Output descritti nello Standard di PrologISOLibrary
definisce i restanti predicati Prolog Standard non definiti nelle precedenti due librerieJavaLibrary
definisce predicati specifici per l'interazione Prolog/JavaLe librerie in tuProlog sono oggetti che:
Dichiarano una teoria, in formato di Stringa
Possono dichiarare primitive, funzioni e direttive, sotto forma di metodi con determinati vincoli di nome, tipi di argomenti, e loro numero
Se si vuole che il "backtracking" sia possibile in un predicato di libreria, si deve scriverlo nella Stringa che verrà riconosciuta come teoria
A livello implementativo abbiamo la classe astratta Library
che codifica le funzionalità di base per l'implementazione di tutte le altre librerie, inclusi i meccanismi di reflection Java utili al riconoscimento di primitive, funzioni e direttive
Per primitive si intendono delle funzionalità che sono richiamabili da un programma Prolog la cui esecuzione non è demandata al risolutore ma all'esecuzione di codice nativo nel linguaggio di origine del motore inferenziale.
Le primitive sopperiscono all'inefficienza e difficoltà di implementazione di certe funzionalità, in termini di librerie Prolog inerentemenete dichiarative
Le primitive in tuProlog sono metodi:
_
(Underscore) e l'arità dello stessoTerm
)Le primitive, così implementate, non possono prendere parte al processo di "backtracking"
Un esempio: se volessi richiamare la primitiva ciao(enrico)
boolean ciao_1(Term arg)
in cui arg
verrebbe istanziato con un atomo enrico
Le funzioni in tuProlog sono come le primitive con la seguente differenza:
Term
)Le funzioni vengono valutate prima di valutare un goal nella sua interezza, siccome trasformano più termini in uno solo, grazie al predicato is/2
Un esempio: se volessi valorizzare una variabile con il risultato di una funzione di somma is(N, sum(2,3))
Term sum_2(Term arg1, Term arg2)
in cui
arg1
verrebbe istanziato con 2
arg2
verrebbe istanziato con 3
Le direttive in tuProlog sono come le primitive con la seguente differenza:
void
in Java)Le direttive sono immediatamente eseguite al caricamento di una teoria Prolog all'interno del motore inferenziale
Esse non possono essere composte, ogni direttiva può lanciare una sola query
Ad esempio: se volessi lanciare la direttiva ciao(enrico)
al caricamento della mia teoria
void ciao_1(Term arg)
in cui arg
verrebbe istanziato con un atomo enrico
:- ciao(enrico).
, la corrispondente direttiva verrebbe eseguita al caricamentoDurante l'esecuzione del motore inferenziale viene fatto affidamento ad alcune strutture dati di supporto, tra cui:
ExecutionContext mantiene le informazioni cruciali riguardanti l'esecuzione corrente:
ChoicePointStore che mantiene le informazioni relative a quali sono i punti di scelta, su cui ancora ci sono scelte non valutate
SubGoalStore che mantiene le informazioni relative ai sotto-goal che dovranno essere eseguiti
True, se la risoluzione ha eseguito con successo l'input senza ulteriori alternative esplorabili
True & Choice Point, se la risoluzione ha eseguito con successo l'input e ci sono altre alternative di esecuzione aperte
False, se l'esecuzione è fallita, non riuscendo a dimostrare l'input con le teorie presenti
Halt, se l'esecuzione è stata arrestata forzatamente
Lo stato iniziale è molto semplice
Estrae il primo sotto-goal da eseguire
Inizializza l'ExecutionContext preparandolo per la computazione
Poi transita sempre nello stato StateGoalSelection
Lo stato di "selezione del goal" ha il compito di selezionare e preparare per l'esecuzione il prossimo sotto-goal
I suoi step possono essere riassunti in:
Carica il prossimo sotto-goal da eseguire dal contesto corrente
Se non è presente alcun goal da eseguire, risale di un livello la catena degli ExecutionContext e riesegue dal punto 1.
2.1. Quando non è possibile risalire la catena perchè si è arrivati all'inizio
Se il goal caricato non è ben formato, transita in False
Se il goal è ben formato, esso viene preparato per l'esecuzione e si transita nello stato StateGoalEvaluation
Controlla se il goal corrente, è una primitiva
Se non è una primitiva transita immediatamente in StateRuleSelection
Se il goal corrente è una primitiva, la esegue e possono verificarsi quattro situazioni:
3.1. Essa ha successo, e si transita nello stato StateGoalSelection
3.2. Essa fallisce, e si transita nello stato StateBacktrack
3.3. Essa va in errore prima di terminare
Lo stato di "backtracking" (tradotto "di marcia indietro"), si occupa di annullare le modifiche intercorse tra il contesto corrente e l'ultimo ChoicePoint con percorsi aperti, permettendo quindi di provarne uno alternativo
Gli step sono:
Carica la prossima scelta selezionabile, nel più recente ChoicePoint generato
Ricarica il goal al momento della scelta, e elimina le modifiche effettuate sul contesto fino a quel momento
Ripristina la coerenza nei contesti di esecuzione, padri di quello corrente, rimuovendo le assegnazioni di variabili relative all'ultima scelta
Lo stato di "eccezione" tratta quelle situazioni in cui si è verificato un errore, durante l'esecuzione, e si deve in qualche modo gestirlo, ripristinando l'operatività
Esso non era previsto nella definizione iniziale della macchina a stati, ma lo Standard Prolog lo richiede; in figura vediamo come si allaccia agli altri stati:
Estrae il termine descrittivo dell'errore, dal goal corrente
Controlla se il contesto corrente ha un padre
2.1. In caso negativo, nessuno può gestire l'errore, transita in Halt
Controlla se il goal del contesto padre, può gestire l'errore
3.1. In caso negativo, imposta come contesto corrente il padre, e riparte dal punto 2.
Imposta come contesto corrente il padre, ed elimina tutti i ChoicePoint generati, a partire dal contesto corrente, fino al contesto che ha lanciato l'errore
Unifica il termine descrittivo dell'errore con il gestore dell'errore (catch), per propagare l'informazione
Prepara per l'esecuzione il "goal di recupero" dall'errore
6.1. Se esso non è ben formato, transita in False
Transita in StateGoalSelection
f(A) :- p(A).
g(B) :- p(B), !.
h(C) :- p(C), throw(my_error).
p(a).
p(b).
f(Var).
g(Var).
h(Var).
f(Var).
f(Var)
all'interno di un SubGoalStore
f(Var)
dal SubGoalStore
f(A) :- p(A)
f(A_1) :- p(A_1)
A_1
come sostituzione di Var
, dopo l'unificazionep(A_1)
all'interno del proprio SubGoalStore
p(A_1)
; SatateGoalEvaluation: non fa nulla come soprap(a)
e p(b)
p(a)
e imposta a
come sostituzione di A_1
SubGoalStore
vuotoVar -> a
; l'utente può decidere di proseguire l'esecuzione (con le prossime alternative) o terminarlag(Var).
f(Var)
fino al punto 5 compreso, utilizzando la regola g(B) :- p(B), !
, poi:StateRuleSelection:
6.1. Carica i fatti p(a)
e p(b)
6.2. Crea un ChoicePoint per ricordre che sarà fatta una scelta, ripercorribile
6.3. Sceglie p(a)
e imposta a
come sostituzione di B_1
StateGoalSelection: carica !
, che ha alias cut
StateGoalEvaluation: esegue la primitiva relativa (cut_0
) che elimina i ChoicePoint aperti relativi alla regola in cui viene eseguito
StateGoalSelection: non ha ulteriori sotto-goal da eseguire, e nessun ChoicePoint
True: Var -> a
; questa è l'unica soluzione data in output siccome le alternative sono state tagliate
h(Var).
f(Var)
fino al punto 5 compreso, utilizzando la regola h(C) :- p(C), throw(my_error)
, poi:StateRuleSelection:
6.1. Carica i fatti p(a)
e p(b)
6.2. Crea un ChoicePoint per ricordre che sarà fatta una scelta, ripercorribile
6.3. Sceglie p(a)
e imposta a
come sostituzione di C_1
StateGoalSelection: carica throw(my_error)
StateGoalEvaluation: esegue la primitiva relativa (throw_1
), la quale lancia l'eccezione PrologError
con il termine my_error
StateException: nessun padre ha un goal di tipo catch/3
che possa gestire l'errore
Halt
L'attuale implemetazione ha diversi problemi; alcuni dovuti a interventi ripetuti nel tempo, che hanno modificato il comportamento di varie parti, perdendo di vista l'insieme; altri causati dai limiti della tecnologia al momento della realizzazione.
Tra i principali:
Classi di modello del dominio con errato livello di dettaglio
Classi di modello mutabili
Gestione interna di multipli flussi di controllo senza possibilità di intervento su questi parametri
Nell'attuale implementazione la gerarchia delle classi del dominio si limita alla seguente:
La suddivisione dei termini tra Strutture, Numeri e Variabili non cattura la variabilità che si può avere al di sotto di Struct
: (Atomi, Clausole, Liste, ecc.), perdendo anche la possibilità di fare un type checking a livello di linguaggio di programmazione
Inoltre il dettaglio con cui si distinguono le possibili istanze di Number
, risulta praticamente inutile
Si propone una rivisitazione della gerarchia delle classi di dominio, come segue:
Struct
, che occupano così il loro posto come tipi di "prima classe"Nell'attuale implementazione le classi di modello sono mutabili, ciò però rende il codice che le gestisce meno sicuro a meno che non siano fatte copie difensive, perchè ci si espone a possibili mutazioni non volute. Ormai è noto che la mutabilità, è da evitare[1] se non si stanno cercando le massime performance in un software, perchè lo complica.
Bloch, Joshua. Effective java. Addison-Wesley Professional, 2017, Item 17. ↩︎
Per semplificare al massimo il codice sviluppato, e seguendo le buone pratiche, si propone di fare dell'immutabilità la condizione di default per tutte le classi.
In questo modo è possibile guadagnare:
Una maggiore semplicità del codice di modellazione del dominio
Oggetti condivisibili senza problemi di accessi e modifiche indesiderate, eliminando alla radice la necessità di creare copie difensive
L'eliminazione dello stato di "backtracking" dalla macchina a stati, siccome non avendo modificato nulla, non è più necessario annullare alcuna modifica
La rimozione delle sovrastrutture per mantenere le modifiche storiche, e relative procedure di navigazione
Tutto ciò al prezzo di avere un oggetto diverso in memoria per ogni modifica necessaria; prezzo che si compensa in parte con l'ultimo punto illustrato qui sopra
Nell'attuale implementazione il motore inferenziale gestisce internamente i propri Thread di controllo, senza dare la possibilità di modificare il comportamento di default.
Questo risulta un problema quando ad esempio si vorrebbe utilizzare tuProlog in sistemi che non hanno molta potenza di calcolo e memoria.
Si propone un approccio per cui, dall'esterno, sia possibile definire quali risorse di calcolo debbano essere utilizzate durante il processo di risoluzione.
Ad esempio si potrebbe passare come parametro di input al risolutore, oltre all'input vero e proprio, anche la strategia con cui si vorrebbe venissero eseguite le computazioni interne.
Piancastelli, Giulio, et al. "The architecture and design of a malleable object-oriented Prolog engine." Proceedings of the 2008 ACM symposium on Applied computing. ACM, 2008.
Denti, Enrico, Andrea Omicini, and Alessandro Ricci. "Multi-paradigm Java–Prolog integration in tuProlog." Science of Computer Programming 57.2 (2005): 217-250.
Wikipedia - https://it.wikipedia.org