お気楽Ｃ＃プログラミング超入門

簡単なプログラム

●三目並べ

三目並べは、皆さんお馴染みの二人で対戦するゲームです。ひとりが○側でもうひとりが×側を受け持ち、3 行 3 列のマス目に○×を書いて、3 つ並べた方が勝ちというゲームです。下図は○側が先手で引き分けになった例です。

三目並べは、両者が最善を尽くすと引き分けになることが知られています。実際、ミニマックス法を使って確かめてみると、初手がどこでも結果は引き分けになります。興味のある方は拙作のページ Puzzle DE Programming 三目並べをお読みくださいませ。

ところで、参考文献 [1] によると、三目並べで両者が次の戦略を用いると、ゲームは常に引き分けになります。

3 つ並べることができるならばそうする
相手が 3 つ並べるのを妨げる
可能ならば中央へ着手する
可能ならば隅へ着手する

本当に引き分けになるのか、プログラムを作って確かめてみましょう。

●プログラムの作成

最初に、ゲームに必要なデータ構造を定義します。

リスト : データ構造の定義

// 駒の種類
enum Piece {Space, Maru, Batu};

// 盤面
Piece[] board = new Piece[9];

// 直線
int[,] lineTable = new int[8, 3] {
  {0, 1, 2},
  {3, 4, 5},
  {6, 7, 8},
  {0, 3, 6},
  {1, 4, 7},
  {2, 5, 8},
  {0, 4, 8},
  {2, 4, 6},
};

駒の種類を enum で定義します。先手が Maru、後手が Batu、空き場所が Space です。盤面は配列 board で表します。盤面と配列の添字の対応は上図のように定義します。すると、駒が 3 つ並ぶ直線は二次元配列 lineTable で表すことができます。

勝敗の判定は関数 CheckWin() で行います。次のリストを見てください。

リスト : 勝敗の判定

Piece CheckWin() {
  for (int i = 0; i < 8; i++) {
    int x = lineTable[i, 0];
    int y = lineTable[i, 1];
    int z = lineTable[i, 2];
    Piece p = board[x];
    if (p != Piece.Space && board[y] == p && board[z] == p) return p;
  }
  return Piece.Space;
}

関数 CheckWin() は 8 本の直線を調べ、同じ駒が 3 つ並んでいるか調べます。直線の先頭に Maru か Batu があり、残り 2 つの場所に同じ駒があれば 3 つ並んでいることがわかります。Maru が 3 つ並んでいれば Maru を、Batu が 3 つ並んでいれば Batu を返します。どちらも 3 つ並んでいなければ Space を返します。

次は同じ駒を 3 つ並べることができる場所を探す関数 GetWinPosition() を作ります。

リスト : 駒を 3 つ並べられるか

int GetWinPosition(Piece p) {
  for (int i = 0; i < 8; i++) {
    int x = lineTable[i, 0];
    int y = lineTable[i, 1];
    int z = lineTable[i, 2];
    if (board[x] == Piece.Space && board[y] == p && board[z] == p)
      return x;
    else if (board[y] == Piece.Space && board[x] == p && board[z] == p)
      return y;
    else if (board[z] == Piece.Space && board[x] == p && board[y] == p)
      return z;
  }
  return -1;
}

引数 p は駒の種類を表します。空き場所が 1 つあり、残りの 2 か所が p と等しい直線を探します。見つけた場合は空き場所の位置を、見つからない場合は -1 を返します。

次はコンピュータの指し手を決める関数 MoveCom() を作ります。

リスト : コンピュータの指し手を決定する

int MoveCom(Piece turn) {
  // 勝てる場所を探す
  int p = GetWinPosition(turn);
  if (p < 0) {
    // 相手の手番で勝ちがあるか
    p = GetWinPosition(turn == Piece.Maru ? Piece.Batu : Piece.Maru);
    if (p < 0) {
      // 中央が空いているか
      if (board[4] == Piece.Space) {
        p = 4;
      } else {
        // 隅が取れるか
        p = GetCornerPosition();
        if (p < 0) {
          // 空き場所に駒を置く
          p = GetSpacePosition();
        }
      }
    }
  }
  return p;
}

関数 MoveCom() は戦略に従ってコンピュータの指し手を決定します。引数 turn は自分の駒の種類を表します。最初に GetWinPosition() を呼び出して、駒を 3 つ並べることができるか調べます。自分が勝てるのであれば、その場所 p に駒を置きます。そうでなければ、相手が駒を 3 つ並べることができるか調べます。これは GetWinPosition() で相手の駒の種類を渡せば調べることができます。そうであれば、その場所 p に自分の駒をおきます。

