2 using System.Collections;
3 using System.Collections.Generic;
10 public class MExpression
12 public delegate object Evaluator (object[] args, MPlist bindings);
14 internal delegate void PrettyPrinter (Function func,
15 string indent, object[] args);
17 internal class Function
19 internal readonly MSymbol name;
20 internal readonly Evaluator eval;
21 internal readonly int min_arg;
22 internal readonly int max_arg;
23 internal readonly Type[] arg_types;
24 internal object[] data;
26 public PrettyPrinter pp;
28 private static PrettyPrinter default_pretty_printer;
29 private static PrettyPrinter set_pretty_printer;
30 internal static Function literal, varref, block, defun;
32 public Function (MSymbol name, Evaluator eval,
33 int min_arg, int max_arg, params Type[] arg_types)
37 this.min_arg = min_arg;
38 this.max_arg = max_arg;
39 this.arg_types = (Type []) arg_types.Clone ();
40 if (arg_types.Length == 2 && arg_types[0] == typeof (MSymbol))
41 pp = set_pretty_printer;
43 pp = default_pretty_printer;
48 default_pretty_printer = new PrettyPrinter (default_pp);
49 set_pretty_printer = new PrettyPrinter (set_pp);
50 literal = Defun ("nil", null, 1, 1);
51 varref = Defun ("symbol", new Evaluator (get_value), 1, 1);
52 block = Defun ("plist", new Evaluator (progn), 1, -1);
54 Defun ("set", new Evaluator (set_value), 2, 2,
55 typeof (MSymbol), typeof (MExpression));
56 Defun ("=", new Evaluator (set_value), 2, 2,
57 typeof (MSymbol), typeof (MExpression));
58 Defun ("+", new Evaluator (plus), 1, -1);
59 Defun ("*", new Evaluator (multi), 2, -1);
60 Defun ("-", new Evaluator (minus), 1, -1);
61 Defun ("/", new Evaluator (divide), 2, -1);
62 Defun ("%", new Evaluator (percent), 2, -1);
63 Defun ("|", new Evaluator (logior), 2, -1);
64 Defun ("&", new Evaluator (logand), 2, -1);
65 Defun ("+=", new Evaluator (pluseq), 2, -1,
66 typeof (MSymbol), typeof (MExpression));
67 Defun ("*=", new Evaluator (multieq), 2, -1,
68 typeof (MSymbol), typeof (MExpression));
69 Defun ("-=", new Evaluator (minuseq), 2, -1,
70 typeof (MSymbol), typeof (MExpression));
71 Defun ("/=", new Evaluator (divideeq), 2, -1,
72 typeof (MSymbol), typeof (MExpression));
73 Defun ("%=", new Evaluator (percenteq), 2, -1,
74 typeof (MSymbol), typeof (MExpression));
75 Defun ("|=", new Evaluator (logioreq), 2, -1,
76 typeof (MSymbol), typeof (MExpression));
77 Defun ("&=", new Evaluator (logandeq), 2, -1,
78 typeof (MSymbol), typeof (MExpression));
79 Defun ("<<", new Evaluator (lshift), 2, 2);
80 Defun (">>", new Evaluator (rshift), 2, 2);
81 Defun ("<<=", new Evaluator (lshifteq), 2, 2,
82 typeof (MSymbol), typeof (MExpression));
83 Defun (">>=", new Evaluator (rshifteq), 2, 2,
84 typeof (MSymbol), typeof (MExpression));
85 Defun ("==", new Evaluator (eq), 2, -1);
86 Defun ("!=", new Evaluator (noteq), 2, 2);
87 Defun ("<", new Evaluator (less), 2, -1);
88 Defun ("<=", new Evaluator (lesseq), 2, -1);
89 Defun (">", new Evaluator (more), 2, -1);
90 Defun (">=", new Evaluator (moreeq), 2, -1);
91 block = Defun ("progn", new Evaluator (progn), 1, -1);
92 block.pp = new PrettyPrinter (block_pp);
93 Defun ("cond", new Evaluator (cond), 1, -1,
94 typeof (MExpression[])).pp = new PrettyPrinter (cond_pp);
95 Defun ("if", new Evaluator (ifclause), 2, -1,
96 typeof (MExpression)).pp = new PrettyPrinter (if_pp);
97 Defun ("while", new Evaluator (whileclause), 1, -1,
98 typeof (MExpression)).pp = new PrettyPrinter (while_pp);
99 defun = Defun ("defun", new Evaluator (define_function), 4, -1,
100 typeof (FunctionTable),
103 typeof (MExpression));
104 defun.pp = new PrettyPrinter (defun_pp);
107 private static MPlist find_binding (object[] args, MPlist bindings)
109 MSymbol var = (MSymbol) args[0];
110 MPlist slot = bindings.Find (var);
113 throw new Exception ("Unbound variable: " + var);
117 public object Call (object[] args, MPlist bindings)
119 if (name == MSymbol.nil)
122 return eval (args, bindings);
124 MPlist arg_symbols = (MPlist) data[0];
125 for (int i = 0; i < args.Length; i++, arg_symbols = arg_symbols.next)
126 bindings = bindings.Cons (arg_symbols.Symbol,
127 ((MExpression) args[i]).Eval (bindings));
129 for (int i = 1; i < data.Length; i++)
130 result = ((MExpression) data[i]).Eval (bindings);
134 // Commonly used pretty-printers.
136 public static void default_pp (Function func,
137 string indent, object[] args)
139 Console.Write ("(" + func.name);
141 foreach (object o in args)
144 if (o is MExpression)
145 ((MExpression) o).pp (indent);
152 private static void set_pp (Function func, string indent, object[] args)
154 Console.Write ("(" + func.name + " " + (MSymbol) args[0] + " ");
155 ((MExpression) args[1]).pp (indent);
159 private static object get_value (object[] args, MPlist bindings)
161 return find_binding (args, bindings).val;
164 private static object set_value (object[] args, MPlist bindings)
166 MSymbol var = (MSymbol) args[0];
167 MPlist slot = bindings.Find (var);
170 slot = bindings.Push (var, null);
171 slot.val = ((MExpression) args[1]).Eval (bindings);
172 if (slot.val is MText)
173 slot.val = ((MText) slot.val).Dup ();
177 private static object plus (object[] args, MPlist bindings)
179 object val = ((MExpression) args[0]).Eval (bindings);
184 foreach (MExpression e in args)
185 n += (int) e.Eval (bindings);
188 else if (val is MText)
190 MText mt = new MText ();
191 foreach (MExpression e in args)
192 mt += (MText) e.Eval (bindings);
198 private static object multi (object[] args, MPlist bindings)
201 foreach (MExpression e in args)
202 n *= (int) e.Eval (bindings);
206 private static object minus (object[] args, MPlist bindings)
208 int n = (int) ((MExpression) args[0]).Eval (bindings);
209 if (args.Length == 1)
211 for (int i = 1; i < args.Length; i++)
212 n -= (int) ((MExpression) args[i]).Eval (bindings);
216 private static object divide (object[] args, MPlist bindings)
218 int n = (int) ((MExpression) args[0]).Eval (bindings);
219 for (int i = 1; i < args.Length; i++)
220 n /= (int) ((MExpression) args[i]).Eval (bindings);
224 private static object percent (object[] args, MPlist bindings)
226 int n = (int) ((MExpression) args[0]).Eval (bindings);
227 for (int i = 1; i < args.Length; i++)
228 n %= (int) ((MExpression) args[i]).Eval (bindings);
232 private static object logior (object[] args, MPlist bindings)
234 int n = (int) ((MExpression) args[0]).Eval (bindings);
235 for (int i = 1; i < args.Length; i++)
236 n |= (int) ((MExpression) args[i]).Eval (bindings);
240 private static object logand (object[] args, MPlist bindings)
242 int n = (int) ((MExpression) args[0]).Eval (bindings);
243 for (int i = 1; i < args.Length; i++)
244 n &= (int) ((MExpression) args[i]).Eval (bindings);
248 private static object pluseq (object[] args, MPlist bindings)
250 MPlist slot = find_binding (args, bindings);
251 object val = slot.val;
256 for (int i = 1; i < args.Length; i++)
257 n += (int) ((MExpression) args[i]).Eval (bindings);
260 else if (val is MText)
262 MText mt = (MText) val;
263 for (int i = 1; i < args.Length; i++)
264 mt.Cat ((MText) ((MExpression) args[i]).Eval (bindings));
269 private static object multieq (object[] args, MPlist bindings)
271 MPlist slot = find_binding (args, bindings);
272 int n = (int) slot.val;
273 for (int i = 1; i < args.Length; i++)
274 n *= (int) ((MExpression) args[i]).Eval (bindings);
275 return (slot.val = n);
278 private static object minuseq (object[] args, MPlist bindings)
280 MPlist slot = find_binding (args, bindings);
281 int n = (int) slot.val;
282 for (int i = 1; i < args.Length; i++)
283 n -= (int) ((MExpression) args[i]).Eval (bindings);
284 return (slot.val = n);
287 private static object divideeq (object[] args, MPlist bindings)
289 MPlist slot = find_binding (args, bindings);
290 int n = (int) slot.val;
291 for (int i = 1; i < args.Length; i++)
292 n /= (int) ((MExpression) args[i]).Eval (bindings);
293 return (slot.val = n);
296 private static object percenteq (object[] args, MPlist bindings)
298 MPlist slot = find_binding (args, bindings);
299 int n = (int) slot.val;
300 for (int i = 1; i < args.Length; i++)
301 n %= (int) ((MExpression) args[i]).Eval (bindings);
302 return (slot.val = n);
305 private static object logioreq (object[] args, MPlist bindings)
307 MPlist slot = find_binding (args, bindings);
308 int n = (int) slot.val;
309 for (int i = 1; i < args.Length; i++)
310 n |= (int) ((MExpression) args[i]).Eval (bindings);
311 return (slot.val = n);
314 private static object logandeq (object[] args, MPlist bindings)
316 MPlist slot = find_binding (args, bindings);
317 int n = (int) slot.val;
318 for (int i = 1; i < args.Length; i++)
319 n &= (int) ((MExpression) args[i]).Eval (bindings);
320 return (slot.val = n);
323 private static object lshift (object[] args, MPlist bindings)
325 int n1 = (int) ((MExpression) args[0]).Eval (bindings);
326 int n2 = (int) ((MExpression) args[1]).Eval (bindings);
330 private static object lshifteq (object[] args, MPlist bindings)
332 MPlist slot = find_binding (args, bindings);
333 int n1 = (int) slot.val;
334 int n2 = (int) ((MExpression) args[1]).Eval (bindings);
335 return (slot.val = (n1 << n2));
338 private static object rshift (object[] args, MPlist bindings)
340 int n1 = (int) ((MExpression) args[0]).Eval (bindings);
341 int n2 = (int) ((MExpression) args[1]).Eval (bindings);
345 private static object rshifteq (object[] args, MPlist bindings)
347 MPlist slot = find_binding (args, bindings);
348 int n1 = (int) slot.val;
349 int n2 = (int) ((MExpression) args[1]).Eval (bindings);
350 return (slot.val = (n1 >> n2));
353 private static object eq (object[] args, MPlist bindings)
355 int n = (int) ((MExpression) args[0]).Eval (bindings);
356 for (int i = 1; i < args.Length; i++)
357 if (n != (int) ((MExpression) args[i]).Eval (bindings))
362 private static object noteq (object[] args, MPlist bindings)
364 int n1 = (int) ((MExpression) args[0]).Eval (bindings);
365 int n2 = (int) ((MExpression) args[1]).Eval (bindings);
369 private static object less (object[] args, MPlist bindings)
371 int n = (int) ((MExpression) args[0]).Eval (bindings);
372 for (int i = 1; i < args.Length; i++)
374 int n1 = (int) ((MExpression) args[i]).Eval (bindings);
382 private static object lesseq (object[] args, MPlist bindings)
384 int n = (int) ((MExpression) args[0]).Eval (bindings);
385 for (int i = 1; i < args.Length; i++)
387 int n1 = (int) ((MExpression) args[i]).Eval (bindings);
395 private static object more (object[] args, MPlist bindings)
397 int n = (int) ((MExpression) args[0]).Eval (bindings);
398 for (int i = 1; i < args.Length; i++)
400 int n1 = (int) ((MExpression) args[i]).Eval (bindings);
408 private static object moreeq (object[] args, MPlist bindings)
410 int n = (int) ((MExpression) args[0]).Eval (bindings);
411 for (int i = 1; i < args.Length; i++)
413 int n1 = (int) ((MExpression) args[i]).Eval (bindings);
421 private static object progn (object[] args, MPlist bindings)
423 object result = null;
425 foreach (MExpression e in args)
426 result = e.Eval (bindings);
430 private static void block_pp (Function func,
431 string indent, object[] args)
437 foreach (MExpression e in args)
442 Console.Write ("\n" + indent);
448 private static bool check_condition (MExpression e, MPlist bindings)
450 object result = e.Eval (bindings);
451 return (! (result is int) || (int) result != 0);
454 private static object cond (object[] args, MPlist bindings)
456 foreach (MExpression[] elist in args)
457 if (check_condition (elist[0], bindings))
460 for (int i = 1; i < elist.Length; i++)
461 result = elist[i].Eval (bindings);
467 private static void cond_pp (Function func,
468 string indent, object[] args)
470 Console.Write ("(cond");
472 foreach (MExpression[] expr_list in args)
474 Console.Write ("\n" + indent + "(");
476 foreach (MExpression e in expr_list)
489 private static object ifclause (object[] args, MPlist bindings)
493 if (check_condition ((MExpression) args[0], bindings))
494 result = ((MExpression) args[1]).Eval (bindings);
496 for (int i = 2; i < args.Length; i++)
497 result = ((MExpression) args[i]).Eval (bindings);
501 private static void if_pp (Function func,
502 string indent, object[] args)
504 Console.Write ("(if ");
505 ((MExpression) args[0]).pp (indent + " ");
506 Console.Write ("\n" + indent + " ");
507 ((MExpression) args[1]).pp (indent + " ");
509 for (int i = 2; i < args.Length; i++)
511 Console.Write ("\n" + indent);
512 ((MExpression) args[i]).pp (indent);
517 private static object whileclause (object[] args, MPlist bindings)
521 while (check_condition ((MExpression) args[0], bindings))
522 for (int i = 1; i < args.Length; i++)
523 result = ((MExpression) args[i]).Eval (bindings);
527 private static void while_pp (Function func,
528 string indent, object[] args)
530 Console.Write ("(while ");
531 ((MExpression) args[0]).pp (indent + " ");
534 for (int i = 1; i < args.Length; i++)
538 Console.Write ("\n" + indent);
543 ((MExpression) args[i]).pp (indent);
548 public static object define_function (object[] args, MPlist bindings)
550 FunctionTable table = (FunctionTable) args[0];
551 MSymbol sym = (MSymbol) args[1];
552 MPlist arg_symbols = (MPlist) args[2];
553 int nargs = arg_symbols.Count;
554 object[] data = new object[args.Length - 2];
557 for (int i = 3; i < args.Length; i++)
558 data[i - 2] = args[i];
560 Function func = new Function (sym, null, nargs, nargs,
561 typeof (MExpression));
562 table.table[sym] = func;
567 private static void defun_pp (Function func,
568 string indent, object[] args)
570 Console.Write ("(defun " + args[1] + " " + args[2]);
573 for (int i = 3; i < args.Length; i++)
577 Console.Write ("\n" + indent);
582 ((MExpression) args[i]).pp (indent);
588 public class FunctionTable
590 internal Dictionary<MSymbol, Function> table;
592 public FunctionTable ()
594 table = new Dictionary<MSymbol, Function> ();
597 public FunctionTable (FunctionTable table)
599 this.table = new Dictionary<MSymbol, Function> (table.table);
602 public void Copy (FunctionTable table)
604 foreach (KeyValuePair<MSymbol, Function> kv in this.table)
605 table.table[kv.Key] = kv.Value;
608 public void Copy (MSymbol name, FunctionTable table)
611 if (this.table.TryGetValue (name, out func))
612 table.table[name] = func;
616 private static FunctionTable basic_table = new FunctionTable ();
618 public static void Defun (FunctionTable table, string name,
619 Evaluator evaluator, int min_arg, int max_arg,
620 params Type[] arg_types)
622 Function func = Defun (name, evaluator, min_arg, max_arg, arg_types);
623 table.table[func.name] = func;
626 public static void Defmacro (FunctionTable table, MSymbol name,
629 object[] args = new object[4];
632 args[2] = new MPlist ();
634 Function.define_function (args, null);
637 private static Function Defun (string name, Evaluator evaluator,
638 int min_arg, int max_arg,
639 params Type[] arg_types)
641 MSymbol sym = MSymbol.Of (name);
642 Function func = new Function (sym, evaluator, min_arg, max_arg,
644 basic_table.table[sym] = func;
648 private static Function Defun (string name, Evaluator evaluator,
649 int min_arg, int max_arg)
651 return Defun (name, evaluator, min_arg, max_arg, typeof (MExpression));
654 private static Function Find (MSymbol name, FunctionTable table)
656 if (name == MSymbol.integer
657 || name == MSymbol.mtext)
658 return Function.literal;
662 || ! table.table.TryGetValue (name, out func))
663 && ! basic_table.table.TryGetValue (name, out func))
668 private void invalid_expression (object o)
670 throw new Exception ("Invalid expresssion: " + o);
673 private void invalid_argument (object o)
675 throw new Exception (String.Format ("Invalid argument to {0}: {1}",
679 private Function function;
680 private object[] args;
682 public MExpression (MSymbol function_name, object[] args,
683 FunctionTable function_table)
685 function = Find (function_name, function_table);
686 int nargs = args.Length;
687 if (nargs < function.min_arg
688 || (function.max_arg >= 0 && nargs > function.max_arg))
689 throw new Exception (String.Format ("Invalid number of arguments to {0}: {1}", function.name, nargs));
690 this.args = (object[]) args.Clone ();
693 private MExpression[] expression_list (MPlist plist, FunctionTable table)
695 int len = plist.Count;
696 MExpression[] expr_list = new MExpression[len];
698 for (int i = 0; i < len; i++, plist = plist.next)
701 expr_list[i] = new MExpression (plist.Symbol);
702 else if (plist.IsMText || plist.IsInteger)
703 expr_list[i] = new MExpression (plist.val);
704 else if (plist.IsPlist)
706 MPlist p = plist.Plist;
708 expr_list[i] = new MExpression (p.Symbol, p.next, table);
710 expr_list[i] = new MExpression (p, table);
713 invalid_expression (plist.val);
718 // EXPR = SYMBOL | MTEXT | INTEGER | FUNCALL | EXPRLIST
719 // FUNCALL = '(' SYMBOL EXPR* ')'
720 // EXPRLIST = '(' EXPR* ')'
722 // EXPRLIST: PLIST = EXPR ...
723 public MExpression (MPlist plist, FunctionTable table)
725 function = Function.block;
726 args = expression_list (plist, table);
729 // FUNCALL: NAME = FUNCTION-NAME, ARG-LIST = EXPR ...
730 private MExpression (MSymbol name, MPlist arg_list, FunctionTable table)
732 function = Find (name, table);
733 if (function == null)
734 throw new Exception ("Unknown function: " + name);
736 int nargs = arg_list.Count;
737 if (nargs < function.min_arg
738 || (function.max_arg >= 0 && nargs > function.max_arg))
739 throw new Exception (String.Format
740 ("Invalid number of arguments to {0}: {1}",
741 function.name, nargs));
744 Type arg_type = typeof (MExpression);
745 if (function.arg_types.Length > 0)
747 arg_type = function.arg_types[0];
748 if (arg_type == typeof (FunctionTable))
751 args = new object[nargs];
755 args = new object[nargs];
758 args = new object[nargs];
760 foreach (MPlist p in arg_list)
762 if (i < function.arg_types.Length)
763 arg_type = function.arg_types[i];
764 if (arg_type == typeof (MExpression))
767 args[i++] = new MExpression (p.Symbol);
768 else if (p.IsMText || p.IsInteger)
769 args[i++] = new MExpression (p.val);
774 args[i++] = new MExpression (p0.Symbol, p0.next, table);
776 args[i++] = new MExpression (p0, table);
779 invalid_expression (p.val);
781 else if (arg_type == typeof (MExpression[]))
784 invalid_argument (p.val);
785 args[i++] = expression_list (p.Plist, table);
787 else if (arg_type == typeof (MSymbol))
790 invalid_argument (p.val);
791 args[i++] = p.Symbol;
796 if (function == Function.defun)
797 function.Call (args, null);
800 public MExpression (MSymbol sym)
802 function = Function.varref;
803 args = new object[1];
807 public MExpression (object obj)
809 function = Function.literal;
810 args = new object[1];
814 public object Eval (MPlist bindings)
816 return function.Call (args, bindings);
819 private void pp (string indent)
821 if (function == Function.varref
822 || function == Function.literal)
824 if (args[0] is MText)
825 Console.Write ("\"{0}\"", args[0]);
827 Console.Write (args[0]);
830 function.pp (function, indent, args);
833 public void PrettyPrint () { pp (""); }