Prolog Language
Monotonicità

Ragionamento sui predicati monotonici

I predicati monotonici possono essere sottoposti a debug applicando il ragionamento dichiarativo .

In puro Prolog, un errore di programmazione può portare a uno o tutti i seguenti fenomeni:

1. il predicato non riesce correttamente in un caso in cui dovrebbe fallire
2. il predicato non riesce correttamente in un caso in cui dovrebbe riuscire
3. il predicato loop inaspettatamente dove dovrebbe produrre soltanto un insieme finito di risposte.

Ad esempio, considera come possiamo eseguire il debug di case (2) per ragionamento dichiarativo: possiamo sistematicamente rimuovere gli obiettivi delle clausole del predicato e vedere se la query non riesce ancora . Nel codice monotono, la rimozione degli obiettivi può al massimo rendere il programma risultante più generale . Quindi, possiamo individuare gli errori vedendo quale degli obiettivi porta al fallimento imprevisto.

Esempi di predicati monotoni

Esempi di predicati monotoni sono:

• unificazione con (=)/2 o unify_with_occurs_check/2
• dif/2 , che esprime disuguaglianza di termini
• Vincoli CLP (FD) come (#=)/2 e (#>)/2 , utilizzando una modalità di esecuzione monotona.

I predicati Prolog che usano solo obiettivi monotonici sono essi stessi monotoni.

I predicati monotonici consentono ragionamenti dichiarativi:

1. Aggiungere un vincolo (cioè un obiettivo) a una query può al massimo ridurre , mai estendere, l'insieme di soluzioni.
2. La rimozione di un obiettivo di tali predicati può al massimo estendere , mai ridurre, l'insieme di soluzioni.

Predicati non monotoni

Ecco alcuni esempi di predicati che non sono monotoni:

• predicati meta-logici come var/1 , integer/1 ecc.
• predicati di confronto termine come (@<)/2 e (@>=)/2
• predicati che usano !/0 , (\+)/1 e altri costrutti che rompono la monotonicità
• predicati di tutte le soluzioni come findall/3 e setof/3 .

Se si utilizzano questi predicati, l' aggiunta di obiettivi può portare a più soluzioni, che va contro l'importante proprietà dichiarativa nota dalla logica che l'aggiunta di vincoli può al massimo ridurre , mai estendere, l'insieme di soluzioni.

Di conseguenza, anche altre proprietà che facciamo affidamento per il debugging dichiarativo e altri ragionamenti sono interrotte. Ad esempio, i predicati non monotonici infrangono la nozione fondamentale di commutatività della congiunzione nota dalla logica del primo ordine. Il seguente esempio illustra questo:

?- var(X), X = a.
X = a.

?- X = a, var(X).
false.

I predicati di tutte le soluzioni come findall/3 interrompono anche la monotonicità: l' aggiunta di clausole può portare al fallimento degli obiettivi che in precedenza erano stati mantenuti . Ciò contrasta anche con la montonicità come nota dalla logica del primo ordine, dove l' aggiunta di fatti può al massimo aumentare , senza mai ridurre l'insieme di conseguenze.

Alternative monotone per costrutti non monotoni

Ecco alcuni esempi di come utilizzare predicati monotonici invece di costrutti impuri e non monotonici nei tuoi programmi:

• dif/2 è pensato per essere usato al posto di costrutti non monotoni come (\=)/2
• i vincoli aritmetici (CLP (FD), CLP (Q) e altri) devono essere utilizzati al posto dei predicati aritmetici modificati
• !/0 porta quasi sempre a programmi non monotoni e dovrebbe essere evitato del tutto.
• errori di istanziazione possono essere sollevati in situazioni in cui non è possibile prendere una decisione corretta in questo momento.

Combinando la monotonicità con l'efficienza

Talvolta si sostiene che, per ragioni di efficienza, dobbiamo accettare l'uso di costrutti non monotonici nei programmi Prolog del mondo reale.

Non ci sono prove per questo. Ricerche recenti indicano che il sottoinsieme monoprono puro di Prolog potrebbe non solo essere sufficiente per esprimere la maggior parte dei programmi del mondo reale, ma anche accettabilmente efficiente nella pratica. Un costrutto che è stato scoperto di recente e incoraggia questa visione è if_/3 : Combina la monotonicità con una riduzione dei punti di scelta. Vedi Indicizzazione dif / 2 .

Ad esempio, il codice del modulo:

pred(L, Ls) :-
    condition(L),
    then(Ls).
pred(L, Ls) :-
    \+ condition(L),
    else(Ls).

Può essere scritto con if_/3 come:

pred(L, Ls) :-
    if_(condition(L),
        then(Ls),
        else(Ls)).

e combina la monotonicità con il determinismo.