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 Symbol : IEquatable<Symbol>
  14     {
  15       private static NameTable nt = new NameTable ();
  16
  17       internal string name;
  18
  19       public Symbol (string str)
  20         {
  21           name = nt.Add (str);
  22         }
  23
  24       public static implicit operator Symbol (string str)
  25       {
  26         return new Symbol (str);
  27       }
  28
  29       public static implicit operator string (Symbol name)
  30       {
  31         return name.name;
  32       }
  33
  34       public static bool operator== (Symbol n1, Symbol n2)
  35         {
  36           return (object) n1.name == (object) n2.name;
  37         }
  38
  39       public static bool operator!= (Symbol n1, Symbol n2)
  40         {
  41           return (object) n1.name != (object) n2.name;
  42         }
  43
  44       public static bool operator== (Symbol n1, string n2)
  45         {
  46           return (object) n1.name == (object) n2;
  47         }
  48
  49       public static bool operator!= (Symbol n1, string n2)
  50         {
  51           return (object) n1.name != (object) n2;
  52         }
  53
  54       public static bool operator== (string n1, Symbol n2)
  55         {
  56           return (object) n1 == (object) n2.name;
  57         }
  58
  59       public static bool operator!= (string n1, Symbol n2)
  60         {
  61           return (object) n1 != (object) n2.name;
  62         }
  63
  64       public bool Equals (Symbol 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 Symbol Nexpr = "expr";
  85
  86     private static Symbol Nnull = "";
  87     private static Symbol Nfuncall = "funcall";
  88     private static Symbol Nvarref = "varref";
  89     private static Symbol Ninteger = "integer";
  90     private static Symbol Nstring = "string";
  91     private static Symbol Nsymbol = "symbol";
  92     private static Symbol Nlist = "list";
  93
  94     private static Symbol Ndefun = "defun";
  95     private static Symbol Nfname = "fname";
  96     private static Symbol Nargs = "args";
  97     private static Symbol Nargs_unevalled = "args-unevalled";
  98     private static Symbol Nfixed = "fixed";
  99     private static Symbol Noptional = "optional";
 100     private static Symbol Nrest = "rest";
 101
 102     private static Symbol Ndefvar = "defvar";
 103     private static Symbol Nvname = "vname";
 104     private static Symbol Ndescription = "description";
 105     private static Symbol Nrange = "range";
 106
 107     public abstract class Function
 108     {
 109       public Symbol name;
 110       public int min_arg, max_arg;
 111
 112       public Function () { }
 113
 114       public Function (Symbol 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, Variable vari, 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         public bool setvar;
 132
 133         public Subroutine (Builtin builtin, Symbol name, bool setvar,
 134                            int min_arg, int max_arg)
 135           : base (name, min_arg, max_arg)
 136           {
 137             this.builtin = builtin;
 138           }
 139
 140         public override Term Call (Domain domain, Variable vari, Term[] args)
 141         {
 142           args = (Term[]) args.Clone ();
 143           for (int i = 0; i < args.Length; i++)
 144             {
 145               args[i] = args[i].Eval (domain);
 146               if (domain.Thrown)
 147                 return args[i];
 148             }
 149           return builtin (domain, vari, args);
 150         }
 151       }
 152
 153       internal class SpecialForm : Function
 154       {
 155         public Builtin builtin;
 156
 157         public SpecialForm (Builtin builtin, Symbol name,
 158                             int min_arg, int max_arg)
 159           : base (name, min_arg, max_arg)
 160           {
 161             this.builtin = builtin;
 162           }
 163
 164         public override Term Call (Domain domain, Variable vari, Term[] args)
 165         {
 166           return builtin (domain, vari, args);
 167         }
 168       }
 169
 170       internal class Lambda : Function
 171       {
 172         internal bool args_evalled;
 173         internal Variable[] args;
 174         internal Term[] body;
 175
 176         public Lambda (Domain domain, XmlNode node)
 177           {
 178             int nfixed = 0;
 179             int noptional = 0;
 180             int nrest = 0;
 181             name = node.Attributes[Nfname].Value;
 182
 183             node = node.FirstChild;
 184             if (node != null
 185                 && (node.Name == Nargs || node.Name == Nargs_unevalled))
 186               {
 187                 XmlNode n;
 188                 args_evalled = node.Name == Nargs;
 189                 for (n = node.FirstChild; n != null; n = n.NextSibling)
 190                   {
 191                     if (n.Name == Nfixed)
 192                       nfixed++;
 193                     else if (n.Name == Noptional)
 194                       noptional++;
 195                     else if (n.Name == Nrest)
 196                       nrest++;
 197                     else
 198                       throw new Exception ("Invalid argument type: " + n);
 199                   }
 200                 min_arg = nfixed;
 201                 max_arg = nfixed + noptional + nrest;
 202                 args = new Variable[max_arg];
 203                 n = node.FirstChild;
 204                 for (int i = 0; i < max_arg; n = n.NextSibling)
 205                   args[i++] = domain.Defvar ((Symbol) n.Attributes[0].Value);
 206                 if (nrest == 1)
 207                   max_arg = - max_arg;
 208               }
 209             else
 210               {
 211                 min_arg = max_arg = 0;
 212               }
 213           }
 214
 215         public Lambda (Domain domain, Symbol name, bool args_evalled, Symbol[] args)
 216           {
 217             int nfixed = 0;
 218             int noptional = 0;
 219             int nrest = 0;
 220
 221             this.name = name;
 222             this.args_evalled = args_evalled;
 223             if (args != null)
 224               {
 225                 int i = 0;
 226                 for (i = 0; i < args.Length; i++, nfixed++)
 227                   if (args[i] == Noptional || args[i] == Nrest)
 228                     break;
 229                 if (i < args.Length)
 230                   {
 231                     if (args[i] == Noptional)
 232                       {
 233                         for (i++; i < args.Length; i++, noptional++)
 234                           if (args[i] == Nrest)
 235                             break;
 236                         if (i < args.Length)
 237                           nrest = 1;
 238                       }
 239                   }
 240                 min_arg = nfixed;
 241                 max_arg = nfixed + noptional + nrest;
 242                 this.args = new Variable[max_arg];
 243                 int j;
 244                 for (i = j = 0; j < this.args.Length; i++)
 245                   if (args[i] != Noptional || args[i] != Nrest)
 246                     this.args[j++] = domain.Defvar (args[i]);
 247               }
 248             else
 249               {
 250                 min_arg = max_arg = 0;
 251               }
 252           }
 253
 254         public void SetBody (Domain domain, XmlNode node)
 255         {
 256           for (node = node.FirstChild; node != null; node = node.NextSibling)
 257             if (node.Name != Ndescription
 258                 && node.Name != Nargs
 259                 && node.Name != Nargs_unevalled)
 260               break;
 261           int nterms = 0;
 262           for (XmlNode n = node; n != null; n = n.NextSibling)
 263             nterms++;
 264           if (nterms > 0)
 265             {
 266               body = new Term[nterms];
 267               for (nterms = 0; node != null; node = node.NextSibling, nterms++)
 268                 body[nterms] = new Term (domain, node);
 269             }
 270         }
 271
 272         public void SetBody (Term[] body)
 273         {
 274           this.body = body;
 275         }
 276
 277         public override Term Call (Domain domain, Variable vari, Term[] args)
 278         {
 279           Bindings current = domain.bindings;
 280           Term result = Zero;
 281
 282           try {
 283             int i;
 284             if (args_evalled)
 285               {
 286                 Term[] newargs = new Term[args.Length];
 287                 for (i = 0; i < min_arg; i++)
 288                   newargs[i] = args[i].Eval (domain);
 289                 args = newargs;
 290               }
 291             for (i = 0; i < min_arg; i++)
 292               domain.Bind (this.args[i], args[i]);
 293             if (body != null)
 294               {
 295                 try {
 296                   if (args_evalled)
 297                     domain.Catch (CatchTag.Return);
 298                   foreach (Term term in body)
 299                     {
 300                       result = term.Eval (domain);
 301                       if (domain.Thrown)
 302                         return result;
 303                     }
 304                 } finally {
 305                   if (args_evalled)
 306                     domain.Uncatch ();
 307                 }
 308               }
 309           } finally {
 310             domain.UnboundTo (current);
 311           }
 312           return result;
 313         }
 314       }
 315     }
 316
 317     public class Variable : TermValue
 318     {
 319       public readonly Symbol name;
 320       public string desc;
 321       internal Term default_val;
 322       internal Term val;
 323       object range;
 324
 325       public Variable (Symbol name, Term value)
 326       {
 327         this.name = name;
 328         val = value;
 329         default_val = Zero;
 330       }
 331
 332       public virtual bool ValueP (Term val) { return true; }
 333
 334       public override TermValue Clone ()
 335       {
 336         Variable v = new Variable (name, val);
 337         v.desc = desc;
 338         v.default_val = default_val;
 339         v.range = range;
 340         return v;
 341       }
 342
 343       public Term Value
 344       {
 345         get { return val; }
 346         set {
 347           if (! ValueP (value))
 348             throw new Exception ("Invalid value: " + value);
 349           val = value;
 350         }
 351       }
 352
 353       public Term DefaultValue
 354       {
 355         get { return default_val; }
 356         set {
 357           if (! ValueP (value))
 358             throw new Exception ("Invalid value: " + value);
 359           default_val = value;
 360         }
 361       }
 362
 363       public virtual object Range
 364       {
 365         get { return range; }
 366         set { range = value; }
 367       }
 368
 369       public override Term Eval (Domain domain) { return val; }
 370
 371       public override string ToString () { return name + "(" + val + ")"; }
 372
 373       public class Int : Variable
 374       {
 375         public int[] range;
 376
 377         private static bool SubsetP (int[] r1, int[] r2)
 378           {
 379             if (r2 == null)
 380               return true;
 381             for (int i = 0; i < r1.Length; i += 2)
 382               {
 383                 int j;
 384                 for (j = 0; j < r2.Length; j += 2)
 385                   if (r2[j] <= r1[i] && r2[j + 1] >= r1[i + 1])
 386                     break;
 387                 if (j >= r2.Length)
 388                   return false;
 389               }
 390             return true;
 391           }
 392
 393         private static bool SubsetP (int val, int[] r)
 394           {
 395             if (r == null)
 396               return true;
 397             for (int i = 0; i < r.Length; i += 2)
 398               if (r[i] <= val && r[i + 1] >= val)
 399                 return true;
 400             return false;
 401           }
 402
 403         public Int (Symbol name, string description, int value, int[] range)
 404           : base (name, new Term (value))
 405           {
 406             if (! SubsetP (value, range))
 407               throw new Exception ("Invalid value: " + value);
 408             desc = description;
 409             default_val = val;
 410             this.range = range;
 411           }
 412
 413         public override bool ValueP (Term term)
 414         {
 415           if (! term.IsInt)
 416             return false;
 417           return SubsetP (term.Intval, range);
 418         }
 419
 420         public override object Range {
 421           get { return range; }
 422           set {
 423             int[] r = (int[]) value;
 424             if (! SubsetP (r, range)
 425                 || ! SubsetP (val.Intval, r)
 426                 || ! SubsetP (default_val.Intval, r))
 427               throw new Exception ("Invalid range");
 428             range = r;
 429           }
 430         }
 431       }
 432
 433       public class Str : Variable
 434       {
 435         public string[] range;
 436
 437         private static bool SubsetP (string[] r1, string[] r2)
 438           {
 439             if (r2 == null)
 440               return true;
 441             foreach (string s in r1)
 442               if (! SubsetP (s, r2))
 443                 return false;
 444             return true;
 445           }
 446
 447         private static bool SubsetP (string str, string[] r)
 448           {
 449             if (r == null)
 450               return true;
 451             foreach (string s in r)
 452               if (str == s)
 453                 return true;
 454             return false;
 455         }
 456
 457         public Str (Symbol name, string description, string value, string[] range)
 458           : base (name, new Term (value))
 459           {
 460             if (! SubsetP (value, range))
 461               throw new Exception ("Invalid value: " + value);
 462             desc = description;
 463             default_val = val;
 464             this.range = range;
 465           }
 466
 467         public override bool ValueP (Term term)
 468         {
 469           if (! (term.objval is string))
 470             return false;
 471           return SubsetP (term.Strval, range);
 472         }
 473
 474         public override object Range {
 475           get { return range; }
 476           set {
 477             string[] r = (string[]) value;
 478             if (! SubsetP (r, range)
 479                 || ! SubsetP (val.Strval, r)
 480                 || ! SubsetP (default_val.Strval, r))
 481               throw new Exception ("Invalid range");
 482             range = r;
 483           }
 484         }
 485       }
 486
 487       public class Sym : Variable
 488       {
 489         public Symbol[] range;
 490
 491         private static bool SubsetP (Symbol[] r1, Symbol[] r2)
 492           {
 493             if (r2 == null)
 494               return true;
 495             foreach (Symbol n in r1)
 496               if (! SubsetP (n, r2))
 497                 return false;
 498             return true;
 499           }
 500
 501         private static bool SubsetP (Symbol name, Symbol[] r)
 502           {
 503             if (r == null)
 504               return true;
 505             foreach (Symbol n in r)
 506               if (name == n)
 507                 return true;
 508             return false;
 509         }
 510
 511         public Sym (Symbol name, string description, Symbol value, Symbol[] range)
 512           : base (name, new Term (value))
 513           {
 514             if (! SubsetP (value, range))
 515               throw new Exception ("Invalid value: " + value);
 516             desc = description;
 517             default_val = val;
 518             this.range = range;
 519           }
 520
 521         public override bool ValueP (Term term)
 522         {
 523           if (! (term.objval is Symbol))
 524             return false;
 525           return SubsetP (term.Symval, range);
 526         }
 527
 528         public override object Range {
 529           get { return range; }
 530           set {
 531             Symbol[] r = (Symbol[]) value;
 532             if (! SubsetP (r, range)
 533                 || ! SubsetP (val.Symval, r)
 534                 || ! SubsetP (default_val.Symval, r))
 535               throw new Exception ("Invalid range");
 536             range = r;
 537           }
 538         }
 539       }
 540     }
 541
 542     internal class Bindings
 543     {
 544       private Variable vari;
 545       private Term old_value;
 546       private Bindings next;
 547
 548       private Bindings (Variable vari)
 549       {
 550         this.vari = vari;
 551         old_value = vari.val;
 552       }
 553
 554       public static Bindings Bind (Bindings bindings, Variable vari, Term val)
 555       {
 556         Bindings b = new Bindings (vari);
 557
 558         b.vari.Value = val;
 559         b.next = bindings;
 560         return b;
 561       }
 562
 563       internal Bindings UnboundTo (Bindings boundary)
 564       {
 565         for (Bindings b = this; b != boundary; b = b.next)
 566           b.vari.val = b.old_value;
 567         return boundary;
 568       }
 569
 570       public override string ToString ()
 571       {
 572         string str = "(bindings";
 573         for (Bindings b = this; b != null; b = b.next)
 574           str += " " + vari.name + "=" + b.old_value;
 575         return str + ")";
 576       }
 577     }
 578
 579 #if false
 580     internal class ThrowException : Exception
 581     {
 582       Symbol tag;
 583       public object value;
 584
 585       public ThrowException (Symbol tag, object value) : base ()
 586         {
 587           this.tag = tag;
 588           this.value = value;
 589         }
 590     }
 591 #endif
 592
 593     internal class CatchTag : IEquatable<CatchTag>
 594     {
 595       private object val;
 596
 597       public CatchTag (Symbol name) { val = name.name; }
 598       private CatchTag (int i) { val = i; }
 599
 600       public static CatchTag Return = new CatchTag (0);
 601       public static CatchTag Break = new CatchTag (1);
 602
 603       public static bool operator== (CatchTag t1, CatchTag t2)
 604         { return t1.val == t2.val; }
 605
 606       public static bool operator!= (CatchTag t1, CatchTag t2)
 607         { return t1.val != t2.val; }
 608
 609       public bool Equals (CatchTag tag) { return this.val == tag.val; }
 610       public override bool Equals (object val) { return this.val == val; }
 611
 612       public override int GetHashCode () { return val.GetHashCode (); }
 613     }
 614
 615     public class Domain
 616     {
 617       public object context;
 618       public int depth = 0;
 619
 620       internal Dictionary<Symbol, TermType> termtypes
 621         = new Dictionary<Symbol, TermType> ();
 622       internal Dictionary<Symbol, Function> functions
 623         = new Dictionary<Symbol, Function> ();
 624       internal Dictionary<Symbol, Variable> variables
 625         = new Dictionary<Symbol, Variable> ();
 626       internal Bindings bindings;
 627       private Stack<CatchTag> catch_stack = new Stack<CatchTag> ();
 628       private int catch_count = 0;
 629
 630       internal Domain () { }
 631
 632       public Domain (object context) : this (basic, context) { }
 633
 634       public Domain (Domain parent, object context)
 635       {
 636         termtypes = new Dictionary<Symbol, TermType> (parent.termtypes);
 637         functions = new Dictionary<Symbol, Function> (parent.functions);
 638         variables = new Dictionary<Symbol, Variable> (parent.variables);
 639         this.context = context;
 640       }
 641
 642       internal void Bind (Variable vari, Term value)
 643       {
 644         bindings = Bindings.Bind (bindings, vari, value);
 645       }
 646
 647       internal void UnboundTo (Bindings boundary)
 648       {
 649         if (bindings != null)
 650           bindings = bindings.UnboundTo (boundary);
 651       }
 652
 653       internal void Catch (CatchTag tag)
 654       {
 655         catch_stack.Push (tag);
 656         catch_count++;
 657       }
 658
 659       internal void Uncatch ()
 660       {
 661         catch_stack.Pop ();
 662         if (catch_count > catch_stack.Count)
 663           catch_count--;
 664       }
 665
 666       public bool Thrown {
 667         get { return catch_count < catch_stack.Count; }
 668       }
 669
 670       internal void ThrowReturn ()
 671       {
 672         foreach (CatchTag tag in catch_stack)
 673           {
 674             catch_count--;
 675             if (tag == CatchTag.Return)
 676               break;
 677           }
 678       }
 679
 680       internal void ThrowBreak ()
 681       {
 682         if (catch_stack.Peek () != CatchTag.Break)
 683           throw new Exception ("No outer loop to break");
 684         catch_count--;
 685       }
 686
 687       internal void ThrowTag (CatchTag tag)
 688       {
 689         foreach (CatchTag elt in catch_stack)
 690           {
 691             catch_count--;
 692             if (elt == tag)
 693               break;
 694           }
 695       }
 696
 697       public void DefTerm (Symbol name, TermParser parser)
 698       {
 699         termtypes[name] = new TermType (name, parser);
 700       }
 701
 702       public void DefSubr (Builtin builtin, string str, bool setvar,
 703                            int min_arg, int max_arg, params string[] aliases)
 704       {
 705         Symbol name = str;
 706         Function func = new Function.Subroutine (builtin, name, setvar,
 707                                                  min_arg, max_arg);
 708         functions[name] = func;
 709         foreach (string a in aliases)
 710           functions[(Symbol) a] = func;
 711       }
 712
 713       public void DefSpecial (Builtin builtin, string str,
 714                               int min_arg, int max_arg,
 715                               params string[] aliases)
 716       {
 717         Symbol name = str;
 718         Function func = new Function.SpecialForm (builtin, name,
 719                                                   min_arg, max_arg);
 720         functions[name] = func;
 721         foreach (string a in aliases)
 722           functions[(Symbol) a] = func;
 723       }
 724
 725       public void DefAlias (string alias, string str)
 726       {
 727         functions[(Symbol) alias] = functions[(Symbol) str];
 728       }
 729
 730       public void Defun (Symbol name, bool args_evalled,
 731                          Symbol[] args, Term[] body, bool prototype)
 732       {
 733         Function func;
 734
 735         if (prototype || ! functions.TryGetValue (name, out func))
 736           {
 737             func = new Function.Lambda (this, name, args_evalled, args);
 738             functions[name] = func;
 739           }
 740         if (! prototype)
 741           ((Function.Lambda) func).SetBody (body);
 742       }
 743
 744       public void Defun (XmlNode node, bool prototype)
 745       {
 746         Symbol name = node.Attributes[Nfname].Value;
 747         Function func;
 748
 749         if (prototype || ! functions.TryGetValue (name, out func))
 750           {
 751             func = new Function.Lambda (this, node);
 752             functions[name] = func;
 753           }
 754         if (! prototype)
 755           ((Function.Lambda) func).SetBody (this, node);
 756       }
 757
 758       public void Defun (Function func)
 759       {
 760         functions[func.name] = func;
 761       }
 762
 763       public Variable Defvar (XmlNode node)
 764       {
 765         Symbol name = node.Attributes[0].Value;
 766         String desc;
 767         Variable vari;
 768
 769         node = node.FirstChild;
 770         if (node != null && node.Name == Ndescription)
 771           {
 772             desc = node.InnerText;
 773             node = node.NextSibling;
 774           }
 775         else
 776           desc = null;
 777         if (node != null)
 778           {
 779             Symbol type = node.Name;
 780             XmlNodeList range_list = null;
 781             int nranges = 0;
 782             string val = node.InnerText;
 783
 784             node = node.NextSibling;
 785             if (node != null)
 786               {
 787                 range_list = node.ChildNodes;
 788                 nranges = range_list.Count;
 789               }
 790
 791             if (type == Ninteger)
 792               {
 793                 int intval = parse_integer (val);
 794                 int[] range = null;
 795                 if (range_list != null)
 796                   {
 797                     range = new int[nranges * 2];
 798                     for (int i = 0; i < nranges; i++)
 799                       {
 800                         XmlNode n = range_list[i];
 801                         if (n.Name == Nrange)
 802                           {
 803                             range[i * 2]
 804                               = parse_integer (n.FirstChild.InnerText);
 805                             range[i * 2 + 1]
 806                               = parse_integer (n.LastChild.InnerText);
 807                           }
 808                         else
 809                           {
 810                             range[i * 2]
 811                               = range[i * 2 + 1]
 812                               = parse_integer (n.FirstChild.InnerText);
 813                           }
 814                       }
 815                   }
 816
 817                 if (variables.TryGetValue (name, out vari))
 818                   {
 819                     if (! (vari is Variable.Int))
 820                       throw new Exception ("Inalid value");
 821                     vari = (Variable) vari.Clone ();
 822                     Term v = new Term (intval);
 823                     vari.Value = v;
 824                     vari.DefaultValue = v;
 825                     if (range != null)
 826                       vari.Range = range;
 827                   }
 828                 else
 829                   vari = new Variable.Int (name, desc, intval, range);
 830               }
 831             else if (type == Nstring)
 832               {
 833                 string[] range = null;
 834                 if (range_list != null)
 835                   {
 836                     range = new string[nranges];
 837                     for (int i = 0; i < nranges; i++)
 838                       range[i] = range_list[i].FirstChild.InnerText;
 839                   }
 840
 841                 if (variables.TryGetValue (name, out vari))
 842                   {
 843                     if (! (vari is Variable.Str))
 844                       throw new Exception ("Invalid value");
 845                     vari = (Variable) vari.Clone ();
 846                     Term v = new Term (val);
 847                     vari.Value = v;
 848                     vari.DefaultValue = v;
 849                     if (range != null)
 850                       vari.Range = range;
 851                   }
 852                 else
 853                   vari = new Variable.Str (name, desc, val, range);
 854               }
 855             else if (type == Nsymbol)
 856               {
 857                 Symbol[] range = null;
 858                 if (range_list != null)
 859                   {
 860                     range = new Symbol[nranges];
 861                     for (int i = 0; i < nranges; i++)
 862                       range[i] = range_list[i].FirstChild.InnerText;
 863                   }
 864
 865                 if (variables.TryGetValue (name, out vari))
 866                   {
 867                     if (! (vari is Variable.Sym))
 868                       throw new Exception ("Invalid value");
 869                     vari = (Variable) vari.Clone ();
 870                     Term v = new Term (val);
 871                     vari.Value = v;
 872                     vari.DefaultValue = v;
 873                     if (range != null)
 874                       vari.Range = range;
 875                   }
 876                 else
 877                   vari = new Variable.Sym (name, desc, val, range);
 878               }
 879             else
 880               throw new Exception ("Unknown type: " + type);
 881           }
 882         else
 883           {
 884             if (variables.TryGetValue (name, out vari))
 885               vari = (Variable) vari.Clone ();
 886             else
 887               vari = new Variable (name, Zero);
 888           }
 889         variables[name] = vari;
 890         return vari;
 891       }
 892
 893       public Variable Defvar (Variable vari)
 894       {
 895         variables[vari.name] = vari;
 896         return vari;
 897       }
 898
 899       internal Variable Defvar (Symbol name)
 900       {
 901         Variable vari = new Variable (name, Zero);
 902         variables[name] = vari;
 903         return vari;
 904       }
 905
 906       internal Function GetFunc (Symbol name)
 907       {
 908         Function func;
 909
 910         if (! functions.TryGetValue (name, out func))
 911           throw new Exception ("Unknown function: " + name);
 912         return func;
 913       }
 914
 915       public bool CopyFunc (Domain domain, Symbol name)
 916       {
 917         Function func = GetFunc (name);
 918
 919         domain.functions[name] = func;
 920         return true;
 921       }
 922
 923       public void CopyFunc (Domain domain)
 924       {
 925         foreach (KeyValuePair<Symbol, Function> kv in functions)
 926           domain.functions[kv.Key] = kv.Value;
 927       }
 928
 929       public Variable GetVar (Symbol name, bool create)
 930       {
 931         Variable vari;
 932
 933         if (! variables.TryGetValue (name, out vari))
 934           {
 935             if (! create)
 936               return null;
 937             variables[name] = vari = new Variable (name, Zero);
 938           }
 939         return vari;
 940       }
 941
 942       public override string ToString ()
 943       {
 944         string str = "<(functions";
 945         foreach (KeyValuePair<Symbol, Function> kv in functions)
 946           str += " " + kv.Key;
 947         str += ") (variabls";
 948         foreach (KeyValuePair<Symbol, Variable> kv in variables)
 949           str += " " + kv.Key;
 950         str += ")";
 951         if (bindings != null)
 952           str += " " + bindings;
 953         if (context != null)
 954           str += " (" + context + ")";
 955         str += ">";
 956         return str;
 957       }
 958
 959       internal void DebugWrite (bool head, string fmt, params string[] arg)
 960       {
 961         if (debug_level > depth)
 962           {
 963             if (head)
 964               {
 965                 Console.WriteLine ();
 966                 for (int i = 0; i < depth; i++)
 967                   Console.Write (" ");
 968               }
 969             Console.Write (fmt, arg);
 970           }
 971       }
 972
 973       public object SaveValues ()
 974       {
 975         Dictionary<Variable,Term> values = new Dictionary<Variable,Term> ();
 976
 977         foreach (KeyValuePair<Symbol,Variable> kv in variables)
 978           values[kv.Value] = kv.Value.val.Clone ();
 979         return values;
 980       }
 981
 982       public void RestoreValues (object values)
 983       {
 984         foreach (KeyValuePair<Variable,Term> kv
 985                  in (Dictionary<Variable,Term>) values)
 986           kv.Key.val = kv.Value;
 987       }
 988     }
 989
 990     public delegate Term Builtin (Domain domain, Variable vari, Term[] args);
 991
 992     private static Domain basic = new Domain ();
 993
 994     static Xexpression ()
 995     {
 996       basic.DefTerm ("funcall", Funcall.parser);
 997
 998       basic.DefSubr (Fset, "set", true, 1, 1, "=");
 999       basic.DefSubr (Fnot, "not", false, 1, 1, "!");
1000       basic.DefSubr (Fadd, "add", true, 1, -1, "+");
1001       basic.DefSubr (Fmul, "mul", true, 1, -1, "*");
1002       basic.DefSubr (Fsub, "sub", true, 1, -1, "-");
1003       basic.DefSubr (Fdiv, "div", true, 1, -1, "/");
1004       basic.DefSubr (Fmod, "mod", true, 1, 2, "%");
1005       basic.DefSubr (Flogior, "logior", true, 1, -1, "|");
1006       basic.DefSubr (Flogand, "logand", true, 1, -1, "&");
1007       basic.DefSubr (Flsh, "lsh", true, 1, 2, "<<");
1008       basic.DefSubr (Frsh, "rsh", true, 1, 2, ">>");
1009       basic.DefSubr (Feq, "eq", false, 2, -1, "==");
1010       basic.DefSubr (Fnoteq, "noteq", false, 2, 2, "!=");
1011       basic.DefSubr (Flt, "lt", false, 2, -1, "<");
1012       basic.DefSubr (Fle, "le", false, 2, -1, "<=");
1013       basic.DefSubr (Fgt, "gt", false, 2, -1, ">");
1014       basic.DefSubr (Fge, "ge", false, 2, -1, ">=");
1015       basic.DefSubr (Fappend, "append", true, 0, -1);
1016       basic.DefSubr (Fconcat, "concat", true, 0, -1);
1017       basic.DefSubr (Fnth, "nth", false, 2, 2);
1018       basic.DefSubr (Fcopy, "copy", false, 1, 1);
1019       basic.DefSubr (Fins, "ins", true, 2, 2);
1020       basic.DefSubr (Fdel, "del", true, 2, 2);
1021       basic.DefSubr (Feval, "eval", false, 1, 1);
1022       basic.DefSubr (Fbreak, "break", false, 0, 1);
1023       basic.DefSubr (Freturn, "return", false, 0, 1);
1024
1025       basic.DefSpecial (Fand, "and", 1, -1, "&&");
1026       basic.DefSpecial (For, "or", 1, -1, "||");
1027       basic.DefSpecial (Fprogn, "progn", 0, -1, "expr");
1028       basic.DefSpecial (Fif, "if", 2, 3);
1029       basic.DefSpecial (Fwhen, "when", 1, -1);
1030       basic.DefSpecial (Floop, "loop", 1, -1);
1031       basic.DefSpecial (Fwhile, "while", 1, -1);
1032       basic.DefSpecial (Fcond, "cond", 1, -1);
1033       basic.DefSpecial (Fforeach, "foreach", 2, -1);
1034       basic.DefSpecial (Fquote, "quote", 1, 1);
1035       basic.DefSpecial (Ftype, "type", 1, 1);
1036       basic.DefSpecial (Fcatch, "catch", 2, 2);
1037       basic.DefSpecial (Fthrow, "throw", 1, 2);
1038     }
1039
1040     private static Term Fset (Domain domain, Variable vari, Term[] args)
1041     {
1042       vari.Value = args[0];
1043       return vari.val;
1044     }
1045
1046     private static Term Fnot (Domain domain, Variable vari, Term[] args)
1047     {
1048       return args[0].IsTrue ? Zero : One;
1049     }
1050
1051     private static Term Fadd (Domain domain, Variable vari, Term[] args)
1052     {
1053       int n = vari == null ? 0 : vari.val.Intval;
1054
1055       foreach (Term arg in args)
1056         n += arg.Intval;
1057       if (vari == null)
1058         return new Term (n);
1059       vari.val.intval = n;
1060       return vari.val;
1061     }
1062
1063     private static Term Fmul (Domain domain, Variable vari, Term[] args)
1064     {
1065       int n = vari == null ? 1 : vari.val.Intval;
1066       foreach (Term arg in args)
1067         n *= arg.Intval;
1068       if (vari == null)
1069         return new Term (n);
1070       vari.val.intval = n;
1071       return vari.val;
1072     }
1073
1074     private static Term Fsub (Domain domain, Variable vari, Term[] args)
1075     {
1076       int n, i;
1077
1078       if (vari == null)
1079         {
1080           n = args[0].Intval;
1081           i = 1;
1082         }
1083       else
1084         {
1085           n = vari.val.Intval;
1086           i = 0;
1087         }
1088       while (i < args.Length)
1089         n -= args[i++].Intval;
1090       if (vari == null)
1091         return new Term (n);
1092       vari.val.intval = n;
1093       return vari.val;
1094     }
1095
1096     private static Term Fdiv (Domain domain, Variable vari, Term[] args)
1097     {
1098       int n, i;
1099
1100       if (vari == null)
1101         {
1102           n = args[0].Intval;
1103           i = 1;
1104         }
1105       else
1106         {
1107           n = vari.val.Intval;
1108           i = 0;
1109         }
1110       while (i < args.Length)
1111         n /= args[i++].Intval;
1112       if (vari == null)
1113         return new Term (n);
1114       vari.val.intval = n;
1115       return vari.val;
1116     }
1117
1118     private static Term Fmod (Domain domain, Variable vari, Term[] args)
1119     {
1120       if (vari == null)
1121         return new Term (args[0].Intval % args[1].Intval);
1122       vari.val.intval = vari.val.Intval % args[0].Intval;
1123       return vari.val;
1124     }
1125
1126     private static Term Flogior (Domain domain, Variable vari, Term[] args)
1127     {
1128       int n = vari == null ? 0 : vari.val.Intval;
1129       foreach (Term arg in args)
1130         n |= arg.Intval;
1131       if (vari == null)
1132         return new Term (n);
1133       vari.val.intval = n;
1134       return vari.val;
1135     }
1136
1137     private static Term Flogand (Domain domain, Variable vari, Term[] args)
1138     {
1139       int n, i;
1140
1141       if (vari == null)
1142         {
1143           n = args[0].Intval;
1144           i = 1;
1145         }
1146       else
1147         {
1148           n = vari.val.Intval;
1149           i = 0;
1150         }
1151       while (i < args.Length)
1152         n &= args[i++].Intval;
1153       if (vari == null)
1154         return new Term (n);
1155       vari.val.intval = n;
1156       return vari.val;
1157     }
1158
1159     private static Term Flsh (Domain domain, Variable vari, Term[] args)
1160     {
1161       if (vari == null)
1162         return new Term (args[0].Intval << args[1].Intval);
1163       vari.val.intval = vari.val.Intval << args[0].Intval;
1164       return vari.val;
1165     }
1166
1167     private static Term Frsh (Domain domain, Variable vari, Term[] args)
1168     {
1169       if (vari == null)
1170         return new Term (args[0].Intval >> args[1].Intval);
1171       vari.val.intval = vari.val.Intval >> args[0].Intval;
1172       return vari.val;
1173     }
1174
1175     private static Term Feq (Domain domain, Variable vari, Term[] args)
1176     {
1177       Term o = args[0];
1178
1179       if (o.objval == null)
1180         {
1181           for (int i = 1; i < args.Length; i++)
1182             if (args[i].objval != null || args[i].intval != o.intval)
1183               return Zero;
1184         }
1185       else
1186         {
1187           for (int i = 1; i < args.Length; i++)
1188             if (o.objval.Equals (args[i].objval))
1189               return Zero;
1190         }
1191       return One;
1192     }
1193
1194     private static Term Fnoteq (Domain domain, Variable vari, Term[] args)
1195     {
1196       return Feq (domain, vari, args);
1197     }
1198
1199     private static Term Flt (Domain domain, Variable vari, Term[] args)
1200     {
1201       int n = args[0].Intval;
1202
1203       for (int i = 1; i < args.Length; i++)
1204         {
1205           int n1 = args[i].Intval;
1206           if (n >= n1)
1207             return Zero;
1208           n = n1;
1209         }
1210       return One;
1211     }
1212
1213     private static Term Fle (Domain domain, Variable vari, Term[] args)
1214     {
1215       int n = args[0].Intval;
1216       for (int i = 1; i < args.Length; i++)
1217         {
1218           int n1 = args[i].Intval;
1219           if (n > n1)
1220             return Zero;
1221           n = n1;
1222         }
1223       return One;
1224     }
1225
1226     private static Term Fgt (Domain domain, Variable vari, Term[] args)
1227     {
1228       int n = args[0].Intval;
1229       for (int i = 1; i < args.Length; i++)
1230         {
1231           int n1 = args[i].Intval;
1232           if (n <= n1)
1233             return Zero;
1234           n = n1;
1235         }
1236       return One;
1237     }
1238
1239     private static Term Fge (Domain domain, Variable vari, Term[] args)
1240     {
1241       int n = args[0].Intval;
1242       for (int i = 1; i < args.Length; i++)
1243         {
1244           int n1 = args[i].Intval;
1245           if (n < n1)
1246             return Zero;
1247           n = n1;
1248         }
1249       return One;
1250     }
1251
1252     private static Term Fappend (Domain domain, Variable vari, Term[] args)
1253     {
1254       List<Term> list;
1255
1256       if (vari == null)
1257         list = new List<Term> ();
1258       else
1259         list = vari.val.Listval;
1260
1261       foreach (Term arg in args)
1262         {
1263           if (arg.IsList)
1264             list.AddRange ((List<Term>) arg.objval);
1265           else
1266             list.Add (arg);
1267         }
1268       if (vari == null)
1269         {
1270           Term result;
1271           result.intval = 0;
1272           result.objval = list;
1273           return result;
1274         }
1275       return vari.val;
1276     }
1277
1278     private static Term Fconcat (Domain domain, Variable vari, Term[] args)
1279     {
1280       string str;
1281
1282       if (vari == null)
1283         str = "";
1284       else
1285         str = vari.val.Strval;
1286
1287       foreach (Term arg in args)
1288         {
1289           if (arg.IsStr)
1290             str += (string) arg.objval;
1291           else if (arg.IsList)
1292             foreach (Term term in (List<Term>) arg.objval)
1293               str += (char) term.Intval;
1294           else
1295             str += (char) arg.Intval;
1296         }
1297       if (vari == null)
1298         {
1299           Term result;
1300           result.intval = 0;
1301           result.objval = str;
1302           return result;
1303         }
1304       vari.val.objval = str;
1305       return vari.val;
1306     }
1307
1308     private static Term Fnth (Domain domain, Variable vari, Term[] args)
1309     {
1310       Term result;
1311
1312       if (args[1].IsStr)
1313         {
1314           result.intval = ((string) args[1].objval)[args[0].Intval];
1315           result.objval = null;
1316         }
1317       else if (args[1].IsList)
1318         {
1319           result = ((List<Term>) args[1].objval)[args[0].Intval];
1320         }
1321       else
1322         throw new Exception ("Term is not enumelable: " + args[1]);
1323       return result;
1324     }
1325
1326     private static Term Fcopy (Domain domain, Variable vari, Term[] args)
1327     {
1328       Term result;
1329
1330       result.intval = 0;
1331       result.objval = new List<Term> (args[0].Listval);
1332       return result;
1333     }
1334
1335     private static Term Fins (Domain domain, Variable vari, Term[] args)
1336     {
1337       if (vari.val.IsStr)
1338         vari.val.objval
1339           = vari.val.Strval.Insert (args[0].Intval, args[1].Strval);
1340       else if (vari.val.IsList)
1341         vari.val.Listval.InsertRange (args[0].Intval, args[1].Listval);
1342       else
1343         throw new Exception ("term is not collection: " + vari.val);
1344       return vari.val;
1345     }
1346
1347     private static Term Fdel (Domain domain, Variable vari, Term[] args)
1348     {
1349       if (vari.val.IsStr)
1350         vari.val.objval
1351           = vari.val.Strval.Remove (args[0].Intval,
1352                                     args[1].Intval - args[0].Intval);
1353
1354       else if (vari.val.IsList)
1355         vari.val.Listval.RemoveRange (args[0].Intval,
1356                                       args[1].Intval - args[0].Intval);
1357       else
1358         throw new Exception ("term is not collection: " + vari.val);
1359       return vari.val;
1360     }
1361
1362     private static Term Fand (Domain domain, Variable vari, Term[] args)
1363     {
1364       foreach (Term arg in args)
1365         if (! arg.Eval (domain).IsTrue)
1366           return Zero;
1367       return One;
1368     }
1369
1370     private static Term For (Domain domain, Variable vari, Term[] args)
1371     {
1372       foreach (Term arg in args)
1373         if (arg.Eval (domain).IsTrue)
1374           return One;
1375       return Zero;
1376     }
1377
1378     private static Term Feval (Domain domain, Variable vari, Term[] args)
1379     {
1380       return (args[0].Eval (domain));
1381     }
1382
1383     private static Term Fprogn (Domain domain, Variable vari, Term[] args)
1384     {
1385       Term result = One;
1386
1387       foreach (Term arg in args)
1388         result = arg.Eval (domain);
1389       return result;
1390     }
1391
1392     private static Term Fif (Domain domain, Variable vari, Term[] args)
1393     {
1394       if (args[0].Eval (domain).IsTrue)
1395         return args[1].Eval (domain);
1396       if (args.Length == 2)
1397         return Zero;
1398       return args[2].Eval (domain);
1399     }
1400
1401     private static Term Fwhen (Domain domain, Variable vari, Term[] args)
1402     {
1403       if (! args[0].Eval (domain).IsTrue)
1404         return Zero;
1405       Term result = One;
1406       for (int i = 1; i < args.Length; i++)
1407         result = args[i].Eval (domain);
1408       return result;
1409     }
1410
1411     private static Term Freturn (Domain domain, Variable vari, Term[] args)
1412     {
1413       domain.ThrowReturn ();
1414       return args.Length == 0 ? Zero : args[0];
1415     }
1416
1417     private static Term Fbreak (Domain domain, Variable vari, Term[] args)
1418     {
1419       domain.ThrowBreak ();
1420       return args.Length == 0 ? Zero : args[0];
1421     }
1422
1423     private static Term Floop (Domain domain, Variable vari, Term[] args)
1424     {
1425       Term result = Zero;
1426       try {
1427         domain.Catch (CatchTag.Break);
1428         while (! domain.Thrown)
1429           foreach (Term arg in args)
1430             {
1431               result = arg.Eval (domain);
1432               if (domain.Thrown)
1433                 return result;
1434             }
1435       } finally {
1436         domain.Uncatch ();
1437       }
1438       return result;
1439     }
1440
1441     private static Term Fwhile (Domain domain, Variable vari, Term[] args)
1442     {
1443       Term result = Zero;
1444       try {
1445         domain.Catch (CatchTag.Break);
1446         while (! domain.Thrown && args[0].Eval (domain).IsTrue)
1447           for (int i = 1; i < args.Length; i++)
1448             {
1449               result = args[i].Eval (domain);
1450               if (domain.Thrown)
1451                 return result;
1452             }
1453       } finally {
1454         domain.Uncatch ();
1455       }
1456       return result;
1457     }
1458
1459     private static Term Fcond (Domain domain, Variable vari, Term[] args)
1460     {
1461       foreach (Term arg in args)
1462         {
1463           List<Term> list = arg.Listval;
1464           Term result = list[0].Eval (domain);
1465
1466           if (result.IsTrue)
1467             {
1468               for (int i = 1; i < list.Count; i++)
1469                 result = list[i].Eval (domain);
1470               return result;
1471             }
1472         }
1473       return Zero;
1474     }
1475
1476     private static Term Fforeach (Domain domain, Variable vari,
1477                                         Term[] args)
1478     {
1479       Term result = args[0].Eval (domain);
1480       if (domain.Thrown)
1481         return result;
1482       List<Term> list = result.Listval;
1483       Bindings current = domain.bindings;
1484
1485       try {
1486         domain.Catch (CatchTag.Break);
1487         foreach (Term term in list)
1488           {
1489             domain.Bind (vari, term);
1490             try {
1491               for (int i = 1; i < args.Length; i++)
1492                 {
1493                   result = args[i].Eval (domain);
1494                   if (domain.Thrown)
1495                     return result;
1496                 }
1497             } finally {
1498               domain.UnboundTo (current);
1499             }
1500           }
1501       } finally {
1502         domain.Uncatch ();
1503       }
1504       return result;
1505     }
1506
1507     private static Term Fquote (Domain domain, Variable vari, Term[] args)
1508     {
1509       return new Term (args[0]);
1510     }
1511
1512     private static Term Ftype (Domain domain, Variable vari, Term[] args)
1513     {
1514       if (args[0].IsInt)
1515         return TermInt;
1516       if (args[0].IsStr)
1517         return TermStr;
1518       if (args[0].IsSymbol)
1519         return TermSymbol;
1520       if (args[0].IsList)
1521         return TermList;
1522       return TermTerm;
1523     }
1524
1525     public static Term Fcatch (Domain domain, Variable vari, Term[] args)
1526     {
1527       Term result = Zero;
1528       try {
1529         domain.Catch (new CatchTag (args[0].Symval));
1530         result = args[1].Eval (domain);
1531       } finally {
1532         domain.Uncatch ();
1533       }
1534       return result;
1535     }
1536
1537     public static Term Fthrow (Domain domain, Variable vari, Term[] args)
1538     {
1539       domain.ThrowTag (new CatchTag (args[0].Symval));
1540       return (args.Length == 1 ? Zero : args[1]);
1541     }
1542
1543     public delegate TermValue TermParser (Domain domain, XmlNode node);
1544
1545     public class TermType
1546     {
1547       public readonly Symbol type;
1548       internal readonly TermParser parser;
1549
1550       public TermType (Symbol type, TermParser parser)
1551       {
1552         this.type = type;
1553         this.parser = parser;
1554       }
1555     }
1556
1557     public abstract class TermValue
1558     {
1559       public virtual Term Eval (Domain domain) { return new Term (this); }
1560       public abstract TermValue Clone ();
1561     }
1562
1563     private class Funcall : TermValue
1564     {
1565       internal Function func;
1566       internal Variable vari;
1567       internal Term[] args;
1568
1569       private Funcall (Function func, Variable vari, Term[] args)
1570         {
1571           this.func = func;
1572           this.vari = vari;
1573           this.args = args;
1574         }
1575
1576       public Funcall (Domain domain, Symbol fname, Term[] args)
1577         {
1578           func = domain.GetFunc (fname);
1579           this.args = args;
1580         }
1581
1582       public Funcall (Domain domain, Symbol fname, Symbol vname, Term[] args)
1583         {
1584           func = domain.GetFunc (fname);
1585           int nargs = args.Length;
1586           if (nargs < func.min_arg
1587               || (func.max_arg >= 0 && nargs > func.max_arg))
1588             throw new Exception ("Invalid number of arguments to: "
1589                                  + fname + " " + nargs);
1590           this.args = args;
1591           if (vname != Nnull)
1592             vari = domain.GetVar (vname, true);
1593         }
1594
1595       internal static TermValue parser (Domain domain, XmlNode node)
1596         {
1597           Symbol fname = node.Name;
1598           Symbol vname = Nnull;
1599           XmlAttribute attr;
1600
1601           if (fname == Nfuncall)
1602             fname = node.Attributes[Nfname].Value;
1603           attr = node.Attributes[Nvname];
1604           if (attr != null)
1605             vname = attr.Value;
1606
1607           XmlNodeList nlist = node.ChildNodes;
1608           int nargs = nlist.Count;
1609           Term[] args = new Term[nargs];
1610           for (int i = 0; i < nargs; i++)
1611             args[i] = new Term (domain, nlist[i]);
1612           return new Funcall (domain, fname, vname, args);
1613         }
1614
1615       public override Term Eval (Domain domain)
1616       {
1617         domain.DebugWrite (true, "(({0}", func.name);
1618         for (int i = 0; i < args.Length; i++)
1619           domain.DebugWrite (false, " {0}", args[i].ToString ());
1620         domain.DebugWrite (false, ")");
1621         domain.depth++;
1622         Term result = func.Call (domain, vari, args);
1623         domain.depth--;
1624         domain.DebugWrite (true, " ==> {0})", result.ToString ());
1625         return result;
1626       }
1627
1628       public override TermValue Clone ()
1629       {
1630         return new Funcall (func, vari, args);
1631       }
1632
1633       public override string ToString ()
1634       {
1635         string str = "<funcall fname=\"" + func.name;
1636         if (args == null)
1637           return str + "\"/>";
1638         str += "\">";
1639         foreach (Term e in args)
1640           str += e;
1641         return (str + "</funcall>");
1642       }
1643     }
1644
1645     public struct Term
1646     {
1647       public int intval;
1648       public object objval;
1649
1650       public Term (int i) { intval = i; objval = null; }
1651       public Term (Symbol name) { intval = 0; objval = name; }
1652       public Term (string str) { intval = 0; objval = str; }
1653       public Term (List<Term> list) { intval = 0; objval = list; }
1654       public Term (Term term) { intval = term.intval; objval = term.objval; }
1655       public Term (TermValue obj) { intval = 0; objval = obj; }
1656
1657       public Term (Domain domain, XmlNode node)
1658         {
1659           Symbol name = node.Name;
1660
1661           if (name == Ninteger)
1662             {
1663               intval = parse_integer (node.InnerText);
1664               objval = null;
1665             }
1666           else
1667             {
1668               intval = 0;
1669               if (name == Nsymbol)
1670                 objval = (Symbol) node.InnerText;
1671               else if (name == Nstring)
1672                 objval = node.InnerText.Clone ();
1673               else if (name == Nvarref)
1674                 objval = domain.GetVar ((Symbol) node.Attributes[0].Value, true);
1675               else if (name == Nlist)
1676                 {
1677                   List<Term> list = new List<Term> ();
1678                   for (node = node.FirstChild; node != null;
1679                        node = node.NextSibling)
1680                     list.Add (new Term (domain, node));
1681                   objval = list;
1682                 }
1683               else
1684                 {
1685                   TermType term_type;
1686
1687                   if (domain.termtypes.TryGetValue (name, out term_type))
1688                     objval = term_type.parser (domain, node);
1689                   else
1690                     objval = Funcall.parser (domain, node);
1691                 }
1692             }
1693         }
1694
1695       public Term (Domain domain, Symbol fname, Term[] args)
1696         {
1697           intval = 0;
1698           objval = new Funcall (domain, fname, args);
1699         }
1700
1701       public Term (Domain domain, Symbol fname, Symbol vname, Term[] args)
1702         {
1703           intval = 0;
1704           objval = new Funcall (domain, fname, vname, args);
1705         }
1706
1707       public object Objval {
1708         get {
1709           if (objval == null)
1710             throw new Exception ("term is an integer: " + this);
1711           return objval;
1712         }
1713       }
1714
1715       public int Intval {
1716         get {
1717           if (objval != null)
1718             throw new Exception ("term is not integer: " + this);
1719           return intval;
1720         }
1721       }
1722
1723       public string Strval {
1724         get {
1725           if (! IsStr)
1726             throw new Exception ("term is not string: " + this);
1727           return (string) objval;
1728         }
1729       }
1730
1731       public string Symval {
1732         get {
1733           if (! IsSymbol)
1734             throw new Exception ("term is not symbol: " + this);
1735           return (Symbol) objval;
1736         }
1737       }
1738
1739       public List<Term> Listval {
1740         get {
1741           if (! IsList)
1742             throw new Exception ("term is not list: " + this);
1743           return (List<Term>) objval;
1744         }
1745       }
1746
1747       public bool IsTrue {
1748         get {
1749           return (objval == null
1750                   ? (intval != 0)
1751                   : objval is List<Term>
1752                   ? (((List<Term>) objval).Count != 0)
1753                   : true);
1754         }
1755       }
1756       public bool IsInt { get { return (objval == null); } }
1757       public bool IsStr { get { return (objval is string); } }
1758       public bool IsSymbol { get { return (objval is Symbol); } }
1759       public bool IsList { get { return (objval is List<Term>); } }
1760
1761       public bool IsType (Type type)
1762       {
1763         return (objval == null ? type == typeof (int)
1764                 : type == objval.GetType ());
1765       }
1766
1767       public Term Eval (Domain domain)
1768       {
1769         if (objval == null || objval is Symbol || objval is string)
1770           return this;
1771         if (objval is List<Term>)
1772           return new Term ((List<Term>) objval);
1773         return ((TermValue) objval).Eval (domain);
1774       }
1775
1776       public Term Clone ()
1777       {
1778         if (objval == null || objval is Symbol || objval is string)
1779           return this;
1780         if (objval is List<Term>)
1781           {
1782             List<Term> list = new List<Term> ();
1783             list.InsertRange (0, ((List<Term>) objval));
1784             return new Term (list);
1785           }
1786         return new Term (((TermValue) objval).Clone ());
1787       }
1788
1789       public override string ToString ()
1790       {
1791         string str;
1792
1793         if (objval == null)
1794           str = "<integer>" + intval + "</integer>";
1795         else if (objval is Symbol)
1796           str = "<symbol>" + objval + "</symbol>";
1797         else if (objval is string)
1798           str = "<string>" + objval + "</string>";
1799         else if (objval is List<Term>)
1800           {
1801             str = "<list>";
1802             foreach (Term e in (List<Term>) objval)
1803               str += e;
1804             str += "</list>";
1805           }
1806         else if (objval is Funcall)
1807           str = "<funcall fname=\"" + ((Funcall) objval).func.name + "\"/>";
1808         else if (objval is Variable)
1809           str = "<variable vname=\"" + ((Variable) objval).name + "\"/>";
1810         else if (objval is Term)
1811           str = "<quote>" + objval + "</quote>";
1812         else
1813           throw new Exception ("invalid Term object: " + objval);
1814         return str;
1815       }
1816     }
1817
1818     static private Term Zero = new Term (0);
1819     static private Term One = new Term (1);
1820     static private Term TermInt = new Term (Ninteger);
1821     static private Term TermStr = new Term (Nstring);
1822     static private Term TermSymbol = new Term (Nsymbol);
1823     static private Term TermList = new Term (Nlist);
1824     static private Term TermTerm = new Term ((Symbol) "term");
1825
1826     internal static int parse_integer (string str)
1827     {
1828       int len = str.Length;
1829       bool negative = false;
1830
1831       if (len <= 1)
1832         return (len == 0 ? 0 : str[0] - '0');
1833
1834       int c = str[0];
1835       int i;
1836
1837       if (c == '?')
1838         return str[1];
1839       if ((c == '0' || c == '#') && str[1] == 'x')
1840         {
1841           i = 0;
1842           for (int idx = 2; idx < len; idx++)
1843             {
1844               c = str[idx];
1845               if (c < '0')
1846                 break;
1847               else if (c <= '9')
1848                 i = i * 16 + (c - '0');
1849               else if (c < 'A')
1850                 break;
1851               else if (c <= 'F')
1852                 i = i * 16 + (c - 'A');
1853               else if (c < 'a')
1854                 break;
1855               else if (c <= 'f')
1856                 i = i * 16 + (c - 'a');
1857               else
1858                 break;
1859             }
1860           return i;
1861         }
1862       if (c == '-')
1863         negative = true;
1864       i = c - '0';
1865       for (int idx = 1; idx < len; idx++)
1866         {
1867           c = str[idx];
1868           if (c < '0' || c > '9')
1869             break;
1870           i = i * 10 + (c - '0');
1871         }
1872       return negative ? - i : i;
1873     }
1874
1875     private Term[] terms;
1876
1877     private void parse_terms (Domain domain, XmlNode node)
1878     {
1879       int nterms = 0;
1880       for (XmlNode n = node; n != null; n = n.NextSibling)
1881         if (n.NodeType == XmlNodeType.Element)
1882           {
1883             if (n.Name == Ndefun)
1884               domain.Defun (n, true);
1885             else if (n.Name == Ndefvar)
1886               domain.Defvar (n);
1887             else
1888               nterms++;
1889           }
1890
1891       terms = new Term[nterms];
1892       int i = 0;
1893       for (XmlNode n = node; n != null; n = n.NextSibling)
1894         if (n.NodeType == XmlNodeType.Element)
1895           {
1896             if (n.Name == Ndefun)
1897               domain.Defun (n, false);
1898             else if (n.Name != Ndefvar)
1899               terms[i++]= new Term (domain, n);
1900           }
1901     }
1902
1903     public Xexpression (Domain domain, XmlNode node)
1904     {
1905       parse_terms (domain, node);
1906     }
1907
1908     public Xexpression (Domain domain, string url)
1909     {
1910       XmlDocument doc = new XmlDocument (Symbol.Table);
1911       XmlNode node;
1912
1913       using (XmlTextReader reader = new XmlTextReader (url, Symbol.Table))
1914         {
1915           do {
1916             reader.Read ();
1917           } while (reader.NodeType != XmlNodeType.None
1918                    && (reader.NodeType != XmlNodeType.Element
1919                        || reader.Name != Nexpr));
1920           if (reader.NodeType == XmlNodeType.None)
1921             throw new Exception ("Node <expr> not found");
1922           node = doc.ReadNode (reader);
1923         }
1924       parse_terms (domain, node.FirstChild);
1925     }
1926
1927     public Term Eval (Domain domain)
1928     {
1929       Term result = Zero;
1930
1931       domain.depth = 0;
1932       try {
1933         domain.Catch (CatchTag.Return);
1934         foreach (Term term in terms)
1935           {
1936             result = term.Eval (domain);
1937             if (domain.Thrown)
1938               return result;
1939           }
1940       } finally {
1941         domain.Uncatch ();
1942       }
1943       return result;
1944     }
1945
1946     public override string ToString ()
1947     {
1948       string str = "";
1949       for (int i = 0; i < terms.Length; i++)
1950         str += terms[i];
1951       return str;
1952     }
1953   }
1954 }