public static int Add(int a, int b) {
  return a + b;
}
>> Add(3, 4)
>> 7
>> Add(5, 5)
>> 10

public static int Factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * Factorial(n - 1);
  }
}

(def factorial (lambda (n) (
  if (= n 1)
    1
    (* n (factorial (- n 1))))))

>> (def a 3)
>> 3
>> a
>> 3

// Arithmetic ops
a + b * c
a / (b + c + d)
// Logical ops
(cond1 && cond2) || cond3
// Comparing ops
a == b
1 < a && a < 3

; Arithmetic ops
(+ a (* b c))
(/ a (+ b c d))
; Logical ops
(or (and cond1 cond2) cond3)
; Comparing ops
(= a b)
(< 1 a 3)

int a = 3;
int b = 5;
int c = (a + b) / 2;

(def c (begin
  (def a 3)
  (def b 5)
  (/ (+ a b) 2)))

>> (define a (if (> 3 2) 1 2))
>> 1
>> a
>> 1

>> (define alist (list 1 2 3 4))
>> (list 1 2 3 4)
>> (first alist)
>> 1
>> (rest alist)
>> (2 3 4)

(def square (func (x) (* x x)))
(def sum_square (func (a b) (+ (square a) (square b))))

public static int Square (int x) {
  return x * x;
}
public static int SumSquare(int a, int b) {
  return Square(a) + Square(b);
}

(def gcd (func (a b)
  (if (= b 0)
    a
    (func (b (% a b))))))

public static int GCD (int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return GCD(b, a % b);
  }
}

; Defines a multiply function.
(def mul (func (a b) (* a b)))
; Defines a list map function.
(def map (func (f alist)
  (if (empty? alist)
    (list )
    (append (list (f (first alist))) (map f (rest alist)))
    )))
; Doubles a list using map and mul.
>> (map (mul 2) (list 1 2 3))
>> (list 2 4 6)

