prolog.java

人工智能代码JAVA程序,包括神经网络,遗传算法

/**********************************************************
 *  P R O L O G O P
 **********************************************************/

class prologop {
    boolean prex,postx;
    int place,priority;
    static int pre=1,in=2,post=3;
    String name;
    static String AND,OR,MATCH,ARROW,CUT,REWRITE;
    /*all operators in play are defined here:*/
    static Hashtable preops,inops,postops;
    static prologop listcons;

    prologop(){}/*empty constructor.
                  use make as a (sometimes failing) constructor*/

    static prologop make(String n,String type,int prior) {
        /*returns such an operator, or null*/
        if(prior<0||prior>1200)
            return null;
        prologop p=new prologop();
        p.name=n;
        p.priority=prior;
        if(type.length()==2&&type.charAt(0)=='f')
            {p.place=pre;
            if(type.equals("fx"))
                p.postx=true;
            else if(type.equals("fy"))
                p.postx=false;
            else
                return null;
            return p;
            }
        else if(type.length()==2&&type.charAt(1)=='f')
            {p.place=post;
            if(type.equals("xf"))
                p.prex=true;
            else if(type.equals("fy"))
                p.prex=false;
            else
                return null;
            return p;
            }
        else if(type.length()==3&&type.charAt(1)=='f') {
            p.place=in;
            if(type.equals("xfx")) {
                p.prex=true;
                p.postx=true;
            }
            else if(type.equals("xfy")) {
                p.prex=true;
                p.postx=false;
            }
            else if(type.equals("yfx")) {
                p.prex=false;
                p.postx=true;
            }/*note that yfy would give rise to ambiguity*/
            else return null;
            return p;
        }
        return null;
    }

    public static void makeops() {
        if(term.emptylist!=null)
            return;
        term.emptylist=term.newconstant("[]","[]");

        AND=",";
        OR=";";
        MATCH="=";
        ARROW=":-";
        CUT="!";
        REWRITE="-->";

        preops=new Hashtable();
        inops=new Hashtable();
        postops=new Hashtable();
        addoperator("?-","fx",1200);//
        addoperator(ARROW,"xfx",1200);//the if
        addoperator(ARROW,"fx",1200);//the do in programs
        addoperator(REWRITE,"xfx",1200);//grammar rules
        addoperator("not","fx",900);
        addoperator(OR,"xfy",1100);//the ;
        addoperator(AND,"xfy",1000);//the ,
        addoperator(MATCH,"xfx",700);//matchable
        addoperator("==","xfx",700);//exactly the same
        addoperator("\\==","xfx",700);//not the same
        addoperator(">","xfx",700);//compare values
        addoperator("<","xfx",700);//compare values
        addoperator(">=","xfx",700);//compare values
        addoperator("<=","xfx",700);//compare values
        addoperator("is","xfx",700);// calculate right
        addoperator("=:=","xfx",700);//values equal
        addoperator("=\\=","xfx",700);//values unequal
        addoperator("=..","xfx",700);//compose a(b)=..[a,b]

        addoperator("+","yfx",500);
        addoperator("-","yfx",500);
        addoperator("-","fx",500);
        addoperator("+","fx",500);
        addoperator("*","yfx",400);
        addoperator("/","yfx",400);
        addoperator("div","yfx",400);
        addoperator("mod","xfx",300);

        listcons=make(".","xfy",600);
    }
    public static boolean addoperator(String s,String type,int level) {
        prologop op=make(s,type,level);
        if(op==null)
            return false;
        if(op.place==op.pre)
            preops.put(s,op);
        else if(op.place==op.in)
            inops.put(s,op);
        else
            postops.put(s,op);
        return true;
    }

    public static prologop preop(String name)
    {return (prologop)preops.get(name);}
    public static prologop inop(String name)
    {return (prologop)inops.get(name);}
    public static prologop postop(String name)
    {return (prologop)postops.get(name);}

    int under(prologop o1,prologop o2) {
        /*1 means that that o1 can be under o2: like 3*4+2
          2 means 2+3*4.
          0 means they cannot be combined. for example let <-- be xfx,
          then a <-- b <-- c is a syntax error.
        */
        if(o1.priority<o2.priority)
            return 1;
        if(o1.priority>o2.priority)
            return 2;
        if(!o2.prex)
            return 1;
        if(!o1.postx)
            return 2;
        return 0;
    }
    int leftunderlevel() {
        if(prex)
            return priority-1;
        return priority;
    }
    int rightunderlevel() {
        if(postx)
            return priority-1;
        return priority;
    }

}