それ以外の場合は、優先順位（中央 -> 隅 -> 空き場所) に従って駒を置きます。空いている隅は関数 GetCornerPosition() で求めます。空き場所は関数 GetSpacePosition() で求めます。最後に指し手 p を返します。これで戦略に従ってコンピュータの指し手を決定することができます。

あとはとくに難しいところはないでしょう。詳細はプログラムリストをお読みくださいませ。

●実行結果

それでは実行結果を示します。

$ dotnet script tictactoe.csx
0 1 2
3 4 5
6 7 8

Input> 4
Maru: 4
0 1 2
3 O 5
6 7 8

Batu: 0
X 1 2
3 O 5
6 7 8

Input> 2
Maru: 2
X 1 O
3 O 5
6 7 8

Batu: 6
X 1 O
3 O 5
X 7 8

Input> 3
Maru: 3
X 1 O
O O 5
X 7 8

Batu: 5
X 1 O
O O X
X 7 8

Input> 7
Maru: 7
X 1 O
O O X
X O 8

Batu: 1
X X O
O O X
X O 8

Input> 8
Maru: 8
X X O
O O X
X O O

draw game

$ dotnet script tictactoe.csx
0 1 2
3 4 5
6 7 8

Input> 4
Maru: 4
0 1 2
3 O 5
6 7 8

Batu: 0
X 1 2
3 O 5
6 7 8

Input> 8
Maru: 8
X 1 2
3 O 5
6 7 O

Batu: 2
X 1 X
3 O 5
6 7 O

Input> 1
Maru: 1
X O X
3 O 5
6 7 O

Batu: 7
X O X
3 O 5
6 X O

Input> 5
Maru: 5
X O X
3 O O
6 X O

Batu: 3
X O X
X O O
6 X O

Input> 6
Maru: 6
X O X
X O O
O X O

draw game

確かに引き分けになりますね。興味のある方はいろいろ試してみてください。

●参考文献

松原仁・竹内郁雄編著,『bit別冊ゲームプログラミング』, 共立出版, 1997

●プログラムリスト

//
// tictactoe.csx : 三目並べ
//
//                 Copyright (C) 2016-2022 Makoto Hiroi
//
enum Piece {Space, Maru, Batu};

// 盤面
// 0 1 2
// 3 4 5
// 6 7 8
Piece[] board = new Piece[9];

// 直線
int[,] lineTable = new int[8, 3] {
  {0, 1, 2},
  {3, 4, 5},
  {6, 7, 8},
  {0, 3, 6},
  {1, 4, 7},
  {2, 5, 8},
  {0, 4, 8},
  {2, 4, 6},
};

// コーナーの位置
int[] corner = new int[4] {0, 2, 6, 8};

// 3 個並ぶ場所を返す
int GetWinPosition(Piece p) {
  for (int i = 0; i < 8; i++) {
    int x = lineTable[i, 0];
    int y = lineTable[i, 1];
    int z = lineTable[i, 2];
    if (board[x] == Piece.Space && board[y] == p && board[z] == p)
      return x;
    else if (board[y] == Piece.Space && board[x] == p && board[z] == p)
      return y;
    else if (board[z] == Piece.Space && board[x] == p && board[y] == p)
      return z;
  }
  return -1;
}

// 空いている隅を返す
int GetCornerPosition() {
  foreach(int x in corner) {
    if (board[x] == Piece.Space) return x;
  }
  return -1;
}

// 空いている場所を返す
int GetSpacePosition() {
  for (int i = 0; i < 9; i++) {
    if (board[i] == Piece.Space) return i;
  }
  return -1;
}

// 勝利判定
Piece CheckWin() {
  for (int i = 0; i < 8; i++) {
    int x = lineTable[i, 0];
    int y = lineTable[i, 1];
    int z = lineTable[i, 2];
    Piece p = board[x];
    if (p != Piece.Space && board[y] == p && board[z] == p) return p;
  }
  return Piece.Space;
}

// 終了判定
bool GameOver() {
  Piece p = CheckWin();
  if (p == Piece.Space) {
    return false;
  } else if (p == Piece.Maru) {
    Console.WriteLine("Maru Win!!");
  } else {
    Console.WriteLine("Batu Win!!");
  }
  return true;
}