public static String[] Tokenize(String text) {
  String[] tokens = text.Replace("(", " ( ").Replace(")", " ) ").Split(" \t\r\n".ToArray(), StringSplitOptions.RemoveEmptyEntries);
  return tokens;
}
// Extends String.Join for a smooth API.
public static String Join(this String separator, IEnumerable<Object> values) {
  return String.Join(separator, values);
}
// Displays the lexes in a readable form.
public static String PrettyPrint(String[] lexes) {
  return "[" + ", ".Join(lexes.Select(s => "'" + s + "'") + "]";
}
// Some tests
>> PrettyPrint(Tokenize("a"))
>> ['a']
>> PrettyPrint(Tokenize("(def a 3)"))
>> ['(', 'def', 'a', '3', ')']
>> PrettyPrint(Tokenize("(begin (def a 3) (* a a))"))
>> ['begin', '(', 'def', 'a', '3', ')', '(', '*', 'a', 'a', ')', ')']

;
(def x (if (> a 1) a 1))
; 换一个角度看的话：
(
  def
  x
  (
    if
    (
      >
      a
      1
    )
    a
    1
  )
)

public class SExpression {
  public String Value { get; private set; }
  public List<SExpression> Children { get; private set; }
  public SExpression Parent { get; private set; }
  public SExpression(String value, SExpression parent) {
    this.Value = value;
    this.Children = new List<SExpression>();
    this.Parent = parent;
  }
  public override String ToString() {
    if (this.Value == "(") {
      return "(" + " ".Join(Children) + ")";
    } else {
      return this.Value;
    }
  }
}

public static SExpression ParseAsIScheme(this String code) {
  SExpression program = new SExpression(value: "", parent: null);
  SExpression current = program;
  foreach (var lex in Tokenize(code)) {
    if (lex == "(") {
      SExpression newNode = new SExpression(value: "(", parent: current);
      current.Children.Add(newNode);
      current = newNode;
    } else if (lex == ")") {
      current = current.Parent;
    } else {
      current.Children.Add(new SExpression(value: lex, parent: current));
    }
  }
  return program.Children[0];
}

>> (def x 1)
>> 1
>> (def y (begin (def x 2) (* x x)))
>> 4
>> x
>> 1

public class SScope {
  public SScope Parent { get; private set; }
  private Dictionary<String, SObject> variableTable;
  public SScope(SScope parent) {
    this.Parent = parent;
    this.variableTable = new Dictionary<String, SObject>();
  }
  public SObject Find(String name) {
    SScope current = this;
    while (current != null) {
      if (current.variableTable.ContainsKey(name)) {
        return current.variableTable[name];
      }
      current = current.Parent;
    }
    throw new Exception(name + " is not defined.");
  }
  public SObject Define(String name, SObject value) {
    this.variableTable.Add(name, value);
    return value;
  }
}

public class SNumber : SObject {
  private readonly Int64 value;
  public SNumber(Int64 value) {
    this.value = value;
  }
  public override String ToString() {
    return this.value.ToString();
  }
  public static implicit operator Int64(SNumber number) {
    return number.value;
  }
  public static implicit operator SNumber(Int64 value) {
    return new SNumber(value);
  }
}

SNumber foo = 30;
SNumber bar = 40;
SNumber foobar = foo * bar;

SNumber foo = new SNumber(value: 30);
SNumber bar = new SNumber(value: 40);
SNumber foobar = new SNumber(value: foo.Value * bar.Value);

public class SObject {
  ...
  public static implicit operator SObject(Int64 value) {
    return (SNumber)value;
  }
}

public class SBool : SObject {
  public static readonly SBool False = new SBool();
  public static readonly SBool True = new SBool();
  public override String ToString() {
    return ((Boolean)this).ToString();
  }
  public static implicit operator Boolean(SBool value) {
    return value == SBool.True;
  }
  public static implicit operator SBool(Boolean value) {
    return value ? True : False;
  }
}

SBool foo = a > 1;
if (foo) {
  // Do something...
}

SBool foo = a > 1 ? SBool.True: SBool.False;
if (foo == SBool.True) {
  // Do something...
}

public class SObject {
  ...
  public static implicit operator SObject(Boolean value) {
    return (SBool)value;
  }
}

public class SList : SObject, IEnumerable<SObject> {
  private readonly IEnumerable<SObject> values;
  public SList(IEnumerable<SObject> values) {
    this.values = values;
  }
  public override String ToString() {
    return "(list " + " ".Join(this.values) + ")";
  }
  public IEnumerator<SObject> GetEnumerator() {
    return this.values.GetEnumerator();
  }
  IEnumerator IEnumerable.GetEnumerator() {
    return this.values.GetEnumerator();
  }
}

public class SFunction : SObject {
  public SExpression Body { get; private set; }
  public String[] Parameters { get; private set; }
  public SScope Scope { get; private set; }
  public Boolean IsPartial {
    get {
      return this.ComputeFilledParameters().Length.InBetween(1, this.Parameters.Length);
    }
  }
  public SFunction(SExpression body, String[] parameters, SScope scope) {
    this.Body = body;
    this.Parameters = parameters;
    this.Scope = scope;
  }
  public SObject Evaluate() {
    String[] filledParameters = this.ComputeFilledParameters();
    if (filledParameters.Length < Parameters.Length) {
      return this;
    } else {
      return this.Body.Evaluate(this.Scope);
    }
  }
  public override String ToString() {
    return String.Format("(func ({0}) {1})",
      " ".Join(this.Parameters.Select(p => {
        SObject value = null;
        if ((value = this.Scope.FindInTop(p)) != null) {
          return p + ":" + value;
        }
        return p;
      })), this.Body);
  }
  private String[] ComputeFilledParameters() {
    return this.Parameters.Where(p => Scope.FindInTop(p) != null).ToArray();
  }
}

>> (def mul (func (a b) (* a b)))
>> (func (a b) (* a b))
>> (mul 3 4)
>> 12
>> (mul 3)
>> (func (a:3 b) (* a b))
>> ((mul 3) 4)
>> 12

(def mul (func (a b) (* a b)))
(def mul3 (mul 3))
>> (mul3 3)
>> 9

(def times (func (n) (func (n x) (* n x)) ) )
(def mul3 (times 3))
>> (mul3 3)
>> 9

public class SScope {
  private static Dictionary<String, Func<SExpression[], SScope, SObject>> builtinFunctions =
    new Dictionary<String, Func<SExpression[], SScope, SObject>>();
  public static Dictionary<String, Func<SExpression[], SScope, SObject>> BuiltinFunctions {
    get { return builtinFunctions; }
  }
  // Dirty HACK for fluent API.
  public SScope BuildIn(String name, Func<SExpression[], SScope, SObject> builtinFuntion) {
    SScope.builtinFunctions.Add(name, builtinFuntion);
    return this;
  }
}

new SScope(parent: null)
  .BuildIn("+", addMethod)
  .BuildIn("-", subMethod)
  .BuildIn("*", mulMethod)
  .BuildIn("/", divMethod);

public static void OrThrows(this Boolean condition, String message = null) {
  if (!condition) { throw new Exception(message ?? "WTF"); }
}

if (a < 3) {
  throw new Exception("Value must be less than 3.");
}

.BuildIn("+", (args, scope) => {
  var numbers = args.Select(obj => obj.Evaluate(scope)).Cast<SNumber>();
  return numbers.Sum(n => n);
})
.BuildIn("-", (args, scope) => {
  var numbers = args.Select(obj => obj.Evaluate(scope)).Cast<SNumber>().ToArray();
  Int64 firstValue = numbers[0];
  if (numbers.Length == 1) {
    return -firstValue;
  }
  return firstValue - numbers.Skip(1).Sum(s => s);
})

public static IEnumerable<T> Evaluate<T>(this IEnumerable<SExpression> expressions, SScope scope)
where T : SObject {
  return expressions.Evaluate(scope).Cast<T>();
}
public static IEnumerable<SObject> Evaluate(this IEnumerable<SExpression> expressions, SScope scope) {
  return expressions.Select(exp => exp.Evaluate(scope));
}

.BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s)))
.BuildIn("-", (args, scope) => {
  var numbers = args.Evaluate<SNumber>(scope).ToArray();
  Int64 firstValue = numbers[0];
  if (numbers.Length == 1) {
    return -firstValue;
  }
  return firstValue - numbers.Skip(1).Sum(s => s);
})

