[prolog] search pruning operator, cut achtig. - Softwareontwikkeling

maandag 26 januari 2004 10:56

Acties:

-= Tja =-

Topicstarter

Ik zit met een probleem bij Prolog en bij de cut. De cut operator doet 2 dingen
-Alle alternatieven bij een rule-call voor de cut verwijdereren
-Geen alternatieve regels meer gebruiken voor de rule-call.

Ik vind dit te beperkt, ik heb eigelijk alleen maar belangstelling bij die geen alternatieven meer gebruiken. Zie ik iets over het hoofd? Of heeft standaard Prolog deze operator niet?

Ik heb intussen zelf een commit_rule operator toegevoegt die dit gedrag trouwens al wel heeft, maar ik wil toch even zeker weten dat ik niets over het hoofd zie.

[edit]
Nog een ander probleem:

Bij Prolog kun je mbv assert gegevens aan de rulebase toevoegen, helaas worden deze gegevens bij het backtracken nooit meer gecleaned. Het is voor mij erg eenvoudig om dit wel voor elkaar te krijgen, maar ik heb hiervoor ook niets in al mijn Prolog boeken gevonden.

Verder heb ik ook nog een map gemaakt waarin je value:terms kan storen op key:term. Deze map wordt ook gecleaned by het backtracken. Hiervoor heb ik ook nog niets in Prolog gezien, maar ik kan er niet over uit dat zoiets nooit is geimplementeerd. Dus.. wie kan me wat info verstrekken over alternatieve manieren van opslag van gegevens??

En dit is een voorbeeld van hoe ik het heb gebruikt.

Prolog:

/**
 * infer_sequence(InferType,InferSequenceList)
 * 
 * Haalt een lijst op met alle afleidingsstappen voor een bepaald afleidingstype.
 *
 * InferType    het InferType waarvan je de lijst met afleidingsstappen wilt ophalen.
 *
 * InferSequenceList    een lijst met alle afleidingsstappen.
 */
 
infer_sequence(query_only,[database,default])
    :-  commit_rule.

infer_sequence(prove_first,[database,rules,user,default])
    :-  commit_rule.

infer_sequence(prove_only,[database,rules,default])
    :-  commit_rule.
    
infer_sequence(ask_first,[database,user,rules,default])
    :-  commit_rule.

infer_sequence(ask_only,[database,user,default])
    :-  commit_rule.
    
infer_sequence(X,_)
    :-  //Message is ('unknown infertype: '+X),
        //writeln('message build'),
        error('unknown inferencetype').
    
    
//----------------------------------------------------------------------------

/**
 * slot_value(Slot,Value,Proof)
 *
 * leidt de waarde voor een slot af. 
 *
 * Slot is het Slot waarvoor je de waarde wilt afleiden
 *
 * Value is de afgeleide waarde
 *
 * Proof is het geleverde bewijs
 */

//Kijk eerst of er al een waarde is afgeleid. 
slot_value(Slot,Value,Proof)
    :-  getValue(Slot,pair(Value,Proof))
    ,   commit_rule.
 