// コンピュータの差し手を決める
int MoveCom(Piece turn) {
  // 勝てる場所を探す
  int p = GetWinPosition(turn);
  if (p < 0) {
    // 相手の手番で勝ちがあるか
    p = GetWinPosition(turn == Piece.Maru ? Piece.Batu : Piece.Maru);
    if (p < 0) {
      // 中央が空いているか
      if (board[4] == Piece.Space) {
        p = 4;
      } else {
        // 隅が取れるか
        p = GetCornerPosition();
        if (p < 0) {
          // 空き場所に駒を置く
          p = GetSpacePosition();
        }
      }
    }
  }
  return p;
}

// 人間の差し手を決める
int MoveHuman(Piece turn) {
  while (true) {
    Console.Write("Input> ");
    string buff = Console.ReadLine();
    int n;
    if (int.TryParse(buff, out n)) {
      if (0 <= n && n < 9 && board[n] == Piece.Space) return n;
    }
    Console.WriteLine("Please Input Number: 0 - 8");
  }
}

// 盤面の表示
void PrintBoard() {
  for (int i = 0; i < 9; i++) {
    if (board[i] == Piece.Space)
      Console.Write("{0} ", i);
    else if (board[i] == Piece.Maru)
      Console.Write("O ");
    else
      Console.Write("X ");
    if (i % 3 == 2) Console.WriteLine("");
  }
  Console.WriteLine("");
}

void main() {
  Piece turn = Piece.Maru;
  PrintBoard();
  while (!GameOver()) {
    int n = turn == Piece.Maru ? MoveHuman(turn) : MoveCom(turn);
    Console.WriteLine("{0}: {1}", turn, n);
    board[n] = turn;
    turn = turn == Piece.Maru ? Piece.Batu : Piece.Maru;
    PrintBoard();
    if (GetSpacePosition() == -1) {
      Console.WriteLine("draw game");
      break;
    }
  }
}

// 実行
main();

●式の計算 (再帰降下法)

再帰降下法で式 (四則演算とカッコ) を計算するプログラムです。アルゴリズムの詳細は拙作のページ Scheme Programming 電卓プログラムの作成をお読みください。

//
// calc0.csx : 式の計算 (単純な再帰降下法)
//
//             Copyright (C) 2016-2022 Makoto Hiroi
//
using System.Text;

// Calc 用例外クラス
class CalcError : Exception {
  public CalcError(string msg) : base(msg) { }
}

// トークン種別
enum Token {Number, Add, Sub, Mul, Div, Lpar, Rpar, Semic, Others };

char ch;         // 先読みバッファ
Token token;     // トークン
double numValue; // 数値

// 記号の先読み
void NextChar() {
  int c = Console.Read();
  if (c == -1)
    throw new CalcError("EOF");
  ch = (char)c;
}

// 記号の読み込み
char GetChar() {
  return ch;
}

// 整数値の読み込み
void GetFixNumber(StringBuilder sb) {
  while (char.IsDigit(GetChar())) {
    sb.Append(GetChar());
    NextChar();
  }
}

// 数値の読み込み
double GetNumber() {
  double val;
  var sb = new StringBuilder();
  GetFixNumber(sb);
  if (GetChar() == '.') {
    sb.Append(GetChar());
    NextChar();
    GetFixNumber(sb);
  }
  if (GetChar() == 'e' || GetChar() == 'E') {
    sb.Append(GetChar());
    NextChar();
    if (GetChar() == '+' || GetChar() == '-') {
      sb.Append(GetChar());
      NextChar();
    }
    GetFixNumber(sb);
  }
  if (!double.TryParse(sb.ToString(), out val)) {
    throw new CalcError("Not Number");
  }
  return val;
}

// トークンの切り分け
void GetToken() {
  while (char.IsWhiteSpace(GetChar())) {
    NextChar();
  }
  if (char.IsDigit(GetChar())) {
    token = Token.Number;
    numValue = GetNumber();
  } else if (GetChar() == '+') {
    token = Token.Add;
    NextChar();
  } else if (GetChar() == '-') {
    token = Token.Sub;
    NextChar();
  } else if (GetChar() == '*') {
    token = Token.Mul;
    NextChar();
  } else if (GetChar() == '/') {
    token = Token.Div;
    NextChar();
  } else if (GetChar() == '(') {
    token = Token.Lpar;
    NextChar();
  } else if (GetChar() == ')') {
    token = Token.Rpar;
    NextChar();
  } else if (GetChar() == ';') {
    token = Token.Semic;
    NextChar();
  } else {
    token = Token.Others;
  }
}