.BuildIn("*", (args, scope) => args.Evaluate<SNumber>(scope).Aggregate((a, b) => a * b))
.BuildIn("/", (args, scope) => {
  var numbers = args.Evaluate<SNumber>(scope).ToArray();
  Int64 firstValue = numbers[0];
  return firstValue / numbers.Skip(1).Aggregate((a, b) => a * b);
})
.BuildIn("%", (args, scope) => {
  (args.Length == 2).OrThrows("Parameters count in mod should be 2");
  var numbers = args.Evaluate<SNumber>(scope).ToArray();
  return numbers[0] % numbers[1];
})

.BuildIn("and", (args, scope) => {
  (args.Length > 0).OrThrows();
  return !args.Any(arg => !(SBool)arg.Evaluate(scope));
})
.BuildIn("or", (args, scope) => {
  (args.Length > 0).OrThrows();
  return args.Any(arg => (SBool)arg.Evaluate(scope));
})
.BuildIn("not", (args, scope) => {
  (args.Length == 1).OrThrows();
  return args[0].Evaluate(scope);
})

.BuildIn("=", (args, scope) => {
  (args.Length > 1).OrThrows("Must have more than 1 argument in relation operation.");
  SNumber current = (SNumber)args[0].Evaluate(scope);
  foreach (var arg in args.Skip(1)) {
    SNumber next = (SNumber)arg.Evaluate(scope);
    if (current == next) {
      current = next;
    } else {
      return false;
    }
  }
  return true;
})

public static SBool ChainRelation(this SExpression[] expressions, SScope scope, Func<SNumber, SNumber, Boolean> relation) {
  (expressions.Length > 1).OrThrows("Must have more than 1 parameter in relation operation.");
  SNumber current = (SNumber)expressions[0].Evaluate(scope);
  foreach (var obj in expressions.Skip(1)) {
    SNumber next = (SNumber)obj.Evaluate(scope);
    if (relation(current, next)) {
      current = next;
    } else {
      return SBool.False;
    }
  }
  return SBool.True;
}

.BuildIn("=", (args, scope) => args.ChainRelation(scope, (s1, s2) => (Int64)s1 == (Int64)s2))
.BuildIn(">", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 > s2))
.BuildIn("<", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 < s2))
.BuildIn(">=", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 >= s2))
.BuildIn("<=", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 <= s2))

.BuildIn("first", (args, scope) => {
  SList list = null;
  (args.Length == 1 && (list = (args[0].Evaluate(scope) as SList)) != null).OrThrows("<first> must apply to a list.");
  return list.First();
})
.BuildIn("rest", (args, scope) => {
  SList list = null;
  (args.Length == 1 && (list = (args[0].Evaluate(scope) as SList)) != null).OrThrows("<rest> must apply to a list.");
  return new SList(list.Skip(1));
})