//Er is nog geen waarde afgeleid, dus leidt een nieuwe af en store de oplossing         
slot_value(Slot,Value,Proof)
    :-  infer_slot_value(Slot,Value,Proof)
    ,   setValue(Slot,pair(Value,Proof))
    .
    
    infer_slot_value(Slot,Value,Proof)
        :-  slot(Slot,Infer_type,_)
        ,   infer_sequence(Infer_type,Infer_sequence)
        ,   infer_from_infer_sequence(Slot,Value,Infer_sequence,Proof)
        ,   commit_rule
        .
        
    infer_slot_value(Slot,Value,Proof)
        :-  Value=unknown
        ,   Proof = proof_by_unknown(Slot,Value)
        ,   commit_rule
        .
                
    infer_slot_slot_value(Slot,Value)
        :-  error('unhandeled value_of')
        .   
    
                    
    /**
     * infer_from_infer_sequence(Slot,Value,InferStageList,Proof)
     *
     * Aan de hand van de lijst met InferStages (InferStageList), ga je deze lijst bij langs 
     * net zo lang totdat je een goed antwoord hebt gevonden voor een inferstage. Heb je een 
     * goed antwoord gevonden dan worden de achterliggende inferstages niet meer gebruikt.
     *
     * Slot = het Slot waarvoor de waarde afgeleid moet worden 
     *
     * Value = de afgeleide waarde.
     *
     * InferStageList = een lijst met alle InferStages
     *
     * Proof = het geleverde bewijs.
     */
            
    infer_from_infer_sequence(Slot,Value,[Inferstage|_],Proof)
        :-  infer_from_inferstage(Slot,Value,Inferstage,Proof)
        ,   commit_rule
        .
                
    infer_from_infer_sequence(Slot,Value,[_|Tail],Proof)
        :-  infer_from_infer_sequence(Slot,Value,Tail,Proof)
        .
    
    
    /**
     * infer_from_inferstage(Slot,Value,InferStage,Proof)   
     *
     * Leidt de waarde af voor een enkele InferStage (dus user,database etc).
     *
     * Slot is het slot waarvoor je de waarde wilt afleiden
     *
     * Value is de afgeleide waarde
     *
     * InferStage = database,user,rules,default,unknown
     *
     * Proof = het geleverde bewijs.
     */
                            
    infer_from_inferstage(Slot,Value,default,Proof)
        :-  slot(Slot,_,Value)
        ,   Proof = proofed_by_default(Slot,Value)
        ,   commit_rule.
    
    //todo: gebruiker vragen (op dit moment komt het uit een slot)      
                    
    infer_from_inferstage(Slot,Value,rules,Proof)   
        :-  (
                infer_from_if_then(Slot,Value,Proof)
            ;   infer_from_if_then_value(Slot,Value,Proof)
            ;   //infer_from_always(Slot,Value,Proof);
                infer_from_slot(Slot,Value,Proof)
            )
        ,   commit_rule
        .
    
    //todo: je houd helemaal geen rekening met de body van de rule.
    infer_from_inferstage(Slot,Value,Inferstage,Proof)
        :-  Query =..[Slot,Value,Inferstage]
        ,   call(Query)
        ,   Value\=unknown
        ,   Proof = proof(Slot,Value,Inferstage)
        .
        
            
        
        //----------------------------------------------------------------------------
        //                  De inference regels voor de objecttaal zelf.
        //----------------------------------------------------------------------------
            
            
        infer_from_slot(Slot,Value,Proof)
            :-  Query =..[Slot,Value,rules]
            ,   call(Query)
            ,   Value\=unknown
            ,   Proof = proofed_by_slot(Slot,Value,rule_slot)
            .
        
        infer_from_always(Slot,Value,Proof) 
            :-  Query =..[always,Slot]
            ,   call(Query)
            ,   Value = true
            ,   Proof = proofed_by_always(Slot,Value)
            .
        
        //todo: de Value wordt nog niet ge-evalueerd.                   
        infer_from_always(Slot,Value,Proof)
            :-  Query =..[always,Slot,Value]
            ,   call(Query)
            ,   Value\=unknown
            ,   Proof = proofed_by_always(Slot,Value)
            .       
                                                            
        infer_from_if_then(Slot,Value,Proof)
            :-  Query =.. [ifthen,Condition,Slot]
            ,   call(Query)
            ,   is_true(Condition,Condition_Proof)
            ,   Value = true
            ,   Proof = proofed_by_if_then(Slot,Value,Condition_Proof,Query)
            .
        
        infer_from_if_then_value(Slot,Value,Proof)
            :-  Query =..[ifthen,Condition,Slot,Value]
            ,   call(Query)
            ,   is_true(Condition)
            ,   Value\=unknown
            ,   Proof = proofed_by_if_then_value(Slot,Value,Query)
            .
    
                
//----------------------------------------------------------------------------
//                  De object-taal.
//----------------------------------------------------------------------------
    
//todo: always.

is_true(P,Proof)
    :-  slot_value(P,true,Proof),
        commit_rule.

    
//ifthen
    
is_true(P,Proof)
    :-  ifthen(Condition,P),
        is_true(Condition,Proof).//todo

is_true(P,Proof)
    :-  ifthen(Condition,P,true),
        is_true(Condition,Proof).       
            
//En        

is_true(en(false,_))
    :-  fail,
        commit_rule.
        
is_true(en(_,false))
    :-  fail,
        commit_rule.
            
is_true(en(P1,P2),Proof)
    :-  is_true(P1,Proof_Left),
        is_true(P2,Proof_right),
        Proof = en(Proof_Left,Proof_right),
        commit_rule.


//Of        
        
is_true(of(true,_))
    :-  commit_rule.
    
is_true(of(_,true))
    :-  commit_rule.