// 構文解析
double Expr() {
  double val = Term();
  while (true) {
    if (token == Token.Add) {
      GetToken();
      val += Term();
    } else if (token == Token.Sub) {
      GetToken();
      val -= Term();
    } else {
      break;
    }
  }
  return val;
}

// 項
double Term() {
  double val = Factor();
  while (true) {
    if (token == Token.Mul) {
      GetToken();
      val *= Factor();
    } else if (token == Token.Div) {
      GetToken();
      val /= Factor();
    } else {
      break;
    }
  }
  return val;
}

// 因子
double Factor() {
  if (token == Token.Lpar) {
    GetToken();
    double val = Expr();
    if (token != Token.Rpar) {
      throw new CalcError("')' expected");
    }
    GetToken();
    return val;
  } else if (token == Token.Number) {
    GetToken();
    return numValue;
  } else if (token == Token.Add) {
    GetToken();
    return Factor();
  } else if (token == Token.Sub) {
    GetToken();
    return -Factor();
  } else {
    throw new CalcError("unexpected token");
  }
}

// トップレベル
void TopLevel() {
  double val = Expr();
  if (token == Token.Semic) {
    Console.WriteLine(val);
    Console.Write("Calc> ");
  } else {
    throw new CalcError("invalid token");
  }
}

void CalcExec() {
  Console.Write("Calc> ");
  NextChar();
  while (true) {
    try {
      GetToken();
      TopLevel();
    } catch(CalcError e) {
      if (e.Message == "EOF") throw;  // 例外の再送出
      Console.WriteLine(e.Message);
      // 入力のクリア
      while (GetChar() != '\r') {
        NextChar();
      }
      Console.Write("Calc> ");
    }
  }
}

// 実行
try {
  CalcExec();
} catch(CalcError e) {
  Console.WriteLine(e.Message);
}