/**********************************************************
 *  P R O G R A M
 **********************************************************/

class program {
    static Hashtable prelude;
    Hashtable user;
    /*the hashtables stores lists of clause of certain name and arity.*/
    solver sv;

    program() {
        if(prelude==null)
            makeprelude();
        user=new Hashtable();
        fillwith(user,prelude);
    }
    void setsolver(solver S) { sv=S; }

    static void makeprelude() {
        prelude=new Hashtable();
        assert(prelude,"member(X,[X|_]).");
        assert(prelude,"member(X,[_|H]):-member(X,H).");
        assert(prelude,"not(X):-X,!,fail.");
        assert(prelude,"not(X).");
        assert(prelude,"append([],B,B).");
        assert(prelude,"append([A|B],C,[A|D]):-append(B,C,D).");
        assert(prelude,"select([X|B],X,B).");
        assert(prelude,"select([A|B],X,[A|C]):-select(B,X,C).");
        assert(prelude,"reverse(X,XR):-reverse(X,[],XR).");
        assert(prelude,"reverse([],XR,XR).");
        assert(prelude,"reverse([H|T],TR,XR):-reverse(T,[H|TR],XR).");
        assert(prelude,"permutation([],[]).");
        assert(prelude,"permutation(LX,[X|LP]):-select(LX,X,L),permutation(L,LP).");
    }
    void remove(String s) {
        /*remove a searchkey.*/
        user.remove(s);
    }

    static void fillwith(Hashtable to,Hashtable from) {
        Enumeration enum=from.elements();
        term oldlist,newlist;
        while(enum.hasMoreElements()) {
            oldlist=(term)enum.nextElement();
            if(oldlist!=term.emptylist)
                to.put(searchkey(head(oldlist.arg[0])),copylist(oldlist));
        }
    }
    static term copylist(term list) {
        if(list==term.emptylist)
            return list;
        return term.makelist(list.arg[0],copylist(list.arg[1]));
    }
    static void listaddz(term list,term t) {
        list=term.skipeq(list);
        while(list.arg[1]!=term.emptylist)
            list=list.arg[1];
        list.arg[1]=term.makelist(t,term.emptylist);
    }

    public String toString() {
        Enumeration enum=user.elements();
        Vector v;
        term t;
        StringBuffer buf=new StringBuffer("\n");
        while(enum.hasMoreElements()) {
            term list=(term)enum.nextElement();
            while(list!=term.emptylist) {
                buf.append(list.arg[0] +".\n");
                list=list.arg[1];
            }
            buf.append("\n");
        }
        return buf.toString();
    }

    static boolean assert(Hashtable h,String s)
    {return assert(h,new prologtokenizer(s).gettermdot(null));}

    static term gramconvert(term t) {
        //we assume no eq's in the term (it is parsed or a copy).
        if(t.type!=term.FUNCTOR||t.arity!=2||!t.name.equals(prologop.REWRITE))
            return t;
        term a,b;
        a=new term();/*differencelist a-b*/
        b=new term();
        t.arg[0].addarg(a);
        t.arg[0].addarg(b);
        t.arg[1]=makediflist(t.arg[1],a,b);
        t.name=prologop.ARROW;
        return t;
    }

    static term makediflist(term t,term a,term b) {
        //t has no eq's
        if(t.type!=term.FUNCTOR)
            return term.newconstant("error");
        if(t.name.equals("[]")&&t.arity==0) {
            term is=term.newconstant(prologop.MATCH);
            is.addarg(a);
            is.addarg(b);
            return is;
        }
        if(t.name.equals(prologop.listcons.name)) {
            listend(t,b);
            term is=term.newconstant(prologop.MATCH);
            is.addarg(a);
            is.addarg(t);
            return is;
        }
        if(t.name.equals(prologop.AND)) {
            term c=new term();
            t.arg[0]=makediflist(t.arg[0],a,c);
            t.arg[1]=makediflist(t.arg[1],c,b);
            return t;
        }
        if(t.name.equals(prologop.OR)) {
            t.arg[0]=makediflist(t.arg[0],a,b);
            t.arg[1]=makediflist(t.arg[1],a,b);
            return t;
        }
        t.addarg(a);
        t.addarg(b);
        return t;
    }

