PrologEdit
Il linguaggio di programmazione Prolog è stato sviluppato nel 1972 da Alain Colmerauer. Nasce da una collaborazione tra Colmerauer a Marsiglia e Robert Kowalski a Edimburgo. Colmerauer stava lavorando sulla comprensione del linguaggio naturale, usando la logica per rappresentare la semantica e usando la risoluzione per rispondere alle domande. Durante l’estate del 1971, Colmerauer e Kowalski scoprirono che la forma clausale della logica poteva essere usata per rappresentare grammatiche formali e che i dimostratori di teorema di risoluzione potevano essere usati per l’analisi. Hanno osservato che alcuni dimostratori di teorema, come l’iper-risoluzione, si comportano come parser dal basso verso l’alto e altri, come SL-resolution (1971), si comportano come parser dall’alto verso il basso.
Fu nell’estate successiva del 1972 che Kowalski, ancora una volta lavorando con Colmerauer, sviluppò l’interpretazione procedurale delle implicazioni. Questa doppia interpretazione dichiarativa / procedurale divenne successivamente formalizzata nella notazione Prolog
H: – B1,…, Bn.
che può essere letto (e usato) sia dichiarativamente che proceduralmente. È anche diventato chiaro che tali clausole potrebbero essere limitate a clausole definitive o clausole Horn, dove H, B1,…, Bn sono tutte le formule logiche dei predicati atomici e quella risoluzione SL potrebbe essere limitata (e generalizzata) alla risoluzione LUSH o SLD. L’interpretazione procedurale di Kowalski e LUSH sono stati descritti in un memo del 1973, pubblicato nel 1974.
Colmerauer, con Philippe Roussel, utilizzò questa duplice interpretazione delle clausole come base del Prolog, che fu implementato nell’estate e nell’autunno del 1972. Il primo programma Prolog, anch’esso scritto nel 1972 e implementato a Marsiglia, era un sistema di risposta alle domande francese. L’uso di Prolog come linguaggio di programmazione pratico è stato dato grande slancio dallo sviluppo di un compilatore da David Warren a Edimburgo nel 1977. Gli esperimenti dimostrarono che Edinburgh Prolog poteva competere con la velocità di elaborazione di altri linguaggi di programmazione simbolici come Lisp. Edimburgo Prolog è diventato lo standard de facto e fortemente influenzato la definizione di standard ISO Prolog.
Programmazione logica abduttivamodifica
La programmazione logica abduttiva è un’estensione della normale programmazione logica che consente ad alcuni predicati, dichiarati predicati abducibili, di essere “aperti” o indefiniti. Una clausola in un programma di logica abduttiva ha la forma:
H: – B1,…, Bn, A1, An, An.
dove H è una formula atomica che non è abducibile, tutti i Bi sono letterali i cui predicati non sono abducibili e l’Ai sono formule atomiche i cui predicati sono abducibili. I predicati abducibili possono essere vincolati da vincoli di integrità, che possono avere la forma:
false: – L1, …, Ln.
dove i Li sono letterali arbitrari (definiti o abducibili e atomici o negati). Ad esempio:
canfly(X) :- bird(X), normal(X).false :- normal(X), wounded(X).bird(john).bird(mary).wounded(john).
dove il predicato normale è abducibile.
Il problem solving si ottiene derivando ipotesi espresse in termini di predicati abducibili come soluzioni di problemi da risolvere. Questi problemi possono essere osservazioni che devono essere spiegate (come nel classico ragionamento abduttivo) o obiettivi da risolvere (come nella normale programmazione logica). Ad esempio, l’ipotesi normale(maria) spiega l’osservazione canfly(maria). Inoltre, la stessa ipotesi comporta l’unica soluzione X = mary dell’obiettivo di trovare qualcosa che può volare:
:- canfly(X).
La programmazione logica abduttiva è stata utilizzata per la diagnosi dei guasti, la pianificazione, l’elaborazione del linguaggio naturale e l’apprendimento automatico. È stato anche usato per interpretare la negazione come Fallimento come forma di ragionamento abduttivo.
Programmazione Metalogicedit
Poiché la logica matematica ha una lunga tradizione di distinguere tra linguaggio oggetto e metalinguaggio, la programmazione logica consente anche la programmazione metalevel. Il programma metalogico più semplice è il cosiddetto meta-interprete “vanilla”:
solve(true). solve((A,B)):- solve(A),solve(B). solve(A):- clause(A,B),solve(B).
dove true rappresenta una congiunzione vuota, e la clausola(A,B) significa che esiste una clausola a livello di oggetto della formA:-B.
La programmazione metalogica consente di combinare rappresentazioni a livello di oggetto e metalevel, come nel linguaggio naturale. Può anche essere utilizzato per implementare qualsiasi logica specificata come regole di inferenza. Metalogic è utilizzato nella programmazione logica per implementare metaprogrammi, che manipolano altri programmi, database, basi di conoscenza o teorie assiomatiche come dati.
Programmazione logica dei vincolimodiFica
La programmazione logica dei vincoli combina la programmazione logica delle clausole Horn con la risoluzione dei vincoli. Estende le clausole Horn consentendo ad alcuni predicati, dichiarati come predicati di vincolo, di verificarsi come letterali nel corpo delle clausole. Un programma di logica dei vincoli è un insieme di clausole della forma:
H: – C1,…, Cn ◊ B1,…, Bn.
dove H e tutti i Bi sono formule atomiche e Ci sono vincoli. Dichiarativamente, tali clausole sono lette come implicazioni logiche ordinarie:
H se C1 e Cn e Cn e B1 e B e Bn.
Tuttavia, mentre i predicati nelle teste delle clausole sono definiti dal programma di logica dei vincoli, i predicati nei vincoli sono predefiniti da una struttura o teoria teorica del modello specifica del dominio.
Proceduralmente, i subgoals i cui predicati sono definiti dal programma sono risolti dalla riduzione degli obiettivi, come nella programmazione logica ordinaria, ma i vincoli sono controllati per la soddisfacibilità da un risolutore di vincoli specifico del dominio, che implementa la semantica dei predicati dei vincoli. Un problema iniziale viene risolto riducendolo a una congiunzione di vincoli soddisfacibile.
Il seguente programma di logica dei vincoli rappresenta un database temporale giocattolo della storia di John come insegnante:
teaches(john, hardware, T) :- 1990 ≤ T, T < 1999.teaches(john, software, T) :- 1999 ≤ T, T < 2005.teaches(john, logic, T) :- 2005 ≤ T, T ≤ 2012.rank(john, instructor, T) :- 1990 ≤ T, T < 2010.rank(john, professor, T) :- 2010 ≤ T, T < 2014.
Qui ≤ e< sono predicati di vincoli, con la loro usuale semantica intesa. La seguente clausola goal interroga il database per scoprire quando john ha insegnato logica ed era professore:
: – teaches(john, logic, T), rank(john, professor, T).
La soluzione è 2010 ≤ T, T ≤ 2012.
La programmazione logica dei vincoli è stata utilizzata per risolvere problemi in campi come l’ingegneria civile, l’ingegneria meccanica, la verifica dei circuiti digitali, l’orario automatizzato, il controllo del traffico aereo e la finanza. È strettamente correlato alla programmazione logica abduttiva.
Concurrent logic programmingEdit
Concurrent logic programming integra concetti di programmazione logica con la programmazione concorrente. Il suo sviluppo è stato dato un grande impulso negli anni 1980 dalla sua scelta per il linguaggio di programmazione dei sistemi del progetto giapponese di quinta generazione (FGCS).
Un programma logico concorrente è un insieme di clausole Horn protette della forma:
H :- G1, …, Gn | B1, …, Bn.
La congiunzione G1,… , Gn è chiamato la guardia della clausola, e / è l’operatore di impegno. Dichiarativamente, le clausole Horn protette sono lette come implicazioni logiche ordinarie:
H se G1 e G e Gn e B1 e B e Bn.
Tuttavia, proceduralmente, quando ci sono diverse clausole le cui teste H corrispondono a un determinato obiettivo, allora tutte le clausole vengono eseguite in parallelo, controllando se le loro guardie G1,… , Gn tenere. Se le guardie di più di una clausola tengono, allora viene fatta una scelta impegnata per una delle clausole, e l’esecuzione procede con i subgoals B1,…, Bn della clausola scelta. Questi obiettivi secondari possono anche essere eseguiti in parallelo. Quindi la programmazione logica concorrente implementa una forma di” non importa il nondeterminismo”, piuttosto che”non so il nondeterminismo”.
Ad esempio, il seguente programma di logica concorrente definisce un predicato shuffle (Left, Right, Merge), che può essere utilizzato per mescolare due liste sinistra e destra, combinandoli in un unico elenco di unione che conserva l’ordine delle due liste sinistra e destra:
shuffle(, , ).shuffle(Left, Right, Merge) :- Left = | Merge = , shuffle(Rest, Right, ShortMerge).shuffle(Left, Right, Merge) :- Right = | Merge = , shuffle(Left, Rest, ShortMerge).
Qui, rappresenta la lista vuota e rappresenta una lista con il primo elemento Head seguito da list Tail, come in Prolog. (Si noti che la prima occorrenza di / nella seconda e nella terza clausola è il costruttore della lista, mentre la seconda occorrenza di / è l’operatore di commit.) Il programma può essere utilizzato, ad esempio, per mischiare le liste e invocando la clausola goal:
shuffle(, , Merge).
Il programma genererà in modo non deterministico una singola soluzione, ad esempio Merge = .
Probabilmente, la programmazione logica concorrente si basa sul passaggio di messaggi, quindi è soggetta alla stessa indeterminatezza di altri sistemi di passaggio di messaggi simultanei, come gli Attori (vedi Indeterminacy in concurrent computation). Carl Hewitt ha sostenuto che la programmazione logica concorrente non si basa sulla logica nel suo senso che i passaggi computazionali non possono essere logicamente dedotti. Tuttavia, nella programmazione logica concorrente, qualsiasi risultato di un calcolo di terminazione è una conseguenza logica del programma e qualsiasi risultato parziale di un calcolo parziale è una conseguenza logica del programma e dell’obiettivo residuo (rete di processo). Quindi l’indeterminatezza dei calcoli implica che non tutte le conseguenze logiche del programma possono essere dedotte.
Programmazione logica dei vincoli simultaneimodifica
Concurrent constraint logic programming combina concurrent logic programming e constraint logic programming, utilizzando i vincoli per controllare la concorrenza. Una clausola può contenere un guard, che è un insieme di vincoli che possono bloccare l’applicabilità della clausola. Quando le guardie di più clausole sono soddisfatte, la programmazione logica dei vincoli simultanei fa una scelta impegnata di usarne solo una.
Programmazione logica induttivamodifica
La programmazione logica induttiva si occupa di generalizzare esempi positivi e negativi nel contesto della conoscenza di base: apprendimento automatico dei programmi logici. Il recente lavoro in questo settore, combinando programmazione logica, apprendimento e probabilità, ha dato origine al nuovo campo dell’apprendimento relazionale statistico e della programmazione logica induttiva probabilistica.
Programmazione logica di ordine superioreedit
Diversi ricercatori hanno esteso la programmazione logica con funzionalità di programmazione di ordine superiore derivate dalla logica di ordine superiore, come le variabili di predicato. Tali linguaggi includono le estensioni Prolog HiLog e λProlog.
Programmazione logica linearedit
Basare la programmazione logica all’interno della logica lineare ha portato alla progettazione di linguaggi di programmazione logica che sono notevolmente più espressivi di quelli basati sulla logica classica. I programmi di clausola Horn possono rappresentare solo il cambiamento di stato in base al cambiamento degli argomenti nei predicati. Nella programmazione logica lineare, si può utilizzare la logica lineare ambientale per supportare il cambiamento di stato. Alcuni primi progetti di linguaggi di programmazione logici basati sulla logica lineare includono LO, Lolli, ACL e Forum . Forum fornisce un’interpretazione obiettivo diretto di tutta la logica lineare.
Programmazione logica orientata agli oggettimodiFica
F-logic estende la programmazione logica con gli oggetti e la sintassi del frame.
Logtalk estende il linguaggio di programmazione Prolog con supporto per oggetti, protocolli e altri concetti OOP. Supporta la maggior parte dei sistemi Prolog conformi agli standard come compilatori di back-end.
Programmazione logica delle transazionimodifica
La logica delle transazioni è un’estensione della programmazione logica con una teoria logica degli aggiornamenti che modificano lo stato. Ha sia una semantica modello-teorica che una procedurale. Un’implementazione di un sottoinsieme di logica di transazione è disponibile nel sistema Flora-2. Sono disponibili anche altri prototipi.