is_true(of(P,_),Proof)
    :-  is_true(P,Proof_left),
        Proof = of(Proof_left),
        commit_rule.
    
is_true(of(_,P),Proof)
    :-  is_true(P,Proof_right),
        Proof = of(Proof_right),
        commit_rule.
    
is_true(P)
    :-  error(P).

[ Voor 110% gewijzigd door Alarmnummer op 26-01-2004 11:36 ]

dinsdag 27 januari 2004 09:36

Acties:

Alarmnummer

-= Tja =-

Topicstarter

*kick*..

helemaal geen prolog mensen hier?

dinsdag 27 januari 2004 12:55

Acties:

it0

Mijn mening is een feit.

Ik denk dat wij echt de enigste 2 zijn, en in tegenstelling tot jouw heb ik er een hekel aan.

Maar als je data wilt opslaan waarom maak je niet een externe call naar C of Java ?

dinsdag 27 januari 2004 12:56

Acties:

Alarmnummer

-= Tja =-

Topicstarter

it0 schreef op 27 januari 2004 @ 12:55:
Ik denk dat wij echt de enigste 2 zijn, en in tegenstelling tot jouw heb ik er een hekel aan.

Maar als je data wilt opslaan waarom maak je niet een externe call naar C of Java ?

Dat doe ik ook

De prolog engine is geschren in java en daar kan ik natuurlijk wel bij allerlei geheugen structuren komen. Het ging mij erom dat ik het wiel niet 2 keer loop uit te vinden. Ik had gisteren mijn afstudeercoordinator ff gesproken, en hij had het erover dat soortgelijke oplossingen wel terug te vinden waren binnen non-iso prolog implementaties. Ik heb hem net ff gemailed voor links en hoop daarmee een beetje uit te voeten te kunnen.

En prolog is harstikke handig man, super om te prototypen en om bepaalde problemen in op te lossen. Het gaat echt stukken sneller/handiger dan in java of andere procedurele taal.

[edit]
Welke combinatie van talen gebruik jij verder?

[ Voor 16% gewijzigd door Alarmnummer op 27-01-2004 13:19 ]

dinsdag 27 januari 2004 13:18

Acties:

Soultaker

Ik ben ook niet echt een fan van Prolog (ik vind het voor veel toepassingen ongeschikt) maar dat neemt niet weg dat ik het wel een interessante omgeving vindt. Het probleem is dat jouw vragen steeds over erg geavanceerde onderwerpen gaan en daar kan ik dan net weer geen antwoord op geven.

In dit geval ging het al mis bij de introductie:

Ik zit met een probleem bij Prolog en bij de cut. De cut operator doet 2 dingen
-Alle alternatieven bij een rule-call voor de cut verwijdereren
-Geen alternatieve regels meer gebruiken voor de rule-call.

Wat is een 'rule-call' en hoezo doet een cut twee dingen? Voor zover ik het begrijp kapt een cut de recursiestack af; er wordt een markering aan de stack toegevoegd en daarvoor kan niet meer worden gebacktrackt. Ik vermoed dat dit je eerste ding is; kun je me de tweede uitleggen? (De kans dat ik je dan wel kan helpen is klein, maar doe het dan voor mij, dan heb ik het in ieder geval beter begrepen

)

dinsdag 27 januari 2004 13:22

Acties:

Verwijderd

it0 schreef op 27 januari 2004 @ 12:55:
Ik denk dat wij echt de enigste 2 zijn, en in tegenstelling tot jouw heb ik er een hekel aan.

/me is een groot Prolog-fan! $_/-\o_$

Alarmnummer: mijn laatste prolog-ervaringen liggen al een jaar of 4 achter me, dus ik snap niet helemaal wat je bedoelt. Ik zal vanavond nog eens m'n Bratko erop naslaan.

Bij Prolog kun je mbv assert gegevens aan de rulebase toevoegen, helaas worden deze gegevens bij het backtracken nooit meer gecleaned. Het is voor mij erg eenvoudig om dit wel voor elkaar te krijgen, maar ik heb hiervoor ook niets in al mijn Prolog boeken gevonden.

Ik weet echt zeker dat dit mogelijk is. Bedoel je niet gewoon retract of retractall?
Zie ook:
http://www.csse.uwa.edu.a.../swi-prolog/sec-3.13.html

dinsdag 27 januari 2004 13:29

Acties:

Alarmnummer

-= Tja =-

Topicstarter

Voorbeeld zonder cut en zonder commit_rule

code:

persoon(jan).

persoon(kees).

