キーワード
インタープリタ, C#, Scheme, 関数型プログラミング
について
この記事では、Schemeの方言であるiSchemeとそのインタプリタをC#で実装する方法を説明します。
a.k.a. Luc
このチュートリアルをモバイルデバイスで読んでいる場合、またはこの記事のコードがフォントサイズとして小さすぎると思われる場合は、読みやすくするためにリンクご利用ください。
ヒント
以下にご興味のある方は、ぜひご連絡ください：
- 基本的な字句解析、構文解析、抽象構文木の生成。
- ネストされたスコープと関数呼び出しの実装
- 通訳の基礎。
- C#プログラミングのヒント
では、続きをお読みください。
以下にご興味のある方は、ぜひご連絡ください：
- 高度な語彙／文法分析テクニック
- 型派生/分析。
- ターゲットコードの最適化。
この記事はちょっと初歩的過ぎるので読み飛ばしてもらっても構いませんが、この記事の間違いは遠慮なく指摘してください :-)
コードサンプル
コード例
public static int Add(int a, int b) {
return a + b;
}
>> Add(3, 4)
>> 7
>> Add(5, 5)
>> 10
このコードは関数を定義し、次の行の値の次の記号は、改行で区切られた異なる値の結果の値の最後の行を示します。これは、コンソールのプロンプトとして解釈することができます。
インタプリタとは
インタープリタ、上記のように、プログラムを読み込んでその結果を直接出力することができるプログラムの一種です。コンパイラ対照的に、インタープリタターゲットとなるマシン・コードを生成せず、簡単に言えばソース・プログラムを直接実行します：
電卓は典型的なインタプリタであり、数式を与えると内部の「インタプリタ」を実行して答えを出します。
iSchemeプログラミング言語
iSchemeとは何ですか？
- Scheme言語の最小限のサブセット。
- 小さいとはいえ、変数、算術|比較|論理演算、リスト、関数、再帰といったプログラミング言語の要素はすべて揃っています。
- 非常に、非常に遅い。この記事のコンセプトを実証するためだけに存在していると言えるかもしれません。
では、スキームとは？
- 関数型プログラミング言語。
- Lisp方言。
- MITのプログラミング入門コースで使用されている言語。
- MIT 6.100使います。
- 詳しくはSchemeプログラミング言語をご覧ください。
階乗を計算する例を見てみましょう：
C#版階乗
public static int Factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * Factorial(n - 1);
}
}
iScheme版階乗
(def factorial (lambda (n) (
if (= n 1)
1
(* n (factorial (- n 1))))))
数値型
iScheme はあくまでデモンストレーション用の言語なので、現在のところ整数しかサポートしていません。
変数の定義
iScheme はキーワードを使って変数を定義します。
>> (def a 3)
>> 3
>> a
>> 3
算術|論理|比較
一般的なプログラミング言語とは異なり、Schemeはポーランド語の表現、すなわち接頭辞表現を用います。例えば
C#の算術|論理|比較演算
// Arithmetic ops
a + b * c
a / (b + c + d)
// Logical ops
(cond1 && cond2) || cond3
// Comparing ops
a == b
1 < a && a < 3
対応するiSchemeコード
; Arithmetic ops
(+ a (* b c))
(/ a (+ b c d))
; Logical ops
(or (and cond1 cond2) cond3)
; Comparing ops
(= a b)
(< 1 a 3)
注意すべき点
- iSchemeの演算子は2つ以上の引数を取ることができます - これは括弧の数をある程度コントロールします。
- iSchemeのロジック操作では、一般的なandの代わりに、andを使用します。
シーケンシャルステートメント
iSchemeはキーワードを使って連続するステートメントを識別し、最後のステートメントの値を結果として返します。2つの数値の平均を求める例を見てみましょう：
C#の逐次文
int a = 3;
int b = 5;
int c = (a + b) / 2;
iSchemeのシーケンシャル・ステートメント
(def c (begin
(def a 3)
(def b 5)
(/ (+ a b) 2)))
制御フロー操作
iSchemeの制御フロー操作には、以下のものしか含まれていません。
if文の例
>> (define a (if (> 3 2) 1 2))
>> 1
>> a
>> 1
リストタイプ
iSchemeはキーワードを使ってリストを定義し、リストの最初の要素を取得するためのキーワードを提供します。
iSchemeのリストの例
>> (define alist (list 1 2 3 4))
>> (list 1 2 3 4)
>> (first alist)
>> 1
>> (rest alist)
>> (2 3 4)
関数の定義
iScheme はキーワードを使って関数を定義します：
iSchemeの関数定義
(def square (func (x) (* x x)))
(def sum_square (func (a b) (+ (square a) (square b))))
対応するC#コード
public static int Square (int x) {
return x * x;
}
public static int SumSquare(int a, int b) {
return Square(a) + Square(b);
}
再帰
iSchemeにはそのような命令型言語のループ構造がないので、繰り返しの操作には再帰が唯一の選択肢になります。
最大公約数の計算の例を見てみましょう：
iScheme は最大公約数を計算します。
(def gcd (func (a b)
(if (= b 0)
a
(func (b (% a b))))))
対応するC#コード
public static int GCD (int a, int b) {
if (b == 0) {
return a;
} else {
return GCD(b, a % b);
}
}
#p#
高階関数
Schemeと同様、iSchemeでも関数はヘッドオブジェクトです：
- 変数を関数として定義することも可能です。
- 関数は引数として関数を取ることができます。
- 関数は関数を返します。
iSchemeの高階関数の例
; 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)
要約
iSchemeの紹介は以上ですが、実はiSchemeの要素はこれだけです。 -_-
メインイベント、iSchemeインタプリタをゼロから構築する作業に移ります。
インタープリタのコンストラクト
iSchemeインタプリタは、解析と評価の2つの主要な部分に分かれています：
- 構文解析：ソース・プログラムを解析し、インタプリタが理解できる中間構造を生成します。この部分には、字句解析、構文解析、意味解析、構文木の生成が含まれます。
- 値：構文解析フェーズで得られた中間構造を実行し、実行結果を取得します。この部分には、スコープ、型システムの設計、構文木のトラバーサルが含まれます。
語彙分析
字句解析は、ソース・プログラムを個々の字句単位に解析し、後の処理に役立てます。
iSchemeの字句解析は非常にシンプルで、iSchemeの字句要素には括弧、空白、数字、変数名しか含まれていないので、C#に付属しているもので十分です。
iSchemeの語彙分析とテスト
public static String[] Tokenize(String text) {
String[] tokens = text.Replace("(", " ( ").Replace(")", " ) ").Split(" \t
".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', ')', ')']
銘記
- 個人的にはstaticメソッドは好きではないので、C#のSchemeプログラミング言語使ったString型の拡張を紹介します。
- 個人的には、LINQ構文よりもLINQ拡張メソッドの方が好きなので、この後のコードはすべてこのスタイルになります。
- 字句解析はとんでもなく簡単だと思わないでください！vczhのポーランド語の表現、完全なプログラミング言語の字句解析のチュートリアルを提供します。
構文ツリー生成
レンマを得たら、次は構文解析です。しかし、Lispライクな言語のプログラムは構文木なので、構文解析は直接省略することができます。
次のプログラムを例にとってみましょう：
構文木としての手続き
;
(def x (if (> a 1) a 1))
; この言葉を別の角度から見てみよう：
(
def
x
(
if
(
>
a
1
)
a
1
)
)
より視覚的な写真：
このため、iSchemeの構文木を定義する型を使用して、拡張メソッド非常に簡単に構築できます。
抽象構文木の定義
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];
}
銘記
- 語彙解析チュートリアル使用することで、サンプルコードの重複を避けることができます。
- 抽象構文ツリー使用すると、コードの可読性が向上します。
- コードの流暢性を向上させるためのS Expression使用：流暢性以上。
- ほとんどのプログラミング言語の構文解析は、それほど単純ではありません！C#のようなプログラミング言語を実装するつもりなら、より強力な構文解析技術が必要です：
スコープ
iScheme はネストされた自動属性使用します。
次のプログラムを例にとってみましょう。
>> (def x 1)
>> 1
>> (def y (begin (def x 2) (* x x)))
>> 4
>> x
>> 1
iSchemeのスコープは、C#が提供する型を使って簡単に実装できます：
iSchemeの実装範囲
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;
}
}
タイプの実装
iSchemeの型システムは非常にシンプルで、Numeric、Bool、List、Functionだけです。 iSchemeの内部では、これらはすべて値オブジェクトであることを考慮し、統一的な方法でこれらを扱うために、ここに統一的な親型を示します：
public class SObject { }
数値型
iSchemeの数値型は、.NETの数値型を単純にカプセル化したものです：
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);
}
}
ここではC#のパラメータの命名使われていることに注意してください：
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);
便宜上、SObjectの拡張メソッドここに追加されています：
public class SObject {
...
public static implicit operator SObject(Int64 value) {
return (SNumber)value;
}
}
Bool
Bool型はTrueとFalseだけなので、staticオブジェクトを使えば十分です。
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;
}
}
ここでもC#の暗黙の演算子オーバーローディングが使われており、これが可能になっています：
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;
}
}
#p#
リストタイプ
iSchemeは.NETの実装リスト型を使っています：
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();
}
}
一度実装すれば、様々なLINQ拡張メソッドを直接使用することが簡単になります。
関数の種類
iSchemeの関数型（）は3つの部分から構成されています：
- 機能本体：すなわち、カウンターパート。
- パラメータリスト。
- スコープ: 関数には独自のスコープがあります。
SF関数の実装
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();
}
}
注意点
- iSchemeは部分評価をサポートしています：
部分評価
>> (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
- そのため、iScheme の理解とテストが非常に簡単になります。
組み込み操作
iSchemeには、算術演算、論理演算、比較演算、リスト演算の4つの組み込み演算があります。
組み込み操作を定義するために、私は表現力豊かなラムダ・メソッド表を選びました：
まず、静的フィールドと、それに対応するアクセスプロパティとアクションメソッドを
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;
}
}
注目してください：
- は、C#が提供するデリゲート型です。
- ここでは、スムーズなAPIセットを実現するために、サンプルメソッドを使って静的メンバを変更するちょっとしたHACKを紹介します。
次のステップは、この方法でビルトインオペレーションを定義することです：
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"); }
}
そこから、流暢なアサーションを書くことができます：
(a < 3).OrThrows("Value must be less than 3.");
よりも
if (a < 3) {
throw new Exception("Value must be less than 3.");
}
算術操作
iScheme の算術演算には、数値型にのみ適用される 5 つの演算があります。
足し算と引き算から始めましょう：
.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];
})
ロジック操作
iSchemeのロジック操作には、and、すなわちwith、またはwithoutがあります。
iSchemeロジックの操作は、暗黙の演算子オーバーロード、つまり
- もし偽なら、式全体が偽となり、ペアの評価は必要ありません。
- もしtrueなら、式全体がtrueとなり、ペアを評価する必要はありません。
加えて、同様に、and はいくつでも引数を取ることができます。
iSchemeの論理演算は以下のように実装されています：
.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);
})
操作の比較
iSchemeの比較操作の注意点は以下の通りです：
- は代入操作ではなく比較操作です。
- 算術演算と同様、数値型に適用され、任意の数の引数をサポートします。
実現は以下の通り：
.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))
オーバーロードがないので、この2つを直接比較することはできません。
リスト操作
The list operations of iScheme include , , and , which are used to take the first element of a list, the parts of the list other than the first one, to determine whether the list is empty and to splice the list, respectively.
で、次のように操作します：
.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)
テスト
iSchemeの組み込み操作が完了したら、最初の結果をテストしましょう。
まず、コンソールベースの分析/値ループを追加します：
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 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);
}
}
}
この解釈と価値のサイクルが最終的に呼び込まれます：
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));
}
プログラムを実行し、いくつかの簡単な式を入力します：
美味しそう）
次にiSchemeの実行ロジックの実装を始めます。
#p#
実行ロジック
iSchemeの実行は、以下のように、ステートメントをスコープでオブジェクトに変換し、スコープに作用させるプロセスです。
iSchemeの実行ロジックは内部にあります：
public class SExpression {
// ...
public override SObject Evaluate(SScope scope) {
// TODO: Todo your ass.
}
}
まず、インプットとアウトプットを明確にします：
- 処理：
- 処理：
- 処理：
- 処理：
- 処理：
- 名前付き関数呼び出し：
- カスタム関数の呼び出しを処理します：
また、ケース1とケース2には子ノードがなく、直接読み込んで評価することができますが、残りのケースは評価のために読み込む必要があります。
子ノードがない場合は最初に処理されます：
文字量と名目量の取り扱い
if (this.Children.Count == 0) {
Int64 number;
if (Int64.TryParse(this.Value, out number)) {
return number;
} else {
return scope.Find(this.Value);
}
}
子ノードの場合は次に説明します：
まず、現在のノードの最初のノードを取得します：
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).Select(node => node.Evaluate(scope)).ToArray();
return SScope.BuiltinFunctions[first.Value](arguments, scope);
}
カスタム関数呼び出しの処理
カスタム関数呼び出しには2つのケースがあります：
- 非名称関数呼び出し：
- 名前付き関数呼び出し：
カスタム関数は新しいスコープで呼び出す必要があります：
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);
}
カスタムスコープの作成を容易にし、関数の引数に値が割り当てられているかどうかを判断するために、addとmethod：
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).Select(node => node.Evaluate(scope)).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();
}
}
}
末尾再帰の削除
この時点でiSchemeインタープリターは完成です。しかし、評価プロセスをよく見ると、末尾の再帰呼び出しにはまだ大きな問題があります：
- 処理のための再帰呼び出しの末尾。
- 関数呼び出しにおける末尾再帰呼び出しの処理。
アレックス・ステパノフは『暗黙の演算子オーバーロード中で、厳密な末尾再帰呼び出しを反復に変換する方法を説明しています：
// 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 {
n -= 1;
result *= 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 {
n -= 1;
result *= 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).Select(node => node.Evaluate(scope)).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;
}
}
}
}
}
#p#
いくつかのデモ
しそくえんざん
(高次関数
レビュー
要約
これらの300行以上のコードには、関数型プログラミング言語のほとんどの機能が実装されています：算術|論理|演算、入れ子スコープ、逐次文、制御文、再帰、Fluent Interface、部分評価。
私が2年前から実装しているScheme方言の比べると、iSchemeは文字列型を持たない以外はLucidaと同じ機能を持ちながら、コード量は前者の8分の1、記述時間は前者の10分の1、拡張性と可読性は前者を凌駕しています。これで説明がつきます：
- コードの量だけではわかりません。
- 開発者によって生産性に大きな差が出ることがあります。
- それでもこの2年で少しは勉強になりました。-_-
いくつかの設計上の決定
拡張メソッドによる可読性の向上
例えば
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));
}
非常に直感的で
- 新しい操作を追加する必要がある場合は、書き込み行を追加するだけです。
- 別の構文を使用する必要がある場合は、パーサー関数を置き換えるだけです。
- ファイルからコードを読み込む必要がある場合は、実行関数を置き換えるだけです。
不十分
もちろん、iSchemeにはまだ不満が残ります：
言語的アイデンティティの側面：
- 実用的な型がない：複合型はおろか、この2つの重要な型もありません。
- ネットワーク通信はおろか、IO操作もありません。
- 非効率：末尾再帰を削除することで少しは効率が改善されましたが、iSchemeの実行効率は依然としてひどいものです。
- エラーメッセージ：エラーメッセージは基本的に読めません。
- 継続通話には対応していません。
- 注釈はありません。
- 様々なバグ：例えば、テキスト量を定義できる、デフォルトの操作をオーバーロードできない、空の括弧が認識される、など。
デザイン実現の側面：
それは後にとっておきます。
拡張読書
書籍
- Engineering a compiler:
- Flex & Bison:
- *Writing Compilers and Interpreters:
- Elements of Programming:
- How to write a lisp interpreter in Python: .html
- An even better lisp interpreter in Python: .html
- プログラミングの要素:
印は中国語訳がありません。
記事
フロントエンドのコンパイルが主な仕事で、バックエンドを自分で作業する時間も能力もありません。-_-
- Pythonでlispインタプリタを書く方法:
- "2900"/03/20/a-recursive-descent-parser-with-an-infix-expression-evaluator/
簡単で実用的な文法分析テクニックをいくつかご紹介します：
- LL(k) 構文解析：
- トップダウン・オペレーター・プレセンデンス
- プリセンデンスクライミング構文解析
かつてはWindows/.Net/C#のプログラマーでしたが、大学院卒業後はLinux/Javaの開発者になりました。Javaは一度ハマると深海のようなものということわざがあるように、今はC#を使っていた年月がとても懐かしいです。
インタプリタ／コンパイラに興味があり、Courseraのコンパイラ独学中。
技術交流への書き込み歓迎： lunageek#gmail#com
