XmlExpr.cs

   1 using System;
   2 using System.Collections;
   3 using System.Collections.Generic;
   4 using System.IO;
   5 using System.Xml;
   6
   7 namespace System.Xml.Expression
   8 {
   9   public class Xexpression
  10   {
  11     public static int debug_level = 0;
  12
  13     public struct Name : IEquatable<Name>
  14     {
  15       private static NameTable nt = new NameTable ();
  16
  17       private string name;
  18
  19       public Name (string str)
  20         {
  21           name = nt.Add (str);
  22         }
  23
  24       public static implicit operator Name (string str)
  25       {
  26         return new Name (str);
  27       }
  28
  29       public static implicit operator string (Name name)
  30       {
  31         return name.name;
  32       }
  33
  34       public static bool operator== (Name n1, Name n2)
  35         {
  36           return (object) n1.name == (object) n2.name;
  37         }
  38
  39       public static bool operator!= (Name n1, Name n2)
  40         {
  41           return (object) n1.name != (object) n2.name;
  42         }
  43
  44       public static bool operator== (Name n1, string n2)
  45         {
  46           return (object) n1.name == (object) n2;
  47         }
  48
  49       public static bool operator!= (Name n1, string n2)
  50         {
  51           return (object) n1.name != (object) n2;
  52         }
  53
  54       public static bool operator== (string n1, Name n2)
  55         {
  56           return (object) n1 == (object) n2.name;
  57         }
  58
  59       public static bool operator!= (string n1, Name n2)
  60         {
  61           return (object) n1 != (object) n2.name;
  62         }
  63
  64       public bool Equals (Name name)
  65       {
  66         return Object.ReferenceEquals (this.name, name.name);
  67       }
  68
  69       public override bool Equals (object obj)
  70       {
  71         return Object.ReferenceEquals (this.name, obj);
  72       }
  73
  74       public override int GetHashCode ()
  75       {
  76         return name.GetHashCode ();
  77       }
  78
  79       public static NameTable Table { get { return nt; } }
  80
  81       public override string ToString () { return name; }
  82     }
  83
  84     private static Name Nexpr = "expr";
  85
  86     private static Name Nfuncall = "funcall";
  87     private static Name Nvariable = "variable";
  88     private static Name Ninteger = "integer";
  89     private static Name Nstring = "string";
  90     private static Name Nsymbol = "symbol";
  91     private static Name Nlist = "list";
  92
  93     private static Name Ndefun = "defun";
  94     private static Name Nfname = "fname";
  95     private static Name Nargs = "args";
  96     private static Name Nargs_unevalled = "args-unevalled";
  97     private static Name Noptional = "optional";
  98     private static Name Nrest = "rest";
  99     private static Name Nbody = "body";
 100
 101     private static Name Ndefvar = "defvar";
 102     private static Name Ndescription = "description";
 103     private static Name Nrange = "range";
 104
 105     private static Name Nprogn = "progn";
 106
 107     internal abstract class Function
 108     {
 109       public Name name;
 110       public int min_arg, max_arg;
 111
 112       public Function () { }
 113
 114       public Function (Name name, int min_arg, int max_arg)
 115       {
 116         this.name = name;
 117         this.min_arg = min_arg;
 118         this.max_arg = max_arg;
 119       }
 120
 121       public abstract Term Call (Domain domain, Term[] args);
 122
 123       public override string ToString ()
 124       {
 125         return name;
 126       }
 127
 128       internal class Subroutine : Function
 129       {
 130         public Builtin builtin;
 131
 132         public Subroutine (Builtin builtin, Name name,
 133                            int min_arg, int max_arg)
 134           : base (name, min_arg, max_arg)
 135           {
 136             this.builtin = builtin;
 137           }
 138
 139         public override Term Call (Domain domain, Term[] args)
 140         {
 141           Term[] newargs = new Term[args.Length];
 142
 143           for (int i = 0; i < args.Length; i++)
 144             newargs[i] = args[i].Eval (domain);
 145           return builtin (domain, newargs);
 146         }
 147       }
 148
 149       internal class SpecialForm : Function
 150       {
 151         public Builtin builtin;
 152
 153         public SpecialForm (Builtin builtin, Name name,
 154                             int min_arg, int max_arg)
 155           : base (name, min_arg, max_arg)
 156           {
 157             this.builtin = builtin;
 158           }
 159
 160         public override Term Call (Domain domain, Term[] args)
 161         {
 162           return builtin (domain, args);
 163         }
 164       }
 165
 166       internal class Lambda : Function
 167       {
 168         internal bool args_evalled;
 169         internal Term[] args;
 170         internal Term[] body;
 171
 172         public Lambda (XmlNode node)
 173         {
 174           int nargs = 0, noptions = 0, nrest = 0;
 175           name = node.Attributes[Nfname].Value;
 176
 177           node = node.FirstChild;
 178           if (node != null
 179               && (node.Name == Nargs || node.Name == Nargs_unevalled))
 180             {
 181               XmlNode n;
 182               args_evalled = node.Name == Nargs;
 183               for (n = node.FirstChild; n != null; n = n.NextSibling)
 184                 {
 185                   if (n.Name != Nsymbol)
 186                     break;
 187                   nargs++;
 188                 }
 189               if (n != null && n.Name == Noptional)
 190                 for (n = n.NextSibling; n != null; n = n.NextSibling)
 191                   {
 192                     if (n.Name == Nrest)
 193                       break;
 194                     noptions++;
 195                   }
 196               if (n != null)
 197                 nrest++;
 198               min_arg = nargs;
 199               max_arg = nargs + noptions + nrest;
 200               args = new Term[max_arg];
 201               n = node.FirstChild;
 202               for (int i = 0; i < max_arg; n = n.NextSibling)
 203                 if (n.Name == Nsymbol)
 204                   args[i++] = new Term (n, null);
 205               if (nrest == 1)
 206                 max_arg = - max_arg;
 207             }
 208           else
 209             {
 210               min_arg = max_arg = 0;
 211             }
 212         }
 213
 214         public void SetBody (XmlNode node, Domain domain)
 215         {
 216
 217           for (node = node.FirstChild; node != null && node.Name != Nbody;
 218                node = node.NextSibling);
 219           if (node != null)
 220             {
 221               XmlNodeList nlist = node.ChildNodes;
 222
 223               body = new Term[nlist.Count];
 224               for (int i = 0; i < nlist.Count; i++)
 225                 body[i] = new Term (nlist[i], domain);
 226             }
 227         }
 228
 229         public override Term Call (Domain domain, Term[] args)
 230         {
 231           Bindings current = domain.bindings;
 232           Term result = Zero;
 233
 234           try {
 235             int i;
 236             if (args_evalled)
 237               {
 238                 Term[] newargs = new Term[args.Length];
 239                 for (i = 0; i < min_arg; i++)
 240                   newargs[i] = args[i].Eval (domain);
 241                 args = newargs;
 242               }
 243             for (i = 0; i < min_arg; i++)
 244               {
 245                 Variable var = domain.GetVar ((Name) this.args[i]);
 246                 domain.Bind (var, args[i]);
 247               }
 248             if (body != null)
 249               foreach (Term term in body)
 250                 result = term.Eval (domain);
 251           } finally {
 252             domain.UnboundTo (current);
 253           }
 254           return result;
 255         }
 256       }
 257     }
 258
 259     internal abstract class Variable
 260     {
 261       public readonly Name name;
 262       internal Term val;
 263
 264       public Variable (Name name, Term term)
 265       {
 266         this.name = name;
 267         Value = term;
 268       }
 269
 270       public Term Value
 271       {
 272         get { return val; }
 273         set
 274           {
 275             if (! ValueP (value))
 276               throw new Exception ("Invalid value of " + name + ": " + value);
 277             val = value;
 278           }
 279       }
 280
 281       public abstract bool ValueP (Term term);
 282
 283       public override string ToString () { return name + "(" + val + ")"; }
 284
 285       internal class Int : Variable
 286       {
 287         public struct Range
 288         {
 289           public int from, to;
 290         }
 291
 292         public Range[] ranges;
 293
 294         public Int (Name name, int i) : base (name, new Term (i)) { }
 295
 296         public override bool ValueP (Term term)
 297         {
 298           int i;
 299
 300           if (term.objval != null)
 301             return false;
 302           if (ranges == null)
 303             return true;
 304           i = term.intval;
 305           foreach (Range r in ranges)
 306             if (i >= r.from && i <= r.to)
 307               return true;
 308           return false;
 309         }
 310       }
 311
 312       internal class Str : Variable
 313       {
 314         public string[] ranges;
 315
 316         public Str (Name name, string str) : base (name, new Term (str)) { }
 317
 318         public override bool ValueP (Term term)
 319         {
 320           if (! (term.objval is string))
 321             return false;
 322           if (ranges == null)
 323             return true;
 324           string str = (string) term.objval;
 325           foreach (string s in ranges)
 326             if (s == str)
 327               return true;
 328           return false;
 329         }
 330       }
 331
 332       internal class Misc : Variable
 333       {
 334         public Misc (Name name, Term term) : base (name, term) { }
 335
 336         public override bool ValueP (Term term) { return true; }
 337       }
 338     }
 339
 340     internal class Bindings
 341     {
 342       private Variable vari;
 343       private Term old_value;
 344       private Bindings next;
 345
 346       private Bindings (Variable vari)
 347       {
 348         this.vari = vari;
 349         old_value = vari.val;
 350       }
 351
 352       public static Bindings Bind (Bindings bindings, Variable vari, Term val)
 353       {
 354         Bindings b = new Bindings (vari);
 355
 356         b.vari.Value = val;
 357         b.next = bindings;
 358         return b;
 359       }
 360
 361       internal Bindings UnboundTo (Bindings boundary)
 362       {
 363         for (Bindings b = this; b != boundary; b = b.next)
 364           b.vari.val = b.old_value;
 365         return boundary;
 366       }
 367
 368       public override string ToString ()
 369       {
 370         string str = "(bindings";
 371         for (Bindings b = this; b != null; b = b.next)
 372           str += " " + vari.name + "=" + b.old_value;
 373         return str + ")";
 374       }
 375     }
 376
 377 #if false
 378     internal class ThrowException : Exception
 379     {
 380       Name tag;
 381       public object value;
 382
 383       public ThrowException (Name tag, object value) : base ()
 384         {
 385           this.tag = tag;
 386           this.value = value;
 387         }
 388     }
 389 #endif
 390
 391     public class Domain
 392     {
 393       public object context;
 394       public int depth = 0;
 395
 396       internal Dictionary<Name, Function> functions;
 397       internal Dictionary<Name, Variable> variables;
 398       internal Bindings bindings;
 399
 400       internal Domain ()
 401       {
 402         functions = new Dictionary<Name, Function> ();
 403         variables = new Dictionary<Name, Variable> ();
 404       }
 405
 406       public Domain (object context) : this (basic, context)
 407       {
 408       }
 409
 410       public Domain (Domain parent, object context)
 411       {
 412         functions = new Dictionary<Name, Function> (parent.functions);
 413         variables = new Dictionary<Name, Variable> (parent.variables);
 414         this.context = context;
 415       }
 416
 417       internal void Bind (Variable vari, Term value)
 418       {
 419         bindings = Bindings.Bind (bindings, vari, value);
 420       }
 421
 422       internal void UnboundTo (Bindings boundary)
 423       {
 424         if (bindings != null)
 425           bindings = bindings.UnboundTo (boundary);
 426       }
 427
 428       public void DefSubr (Builtin builtin, string str,
 429                            int min_arg, int max_arg, params string[] aliases)
 430       {
 431         Name name = str;
 432         Function func = new Function.Subroutine (builtin, name,
 433                                                  min_arg, max_arg);
 434         functions[name] = func;
 435         foreach (string a in aliases)
 436           functions[(Name) a] = func;
 437       }
 438
 439       public void DefSpecial (Builtin builtin, string str,
 440                               int min_arg, int max_arg,
 441                               params string[] aliases)
 442       {
 443         Name name = str;
 444         Function func = new Function.SpecialForm (builtin, name,
 445                                                   min_arg, max_arg);
 446         functions[name] = func;
 447         foreach (string a in aliases)
 448           functions[(Name) a] = func;
 449       }
 450
 451       public void DefAlias (string alias, string str)
 452       {
 453         functions[(Name) alias] = functions[(Name) str];
 454       }
 455
 456       internal Function.Lambda RegisterFunction (XmlNode node)
 457       {
 458         Function.Lambda lambda = new Function.Lambda (node);
 459
 460         functions[lambda.name] = lambda;
 461         return lambda;
 462       }
 463
 464       internal Function Defun (XmlNode node)
 465       {
 466         Name name = node.Attributes[Nfname].Value;
 467         Function func;
 468
 469         if (! functions.TryGetValue (name, out func))
 470           func = RegisterFunction (node);
 471         ((Function.Lambda) func).SetBody (node, this);
 472         return func;
 473       }
 474
 475       public void Defvar (XmlNode node)
 476       {
 477         Name name = node.Attributes[0].Value;
 478         Variable vari;
 479
 480         node = node.FirstChild;
 481         if (node.Name == Ndescription)
 482           node = node.NextSibling;
 483         if (node != null)
 484           {
 485             Name type = node.Name;
 486             XmlNodeList range_list = null;
 487             int nranges = 0;
 488             string val = node.InnerText;
 489
 490             node = node.NextSibling;
 491             if (node != null)
 492               {
 493                 range_list = node.ChildNodes;
 494                 nranges = range_list.Count;
 495               }
 496
 497             if (type == Ninteger)
 498               {
 499                 Variable.Int vi = new Variable.Int (name, parse_integer (val));
 500                 if (range_list != null)
 501                   {
 502                     vi.ranges = new Variable.Int.Range[nranges];
 503
 504                     for (int i = 0; i < nranges; i++)
 505                       {
 506                         XmlNode n = range_list[i];
 507
 508                         if (n.Name == Nrange)
 509                           {
 510                             vi.ranges[i].from =
 511                               parse_integer (n.FirstChild.InnerText);
 512                             vi.ranges[i].to =
 513                               parse_integer (n.LastChild.InnerText);
 514                           }
 515                         else
 516                           {
 517                             int num = parse_integer (n.InnerText);
 518                             vi.ranges[i].from = vi.ranges[i].to = num;
 519                           }
 520                       }
 521                   }
 522                 vari = vi;
 523               }
 524             else if (type == Nstring)
 525               {
 526                 Variable.Str vs = new Variable.Str (name, val);
 527                 if (range_list != null)
 528                   vs.ranges = new string[nranges];
 529                 for (int i = 0; i < nranges; i++)
 530                   vs.ranges[i] = range_list[i].Value;
 531                 vari = vs;
 532               }
 533             else
 534               throw new Exception ("Unknown type: " + type);
 535           }
 536         else
 537           vari = new Variable.Misc (name, Zero);
 538         variables[name] = vari;
 539       }
 540
 541       internal Function GetFunc (Name name)
 542       {
 543         Function func;
 544
 545         if (! functions.TryGetValue (name, out func))
 546           throw new Exception ("Unknown function: " + name);
 547         return func;
 548       }
 549
 550       public bool CopyFunc (Domain domain, Name name)
 551       {
 552         Function func = GetFunc (name);
 553
 554         domain.functions[name] = func;
 555         return true;
 556       }
 557
 558       public void CopyFunc (Domain domain)
 559       {
 560         foreach (KeyValuePair<Name, Function> kv in functions)
 561           domain.functions[kv.Key] = kv.Value;
 562       }
 563
 564       internal Variable GetVar (Name name)
 565       {
 566         Variable vari;
 567
 568         if (! variables.TryGetValue (name, out vari))
 569           variables[name] = vari = new Variable.Misc (name, Zero);
 570         return vari;
 571       }
 572
 573       public override string ToString ()
 574       {
 575         string str = "<(functions";
 576         foreach (KeyValuePair<Name, Function> kv in functions)
 577           str += " " + kv.Key;
 578         str += ") (variabls";
 579         foreach (KeyValuePair<Name, Variable> kv in variables)
 580           str += " " + kv.Key;
 581         str += ")";
 582         if (bindings != null)
 583           str += " " + bindings;
 584         if (context != null)
 585           str += " (" + context + ")";
 586         str += ">";
 587         return str;
 588       }
 589
 590       public void DebugWrite (bool head, string fmt, params string[] arg)
 591       {
 592         if (debug_level > depth)
 593           {
 594             if (head)
 595               {
 596                 Console.WriteLine ();
 597                 for (int i = 0; i < depth; i++)
 598                   Console.Write (" ");
 599               }
 600             Console.Write (fmt, arg);
 601           }
 602       }
 603     }
 604
 605     public delegate Term Builtin (Domain domain, Term[] args);
 606
 607     private static Domain basic = new Domain ();
 608
 609     internal static Function Fprogn;
 610
 611     static Xexpression ()
 612     {
 613       basic.DefSubr (set_value, "set", 2, 2, "=");
 614       basic.DefSpecial (and, "and", 1, -1, "&&");
 615       basic.DefSpecial (or, "or", 1, -1, "||");
 616       basic.DefSubr (not, "not", 1, 1, "!");
 617       basic.DefSubr (add, "add", 2, -1, "+");
 618       basic.DefSubr (mul, "mul", 2, -1, "*");
 619       basic.DefSubr (sub, "sub", 1, -1, "-");
 620       basic.DefSubr (div, "div", 2, -1, "/");
 621       basic.DefSubr (mod, "mod", 2, 2, "%");
 622       basic.DefSubr (logior, "logior", 2, -1, "|");
 623       basic.DefSubr (logand, "logand", 2, -1, "&");
 624       basic.DefSubr (add_set, "add-set", 2, -1, "+=");
 625       basic.DefSubr (mul_set, "mul-set", 2, -1, "*=");
 626       basic.DefSubr (sub_set, "sub-set", 2, -1, "-=");
 627       basic.DefSubr (div_set, "div-set", 2, -1, "/=");
 628       basic.DefSubr (mod_set, "mod-set", 2, 2, "%=");
 629       basic.DefSubr (logior_set, "logior-set", 2, -1, "|=");
 630       basic.DefSubr (logand_set, "logand-set", 2, -1, "&=");
 631       basic.DefSubr (lsh, "lsh", 2, 2, "<<");
 632       basic.DefSubr (rsh, "rsh", 2, 2, ">>");
 633       basic.DefSubr (lsh_set, "lsh-set", 2, 2, "<<=");
 634       basic.DefSubr (rsh_set, "rsh-set", 2, 2, ">>=");
 635       basic.DefSubr (eq, "eq", 2, -1, "==");
 636       basic.DefSubr (noteq, "noteq", 2, 2, "!=");
 637       basic.DefSubr (less_than, "lt", 2, -1, "<");
 638       basic.DefSubr (less_eq, "le", 2, -1, "<=");
 639       basic.DefSubr (greater_than, "gt", 2, -1, ">");
 640       basic.DefSubr (greater_eq, "ge", 2, -1, ">=");
 641       basic.DefSubr (copy, "copy", 1, 1);
 642       basic.DefSubr (append, "append", 0, -1);
 643       basic.DefSubr (concat, "concat", 0, -1);
 644       basic.DefSubr (nth, "nth", 2, 2);
 645       basic.DefSubr (eval_clause, "eval", 1, 1);
 646       basic.DefSpecial (quote_clause, "quote", 1, 1);
 647       basic.DefSpecial (progn_clause, "progn", 0, -1, "expr");
 648       basic.DefSpecial (if_clause, "if", 2, -1);
 649       basic.DefSpecial (when_clause, "when", 1, -1);
 650       basic.DefSpecial (while_clause, "while", 1, -1);
 651
 652       Fprogn = basic.GetFunc (Nprogn);
 653     }
 654
 655     private static Term set_value (Domain domain, Term[] args)
 656     {
 657       Variable vari = domain.GetVar ((Name) args[0]);
 658
 659       vari.Value = args[1];
 660       return vari.val;
 661     }
 662
 663     private static Term and (Domain domain, Term[] args)
 664     {
 665       foreach (Term arg in args)
 666         if (! arg.Eval (domain).IsTrue)
 667           return Zero;
 668       return One;
 669     }
 670
 671     private static Term or (Domain domain, Term[] args)
 672     {
 673       foreach (Term arg in args)
 674         if (arg.Eval (domain).IsTrue)
 675           return One;
 676       return Zero;
 677     }
 678
 679     private static Term not (Domain domain, Term[] args)
 680     {
 681       return args[0].IsTrue ? Zero : One;
 682     }
 683
 684     private static Term add (Domain domain, Term[] args)
 685     {
 686       int n = 0;
 687       foreach (Term arg in args)
 688         n += (int) arg;
 689       return n;
 690     }
 691
 692     private static Term mul (Domain domain, Term[] args)
 693     {
 694       int n = 1;
 695       foreach (Term arg in args)
 696         n *= (int) arg;
 697       return n;
 698     }
 699
 700     private static Term sub (Domain domain, Term[] args)
 701     {
 702       int n = (int) args[0];
 703       if (args.Length == 1)
 704         return - n;
 705       for (int i = 1; i < args.Length; i++)
 706         n -= (int) args[i];
 707       return n;
 708     }
 709
 710     private static Term div (Domain domain, Term[] args)
 711     {
 712       int n = (int) args[0];
 713       for (int i = 1; i < args.Length; i++)
 714         n /= (int) args[i];
 715       return n;
 716     }
 717
 718     private static Term mod (Domain domain, Term[] args)
 719     {
 720       return ((int) args[0] % (int) args[1]);
 721     }
 722
 723     private static Term logior (Domain domain, Term[] args)
 724     {
 725       int n = 0;
 726       foreach (Term arg in args)
 727         n |= (int) arg;
 728       return n;
 729     }
 730
 731     private static Term logand (Domain domain, Term[] args)
 732     {
 733       int n = (int) args[0];
 734       for (int i = 1; i < args.Length; i++)
 735         n &= (int) args[i];
 736       return n;
 737     }
 738
 739     private static Term add_set (Domain domain, Term[] args)
 740     {
 741       Variable vari = domain.GetVar ((Name) args[0]);
 742       int n = (int) vari.val;
 743
 744       for (int i = 1; i < args.Length; i++)
 745         n += (int) args[i];
 746       vari.val = n;
 747       return vari.val;
 748     }
 749
 750     private static Term mul_set (Domain domain, Term[] args)
 751     {
 752       Variable vari = domain.GetVar ((Name) args[0]);
 753       int n = (int) vari.val;
 754
 755       for (int i = 1; i < args.Length; i++)
 756         n *= (int) args[i];
 757       vari.val = n;
 758       return vari.val;
 759     }
 760
 761     private static Term sub_set (Domain domain, Term[] args)
 762     {
 763       Variable vari = domain.GetVar ((Name) args[0]);
 764       int n = (int) vari.val;
 765
 766       for (int i = 1; i < args.Length; i++)
 767         n -= (int) args[i];
 768       vari.val = n;
 769       return vari.val;
 770     }
 771
 772     private static Term div_set (Domain domain, Term[] args)
 773     {
 774       Variable vari = domain.GetVar ((Name) args[0]);
 775       int n = (int) vari.val;
 776
 777       for (int i = 1; i < args.Length; i++)
 778         n /= (int) args[i];
 779       vari.val = n;
 780       return vari.val;
 781     }
 782
 783     private static Term mod_set (Domain domain, Term[] args)
 784     {
 785       Variable vari = domain.GetVar ((Name) args[0]);
 786       int n = (int) vari.val;
 787
 788       for (int i = 1; i < args.Length; i++)
 789         n %= (int) args[i];
 790       vari.val = n;
 791       return vari.val;
 792     }
 793
 794     private static Term logior_set (Domain domain, Term[] args)
 795     {
 796       Variable vari = domain.GetVar ((Name) args[0]);
 797       int n = (int) vari.val;
 798
 799       for (int i = 1; i < args.Length; i++)
 800         n |= (int) args[i];
 801       vari.val = n;
 802       return vari.val;
 803     }
 804
 805     private static Term logand_set (Domain domain, Term[] args)
 806     {
 807       Variable vari = domain.GetVar ((Name) args[0]);
 808       int n = (int) vari.val;
 809
 810       for (int i = 1; i < args.Length; i++)
 811         n &= (int) args[i];
 812       vari.val = n;
 813       return vari.val;
 814     }
 815
 816     private static Term lsh (Domain domain, Term[] args)
 817     {
 818       return (int) args[0] << (int) args[1];
 819     }
 820
 821     private static Term lsh_set (Domain domain, Term[] args)
 822     {
 823       Variable vari = domain.GetVar ((Name) args[0]);
 824       int n = (int) vari.val;
 825
 826       n <<= (int) args[1];
 827       vari.val = n;
 828       return vari.val;
 829     }
 830
 831     private static Term rsh (Domain domain, Term[] args)
 832     {
 833       return (int) args[0] >> (int) args[1];
 834     }
 835
 836     private static Term rsh_set (Domain domain, Term[] args)
 837     {
 838       Variable vari = domain.GetVar ((Name) args[0]);
 839       int n = (int) vari.val;
 840
 841       n >>= (int) args[1];
 842       vari.val = n;
 843       return vari.val;
 844     }
 845
 846     private static Term eq (Domain domain, Term[] args)
 847     {
 848       Term o = args[0];
 849
 850       if (o.objval == null)
 851         {
 852           for (int i = 1; i < args.Length; i++)
 853             if (args[i].objval != null || args[i].intval != o.intval)
 854               return Zero;
 855         }
 856       else
 857         {
 858           for (int i = 1; i < args.Length; i++)
 859             if (o.objval.Equals (args[i].objval))
 860               return Zero;
 861         }
 862       return One;
 863     }
 864
 865     private static Term noteq (Domain domain, Term[] args)
 866     {
 867       return eq (domain, args);
 868     }
 869
 870     private static Term less_than (Domain domain, Term[] args)
 871     {
 872       int n = (int) args[0];
 873
 874       for (int i = 1; i < args.Length; i++)
 875         {
 876           int n1 = (int) args[i];
 877           if (n >= n1)
 878             return Zero;
 879           n = n1;
 880         }
 881       return One;
 882     }
 883
 884     private static Term less_eq (Domain domain, Term[] args)
 885     {
 886       int n = (int) args[0];
 887       for (int i = 1; i < args.Length; i++)
 888         {
 889           int n1 = (int) args[i];
 890           if (n > n1)
 891             return Zero;
 892           n = n1;
 893         }
 894       return One;
 895     }
 896
 897     private static Term greater_than (Domain domain, Term[] args)
 898     {
 899       int n = (int) args[0];
 900       for (int i = 1; i < args.Length; i++)
 901         {
 902           int n1 = (int) args[i];
 903           if (n <= n1)
 904             return Zero;
 905           n = n1;
 906         }
 907       return One;
 908     }
 909
 910     private static Term greater_eq (Domain domain, Term[] args)
 911     {
 912       int n = (int) args[0];
 913       for (int i = 1; i < args.Length; i++)
 914         {
 915           int n1 = (int) args[i];
 916           if (n < n1)
 917             return Zero;
 918           n = n1;
 919         }
 920       return One;
 921     }
 922
 923     private static Term copy (Domain domain, Term[] args)
 924     {
 925       object obj = args[0].objval;
 926
 927       if (! (obj is List<Term>))
 928         throw new Exception ("Invalid arg to copy: " + args[0]);
 929       return new Term (new List<Term> ((List<Term>) obj));
 930     }
 931
 932     private static Term append (Domain domain, Term[] args)
 933     {
 934       List<Term> list = new List<Term> ();
 935       Term result;
 936
 937       foreach (Term arg in args)
 938         {
 939           if (arg.IsList)
 940             list.AddRange ((List<Term>) arg.objval);
 941           else
 942             list.Add (arg);
 943         }
 944       result.intval = 0;
 945       result.objval = list;
 946       return result;
 947     }
 948
 949     private static Term concat (Domain domain, Term[] args)
 950     {
 951       string str = "";
 952       Term result;
 953
 954       foreach (Term arg in args)
 955         {
 956           if (arg.IsStr)
 957             str += (string) arg.objval;
 958           else if (arg.IsList)
 959             foreach (Term term in (List<Term>) arg.objval)
 960               str += (char) term.Intval;
 961           else
 962             str += (char) arg.Intval;
 963         }
 964       result.intval = 0;
 965       result.objval = str;
 966       return result;
 967     }
 968
 969     private static Term nth (Domain domain, Term[] args)
 970     {
 971       Term result;
 972
 973       if (args[1].IsStr)
 974         {
 975           result.intval = ((string) args[1].objval)[args[0].Intval];
 976           result.objval = null;
 977         }
 978       else if (args[1].IsList)
 979         {
 980           result.intval = 0;
 981           result.objval = ((List<Term>) args[1].objval)[args[0].Intval];
 982         }
 983       else
 984         throw new Exception ("Term is not enumelable: " + args[1]);
 985       return result;
 986     }
 987
 988     private static Term quote_clause (Domain domain, Term[] args)
 989     {
 990       return new Term (args[0]);
 991     }
 992
 993     private static Term eval_clause (Domain domain, Term[] args)
 994     {
 995       return (args[0].Eval (domain));
 996     }
 997
 998     private static Term progn_clause (Domain domain, Term[] args)
 999     {
1000       Term result = One;
1001
1002       foreach (Term arg in args)
1003         result = arg.Eval (domain);
1004       return result;
1005     }
1006
1007     private static Term if_clause (Domain domain, Term[] args)
1008     {
1009       if (args[0].Eval (domain).IsTrue)
1010         return args[1].Eval (domain);
1011
1012       Term result = Zero;
1013       for (int i = 2; i < args.Length; i++)
1014         result = args[i].Eval (domain);
1015       return result;
1016     }
1017
1018     private static Term when_clause (Domain domain, Term[] args)
1019     {
1020       if (! args[0].Eval (domain).IsTrue)
1021         return Zero;
1022
1023       Term result = One;
1024       for (int i = 1; i < args.Length; i++)
1025         result = args[i].Eval (domain);
1026       return result;
1027     }
1028
1029     private static Term while_clause (Domain domain, Term[] args)
1030     {
1031       while (args[0].Eval (domain).IsTrue)
1032         for (int i = 1; i < args.Length; i++)
1033           args[i].Eval (domain);
1034       return Zero;
1035     }
1036
1037     public struct Term
1038     {
1039       public int intval;
1040       public object objval;
1041
1042       public Term (int i) { intval = i; objval = null; }
1043       public Term (Name name) { intval = 0; objval = name; }
1044       public Term (string str) { intval = 0; objval = str; }
1045       public Term (List<Term> list) { intval = 0; objval = list; }
1046       public Term (Term term) { intval = 0; objval = term; }
1047
1048       public Term (XmlNode node, Domain domain)
1049         {
1050           Name name = node.Name;
1051
1052           if (name == Ninteger)
1053             {
1054               intval = parse_integer (node.InnerText);
1055               objval = null;
1056             }
1057           else
1058             {
1059               intval = 0;
1060               if (name == Nsymbol)
1061                 objval = (Name) node.InnerText;
1062               else if (name == Nstring)
1063                 objval = node.InnerText.Clone ();
1064               else if (name == Nvariable)
1065                 objval = domain.GetVar ((Name) node.Attributes[0].Value);
1066               else if (name == Nlist)
1067                 {
1068                   List<Term> list = new List<Term> ();
1069                   for (node = node.FirstChild; node != null;
1070                        node = node.NextSibling)
1071                     list.Add (new Term (node, domain));
1072                   objval = list;
1073                 }
1074               else
1075                 {
1076                   if (name == Nfuncall)
1077                     name = node.Attributes[0].Value;
1078
1079                   Function func = domain.GetFunc (name);
1080                   XmlNodeList nlist = node.ChildNodes;
1081                   int nargs = nlist.Count;
1082
1083                   if (nargs < func.min_arg
1084                       || (func.max_arg >= 0 && nargs > func.max_arg))
1085                     throw new Exception ("Invalid number of arguments to: "
1086                                          + name + " " + nargs);
1087                   Term[] args = new Term[nargs];
1088                   for (int i = 0; i < nlist.Count; i++)
1089                     args[i] = new Term (nlist[i], domain);
1090                   objval = new Funcall (func, args);
1091                 }
1092             }
1093         }
1094
1095       private class Funcall
1096       {
1097         internal Function func;
1098         internal Term[] args;
1099
1100         public Funcall (Function func, Term[] args)
1101         {
1102           this.func = func;
1103           this.args = args;
1104         }
1105
1106         public Term Eval (Domain domain)
1107         {
1108           domain.DebugWrite (true, "(({0}", func.name);
1109           for (int i = 0; i < args.Length; i++)
1110             domain.DebugWrite (false, " {0}", args[i].ToString ());
1111           domain.DebugWrite (false, ")");
1112           domain.depth++;
1113           Term result = func.Call (domain, args);
1114           domain.depth--;
1115           domain.DebugWrite (true, " ==> {0})", result.ToString ());
1116           return result;
1117         }
1118
1119         public override string ToString ()
1120         {
1121           string str = "<funcall fname=\"" + func.name;
1122           if (args == null)
1123             return str + "\"/>";
1124           str += "\">";
1125           foreach (Term e in args)
1126             str += e;
1127           return (str + "</funcall>");
1128         }
1129       }
1130
1131       public int Intval {
1132         get {
1133           if (objval != null)
1134             throw new Exception ("term is not integer: " + this);
1135           return intval;
1136         }
1137       }
1138
1139       public bool IsTrue {
1140         get {
1141           return (objval == null
1142                   ? (intval != 0)
1143                   : objval is List<Term>
1144                   ? (((List<Term>) objval).Count != 0)
1145                   : true);
1146         }
1147       }
1148       public bool IsInt { get { return (objval == null); } }
1149       public bool IsStr { get { return (objval is string); } }
1150       public bool IsList { get { return (objval is List<Term>); } }
1151
1152       public Term Eval (Domain domain)
1153       {
1154         if (objval == null || objval is Name || objval is string)
1155           return this;
1156         if (objval is List<Term>)
1157           return new Term ((List<Term>) objval);
1158         if (objval is Funcall)
1159           return ((Funcall) objval).Eval (domain);
1160         if (objval is Variable)
1161           return ((Variable) objval).val;
1162         if (objval is Term)
1163           return (Term) objval;
1164         throw new Exception ("invalid Term object: " + objval);
1165       }
1166
1167       public static explicit operator int (Term term)
1168       {
1169         if (term.objval != null)
1170           throw new Exception ("Not an integer term: " + term);
1171         return term.intval;
1172       }
1173
1174       public static explicit operator Name (Term term)
1175       {
1176         return (Name) term.objval;
1177       }
1178
1179       public static implicit operator Term (int i)
1180       {
1181         return new Term (i);
1182       }
1183
1184       public override string ToString ()
1185       {
1186         string str;
1187
1188         if (objval == null)
1189           str = "<integer>" + intval + "</integer>";
1190         else if (objval is Name)
1191           str = "<symbol>" + objval + "</symbol>";
1192         else if (objval is string)
1193           str = "<string>" + objval + "</string>";
1194         else if (objval is List<Term>)
1195           {
1196             str = "<list>";
1197             foreach (Term e in (List<Term>) objval)
1198               str += e;
1199             str += "</list>";
1200           }
1201         else if (objval is Funcall)
1202           str = "<funcall fname=\"" + ((Funcall) objval).func.name + "\"/>";
1203         else if (objval is Variable)
1204           str = "<variable vname=\"" + ((Variable) objval).name + "\"/>";
1205         else if (objval is Term)
1206           str = "<quote>" + objval + "</quote>";
1207         else
1208           throw new Exception ("invalid Term object: " + objval);
1209         return str;
1210       }
1211     }
1212
1213     static Term Zero = new Term (0);
1214     static Term One = new Term (1);
1215
1216     internal static int parse_integer (string str)
1217     {
1218       int len = str.Length;
1219       bool negative = false;
1220
1221       if (len <= 1)
1222         return (len == 0 ? 0 : str[0] - '0');
1223
1224       int c = str[0];
1225       int i;
1226
1227       if (c == '0' && str[1] == 'x')
1228         {
1229           i = 0;
1230           for (int idx = 2; idx < len; idx++)
1231             {
1232               c = str[idx];
1233               if (c < '0')
1234                 break;
1235               else if (c <= '9')
1236                 i = i * 16 + (c - '0');
1237               else if (c < 'A')
1238                 break;
1239               else if (c <= 'F')
1240                 i = i * 16 + (c - 'A');
1241               else if (c < 'a')
1242                 break;
1243               else if (c <= 'f')
1244                 i = i * 16 + (c - 'a');
1245               else
1246                 break;
1247             }
1248           return i;
1249         }
1250       if (c == '-')
1251         negative = true;
1252       i = c - '0';
1253       for (int idx = 1; idx < len; idx++)
1254         {
1255           c = str[idx];
1256           if (c < '0' || c > '9')
1257             break;
1258           i = i * 10 + (c - '0');
1259         }
1260       return negative ? - i : i;
1261     }
1262
1263     private Term[] terms;
1264
1265     public Xexpression (string url, Domain domain)
1266     {
1267       XmlDocument doc = new XmlDocument (Name.Table);
1268       XmlNode node;
1269
1270       using (XmlTextReader reader = new XmlTextReader (url, Name.Table))
1271         {
1272           do {
1273             reader.Read ();
1274           } while (reader.NodeType != XmlNodeType.None
1275                    && (reader.NodeType != XmlNodeType.Element
1276                        || reader.Name != Nexpr));
1277           if (reader.NodeType == XmlNodeType.None)
1278             throw new Exception ("Node <expr> not found");
1279           node = doc.ReadNode (reader);
1280         }
1281
1282       int nterms = 0;
1283       for (XmlNode n = node.FirstChild; n != null; n = n.NextSibling)
1284         if (n.NodeType == XmlNodeType.Element)
1285           {
1286             if (n.Name == Ndefun)
1287               domain.RegisterFunction (n);
1288             else if (n.Name == Ndefvar)
1289               domain.Defvar (n);
1290             else
1291               nterms++;
1292           }
1293
1294       terms = new Term[nterms];
1295       int i = 0;
1296       for (XmlNode n = node.FirstChild; n != null; n = n.NextSibling)
1297         if (n.NodeType == XmlNodeType.Element)
1298           {
1299             if (n.Name == Ndefun)
1300               domain.Defun (n);
1301             else if (n.Name != Ndefvar)
1302               terms[i++]= new Term (n, domain);
1303           }
1304     }
1305
1306     public Term Eval (Domain domain)
1307     {
1308       Term result = Zero;
1309
1310       domain.depth = 0;
1311       foreach (Term term in terms)
1312         result = term.Eval (domain);
1313       return result;
1314     }
1315
1316     public override string ToString ()
1317     {
1318       string str = "";
1319       for (int i = 0; i < terms.Length; i++)
1320         str += terms[i];
1321       return str;
1322     }
1323   }
1324 }