$ dotnet script calc0.csx
Calc> 1 + 2 + 3 + 4 + 5;
15
Calc> (1 + 2) * (3 - 4);
-3
Calc> 1.11111111 * 1.11111111;
1.234567898765432
Calc> 1 / 7;
0.142857142857143
Calc> -10 * -10;
100
Calc> (1 + 2;
')' expected
Calc> 1 + * 2;
unexpected token
Calc> (終了は CTRL-D を入力してください)

●式の計算 (構文木の構築)

再帰降下法で構文木を構築して式 (四則演算とカッコ) を計算するプログラムです。アルゴリズムの詳細は拙作のページお気楽 SML/NJ プログラミング入門電卓プログラムの作成をお読みください。

//
// calc1.csx : 式の計算 (構文木の構築)
//
//             Copyright (C) 2016-2022 Makoto Hiroi
//
using System.Text;

// Calc 用例外クラス
class CalcError : Exception {
  public CalcError(string msg) : base(msg) { }
}

// 演算子
enum Op {Add, Sub, Mul, Div};

// 構文木
abstract class ExprTree { }

// 単項演算子
class Node1 : ExprTree {
  public Op Operation { get; set; }
  public ExprTree Right { get; set; }

  public Node1(Op op, ExprTree expr) {
    Operation = op;
    Right = expr;
  }
}

// 二項演算子
class Node2 : ExprTree {
  public Op Operation { get; set; }
  public ExprTree Left { get; set; }
  public ExprTree Right { get; set; }

  public Node2(Op op, ExprTree eLeft, ExprTree eRight) {
    Operation = op;
    Left = eLeft;
    Right = eRight;
  }
}

// 数値 (木構造の葉に相当)
class Leaf : ExprTree {
  public double Value { get; set; }
  public Leaf(double val) { Value = val; }
}

// トークン種別
enum Token {Number, Add, Sub, Mul, Div, Lpar, Rpar, Semic, Others };

char ch;         // 先読みバッファ
Token token;     // トークン
double numValue; // 数値

// 記号の先読み
void NextChar() {
  int c = Console.Read();
  if (c == -1)
    throw new CalcError("EOF");
  ch = (char)c;
}

// 記号の読み込み
char GetChar() {
  return ch;
}

// 整数値の読み込み
void GetFixNumber(StringBuilder sb) {
  while (char.IsDigit(GetChar())) {
    sb.Append(GetChar());
    NextChar();
  }
}

// 数値の読み込み
double GetNumber() {
  double val;
  var sb = new StringBuilder();
  GetFixNumber(sb);
  if (GetChar() == '.') {
    sb.Append(GetChar());
    NextChar();
    GetFixNumber(sb);
  }
  if (GetChar() == 'e' || GetChar() == 'E') {
    sb.Append(GetChar());
    NextChar();
    if (GetChar() == '+' || GetChar() == '-') {
      sb.Append(GetChar());
      NextChar();
    }
    GetFixNumber(sb);
  }
  if (!double.TryParse(sb.ToString(), out val)) {
    throw new CalcError("Not Number");
  }
  return val;
}

// トークンの切り分け
void GetToken() {
  while (char.IsWhiteSpace(GetChar())) {
    NextChar();
  }
  if (char.IsDigit(GetChar())) {
    token = Token.Number;
    numValue = GetNumber();
  } else if (GetChar() == '+') {
    token = Token.Add;
    NextChar();
  } else if (GetChar() == '-') {
    token = Token.Sub;
    NextChar();
  } else if (GetChar() == '*') {
    token = Token.Mul;
    NextChar();
  } else if (GetChar() == '/') {
    token = Token.Div;
    NextChar();
  } else if (GetChar() == '(') {
    token = Token.Lpar;
    NextChar();
  } else if (GetChar() == ')') {
    token = Token.Rpar;
    NextChar();
  } else if (GetChar() == ';') {
    token = Token.Semic;
    NextChar();
  } else {
    token = Token.Others;
  }
}

// 構文解析
ExprTree Expr() {
  ExprTree e = Term();
  while (true) {
    if (token == Token.Add) {
      GetToken();
      e = new Node2(Op.Add, e, Term());
    } else if (token == Token.Sub) {
      GetToken();
      e = new Node2(Op.Sub, e, Term());
    } else {
      break;
    }
  }
  return e;
}

// 項
ExprTree Term() {
  ExprTree e = Factor();
  while (true) {
    if (token == Token.Mul) {
      GetToken();
      e = new Node2(Op.Mul, e, Factor());
    } else if (token == Token.Div) {
      GetToken();
      e = new Node2(Op.Div, e, Factor());
    } else {
      break;
    }
  }
  return e;
}

// 因子
ExprTree Factor() {
  if (token == Token.Lpar) {
    GetToken();
    ExprTree e = Expr();
    if (token != Token.Rpar) {
      throw new CalcError("')' expected");
    }
    GetToken();
    return e;
  } else if (token == Token.Number) {
    GetToken();
    return new Leaf(numValue);
  } else if (token == Token.Add) {
    GetToken();
    return new Node1(Op.Add, Factor());
  } else if (token == Token.Sub) {
    GetToken();
    return new Node1(Op.Sub, Factor());
  } else {
    throw new CalcError("unexpected token");
  }
}

// 式の評価
double Eval(ExprTree e) {
  Leaf a = e as Leaf;
  if (a != null) return a.Value;
  Node1 b = e as Node1;
  if (b != null) {
    if (b.Operation == Op.Add)
      return Eval(b.Right);
    else
      return -Eval(b.Right);
  }
  Node2 c = (Node2)e;
  double x = Eval(c.Left);
  double y = Eval(c.Right);
  if (c.Operation == Op.Add)
    return x + y;
  else if (c.Operation == Op.Sub)
    return x - y;
  else if (c.Operation == Op.Mul)
    return x * y;
  else
    return x / y;
}

// トップレベル
void TopLevel() {
  ExprTree e = Expr();
  if (token == Token.Semic) {
    Console.WriteLine(Eval(e));
    Console.Write("Calc> ");
  } else {
    throw new CalcError("invalid token");
  }
}

void CalcExec() {
  Console.Write("Calc> ");
  NextChar();
  while (true) {
    try {
      GetToken();
      TopLevel();
    } catch(CalcError e) {
      if (e.Message == "EOF") throw;    // 例外の再送出
      Console.WriteLine(e.Message);
      // 入力のクリア
      while (GetChar() != '\r') {
        NextChar();
      }
      Console.Write("Calc> ");
    }
  }
}

// 実行
try {
  CalcExec();
} catch(CalcError e) {
  Console.WriteLine(e.Message);
}

実行例は再帰降下法と同じです。

●最小の Lisp

小さな小さな Scheme ライクの Lisp インタプリタです。最小の Lisp については、拙作のページ Scheme Programming Scheme で作る micro Scheme をお読みください。

真偽値は #t, #f ではなく t, nil (Common Lisp と同じ)
空リストも nil
car, cdr, cons, eq?, pair?, quote, if, lambda, define
データ型はシンボル、整数 (BigInteger)、リスト、関数
+, -, *, /, =, <. <=, >, >=
関数定義は (define 名前 (lambda (...) ...))
再帰定義もできる
マクロ、継続、末尾再帰最適化といった Scheme らしい機能はない

//
// mscm.csx : micro Scheme インタプリタ
//
//            Copyright (C) 2016-2022 Makoto Hiroi
//
using System.Text;
using System.Numerics;
using System.Collections.Generic;

// Scheme 用例外クラス
class SchemeError : Exception {
  public SchemeError(string msg) : base(msg) { }
}

// コンスセル
class Cons {
  public object car;
  public object cdr;

  public Cons(object x, object y) {
    car = x;
    cdr = y;
  }
}

// シンボル
class Symbol {
  public string Name { set; get; }
  public object Value { set; get; }

  public Symbol(string s, object val = null) {
    Name = s;
    Value = val;
  }

  public override string ToString() {
    return Name;
  }
}

// シンボル表
Dictionary<string, Symbol> symTable = new Dictionary<string, Symbol>();

// シンボルの生成
Symbol MakeSymbol(string name, object val = null) {
  if (!symTable.ContainsKey(name)) {
    symTable[name] = new Symbol(name, val);
  }
  return symTable[name];
}

// システムシンボル
Symbol sT = MakeSymbol("t");
Symbol sNil = MakeSymbol("nil");
Symbol sQuote = MakeSymbol("quote");
Symbol sDefine = MakeSymbol("define");
Symbol sLambda = MakeSymbol("lambda");
Symbol sIf = MakeSymbol("if");

// 述語
bool Consp(object xs) { return xs is Cons; }
bool Null(object xs) { return xs == sNil; }
bool Symbolp(object xs) { return xs is Symbol; }
bool Numberp(object xs) { return xs is BigInteger; }

// アクセス関数
object Car(object xs) {
  if (!Consp(xs)) {
    throw new SchemeError("Car: pair required");
  }
  return ((Cons)xs).car;
}

object Cdr(object xs) {
  if (!Consp(xs)) {
    throw new SchemeError("Cdr: pair required");
  }
  return ((Cons)xs).cdr;
}

// 数値のチェック
void CheckNumber(object xs) {
  if (!Numberp(Car(xs)) || !Numberp(Car(Cdr(xs))))
    throw new SchemeError("Number required");
}

// 組み込み関数
void MakePrimitive() {
  sT.Value = sT;
  sNil.Value = sNil;
  Func<object, object> car = xs => Car(Car(xs));
  MakeSymbol("car", car);
  Func<object, object> cdr = xs => Cdr(Car(xs));
  MakeSymbol("cdr", cdr);
  Func<object, object> cons = xs => new Cons(Car(xs), Car(Cdr(xs)));
  MakeSymbol("cons", cons);
  Func<object, object> eq = xs => Car(xs) == Car(Cdr(xs)) ? sT : sNil;
  MakeSymbol("eq?", eq);
  Func<object, object> pair = xs => Consp(Car(xs)) ? sT : sNil;
  MakeSymbol("pair?", pair);
  Func<object, object> plus = xs => {
    return (BigInteger)Car(xs) + (BigInteger)Car(Cdr(xs));
  };
  MakeSymbol("+", plus);
  Func<object, object> mult = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) * (BigInteger)Car(Cdr(xs));
  };
  MakeSymbol("*", mult);
  Func<object, object> minus = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) - (BigInteger)Car(Cdr(xs));
  };
  MakeSymbol("-", minus);
  Func<object, object> div = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) / (BigInteger)Car(Cdr(xs));
  };
  MakeSymbol("/", div);
  Func<object, object> equal = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) == (BigInteger)Car(Cdr(xs)) ? sT : sNil;
  };
  MakeSymbol("=", equal);
  Func<object, object> notEqual = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) != (BigInteger)Car(Cdr(xs)) ? sT : sNil;
  };
  MakeSymbol("/=", notEqual);
  Func<object, object> lt = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) < (BigInteger)Car(Cdr(xs)) ? sT : sNil;
  };
  MakeSymbol("<", lt);
  Func<object, object> le = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) <= (BigInteger)Car(Cdr(xs)) ? sT : sNil;
  };
  MakeSymbol("<=", le);
  Func<object, object> gt = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) > (BigInteger)Car(Cdr(xs)) ? sT : sNil;
  };
  MakeSymbol(">", gt);
  Func<object, object> ge = xs => {
    CheckNumber(xs);
    return (BigInteger)Car(xs) >= (BigInteger)Car(Cdr(xs)) ? sT : sNil;
  };
  MakeSymbol(">=", ge);
}