public static SList RetrieveSList(this SExpression[] expressions, SScope scope, String operationName) {
  SList list = null;
  (expressions.Length == 1 && (list = (expressions[0].Evaluate(scope) as SList)) != null)
    .OrThrows("<" + operationName + "> must apply to a list");
  return list;
}

.BuildIn("first", (args, scope) => args.RetrieveSList(scope, "first").First())
.BuildIn("rest", (args, scope) => new SList(args.RetrieveSList(scope, "rest").Skip(1)))
.BuildIn("append", (args, scope) => {
  SList list0 = null, list1 = null;
  (args.Length == 2
    && (list0 = (args[0].Evaluate(scope) as SList)) != null
    && (list1 = (args[1].Evaluate(scope) as SList)) != null).OrThrows("Input must be two lists");
  return new SList(list0.Concat(list1));
})
.BuildIn("empty?", (args, scope) => args.RetrieveSList(scope, "empty?").Count() == 0)

public static void KeepInterpretingInConsole(this SScope scope, Func<String, SScope, SObject> evaluate) {
  while (true) {
    try {
      Console.ForegroundColor = ConsoleColor.Gray;
      Console.Write(">> ");
      String code;
      if (!String.IsNullOrWhiteSpace(code = Console.ReadLine())) {
        Console.ForegroundColor = ConsoleColor.Green;
        Console.WriteLine(">> " + evaluate(code, scope));
      }
    } catch (Exception ex) {
      Console.ForegroundColor = ConsoleColor.Red;
      Console.WriteLine(">> " + ex.Message);
    }
  }
}

public override SObject Evaluate(SScope scope) {
  if (this.Children.Count == 0) {
    Int64 number;
    if (Int64.TryParse(this.Value, out number)) {
      return number;
    }
  } else {
    SExpression first = this.Children[0];
    if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
      var arguments = this.Children.Skip(1).Select(node => node.Evaluate(scope)).ToArray();
      return SScope.BuiltinFunctions[first.Value](arguments, scope);
    }
  }
  throw new Exception("THIS IS JUST TEMPORARY!");
}

static void Main(String[] cmdArgs) {
  new SScope(parent: null)
    .BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s)))
    // 省略若干内置函数
    .BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0)
    .KeepInterpretingInConsole((code, scope) => code.ParseAsScheme().Evaluate(scope));
}

public class SExpression {
  // ...
  public override SObject Evaluate(SScope scope) {
    // TODO: Todo your ass.
  }
}

if (this.Children.Count == 0) {
  Int64 number;
  if (Int64.TryParse(this.Value, out number)) {
    return number;
  } else {
    return scope.Find(this.Value);
  }
}

if (first.Value == "if") {
  SBool condition = (SBool)(this.Children[1].Evaluate(scope));
  return condition ? this.Children[2].Evaluate(scope) : this.Children[3].Evaluate(scope);
}

else if (first.Value == "def") {
  return scope.Define(this.Children[1].Value, this.Children[2].Evaluate(new SScope(scope)));
}

else if (first.Value == "begin") {
  SObject result = null;
  foreach (SExpression statement in this.Children.Skip(1)) {
    result = statement.Evaluate(scope);
  }
  return result;
}

else if (first.Value == "func") {
  SExpression body = this.Children[2];
  String[] parameters = this.Children[1].Children.Select(exp => exp.Value).ToArray();
  SScope newScope = new SScope(scope);
  return new SFunction(body, parameters, newScope);
}

else if (first.Value == "list") {
  return new SList(this.Children.Skip(1).Select(exp => exp.Evaluate(scope)));
}

else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
  var arguments = this.Children.Skip(1).ToArray();
  return SScope.BuiltinFunctions[first.Value](arguments, scope);
}

public SFunction Update(SObject[] arguments) {
  var existingArguments = this.Parameters.Select(p => this.Scope.FindInTop(p)).Where(obj => obj != null);
  var newArguments = existingArguments.Concat(arguments).ToArray();
  SScope newScope = this.Scope.Parent.SpawnScopeWith(this.Parameters, newArguments);
  return new SFunction(this.Body, this.Parameters, newScope);
}

public SScope SpawnScopeWith(String[] names, SObject[] values) {
  (names.Length >= values.Length).OrThrows("Too many arguments.");
  SScope scope = new SScope(this);
  for (Int32 i = 0; i < values.Length; i++) {
    scope.variableTable.Add(names[i], values[i]);
  }
  return scope;
}
public SObject FindInTop(String name) {
  if (variableTable.ContainsKey(name)) {
    return variableTable[name];
  }
  return null;
}

