ループでEval（その1）

evalを再帰で書くとすぐStackOverflowExceptionで死んじゃうので、ループで書いてみようという試み。
単純に走査するだけのコードを前回のエントリで書いたので、それを使いつつ。
こんな感じ。

using System;
using System.Collections.Generic;

abstract class SExp { }

class Pair : SExp
{
  public SExp Car { get; set; }
  public SExp Cdr { get; set; }

  public Pair(SExp car, SExp cdr)
  {
    this.Car = car;
    this.Cdr = cdr;
  }

  public override string ToString()
  {
    return "(" + this.Car + " . " + this.Cdr + ")";
  }
}

class Atom : SExp
{
  public string Value { get; set; }

  public Atom(string str)
  {
    this.Value = str;
  }

  public override string ToString()
  {
    return this.Value;
  }
}

class Nil : SExp 
{
  public override string ToString()
  {
    return "()";
  }
}

class App
{
  static void Main(string[] args)
  {
    // (a b c)
    SExp exp1 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Nil())));
    // (a b c . d)
    SExp exp2 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Atom("d"))));
    // (x y (a b c) z)
    SExp exp3 = new Pair(new Atom("x"), new Pair(new Atom("y"), new Pair(exp1, new Pair(new Atom("z"), new Nil()))));

    SExp result = Scan(exp1);
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(exp2);
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(exp3);
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(new Atom("hoge"));
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(new Nil());
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");
  }

  static SExp Scan(SExp exp)
  {
    Stack<SExp> stk1 = new Stack<SExp>();
    Stack<Frame> stk2 = new Stack<Frame>();
    Frame frame = new Frame();
    int sqn = 0;

    SExp result = null;

    while (true)
    {
      if (exp is Pair)
      {
        SExp car = (exp as Pair).Car;
        SExp cdr = (exp as Pair).Cdr;

        if (cdr is Nil || cdr is Atom)
        {
          frame.State = Frame.StateForEval.LastCellScaned;
        }

        stk1.Push(cdr);
        exp = car;

        if (car is Pair)
        {
          Console.WriteLine("push");
          stk2.Push(frame);
          frame = new Frame();
        }
      }
      else
      {
        Console.WriteLine("eval: " + exp);
        result = exp;
        if (frame.State == Frame.StateForEval.LastCarEvaled)
        {
          frame.State = Frame.StateForEval.CanEval;
        }
        if (frame.State == Frame.StateForEval.LastCellScaned)
        {
          frame.State = Frame.StateForEval.LastCarEvaled;
        }

        if (frame.State == Frame.StateForEval.CanEval)
        {
          if (frame.List is Nil)
          {
            frame.List = new Pair(exp, new Nil());
          }
          else
          {
            Pair last = GetLastPair(frame.List as Pair);
            if (exp is Atom)
            {
              last.Cdr = exp;
            }
          }

          // 評価した部分リストは、表示短縮のために　E1, E2, E3,... で表記しておく
          sqn++;
          Console.WriteLine("EVAL: " + frame.List + " => E" + sqn);
          Atom a = new Atom("E" + sqn);

          if (stk2.Count == 0)
          {
            result = a;
          }
          else
          {
            Console.WriteLine("pop");
            frame = stk2.Pop();

            if (frame.State == Frame.StateForEval.LastCarEvaled)
            {
              frame.State = Frame.StateForEval.CanEval;
            }
            if (frame.State == Frame.StateForEval.LastCellScaned)
            {
              frame.State = Frame.StateForEval.LastCarEvaled;
            }

            if (frame.List is Nil)
            {
              frame.List = new Pair(exp, new Nil());
            }
            else
            {
              Pair last = GetLastPair(frame.List as Pair);
              last.Cdr = new Pair(a, new Nil());
            }
          }
        }
        else
        {
          if (frame.List is Nil)
          {
            frame.List = new Pair(exp, new Nil());
          }
          else
          {
            Pair last = GetLastPair(frame.List as Pair);
            last.Cdr = new Pair(exp, new Nil());
          }
        }

        if (0 == stk1.Count) break;
        exp = stk1.Pop();
      }
    }

    return result;
  }

  class Frame
  {
    public SExp List { get; set; }
    public StateForEval State { get; set; }

    public Frame()
    {
      List = new Nil();
      State = StateForEval.None;
    }

    public enum StateForEval
    {
      // まだ最後のコンスセルまで来てない
      None,
      // 最後のコンスセル読み込んだ
      LastCellScaned,
      // 最後のコンスセルのcarを処理した
      LastCarEvaled,
      // 最後のコンスセルのcdrを処理した（リストの要素全部を評価した）
      CanEval,
    }
  }

  // 最後のノード取得は番兵でやるべきだろ
  static Pair GetLastPair(Pair list)
  {
    while (list.Cdr is Pair)
    {
      list = list.Cdr as Pair;
    }
    return list;
  }
}

実行結果→Ideone.com - sh0FXd - Online C# Compiler & Debugging Tool
スタック2個使ったけど、大丈夫なのかな。変な事してないかな...。

• 構文木を走査するためのスタック（stk1）
• リストの評価がどこまで終わってるか覚えておくためのスタック（stk2）

今回は手続きだけを想定して書いたけど、構文（defineやlambdaなど）は、それ独自の評価ルールがあるから、どげんかせんといかん。