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