else {
  SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value);
  var arguments = this.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray();
  return function.Update(arguments).Evaluate();
}

public SObject Evaluate(SScope scope) {
  if (this.Children.Count == 0) {
    Int64 number;
    if (Int64.TryParse(this.Value, out number)) {
      return number;
    } else {
      return scope.Find(this.Value);
    }
  } else {
    SExpression first = this.Children[0];
    if (first.Value == "if") {
      SBool condition = (SBool)(this.Children[1].Evaluate(scope));
      return condition ? this.Children[2].Evaluate(scope) : this.Children[3].Evaluate(scope);
    } else if (first.Value == "def") {
      return scope.Define(this.Children[1].Value, this.Children[2].Evaluate(new SScope(scope)));
    } else if (first.Value == "begin") {
      SObject result = null;
      foreach (SExpression statement in this.Children.Skip(1)) {
        result = statement.Evaluate(scope);
      }
      return result;
    } else if (first.Value == "func") {
      SExpression body = this.Children[2];
      String[] parameters = this.Children[1].Children.Select(exp => exp.Value).ToArray();
      SScope newScope = new SScope(scope);
      return new SFunction(body, parameters, newScope);
    } else if (first.Value == "list") {
      return new SList(this.Children.Skip(1).Select(exp => exp.Evaluate(scope)));
    } else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
      var arguments = this.Children.Skip(1).ToArray();
      return SScope.BuiltinFunctions[first.Value](arguments, scope);
    } else {
      SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value);
      var arguments = this.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray();
      return function.Update(arguments).Evaluate();
    }
  }
}

// Recursive factorial.
int fact (int n) {
  if (n == 1)
    return result;
  return n * fact(n - 1);
}
// First tranform to tail recursive version.
int fact (int n, int result) {
  if (n == 1)
    return result;
  else {
    result *= n;
    n -= 1;
    return fact(n, result);// This is a strict tail-recursive call which can be omitted
  }
}
// Then transform to iterative version.
int fact (int n, int result) {
  while (true) {
    if (n == 1)
      return result;
    else {
      result *= n;
      n -= 1;
    }
  }
}

public SObject Evaluate(SScope scope) {
  SExpression current = this;
  while (true) {
    if (current.Children.Count == 0) {
      Int64 number;
      if (Int64.TryParse(current.Value, out number)) {
        return number;
      } else {
        return scope.Find(current.Value);
      }
    } else {
      SExpression first = current.Children[0];
      if (first.Value == "if") {
        SBool condition = (SBool)(current.Children[1].Evaluate(scope));
        current = condition ? current.Children[2] : current.Children[3];
      } else if (first.Value == "def") {
        return scope.Define(current.Children[1].Value, current.Children[2].Evaluate(new SScope(scope)));
      } else if (first.Value == "begin") {
        SObject result = null;
        foreach (SExpression statement in current.Children.Skip(1)) {
          result = statement.Evaluate(scope);
        }
        return result;
      } else if (first.Value == "func") {
        SExpression body = current.Children[2];
        String[] parameters = current.Children[1].Children.Select(exp => exp.Value).ToArray();
        SScope newScope = new SScope(scope);
        return new SFunction(body, parameters, newScope);
      } else if (first.Value == "list") {
        return new SList(current.Children.Skip(1).Select(exp => exp.Evaluate(scope)));
      } else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
        var arguments = current.Children.Skip(1).ToArray();
        return SScope.BuiltinFunctions[first.Value](arguments, scope);
      } else {
        SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value);
        var arguments = current.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray();
        SFunction newFunction = function.Update(arguments);
        if (newFunction.IsPartial) {
          return newFunction.Evaluate();
        } else {
          current = newFunction.Body;
          scope = newFunction.Scope;
        }
      }
    }
  }
}

public static void OrThrows(this Boolean condition, String message = null) {
  if (!condition) { throw new Exception(message ?? "WTF"); }
}

(a < 3).OrThrows("Value must be less than 3.");

static void Main(String[] cmdArgs) {
  new SScope(parent: null)
    .BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s)))
    // Other build
    .BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0)
    .KeepInterpretingInConsole((code, scope) => code.ParseAsIScheme().Evaluate(scope));
}