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)
{
// exp2 == (x y (a b c) z)
SExp exp1 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Nil())));
SExp exp2 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Atom("d"))));
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)
{
{
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);
if (car is Pair)
{
Console.WriteLine("push");
stk2.Push(frame);
frame = new Frame();
}
}
else
{
Console.
WriteLine("eval: " + 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);
{
}
}
// represent last evaluated list symbolically
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;
}
}
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,
LastCarEvaled,
CanEval,
}
}
static Pair GetLastPair(Pair list)
{
while (list.Cdr is Pair)
{
list = list.Cdr as Pair;
}
return list;
}
}