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