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