    static void listend(term list,term t) {
        while(list.arg[1]!=term.emptylist)
            list=list.arg[1];
        list.arg[1]=t;
    }

    static boolean assert(Hashtable h,term t) {
        if(t==null)  return false;
        term thead=head(t);
        if(thead==null)  return false;
        term list=(term)h.get(searchkey(thead));
        if(list==null||list==term.emptylist) {
            list=term.makelist(t,term.emptylist);
            h.put(searchkey(thead),list);
        }
        else  listaddz(list,t);
        return true;
    }

    static boolean asserta(Hashtable h,term t) {
        if(t==null)  return false;
        //t=term.skipeq(t);
        term thead=head(t);
        if(thead==null)  return false;
        term list=(term)h.get(searchkey(thead));
        if(list==null)
            list=term.makelist(t,term.emptylist);
        else
            list=term.makelist(t,list);
        h.put(searchkey(thead),list);
        return true;
    }

    static String searchkey(term t)
    /*calculates a key for a head, to find it in a hashtable*/
    {return t.name+"/"+t.arity;}

    term get(term head)
    /*give a predicate, it returns a list of all clauses */
    {return (term)user.get(searchkey(head));}

    static term head(term t) {
        if(t.type!=t.FUNCTOR)               return null;
        if(t.name.equals(prologop.ARROW))   return t.arg[0];
        else return t;
    }
    static term body(term t) {
        if(t.type==t.FUNCTOR&&t.name.equals(prologop.ARROW))
            return t.arg[1];
        return null;
    }
}

/**********************************************************
 *  R A C K
 **********************************************************/

class rack {
    term pred;
    int solveoption;
    static int BUILTIN=-4,NOTAGAIN=-2,UNKNOWN=-1;
    term clauses;
    int substdone;
    rack parent;

    rack(term h,rack p) {
        pred=h;
        solveoption=UNKNOWN;
        substdone=0;
        parent=p;
    }
}

/**********************************************************
 *  S O L V E R
 **********************************************************/
class solver {
    Stack todo;
    Stack done;
    Stack subst;
    Thread mythread;
    program lib;
    Vector uservars;
    prologtokenizer inp;
    Stack consultstack;
    static Hashtable bi_pred;
    long time;
    static term ASK;
    boolean wait;

    void bi(String s,int a,int n)
    {bi_pred.put(s+"/"+a,new Integer(n));}

    solver(program l) {
        if(ASK==null) {
            ASK=term.newconstant("ask user ");
            bi_pred=new Hashtable();
            bi("repeat",0,1);
            bi("fail",0,2);
            bi("true",0,3);
            bi("!",0,4);
            bi("=",2,5);
            bi("is",2,6);
            bi("=:=",2,7);
            bi("<",2,8);
            bi(">",2,9);
            bi("<=",2,10);
            bi(">=",2,11);
            bi("=\\=",2,12);
            bi("get",1,15);
            bi("get0",1,16);
            bi("seen",0,17);
            bi("nl",0,20);
            bi("put",1,21);
            bi("told",0,22);
            bi("newprogram",0,23);
            bi(prologop.listcons.name,2,25);
            bi("assert",1,26);
            bi("assertz",1,26);
            bi("asserta",1,27);
            bi("retract",1,28);
            bi("writeprogram",0,29);
            bi("op",3,30);
            bi("var",1,31);
            bi("nonvar",1,32);
            bi("atom",1,33);
            bi("integer",1,34);
            bi("=..",2,35);
            bi("name",2,36);
            bi("==",2,37);
            bi(";",2,38);
            bi(",",2,39);
            bi("compound",1,40);
            bi("random",3,41);
            bi("\\==",2,42);
            bi("writenoq",1,43);
            bi("writeq",1,44);
        }
        lib=l;
    }
    int getbinum(term r) {
        Integer i=(Integer)bi_pred.get(lib.searchkey(r));
        if(i==null)
            return -1;
        return i.intValue();
    }

    void stacktodo(term q,rack r)
    { /*push all goals in q on the todo stack, with parent r.*/
        if(q==null)
            return;
        if(q.type==q.FUNCTOR&&q.name==prologop.AND) {
            stacktodo(q.arg[1],r);
            stacktodo(q.arg[0],r);