p(X):-persoon(X).

p(X):-error.

?p(X).

Stel ik ga dit programma evalueren, dan krijg je 2 oplossingen namelijk X = jan en X = kees en je krijgt ook een error.

Voorbeeld met cut.

Prolog:

persoon(jan).

persoon(kees).

p(X):-persoon(X),cut.

p(X):-error.

?p(X).

Je krijgt 1 antwoord (namelijk X=jan) en verder geen error omdat de 2e p regel niet wordt geevalueerd.

de cut doet dus 2 dingen.
andere combinaties voor de cut zijn niet meer mogelijk
en andere p combinaties zijn niet meer mogelijk

Ik ben verder wel geinteresseerd in alle afleidingen die door de 1e toepassing van p afgeleid kunnen worden en de cut operator verhindert dat.

voorbeeld commit_rule

Prolog:

persoon(jan).

persoon(kees).

p(X):-persoon(X),commit_rule.

p(X):-error.

?p(X).

In dit geval krijg 2 oplossingen, namelijk X = jan en X = kees, en verder ook geen foutmelding.

[edit]

Dit is exact het gedrag dat ik zoek. Voor het expertsysteem zijn die contextsplitsingen enorm belangrijk omdat allerlei posities omtrend een stuk wetgeving bekeken moeten worden en juristen dus verschillende posities naast elkaar neer gaan leggen.

En een rulecall kan je vergelijken met een functie call (alhoewel je dus nog niet weet welke rule aangeroepen gaat worden en of de aanroep ook lukt).

[ Voor 20% gewijzigd door Alarmnummer op 27-01-2004 13:36 ]

dinsdag 27 januari 2004 13:32

Acties:

Alarmnummer

-= Tja =-

Topicstarter

Verwijderd schreef op 27 januari 2004 @ 13:22:
[...]

/me is een groot Prolog-fan! $_/-\o_$

Alarmnummer: mijn laatste prolog-ervaringen liggen al een jaar of 4 achter me, dus ik snap niet helemaal wat je bedoelt. Ik zal vanavond nog eens m'n Bratko erop naslaan.

Helaas staat er absoluut niet vermeld over in bratko (tenzij er in de 3e editie nog iets is bijgekomen)

Ik weet echt zeker dat dit mogelijk is. Bedoel je niet gewoon retract of retractall?

Als je gaat asserten blijven de gegevens er voor altijd instaan. Tenzij je natuurlijk een retract gaat gebruiken. Maar je moet dan wel zorgen dat er altijd een opruim regel bij komt te staan waarmee je dus je info weer gaat verwijderen. Dit lijkt me redelijk gevaarlijk ivm bugs.

Als je dit automatisch door prolog laat doen (dus opruimen bij het backtracken) dan heb je een systeem dat handiger werkt.

http://www.csse.uwa.edu.a.../swi-prolog/sec-3.13.html

Ik zal er eens naar kijken, thanx.

[ Voor 7% gewijzigd door Alarmnummer op 27-01-2004 13:38 ]

dinsdag 27 januari 2004 13:37

Acties:

Soultaker

Ok, tnx voor de uitleg.

Alarmnummer schreef op 27 januari 2004 @ 13:29:
Voorbeeld met cut.
Prolog:
1
2
3
4
5
6
7
persoon(jan).
persoon(kees).

p(X):-persoon(X),cut.
p(X):-error.

?p(X).

Als ik het goed begrijp zou je hier X=jan, X=kees uit willen krijgen. In dit voorbeeld zou ik zeggen dat je cut dan gewoon op de verkeerde plaats staat; hij moet voor persoon(x). Of is het slechts de bedoeling dat er gecut wordt als er tenminste één unification volgt?

dinsdag 27 januari 2004 13:40

Acties:

Alarmnummer

-= Tja =-

Topicstarter

Soultaker schreef op 27 januari 2004 @ 13:37:
Ok, tnx voor de uitleg.

[...]

Als ik het goed begrijp zou je hier X=jan, X=kees uit willen krijgen. In dit voorbeeld zou ik zeggen dat je cut dan gewoon op de verkeerde plaats staat; hij moet voor persoon(x). Of is het slechts de bedoeling dat er gecut wordt als er tenminste één unification volgt?

