MaudeTypedLog: A Typed Interpreter for Prolog in Maude

Stel je voor dat je een kaartenhuis bouwt. In de wereld van de informatica is er een populaire taal genaamd Prolog die fungeert als een meesterbouwer, maar het heeft een zeer losjes regelboek: het geeft niet om het feit of je een zware baksteen bovenop een delicate papieren tent probeert te balanceren. Het probeert gewoon ze passend te maken. Als de baksteen te zwaar is, kan het hele bouwwerk later instorten, of zegt de bouwer simpelweg: "Nou, dit werkte niet," zonder je te vertellen waarom het misging. Dit komt omdat Prolog van oudsher "ongetypeerd" is, wat betekent dat het niet controleert of de stukken die je probeert te verbinden wel de juiste vorm of het juiste materiaal hebben voordat het begint met bouwen.

Echter, soms weet de bouwer het wél beter. Als je hem vraagt om een lijst met getallen op een specifieke manier met een enkel getal te mengen, kan hij zijn handen omhoog gooien en roepen: "Error!" Maar dit gebeurt pas nadat het bouwen al is begonnen en het bouwwerk al begint te wankelen. Jarenlang hebben informatici geprobeerd Prolog een beter regelboek te geven—een "type systeem"—dat de materialen controleert voordat het bouwen begint. Het probleem is dat de meeste van deze pogingen óf te ingewikkeld zijn voor mensen om te gebruiken, óf zo vaag zijn dat ze de overduidelijke fouten missen. Het is als een veiligheidsinspecteur die alleen het dak controleert als je er specifiek om vraagt, of een inspecteur die zegt "misschien zijn de bakstenen oké" terwijl ze overduidelijk van gelei zijn gemaakt.

Hier komt een nieuwe tool kijken, gebouwd door onderzoekers Enrique Gallifa-Tronch, João Barbosa en Santiago Escobar. Ze besloten niet langer te proberen Prolog direct te repareren, maar bouwden in plaats daarvan een gloednieuwe, superstrikte interpreter genaamd MaudeTypedLog. Denk aan het nemen van de blauwdrukken van Prolog en deze door een magische, hogesnelheidssimulatie-engine genaamd Maude laten lopen. Deze engine probeert niet alleen de stukken in elkaar te passen; het controleert of de stukken überhaupt wel naast elkaar mogen liggen. Als je probeert een "getal" aan een "woord" te lijmen, stopt de machine onmiddellijk en roept: "Type Error!" voordat er enige schade wordt aangericht.

Het artikel presenteert deze nieuwe interpreter, die de eerste van zijn soort is die een specifieke, driedelige logica gebruikt. In plaats van alleen maar "Ja" (het werkt) of "Nee" (het werkt niet) te zeggen, kan dit systeem "Fout" (het is een typefout) zeggen. De auteurs hebben niet alleen geraden dat dit zou werken; ze hebben de code geschreven, de interpreter gebouwd en getest met verschillende logische programma's. Ze lieten zien dat hun tool succesvol fouten kan opsporen in zowel de instructies (het programma) als de vragen (de queries) die andere tools zouden missen. Ze toonden ook aan dat ze precies kunnen aanwijzen naar de specifieke regel code die de problemen veroorzaakt, optredend als een detective die niet alleen zegt "er is een misdaad gepleegd", maar de exacte verdachte aanwijst. Hoewel ze toegeven dat hun tool nog niet perfect is en meer tests nodig heeft met complexe wiskundige functies, bewijzen hun simulaties dat deze nieuwe, strikte manier van het controleren van Prolog-programma's een levensvatbare en krachtige manier is om fouten vroegtijdig te vangen.

Het Verhaal van MaudeTypedLog

Het Probleem: De "Lijm" Die Niet Controleert
Prolog is een taal die wordt gebruikt voor het oplossen van puzzels en logische problemen. Het werkt door een lijst met feiten en regels te nemen en te proberen deze aan elkaar te lijmen om een vraag te beantwoorden. Traditioneel is Prolog "ongetypeerd". Stel je voor dat je een spel speelt waarbij je sokken moet matchen. In Prolog kun je proberen een rode sok met een blauwe schoen te matchen, en het spel blijft het gewoon proberen totdat het opgeeft. Het schreeuwt niet: "Hé, dat zijn niet eens hetzelfde soort object!", totdat het allerlaatste moment, en zelfs dan kan het simpelweg "Geen match" zeggen zonder uit te leggen dat de schoen het probleem was.

