fork(1) download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. abstract class SExp { }
  5.  
  6. class Pair : SExp
  7. {
  8.   public SExp Car { get; set; }
  9.   public SExp Cdr { get; set; }
  10.  
  11.   public Pair(SExp car, SExp cdr)
  12.   {
  13.     this.Car = car;
  14.     this.Cdr = cdr;
  15.   }
  16.  
  17.   public override string ToString()
  18.   {
  19.     return "(" + this.Car + " . " + this.Cdr + ")";
  20.   }
  21. }
  22.  
  23. class Atom : SExp
  24. {
  25.   public string Value { get; set; }
  26.  
  27.   public Atom(string str)
  28.   {
  29.     this.Value = str;
  30.   }
  31.  
  32.   public override string ToString()
  33.   {
  34.     return this.Value;
  35.   }
  36. }
  37.  
  38. class Nil : SExp 
  39. {
  40.   public override string ToString()
  41.   {
  42.     return "()";
  43.   }
  44. }
  45.  
  46. class App
  47. {
  48.   static void Main(string[] args)
  49.   {
  50.     // exp2 == (x y (a b c) z)
  51.     SExp exp1 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Nil())));
  52.     SExp exp2 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Atom("d"))));
  53.     SExp exp3 = new Pair(new Atom("x"), new Pair(new Atom("y"), new Pair(exp1, new Pair(new Atom("z"), new Nil()))));
  54.  
  55.     SExp result = Scan(exp1);
  56.     Console.WriteLine("result: " + result);
  57.     Console.WriteLine("==========");
  58.  
  59.     result = Scan(exp2);
  60.     Console.WriteLine("result: " + result);
  61.     Console.WriteLine("==========");
  62.  
  63.     result = Scan(exp3);
  64.     Console.WriteLine("result: " + result);
  65.     Console.WriteLine("==========");
  66.  
  67.     result = Scan(new Atom("hoge"));
  68.     Console.WriteLine("result: " + result);
  69.     Console.WriteLine("==========");
  70.  
  71.     result = Scan(new Nil());
  72.     Console.WriteLine("result: " + result);
  73.     Console.WriteLine("==========");
  74.   }
  75.  
  76.   static SExp Scan(SExp exp)
  77.   {
  78.     Stack<SExp> stk1 = new Stack<SExp>();
  79.     Stack<Frame> stk2 = new Stack<Frame>();
  80.     Frame frame = new Frame();
  81.     int sqn = 0;
  82.  
  83.     SExp result = null;
  84.  
  85.     while (true)
  86.     {
  87.       if (exp is Pair)
  88.       {
  89.         SExp car = (exp as Pair).Car;
  90.         SExp cdr = (exp as Pair).Cdr;
  91.  
  92.         if (cdr is Nil || cdr is Atom)
  93.         {
  94.           frame.State = Frame.StateForEval.LastCellScaned;
  95.         }
  96.  
  97.         stk1.Push(cdr);
  98.         exp = car;
  99.  
  100.         if (car is Pair)
  101.         {
  102.           Console.WriteLine("push");
  103.           stk2.Push(frame);
  104.           frame = new Frame();
  105.         }
  106.       }
  107.       else
  108.       {
  109.         Console.WriteLine("eval: " + exp);
  110.         result = exp;
  111.         if (frame.State == Frame.StateForEval.LastCarEvaled)
  112.         {
  113.           frame.State = Frame.StateForEval.CanEval;
  114.         }
  115.         if (frame.State == Frame.StateForEval.LastCellScaned)
  116.         {
  117.           frame.State = Frame.StateForEval.LastCarEvaled;
  118.         }
  119.  
  120.         if (frame.State == Frame.StateForEval.CanEval)
  121.         {
  122.           if (frame.List is Nil)
  123.           {
  124.             frame.List = new Pair(exp, new Nil());
  125.           }
  126.           else
  127.           {
  128.             Pair last = GetLastPair(frame.List as Pair);
  129.             if (exp is Atom)
  130.             {
  131.               last.Cdr = exp;
  132.             }
  133.           }
  134.  
  135.           // represent last evaluated list symbolically
  136.           sqn++;
  137.           Console.WriteLine("EVAL: " + frame.List + " => E" + sqn);
  138.           Atom a = new Atom("E" + sqn);
  139.  
  140.           if (stk2.Count == 0)
  141.           {
  142.             result = a;
  143.           }
  144.           else
  145.           {
  146.             Console.WriteLine("pop");
  147.             frame = stk2.Pop();
  148.             if (frame.State == Frame.StateForEval.LastCarEvaled)
  149.             {
  150.               frame.State = Frame.StateForEval.CanEval;
  151.             }
  152.             if (frame.State == Frame.StateForEval.LastCellScaned)
  153.             {
  154.               frame.State = Frame.StateForEval.LastCarEvaled;
  155.             }
  156.  
  157.             if (frame.List is Nil)
  158.             {
  159.               frame.List = new Pair(exp, new Nil());
  160.             }
  161.             else
  162.             {
  163.               Pair last = GetLastPair(frame.List as Pair);
  164.               last.Cdr = new Pair(a, new Nil());
  165.             }
  166.           }
  167.         }
  168.         else
  169.         {
  170.           if (frame.List is Nil)
  171.           {
  172.             frame.List = new Pair(exp, new Nil());
  173.           }
  174.           else
  175.           {
  176.             Pair last = GetLastPair(frame.List as Pair);
  177.             last.Cdr = new Pair(exp, new Nil());
  178.           }
  179.         }
  180.  
  181.         if (0 == stk1.Count) break;
  182.         exp = stk1.Pop();
  183.       }
  184.     }
  185.  
  186.     return result;
  187.   }
  188.  
  189.   class Frame
  190.   {
  191.     public SExp List { get; set; }
  192.     public StateForEval State { get; set; }
  193.  
  194.     public Frame()
  195.     {
  196.       List = new Nil();
  197.       State = StateForEval.None;
  198.     }
  199.  
  200.     public enum StateForEval
  201.     {
  202.       None,
  203.       LastCellScaned,
  204.       LastCarEvaled,
  205.       CanEval,
  206.     }
  207.   }
  208.  
  209.   static Pair GetLastPair(Pair list)
  210.   {
  211.     while (list.Cdr is Pair)
  212.     {
  213.       list = list.Cdr as Pair;
  214.     }
  215.     return list;
  216.   }
  217. }
  218.  
Success #stdin #stdout 0.04s 33936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
eval: a
eval: b
eval: c
eval: ()
EVAL: (a . (b . (c . ()))) => E1
result: E1
==========
eval: a
eval: b
eval: c
eval: d
EVAL: (a . (b . (c . d))) => E1
result: E1
==========
eval: x
eval: y
push
eval: a
eval: b
eval: c
eval: ()
EVAL: (a . (b . (c . ()))) => E1
pop
eval: z
eval: ()
EVAL: (x . (y . (E1 . (z . ())))) => E2
result: E2
==========
eval: hoge
result: hoge
==========
eval: ()
result: ()
==========
https://ideone.com/sh0FXd
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!