*** empty log message ***
[m17n/m17n-lib-cs.git] / MExpression.cs
1 using System;
2 using System.Collections;
3 using System.Collections.Generic;
4 using System.IO;
5 using M17N;
6 using M17N.Core;
7
8 namespace M17N.Core
9 {
10   public class MExpression
11   {
12     public delegate object Evaluator (object[] args, MPlist bindings);
13
14     internal delegate void PretyPrinter (MFunction func,
15                                          string indent, object[] args);
16
17     internal class MFunction
18     {
19       internal MSymbol name;
20       internal readonly Evaluator eval;
21       internal int min_arg;
22       internal int max_arg;
23       internal Type[] arg_types;
24
25       public PretyPrinter pp;
26
27       private static PretyPrinter default_prety_printer;
28       private static PretyPrinter set_prety_printer;
29       internal static MFunction literal, varref, block;
30
31       public MFunction (MSymbol name, Evaluator eval,
32                         int min_arg, int max_arg, Type[] arg_types)
33       {
34         this.name = name;
35         this.eval = eval;
36         this.min_arg = min_arg;
37         this.max_arg = max_arg;
38         this.arg_types = (Type []) arg_types.Clone ();
39         if (arg_types.Length == 2 && arg_types[0] == typeof (MSymbol))
40           pp = set_prety_printer;
41         else
42           pp = default_prety_printer;
43       }
44
45       static MFunction ()
46       {
47         default_prety_printer = new PretyPrinter (default_pp);
48         set_prety_printer = new PretyPrinter (set_pp);
49         literal = Defun ("nil", null, 1, 1);
50         varref = Defun ("symbol", new Evaluator (get_value), 1, 1);
51         block = Defun ("plist", new Evaluator (progn), 1, -1);
52
53         Defun ("set", new Evaluator (set_value), 2, 2,
54                typeof (MSymbol), typeof (MExpression));
55         Defun ("=", new Evaluator (set_value), 2, 2,
56                typeof (MSymbol), typeof (MExpression));
57         Defun ("+", new Evaluator (plus), 1, -1);
58         Defun ("*", new Evaluator (multi), 2, -1);
59         Defun ("-", new Evaluator (minus), 1, -1);
60         Defun ("/", new Evaluator (divide), 2, -1);
61         Defun ("%", new Evaluator (percent), 2, -1);
62         Defun ("|", new Evaluator (logior), 2, -1);
63         Defun ("&", new Evaluator (logand), 2, -1);
64         Defun ("+=", new Evaluator (pluseq), 2, -1,
65                typeof (MSymbol), typeof (MExpression));
66         Defun ("*=", new Evaluator (multieq), 2, -1,
67                typeof (MSymbol), typeof (MExpression));
68         Defun ("-=", new Evaluator (minuseq), 2, -1,
69                typeof (MSymbol), typeof (MExpression));
70         Defun ("/=", new Evaluator (divideeq), 2, -1,
71                typeof (MSymbol), typeof (MExpression));
72         Defun ("%=", new Evaluator (percenteq), 2, -1,
73                typeof (MSymbol), typeof (MExpression));
74         Defun ("|=", new Evaluator (logioreq), 2, -1,
75                typeof (MSymbol), typeof (MExpression));
76         Defun ("&=", new Evaluator (logandeq), 2, -1,
77                typeof (MSymbol), typeof (MExpression));
78         Defun ("<<", new Evaluator (lshift), 2, 2);
79         Defun (">>", new Evaluator (rshift), 2, 2);
80         Defun ("<<=", new Evaluator (lshifteq), 2, 2,
81                typeof (MSymbol), typeof (MExpression));
82         Defun (">>=", new Evaluator (rshifteq), 2, 2,
83                typeof (MSymbol), typeof (MExpression));
84         Defun ("==", new Evaluator (eq), 2, -1);
85         Defun ("!=", new Evaluator (noteq), 2, 2);
86         Defun ("<", new Evaluator (less), 2, -1);
87         Defun ("<=", new Evaluator (lesseq), 2, -1);
88         Defun (">", new Evaluator (more), 2, -1);
89         Defun (">=", new Evaluator (moreeq), 2, -1);
90         block = Defun ("progn", new Evaluator (progn), 1, -1);
91         block.pp = new PretyPrinter (block_pp);
92         Defun ("cond", new Evaluator (cond), 1, -1,
93                typeof (MExpression[])).pp = new PretyPrinter (cond_pp);
94         Defun ("if", new Evaluator (ifclause), 2, -1,
95                typeof (MExpression)).pp = new PretyPrinter (if_pp);
96         Defun ("while", new Evaluator (whileclause), 1, -1,
97                typeof (MExpression)).pp = new PretyPrinter (while_pp);
98       }
99
100       public object Call (object[] args, MPlist bindings)
101       {
102         if (name == MSymbol.nil)
103           return args[0];
104         return eval (args, bindings);
105       }
106
107       private static MPlist find_binding (object[] args, MPlist bindings)
108       {
109         MSymbol var = (MSymbol) args[0];
110         MPlist slot = bindings.Find (var);
111
112         if (slot == null)
113           throw new Exception ("Unbound variable: " + var);
114         return slot;
115       }
116
117       public static void default_pp (MFunction func,
118                                      string indent, object[] args)
119       {
120         Console.Write ("(" + func.name);
121         indent += "  ";
122         foreach (MExpression o in args)
123           {
124             Console.Write (" ");
125             o.pp (indent);
126           }
127         Console.Write (")");
128       }
129
130       private static object get_value (object[] args, MPlist bindings)
131       {
132         return find_binding (args, bindings).val;
133       }
134
135       private static object set_value (object[] args, MPlist bindings)
136       {
137         MSymbol var = (MSymbol) args[0];
138         MPlist slot = bindings.Find (var);
139
140         if (slot == null)
141           slot = bindings.Push (var, null);
142         slot.val = ((MExpression) args[1]).Eval (bindings);
143         if (slot.val is MText)
144           slot.val = ((MText) slot.val).Dup ();
145         return slot.val;
146       }
147
148       private static void set_pp (MFunction func, string indent, object[] args)
149       {
150         Console.Write ("(set " + (MSymbol) args[0] + " ");
151         ((MExpression) args[1]).pp (indent);
152         Console.Write (")");
153       }
154
155       private static object plus (object[] args, MPlist bindings)
156       {
157         object val = ((MExpression) args[0]).Eval (bindings);
158
159         if (val is int)
160           {
161             int n = 0;
162             foreach (MExpression e in args)
163               n += (int) e.Eval (bindings);
164             val = n;
165           }
166         else if (val is MText)
167           {
168             MText mt = new MText ();
169             foreach (MExpression e in args)
170               mt += (MText) e.Eval (bindings);
171             val = mt;
172           }
173         return val;
174       }
175
176       private static object multi (object[] args, MPlist bindings)
177       {
178         int n = 1;
179         foreach (MExpression e in args)
180           n *= (int) e.Eval (bindings);
181         return n;
182       }
183
184       private static object minus (object[] args, MPlist bindings)
185       {
186         int n = (int) ((MExpression) args[0]).Eval (bindings);
187         if (args.Length == 1)
188           return - n;
189         for (int i = 1; i < args.Length; i++)
190           n -= (int) ((MExpression) args[i]).Eval (bindings);
191         return n;
192       }
193
194       private static object divide (object[] args, MPlist bindings)
195       {
196         int n = (int) ((MExpression) args[0]).Eval (bindings);
197         for (int i = 1; i < args.Length; i++)
198           n /= (int) ((MExpression) args[i]).Eval (bindings);
199         return n;
200       }
201
202       private static object percent (object[] args, MPlist bindings)
203       {
204         int n = (int) ((MExpression) args[0]).Eval (bindings);
205         for (int i = 1; i < args.Length; i++)
206           n %= (int) ((MExpression) args[i]).Eval (bindings);
207         return n;
208       }
209
210       private static object logior (object[] args, MPlist bindings)
211       {
212         int n = (int) ((MExpression) args[0]).Eval (bindings);
213         for (int i = 1; i < args.Length; i++)
214           n |= (int) ((MExpression) args[i]).Eval (bindings);
215         return n;
216       }
217
218       private static object logand (object[] args, MPlist bindings)
219       {
220         int n = (int) ((MExpression) args[0]).Eval (bindings);
221         for (int i = 1; i < args.Length; i++)
222           n &= (int) ((MExpression) args[i]).Eval (bindings);
223         return n;
224       }
225
226       private static object pluseq (object[] args, MPlist bindings)
227       {
228         MPlist slot = find_binding (args, bindings);
229         object val = slot.val;
230
231         if (val is int)
232           {
233             int n = (int) val;
234             for (int i = 1; i < args.Length; i++)
235               n += (int) ((MExpression) args[i]).Eval (bindings);
236             slot.val = n;
237           }
238         else if (val is MText)
239           {
240             MText mt = (MText) val;
241             for (int i = 1; i < args.Length; i++)
242               mt.Cat ((MText) ((MExpression) args[i]).Eval (bindings));
243           }
244         return slot.val;
245       }
246
247       private static object multieq (object[] args, MPlist bindings)
248       {
249         MPlist slot = find_binding (args, bindings);
250         int n = (int) slot.val;
251         for (int i = 1; i < args.Length; i++)
252           n *= (int) ((MExpression) args[i]).Eval (bindings);
253         return (slot.val = n);
254       }
255
256       private static object minuseq (object[] args, MPlist bindings)
257       {
258         MPlist slot = find_binding (args, bindings);
259         int n = (int) slot.val;
260         for (int i = 1; i < args.Length; i++)
261           n -= (int) ((MExpression) args[i]).Eval (bindings);
262         return (slot.val = n);
263       }
264
265       private static object divideeq (object[] args, MPlist bindings)
266       {
267         MPlist slot = find_binding (args, bindings);
268         int n = (int) slot.val;
269         for (int i = 1; i < args.Length; i++)
270           n /= (int) ((MExpression) args[i]).Eval (bindings);
271         return (slot.val = n);
272       }
273
274       private static object percenteq (object[] args, MPlist bindings)
275       {
276         MPlist slot = find_binding (args, bindings);
277         int n = (int) slot.val;
278         for (int i = 1; i < args.Length; i++)
279           n %= (int) ((MExpression) args[i]).Eval (bindings);
280         return (slot.val = n);
281       }
282
283       private static object logioreq (object[] args, MPlist bindings)
284       {
285         MPlist slot = find_binding (args, bindings);
286         int n = (int) slot.val;
287         for (int i = 1; i < args.Length; i++)
288           n |= (int) ((MExpression) args[i]).Eval (bindings);
289         return (slot.val = n);
290       }
291
292       private static object logandeq (object[] args, MPlist bindings)
293       {
294         MPlist slot = find_binding (args, bindings);
295         int n = (int) slot.val;
296         for (int i = 1; i < args.Length; i++)
297           n &= (int) ((MExpression) args[i]).Eval (bindings);
298         return (slot.val = n);
299       }
300
301       private static object lshift (object[] args, MPlist bindings)
302       {
303         int n1 = (int) ((MExpression) args[0]).Eval (bindings);
304         int n2 = (int) ((MExpression) args[1]).Eval (bindings);
305         return n1 << n2;
306       }
307
308       private static object lshifteq (object[] args, MPlist bindings)
309       {
310         MPlist slot = find_binding (args, bindings);
311         int n1 = (int) slot.val;
312         int n2 = (int) ((MExpression) args[1]).Eval (bindings);
313         return (slot.val = (n1 << n2));
314       }
315
316       private static object rshift (object[] args, MPlist bindings)
317       {
318         int n1 = (int) ((MExpression) args[0]).Eval (bindings);
319         int n2 = (int) ((MExpression) args[1]).Eval (bindings);
320         return n1 >> n2;
321       }
322
323       private static object rshifteq (object[] args, MPlist bindings)
324       {
325         MPlist slot = find_binding (args, bindings);
326         int n1 = (int) slot.val;
327         int n2 = (int) ((MExpression) args[1]).Eval (bindings);
328         return (slot.val = (n1 >> n2));
329       }
330
331       private static object eq (object[] args, MPlist bindings)
332       {
333         int n = (int) ((MExpression) args[0]).Eval (bindings);
334         for (int i = 1; i < args.Length; i++)
335           if (n != (int) ((MExpression) args[i]).Eval (bindings))
336             return 0;
337         return 1;
338       }
339
340       private static object noteq (object[] args, MPlist bindings)
341       {
342         int n1 = (int) ((MExpression) args[0]).Eval (bindings);
343         int n2 = (int) ((MExpression) args[1]).Eval (bindings);
344         return (n1 != n2);
345       }
346
347       private static object less (object[] args, MPlist bindings)
348       {
349         int n = (int) ((MExpression) args[0]).Eval (bindings);
350         for (int i = 1; i < args.Length; i++)
351           {
352             int n1 = (int) ((MExpression) args[i]).Eval (bindings);
353             if (n >= n1)
354               return 0;
355             n = n1;
356           }
357         return 1;
358       }
359
360       private static object lesseq (object[] args, MPlist bindings)
361       {
362         int n = (int) ((MExpression) args[0]).Eval (bindings);
363         for (int i = 1; i < args.Length; i++)
364           {
365             int n1 = (int) ((MExpression) args[i]).Eval (bindings);
366             if (n > n1)
367               return 0;
368             n = n1;
369           }
370         return 1;
371       }
372
373       private static object more (object[] args, MPlist bindings)
374       {
375         int n = (int) ((MExpression) args[0]).Eval (bindings);
376         for (int i = 1; i < args.Length; i++)
377           {
378             int n1 = (int) ((MExpression) args[i]).Eval (bindings);
379             if (n <= n1)
380               return 0;
381             n = n1;
382           }
383         return 1;
384       }
385
386       private static object moreeq (object[] args, MPlist bindings)
387       {
388         int n = (int) ((MExpression) args[0]).Eval (bindings);
389         for (int i = 1; i < args.Length; i++)
390           {
391             int n1 = (int) ((MExpression) args[i]).Eval (bindings);
392             if (n < n1)
393               return 0;
394             n = n1;
395           }
396         return 1;
397       }
398
399       private static object progn (object[] args, MPlist bindings)
400       {
401         object result = null;
402
403         foreach (MExpression e in args)
404           result = e.Eval (bindings);
405         return result;
406       }
407
408       private static void block_pp (MFunction func,
409                                     string indent, object[] args)
410       {
411         bool first = true;
412
413         Console.Write ("(");
414         indent += " ";
415         foreach (MExpression e in args)
416           {
417             if (first)
418               first = false;
419             else
420               Console.Write ("\n" + indent);
421             e.pp (indent);
422           }
423         Console.Write (")");
424       }
425
426       private static object cond (object[] args, MPlist bindings)
427       {
428         foreach (MExpression[] elist in args)
429           {
430             int i = (int) elist[0].Eval (bindings);
431             if (i != 0)
432               return progn ((object[]) elist, bindings);
433           }
434         return 0;
435       }
436
437       private static void cond_pp (MFunction func,
438                                     string indent, object[] args)
439       {
440         Console.Write ("(cond");
441         indent += "  ";
442         foreach (MExpression[] expr_list in args)
443           {
444             Console.Write ("\n" + indent + "(");
445             bool first = true;
446             foreach (MExpression e in expr_list)
447               {
448                 if (first)
449                   first = false;
450                 else
451                   Console.Write (" ");
452                 e.pp (indent);
453               }
454             Console.Write (")");
455           }
456         Console.Write (")");
457       }
458
459       private static object ifclause (object[] args, MPlist bindings)
460       {
461         object result = 0;
462
463         if ((int) ((MExpression) args[0]).Eval (bindings) != 0)
464           result = ((MExpression) args[1]).Eval (bindings);
465         else
466           for (int i = 2; i < args.Length; i++)
467             result = ((MExpression) args[i]).Eval (bindings);
468         return result;
469       }
470
471       private static void if_pp (MFunction func,
472                                  string indent, object[] args)
473       {
474         Console.Write ("(if ");
475         ((MExpression) args[0]).pp (indent + "    ");
476         Console.Write ("\n" + indent + "    ");
477         ((MExpression) args[1]).pp (indent + "    ");
478         bool first = true;
479         indent += "  ";
480         for (int i = 2; i < args.Length; i++)
481           {
482             if (first)
483               {
484                 Console.Write ("\n" + indent);
485                 first = false;
486               }
487             else
488               Console.Write (" ");
489             ((MExpression) args[i]).pp (indent);
490           }
491       }
492
493       private static object whileclause (object[] args, MPlist bindings)
494       {
495         object result = 0;
496
497         while ((int) ((MExpression) args[0]).Eval (bindings) != 0)
498           for (int i = 1; i < args.Length; i++)
499             result = ((MExpression) args[i]).Eval (bindings);
500         return result;
501       }
502
503       private static void while_pp (MFunction func,
504                                     string indent, object[] args)
505       {
506         Console.Write ("(while ");
507         ((MExpression) args[0]).pp (indent + "       ");
508         bool first = true;
509         indent += "  ";
510         for (int i = 1; i < args.Length; i++)
511           {
512             if (first)
513               {
514                 Console.Write ("\n" + indent);
515                 first = false;
516               }
517             else
518               Console.Write (" ");
519             ((MExpression) args[i]).pp (indent);
520           }
521       }
522     }
523
524     public class FunctionTable
525     {
526       internal Dictionary<MSymbol, MFunction> table
527         = new Dictionary<MSymbol, MFunction> ();
528     }
529
530     private static FunctionTable basic_table = new FunctionTable ();
531
532     public static void Defun (FunctionTable table, string name,
533                               Evaluator evaluator, int min_arg, int max_arg,
534                               params Type[] arg_types)
535     {
536       MSymbol sym = MSymbol.Of (name);
537       MFunction func = new MFunction (sym, evaluator, min_arg, max_arg,
538                                       arg_types);
539       table.table[sym] = func;
540     }
541
542     private static MFunction Defun (string name, Evaluator evaluator,
543                                     int min_arg, int max_arg,
544                                     params Type[] arg_types)
545     {
546       MSymbol sym = MSymbol.Of (name);
547       MFunction func = new MFunction (sym, evaluator, min_arg, max_arg,
548                                       arg_types);
549       basic_table.table[sym] = func;
550       return func;
551     }
552
553     private static MFunction Defun (string name, Evaluator evaluator,
554                                     int min_arg, int max_arg)
555     {
556       return Defun (name, evaluator, min_arg, max_arg, typeof (MExpression));
557     }
558
559     private static MFunction Find (MSymbol name, FunctionTable table)
560     {
561       if (name == MSymbol.integer
562           || name == MSymbol.mtext)
563         return MFunction.literal;
564
565       MFunction func;
566       if ((table == null
567            || ! table.table.TryGetValue (name, out func))
568           && ! basic_table.table.TryGetValue (name, out func))
569         return null;
570       return func;
571     }
572
573     private void invalid_expression (object o)
574     {
575       throw new Exception ("Invalid expresssion: " + o);
576     }
577
578     private void invalid_argument (object o)
579     {
580       throw new Exception ("Invalid argument: " + o);
581     }
582
583     private MFunction function;
584     private object[] args;
585
586     public MExpression (MSymbol function_name, object[] args,
587                         FunctionTable function_table)
588     {
589       function = Find (function_name, function_table);
590       int nargs = args.Length;
591       if (nargs < function.min_arg
592           || (function.max_arg >= 0 && nargs > function.max_arg))
593         throw new Exception ("Invalid number of arguments: " + args);
594       this.args = (object[]) args.Clone ();
595     }
596
597     private MExpression[] expression_list (MPlist plist, FunctionTable table)
598     {
599       int len = plist.Count;
600       MExpression[] expr_list = new MExpression[len];
601
602       for (int i = 0; i < len; i++, plist = plist.next)
603         {
604           if (plist.IsSymbol)
605             expr_list[i] = new MExpression (plist.Symbol);
606           else if (plist.IsMText || plist.IsInteger)
607             expr_list[i] = new MExpression (plist.val);
608           else if (plist.IsPlist)
609             {
610               MPlist p = plist.Plist;
611               if (p.IsSymbol)
612                 expr_list[i] = new MExpression (p.Symbol, p.next, table);
613               else
614                 expr_list[i] = new MExpression (p, table);
615             }
616           else
617             invalid_expression (plist.val);
618         }
619       return expr_list;
620     }
621
622     // EXPR = SYMBOL | MTEXT | INTEGER | FUNCALL | EXPRLIST
623     // FUNCALL = '(' SYMBOL EXPR* ')'
624     // EXPRLIST = '(' EXPR* ')'
625
626     // EXPRLIST: PLIST = EXPR ...
627     public MExpression (MPlist plist, FunctionTable table)
628     {
629       function = MFunction.block;
630       args = expression_list (plist, table);
631     }
632
633     // FUNCALL: NAME = FUNCTION-NAME, ARG-LIST = EXPR ...
634     private MExpression (MSymbol name, MPlist arg_list, FunctionTable table)
635     {
636       function = Find (name, table);
637       if (function == null)
638         throw new Exception ("Unknown function: " + name);
639
640       int nargs = arg_list.Count;
641       if (nargs < function.min_arg
642           || (function.max_arg >= 0 && nargs > function.max_arg))
643         throw new Exception ("Invalid number of arguments: " + nargs);
644       args = new object[nargs];
645
646       int i = 0;
647       Type arg_type = typeof (MExpression);
648       foreach (MPlist p in arg_list)
649         {
650           if (i < function.arg_types.Length)
651             arg_type = function.arg_types[i];
652           if (arg_type == typeof (MExpression))
653             {
654               if (p.IsSymbol)
655                 args[i++] = new MExpression (p.Symbol);
656               else if (p.IsMText || p.IsInteger)
657                 args[i++] = new MExpression (p.val);
658               else if (p.IsPlist)
659                 {
660                   MPlist p0 = p.Plist;
661                   if (p0.IsSymbol)
662                     args[i++] = new MExpression (p0.Symbol, p0.next, table);
663                   else
664                     args[i++] = new MExpression (p0, table);
665                 }
666               else
667                 invalid_expression (p.val);
668             }
669           else if (arg_type == typeof (MExpression[]))
670             {
671               if (! p.IsPlist)
672                 invalid_argument (p.val);
673               args[i++] = expression_list (p.Plist, table);
674             }
675           else if (arg_type == typeof (MSymbol))
676             {
677               if (! p.IsSymbol)
678                 invalid_argument (p.val);
679               args[i++] = p.Symbol;
680             }
681           else
682             args[i++] = p.val;
683         }
684     }
685
686     public MExpression (MSymbol sym)
687     {
688       function = MFunction.varref;
689       args = new object[1];
690       args[0] = sym;
691     }
692
693     public MExpression (object obj)
694     {
695       function = MFunction.literal;
696       args = new object[1];
697       args[0] = obj;
698     }
699
700     public object Eval (MPlist bindings)
701     {
702       return function.Call (args, bindings);
703     }
704
705     private void pp (string indent)
706     {
707       if (function == MFunction.varref
708           || function == MFunction.literal)
709         {
710           if (args[0] is MText)
711             Console.Write ("\"{0}\"", args[0]);
712           else
713             Console.Write (args[0]);
714         }
715       else
716         function.pp (function, indent, args);
717     }
718
719     public void PretyPrint () { pp (""); }
720   }
721 }