De auteurs stellen dat dit gevaarlijk is. Soms zegt een programma "Nee" omdat het antwoord echt "Nee" is (zoals 2 niet in de lijst [1, 3] zit), maar andere keren zegt het "Nee" omdat je iets onmogelijks hebt geprobeerd (zoals een getal in een lijst met woorden plaatsen). Prolog behandelt beide "Nee"-gevallen op dezelfde manier, wat verwarrend is.

De Oplossing: Een Drie-Wegen Verkeerslicht
De onderzoekers bouwden MaudeTypedLog, een interpreter die Prolog-programma's draait maar bij elke stap een strikte "Type Check" toevoegt. In plaats van een eenvoudig verkeerslicht met alleen Groen (Rijden) en Rood (Stoppen), heeft dit systeem een derde licht: Geel (Fout).

• Groen (Waar): De stukken passen, de types komen overeen en de logica werkt.
• Rood (Onwaar): De stukken passen qua types, maar de logica werkt niet (bijv. 2 zit niet in de lijst).
• Geel (Fout): De stukken kunnen niet passen omdat ze de verkeerde type hebben (bijv. een woord bij een getal willen optellen).

Dit "Gele" licht is de kerninnovatie. Het stelt het systeem in staat om onmiddellijk te stoppen wanneer het een typefout ziet, in plaats van het programma later te laten crashen of een verwarrend antwoord te geven.

Hoe Ze Het Gebouwd Hebben
Om dit mogelijk te maken, gebruikten de auteurs een krachtige tool genaamd Maude. Maude is als een supergeladen simulatie-engine die regels zeer snel kan herschrijven. De auteurs namen de regels van Prolog en herschreven deze binnen Maude.

1. Het Typed Unification Algoritme: Dit is de kernmotor. In normale Prolog is "unificatie" het proces om twee dingen gelijk te maken. In MaudeTypedLog creëerden ze een "Typed Unification" algoritme. Voordat het probeert twee dingen aan elkaar te lijmen, controleert het hun "types". Als de types niet overeenkomen, faalt het niet alleen; het geeft een specifiek "Wrong" signaal terug.
2. TSLD-Resolution: Dit is de chique naam voor de methode die zij gebruiken om de puzzels op te lossen. Het is een verbeterde versie van de standaard SLD-resolutie methode in Prolog. De "T" staat voor "Typed". Het bouwt een boom van alle mogelijke manieren om een probleem op te lossen. Als een tak van de boom een "Wrong" signaal raakt, wordt die tak onmiddellijk afgesneden en weet het systeem precies welke regel de fout veroorzaakte.

Wat Ze Hebben Ontdekt
De auteurs testten hun nieuwe interpreter met verschillende voorbeelden.

• Voorbeeld 1: Ze maakten een programma waar een regel genaamd r probeert een getal te vinden dat zowel in een lijst met getallen als in een lijst met letters zit. Het systeem identificeerde correct dat terwijl sommige paden werkten (het vinden van het getal 1), andere paden een "Wrong" signaal raakten omdat ze probeerden getallen en letters te mengen.
• Voorbeeld la 2: Ze maakten een programma met een verborgen typefout. Eén regel probeerde een letter in een gat te plaatsen dat bedoeld was voor een getal. Toen ze het "check" commando uitvoerden, wees MaudeTypedLog niet alleen aan dat het programma faalde; het wees direct naar de specifieke regel (clause 3) die de schuldige was.

De resultaten lieten zien dat de tool precies werkt zoals de theorie voorspelde. Het kan typefouten detecteren in zowel het programma zelf als in de vragen die aan het programma worden gesteld.

Wat Het Nog Niet Kan
De auteurs zijn eerlijk over de beperkingen van hun huidige werk. Hun tool is een prototype. Het kan nog niet alle complexe wiskundige functies aan die Prolog gewoonlijk heeft (zoals het berekenen van vierkantswortels of het dynamisch optellen van getallen). Ze hebben het ook nog niet getest op de enorme bibliotheken van regels die professionele Prolog-programma's gebruiken. Ze suggereren dat ze in de toekomst de tool moeten leren hoe ze deze geavanceerde wiskundige functies en complexere datastructuren zoals bomen moeten afhandelen.

Waarom Het Er Toe Doet
Dit artikel beweert niet dat het elk probleem in de informatica heeft opgelost. In plaats daarvan biedt het een nieuwe, duidelijkere manier om naar logische programmering te kijken. Door Maude te gebruiken om een strikte, getypeerde interpreter te creëren, hebben de auteurs aangetoond dat het mogelijk is om fouten vroegtijdig te vangen en exact aan te wijzen waar ze voorkomen. Het is alsof je een bouwer een laserwaterpas geeft die niet alleen vertelt dat een muur scheef staat, maar ook precies vertelt welke baksteen de verkeerde vorm heeft, zodat je het kunt herstellen voordat het huis instort.