Als je hem voor persoon(X) gaat plaatsen, dan wordt per definitie die p(X):-error regel nooit meer uitgevoerd. En dat wil ik dus wel als voorgaande regels niet tot een oplossing hebben kunnen leiden. Ik wil de andere regels dus afkeuren als er 1 of meerdere oplossingen voor de commit_rule gelukt zijn, maar ik wil wel al die oplossingen kunnen gebruiken) En bij de cut kan je die andere oplossingen dus niet meer gebruiken.

[ Voor 5% gewijzigd door Alarmnummer op 27-01-2004 13:42 ]

dinsdag 27 januari 2004 13:43

Acties:

soepkip

Kratjes kunnen nu ook voorin

Oei dat is lang geleden (hoe lang ook alweer Blues ??)

Maare Prolog was toch in C geschreven, niet in java

Beste film ooit

dinsdag 27 januari 2004 13:45

Acties:

Alarmnummer

-= Tja =-

Topicstarter

soepkip schreef op 27 januari 2004 @ 13:43:
Oei dat is lang geleden (hoe lang ook alweer Blues ??)

Maare Prolog was toch in C geschreven, niet in java

Prolog kan in allerlei talen geschreven worden, uiteraard c,c++,java maar ook Lisp of Prolog. Ik heb voor mijn afstuderen oa een prolog interpreter geschreven in Java icm een 'expertsysteem' in Prolog voor juristen.

[ Voor 6% gewijzigd door Alarmnummer op 27-01-2004 13:45 ]

dinsdag 27 januari 2004 13:49

Acties:

soepkip

Kratjes kunnen nu ook voorin

Alarmnummer schreef op 27 januari 2004 @ 13:45:
[...]

Prolog kan in allerlei talen geschreven worden, uiteraard c,c++,java maar ook Lisp of Prolog. Ik heb voor mijn afstuderen oa een prolog interpreter geschreven in Java icm een 'expertsysteem' in Prolog voor juristen.

Ik neem aan dat de kern van het expersysteem uit prolog bestond ?

zoals gezecht is het lang geleden (1995-1997 ??) en ik herrinner me dat de swi-prolog die we gebruikte makkelijk te combineren was met C

Beste film ooit

dinsdag 27 januari 2004 13:51

Acties:

Alarmnummer

-= Tja =-

Topicstarter

soepkip schreef op 27 januari 2004 @ 13:49:
[...]
Ik neem aan dat de kern van het expersysteem uit prolog bestond ?

Idd.. De expertsysteem engine is geschreven in Prolog + deze extra operatoren dus (en nog een paar extra`s zoals metadata) , en deze engine wordt dus weer geevalueerd in Prolog (mijn eigen prolog interpreter dus).

[ Voor 24% gewijzigd door Alarmnummer op 27-01-2004 13:54 ]

dinsdag 27 januari 2004 14:16

Acties:

Verwijderd

Alarmnummer schreef op 27 januari 2004 @ 13:29:
Voorbeeld zonder cut en zonder commit_rule
Dit is exact het gedrag dat ik zoek. Voor het expertsysteem zijn die contextsplitsingen enorm belangrijk omdat allerlei posities omtrend een stuk wetgeving bekeken moeten worden en juristen dus verschillende posities naast elkaar neer gaan leggen.

Is dit dan niet uit te drukken als een soort exclusive or? Of hij matcht op alle personen (recursief), of hij geeft een error?

dinsdag 27 januari 2004 14:55

Acties:

Alarmnummer

-= Tja =-

Topicstarter

Verwijderd schreef op 27 januari 2004 @ 14:16:
[...]

Is dit dan niet uit te drukken als een soort exclusive or? Of hij matcht op alle personen (recursief), of hij geeft een error?

Ik weet niet of dat kan, maar stel dat het wel zou kunnen, dan zou je wel erg moeilijk moeten doen voor iets dat vrij eenvoudig te realiseren is. En zeker als je nagaat dat ik het dus erg veel nodig ben.

[edit]
Als je bv kijkt naar prolog varianten zoals Godel, dan zie je dat ze ook geen genoegen namen met de standaard search tree pruning operator, maar hieraan ook nieuwe hebben toegevoegt.

[ Voor 25% gewijzigd door Alarmnummer op 27-01-2004 15:03 ]

dinsdag 27 januari 2004 15:15

Acties:

chris

Alarmnummer: ik denk niet dat zoiets standaard in Prolog zit. Er word in geen enkele manual over gesproken, het enige 'alternatief' voor normaal backtracken is de cut. Misschien zou je de auteurs van SWI-Prolog (komt uit A'dam) eens kunnen mailen ofzo?

Pagina: 1

Reageer