三目並べは、皆さんお馴染みの二人で対戦するゲームです。ひとりが○側でもうひとりが×側を受け持ち、3 行 3 列のマス目に○×を書いて、3 つ並べた方が勝ちというゲームです。下図は○側が先手で引き分けになった例です。
┌─┬─┬─┐ │×│○│○│ ├─┼─┼─┤ │○│○│×│ ├─┼─┼─┤ │×│×│○│ └─┴─┴─┘ 図 : 三目並べ
三目並べは、両者が最善を尽くすと引き分けになることが知られています。実際、ミニマックス法を使って確かめてみると、初手がどこでも結果は引き分けになります。興味のある方は拙作のページ Puzzle DE Programming 「三目並べ」をお読みくださいませ。
ところで、参考文献『bit別冊 ゲームプログラミング』によると、三目並べで両者が次の戦略を用いると、ゲームは常に引き分けになります。
本当に引き分けになるのか、プログラムを作って確かめてみましょう。
最初に、ゲームに必要なデータ構造を定義します。
┌─┬─┬─┐ │０│１│２│ ├─┼─┼─┤ │３│４│５│ ├─┼─┼─┤ │６│７│８│ └─┴─┴─┘ 図 : 盤面の番号
リスト : データ構造の定義
// 駒の種類
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
確かに引き分けになりますね。興味のある方はいろいろ試してみてください。
//
// 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);
}
小さな小さな Scheme ライクの Lisp インタプリタです。最小の Lisp については、拙作のページ Scheme Programming 「Scheme で作る micro 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