Logisch programmeren is het gebruik van wiskundige logica om computerprogramma's te schrijven. Er zijn gespecialiseerde programmeertalen waar de gebruiker direct logische beweringen kan invoeren. Waarschijnlijk heet de bekendste van deze talen Prolog. Alonzo Church gebruikte een vorm van logisch programmeren in wat vandaag de dag bekend staat als lambda calculus. Logisch programmeren is ook gebruikt in LISP. De stijl van logisch programmeren is declaratief: in plaats van stap-voor-stap te beschrijven hoe iets bereikt moet worden (zoals bij imperatieve talen), formuleert de programmeur feiten en regels en laat het systeem afleiden wat waar is.
Belangrijke principes
Een aantal kernbegrippen bij logisch programmeren:
- Feiten en regels: Programma's bestaan doorgaans uit feiten (bijvoorbeeld parent(anna, bob).) en regels (bijvoorbeeld grandparent(X, Z) :- parent(X, Y), parent(Y, Z).).
- Predikaten en atomaire formules: Kennis wordt uitgedrukt als predikaten met argumenten; samen vormen ze predicatenlogische clausules.
- Unificatie: Het mechanisme waarmee variabelen worden gebonden zodat twee termen gelijk gemaakt kunnen worden; essentieel voor patroonmatching tijdens het afleiden.
- Resolutie en backtracking: Algoritmes (zoals SLD-resolutie in Prolog) proberen bewijzen te vinden door regels toe te passen; bij mislukking terugkeren (backtracken) en alternatieven proberen.
- Horn-clausules: Veel logisch-programmeer-systemen gebruiken Horn-clausules, een klasse logische formules die efficiënt af te handelen zijn.
Ontkenning als mislukking (zwakke ontkenning)
De programma's bestaan uit een reeks regels en feiten. In de meeste gevallen gebruikt de logica-programmering de zogenaamde ontkenning als mislukking of zwakke ontkenning: Dit betekent dat als het niet mogelijk is om een of andere clausule p {\playstyle p}
af te leiden uit de feiten en regels, het systeem zal aannemen dat de ontkenning ervan waar is.
Praktisch betekent dat: als een query niet bewezen kan worden met de beschikbare kennis, behandelt het systeem ¬p (niet-p) als waar. Dit is nuttig voor veel toepassingen maar heeft ook beperkingen: het is niet hetzelfde als klassieke logische negatie en leidt tot niet-monotone redenering (toevoegen van nieuwe feiten kan eerdere conclusies ongeldig maken). Om hiermee om te gaan bestaan uitgebreidere semantieken zoals de well-founded semantics en stable model semantics, en talen die expliciete (klassieke) negatie ondersteunen naast negation-as-failure.
Prolog: kernbegrippen en voorbeeld
Prolog is de bekendste logische programmeertaal en implementeert de hierboven beschreven ideeën. Belangrijke eigenschappen van Prolog:
- Declaratieve specificatie van feiten en regels.
- Automatische unificatie en backtracking als mechanisme voor zoeken.
- Mogelijkheid tot invoegen van controleconstructies (zoals de cut-operator !) om zoekruimte te beperken.
Een eenvoudig Prolog-voorbeeld (familierelaties):
parent(anna, bob). parent(bob, carl). grandparent(X, Z) :- parent(X, Y), parent(Y, Z). Een query grandparent(anna, Who). zal via unificatie en resolutie Who = carl vinden. Negation as failure wordt in Prolog vaak uitgedrukt met \+ (bijvoorbeeld \+ reachable(a, b) betekent: het is niet mogelijk te bewijzen dat b bereikbaar is vanaf a).
LISP en logisch programmeren
LISP is traditioneel geen pure logische programmeertaal maar een taal voor symbolische verwerking en functionele programmering met wortels in de lambda- en rekencalculi. Toch is logisch programmeren in LISP mogelijk en zijn er historische en praktische verbindingen:
- LISP’s expressiviteit en manipulatie van symbolische data maken het geschikt om interpreters voor logische talen of bibliotheken voor redeneermechanismen te implementeren.
- Verschillende systemen en extensies (zoals micro-implementaties van Prolog in Lisp) laten toe logische regels en proof-search in een Lisp-omgeving uit te voeren.
- Alonzo Church’s werk aan lambda-calculus beïnvloedde de ontwikkeling van functionele en symbolische talen; sommige ideeën zoals hogere-orde representatie en naamgeving hebben raakvlakken met logisch en kennisgebaseerd programmeren.
Toepassingen
Logisch programmeren wordt veel gebruikt in gebieden waar kennisrepresentatie, redeneren en symbolische manipulatie centraal staan, bijvoorbeeld:
- Kunstmatige intelligentie en expert systemen.
- Natural language processing en semantische analyse.
- Regelgebaseerde systemen en beleids- of regelsystemen.
- Automatisch bewijzen en type-inferencing in programmeertalenonderzoek.
Voordelen en beperkingen
- Voordelen: Declaratieve stijl maakt programma's vaak kort en dichtbij de probleemformulering; krachtige ingebouwde redeneermachines (unificatie, backtracking) besparen veel implementatiewerk.
- Beperkingen: Prestatie en schaalbaarheid kunnen problematisch zijn voor grote kennisbases; negation-as-failure is niet altijd wenselijk en vereist zorgvuldige semantiek; sommige problemen (bijvoorbeeld numerieke intensieve berekeningen) zijn beter geschikt voor imperatieve talen.
Samengevat: logisch programmeren biedt een natuurlijke manier om kennis en regels te formaliseren en automatische redenering toe te passen. Talen als Prolog implementeren deze benadering direct, terwijl talen als LISP veelzijdigheid bieden om logische systemen te bouwen of te integreren met andere stijlmiddelen (functioneel, symbolisch).