// 先読みバッファ
char ch;

// 記号の先読み
void NextChar() {
  int c = Console.Read();
  if (c == -1)
    throw new SchemeError("EOF");
  ch = (char)c;
}

// 記号の読み込み
char GetChar() {
  return ch;
}

// 数値の読み込み
BigInteger GetNumber() {
  var sb = new StringBuilder();
  BigInteger val;
  do {
    sb.Append(GetChar());
    NextChar();
  } while (char.IsDigit(GetChar()));
  if (!BigInteger.TryParse(sb.ToString(), out val)) {
    throw new SchemeError("Number required");
  }
  return val;
}

// Symbol に含めてよい記号
bool IsSymbol(char c) {
  string symCode = "!&*+-/:<=>?@^_~";
  return char.IsLetter(GetChar()) || symCode.IndexOf(GetChar()) > 0;
}

// Symbol の読み込み
Symbol GetSymbol() {
  var sb = new StringBuilder();
  do {
    sb.Append(GetChar());
    NextChar();
  } while (IsSymbol(GetChar()) || char.IsDigit(GetChar()));
  return MakeSymbol(sb.ToString());
}

// 空白文字をスキップ
void SkipSpace() {
  while (char.IsWhiteSpace(GetChar())) {
    NextChar();
  }
}

// リストの読み込み
object ReadList() {
  SkipSpace();
  if (GetChar() == ')') {
    NextChar();
    return sNil;
  } else if (GetChar() == '.') {
    NextChar();
    object x = ReadS();
    SkipSpace();
    if (GetChar() != ')') {
      throw new SchemeError("invalid dot list");
    }
    NextChar();
    return x;
  } else {
    return new Cons(ReadS(), ReadList());
  }
}

// S 式の読み込み
object ReadS() {
  SkipSpace();
  char c = GetChar();
  if (char.IsDigit(c)) { // || c == '+' || c == '-') {
    return GetNumber();
  } else if (IsSymbol(GetChar()) ){
    return GetSymbol();
  } else if (GetChar() == '\'') {
    NextChar();
    return new Cons(sQuote, new Cons(ReadS(), sNil));
  } else if (GetChar() == '(') {
    NextChar();
    return ReadList();
  } else {
    throw new SchemeError("invalid token");
  }
}

// S 式の出力
void PrintS(object xs) {
  if (Consp(xs)) {
    Console.Write("(");
    while (Consp(xs)) {
      if (Consp(Car(xs))) {
        PrintS(Car(xs));
      } else {
        Console.Write("{0}", Car(xs));
      }
      if (!Null(Cdr(xs))) Console.Write(" ");
      xs = Cdr(xs);
    }
    if (!Null(xs)) Console.Write(". {0}", xs);
    Console.Write(")");
  } else {
    Console.Write("{0}", xs);
  }
}

// 環境
class Env {
  public Symbol Key { get; set; }
  public object Value { get; set; }
  public Env Next { get; set; }

  public Env(Symbol k, object v, Env n) {
    Key = k;
    Value = v;
    Next = n;
  }

  public object Assoc(Symbol key) {
    Env xs = this;
    while (xs != null) {
      if (xs.Key == key) return xs.Value;
      xs = xs.Next;
    }
    return null;
  }
}

// 変数の値を求める
object Lookup(Symbol key, Env env) {
  object val = env != null ? env.Assoc(key) : null;
  if (val == null) {
    if (key.Value == null)
      throw new SchemeError("unbound variable");
    else
      return key.Value;
  }
  return val;
}

// クロージャ
class Closure {
  public object Args { set; get; }
  public object Body { set; get; }
  public Env    Cenv { set; get; }
  public Closure(object a, object b, Env e) {
    Args = a;
    Body = b;
    Cenv = e;
  }
}

// 引数の評価
object EvalArguments(object xs, Env env) {
  if (Null(xs)) {
    return sNil;
  } else {
    return new Cons(EvalS(Car(xs), env), EvalArguments(Cdr(xs), env));
  }
}

// 変数束縛
Env AddBinding(object xs, object args, Env env) {
  while (Consp(xs) && Consp(args)) {
    env = new Env((Symbol)Car(xs), Car(args), env);
    xs = Cdr(xs);
    args = Cdr(args);
  }
  if (!Null(xs) || !Null(args)) {
    throw new SchemeError("wrong number of arguments");
  }
  return env;
}

// 本体の評価
object EvalBody(object xs, Env env) {
  object result = sNil;
  while (Consp(xs)) {
    result = EvalS(Car(xs), env);
    xs = Cdr(xs);
  }
  return result;
}

object ApplyS(object fn, object args) {
  if (fn is Delegate) {
    // 組み込み関数
    return ((Func<object, object>)fn)(args);
  } else if (fn is Closure) {
    // クロージャ
    Closure c = (Closure)fn;
    return EvalBody(c.Body, AddBinding(c.Args, args, c.Cenv));
  } else {
    throw new SchemeError("Function required");
  }
}

// 特殊形式
object DefineS(object xs, Env env) {
  if (!Symbolp(Car(xs)) || Null(Cdr(xs)))
    throw new SchemeError("invalid define form");
  ((Symbol)Car(xs)).Value = EvalS(Car(Cdr(xs)), env);
  return Car(xs);
}

object IfS(object xs, Env env) {
  if (Consp(xs) && Consp(Cdr(xs))) {
    object result = EvalS(Car(xs), env);
    if (result != sNil) {
      return EvalS(Car(Cdr(xs)), env);
    } else if (Consp(Cdr(Cdr(xs)))) {
      return EvalS(Car(Cdr(Cdr(xs))), env);
    } else {
      return sNil;
    }
  } else {
    throw new SchemeError("invalid if form");
  }
}

// S 式の評価
object EvalS(object xs, Env env) {
  if (Numberp(xs)) {
    return xs;
  } else if (Symbolp(xs)) {
    return Lookup((Symbol)xs, env);
  } else if (Consp(xs)) {
    // 特殊形式のチェック
    if (Car(xs) == sQuote) {
      return Car(Cdr(xs));
    } else if (Car(xs) == sDefine) {
      return DefineS(Cdr(xs), env);
    } else if (Car(xs) == sIf) {
      return IfS(Cdr(xs), env);
    } else if (Car(xs) == sLambda) {
      return new Closure(Car(Cdr(xs)), Cdr(Cdr(xs)), env);
    } else {
      // 関数呼び出し
      object fn = EvalS(Car(xs), env);
      return ApplyS(fn, EvalArguments(Cdr(xs), env));
    }
  } else {
    throw new SchemeError("EvalS: invalid object");
  }
}

// トップレベル
void TopLevel() {
  Console.Write("mscm> ");
  NextChar();
  while (true) {
    try {
      PrintS(EvalS(ReadS(), null));
      Console.WriteLine("");
    } catch(SchemeError e) {
      if (e.Message == "EOF") throw;
      Console.WriteLine(e.Message);
      // 入力のクリア
      while (GetChar() != '\r') {
        NextChar();
      }
    }
    Console.Write("mscm> ");
  }
}

// 実行
try {
  MakePrimitive();
  TopLevel();
} catch(SchemeError e) {
  Console.WriteLine(e.Message);
}

$ dotnet script mscm.csx
mscm> 'a
a
mscm> 12345
12345
mscm> '(1 2 3 4 5)
(1 2 3 4 5)
mscm> (car '(a b c))
a
mscm> (cdr '(a b c))
(b c)
mscm> (cons 'a 'b)
(a . b)
mscm> (pair? '(a b c))
t
mscm> (pair? 'a)
nil
mscm> (eq? 'a 'a)
t
mscm> (eq? 'a 'b)
nil
mscm> (define a 10)
a
mscm> a
10
mscm> (define square (lambda (x) (* x x)))
square
mscm> (square 123)
15129
mscm> ((lambda (x) (* x x)) 10)
100
mscm> (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
fact
mscm> (fact 10)
3628800
mscm> (fact 20)
2432902008176640000
mscm> (fact 50)
30414093201713378043612608166064768844377641568960512000000000000
mscm> (define iota (lambda (n m) (if (> n m) nil (cons n (iota (+ n 1) m)))))
iota
mscm> (iota 1 10)
(1 2 3 4 5 6 7 8 9 10)
mscm> (define map (lambda (f xs) (if (pair? xs)
(cons (f (car xs)) (map f (cdr xs))))))
map
mscm> (map (lambda (x) (* x x)) (iota 1 20))
(1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400)
mscm> (define foo (lambda (x) (lambda (y) (+ x y))))
foo
mscm> (define foo100 (foo 100))
foo100
mscm> (foo100 100)
200
mscm> (foo100 1000)
1100

初版 2016 年 10 月
改訂 2022 年 2 月 12 日

C# Programming