先日、プログラミング言語を作る。１時間で。
という記事を投稿したところ、予想もしていなかったほど多くのストックや、
「俺も○○言語で俺言語を作ってみた！」のような反応を頂きました。
とても嬉しいので、調子に乗って続編を書きます。
前回は、言語らしきものをとにかく「１時間以内に作る」ことを念頭において書きました。
今回は、もう１時間を追加して、関数定義、変数スコープ、高階関数、クロージャといった題材で、orelang(俺言語)を拡張していきます。
では、はじめましょう。とりあえず、リポジトリはこちらです。
S式っぽく書けるようにする：所要時間5分
前回の記事で作成した、 1 + 2 + (4 * 5) を計算する orelang のコードは、以下のようなものでした。
["+", 1, 2, ["*", 3, 4]]
お世辞にもこれは、書きやすいとはいえません。
このような書き方になったのは、orelangが構文解析にJSONライブラリを利用する前提になっているためです。
本当は、次のようにS式風に書きたいですよね。
(+ 1 2 (* 3 4))
というわけで、この俺式S式からJSONへ変換するトランスパイラを用意することにします。
ここは、@alpha_kai_NET様の記事を参考にさせてもらいました。
package orelang;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import net.arnx.jsonic.JSON;
public class Transpiler {
public static Object transpile(Reader reader) throws IOException{
StringBuilder builder = new StringBuilder();
BufferedReader br = new BufferedReader(reader);
String l;
while ((l = br.readLine()) != null){
builder.append(l).append("\n");
}
return transpile(builder.toString());
}
public static Object transpile(String script){
String s = script;
s = s.replaceAll(";.*", "");
s = s.replaceAll("\\(\\s*", "[");
s = s.replaceAll("\\s*\\)", "]");
s = s.replaceAll("\n", "");
s = s.replaceAll("^\\s+", "");
s = s.replaceAll("\\s+$", "");
s = s.replaceAll("\\s+", ", ");
s = s.replaceAll("[+*=](?=[, \\]])", "\"$0\"");
s = s.replaceAll("[a-zA-Z_][a-zA-Z0-9_]*", "\"$0\"");
return JSON.decode(s);
}
}
以下のような書き方で、orelangを実行できるようになります。
Engine engine = new Engine();
Object result = engine.eval(Transpiler.transpile("(+ 1 2 (* 3 4))"));
System.out.println(result);
横着せずに構文解析ライブラリの使い方を学べ、という意見も。ごもっともです。
シンボルの評価：所要時間10分
トランスパイラによって、"+" と書く代わりに + と書けるようになりました。
つまり、オペレータ名や変数名をシンボルっぽく書けるようになったのです。
それはいいのですが、じゃあ文字列とシンボルはどう区別するんだ？という話になってきます。。。うーむ。
よろしい。ならば割り切ってしまおう。orelangでは文字列は扱えません。
だいたい、文字列を扱うオペレータもないんだし。文字列などない。
数値以外はシンボルしかなく、さらにシンボルとは常に変数名なので、評価されると代入されている値を返すようにしましょう。
つまり、以下のコードは
(step
(set v 5)
(* (get v) (get v)))
次のコードと等価なものとして評価することにします。
(step
(set v 5)
(* v v))
念のために書いておくと、これはコードの書き方をちょっと楽にするだけのシュガー（構文糖）にすぎないという見方もできるでしょう。
本筋とは関係なさそうだし、ほっとけば？と思われるかもしれませんが、後々実現しようと思っている高階関数との兼ね合いを考えて対応することにします。
((get +) 1 1)とは、さすがに書きたくないですよね。
では、コードを修正していきます。
これまで、オペレータ呼び出しと即値しかなかった式(IExpression)に、新しくシンボル値(SymbolValue)を追加します。
package orelang.expression;
import orelang.Engine;
public class SymbolValue implements IExpression {
private String symbol;
public SymbolValue(String symbol){
this.symbol = symbol;
}
@Override
public Object eval(Engine engine) {
return engine.variables.get(symbol);
}
}
シンボルを表す文字列(symbol)を保持し、評価されると対応する変数値を返すという実装です。
続いて、EngineクラスのgetExpressionメソッドを、以下のように修正します。
private IExpression getExpression(Object script){
if (script instanceof List){
List<?> scriptList = (List<?>)script;
return new CallOperator(
operators.get(scriptList.get(0)),
scriptList.subList(1, scriptList.size()));
}else if (script instanceof String){
return new SymbolValue((String)script);
}else{
return new ImmediateValue(script);
}
}
文字列ならばシンボル値(SymbolValue)にします。
さて、以上の対応で十分のような気もしますが。。。
実は、SetOperatorとGetOperatorも修正する必要があります。なぜか？
例えば (set v 5) という式を評価する場合、 v というシンボルは、値が代入される前に評価されてしまうのです。
これは、前回の記事でそう実装してしまったからです。失敗した。。。
それぞれ、以下のように修正してください。
public class SetOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
Object value = engine.eval(args.get(1));
// args.get(0) にかかってた engine.eval() を外す
engine.variables.put((String)args.get(0), value);
return value;
}
}
public class GetOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
// args.get(0) にかかってた engine.eval() を外す
return engine.variables.get(args.get(0));
}
}
シンボルを書けば変数への参照が行える以上、もう GetOperator はいらない子？とも思えますが、残しておいてください。この記事の最後に、とある使い方をします。
さて、ここまでの修正で、前回記事でも紹介した1から10の和を計算するコードは、以下のようにだいぶ読みやすい形に書き直せます。
(step
(set i 10)
(set sum 0)
(until (= i 0)
(step
(set sum (+ sum i))
(set i (+ i -1))))
(print sum))
これを実行すると、結果として 55 を返します。
ここでひそかに、printオペレータを追加しています。実装は以下のように簡単です。
package orelang.operator;
import java.util.List;
import orelang.Engine;
public class PrintOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
Object value = engine.eval(args.get(0)).toString();
System.out.println(value);
return value;
}
}
標準出力に、引数の値を出力するだけです。
Engineクラスの operators マップへ print という名前で登録しておきます。(コードは割愛)
オペレータ（関数）を第1級オブジェクトにする：所要時間10分
ここまでの修正で、orelangの読み書きはかなり行いやすくなりました。
が、この記事はそんなことのために書いたのではありません。本番はここからです。
次は、オペレータを第１級オブジェクトにします。
オペレータ（ここでは関数と呼びます）を、第１級オブジェクトにするとは、
関数を、数値や文字列（orelangでは扱えませんが）などの値と分け隔てなく扱えるようにするということを意味します。
例えば、関数を変数に代入することや、関数を他の関数の引数や戻り値にすることができるようになります（こうした関数を高階関数と呼びます）。
これが可能になると、orelangの表現力はぐっと向上するはずです。
ではさっそく、作業に移りましょう。
Engineクラスのコードを、以下のように書き換えます。
public class Engine {
// operatorsマップは廃止。variablesで全てを一元管理する。
public Map<String, Object> variables = new HashMap<String, Object>();
public Engine(){
variables.put("+", new AddOperator());
variables.put("*", new MultiplyOperator());
variables.put("=", new EqualOperator());
variables.put("set", new SetOperator());
variables.put("get", new GetOperator());
variables.put("until", new UntilOperator());
variables.put("step", new StepOperator());
variables.put("print", new PrintOperator());
}
public Object eval(Object script){
return getExpression(script).eval(this);
}
private IExpression getExpression(Object script){
if (script instanceof List){
List<?> scriptList = (List<?>)script;
return new CallOperator(
scriptList.get(0), // オペレータオブジェクトに変換せずに渡す。
scriptList.subList(1, scriptList.size()));
}else if (script instanceof String){
return new SymbolValue((String)script);
}else{
return new ImmediateValue(script);
}
}
}
これまで、Engineクラス内では、variablesというマップで変数を管理し、operatorsというマップでオペレータを管理していました。
しかし、今後は両者を区別することはできません。
operatorsメンバを削除し、variablesで一元管理するようにします。オペレータもvariablesに登録するように修正します。
さらに、getExpressionメソッド内では、CallOperatorのコンストラクタにオペレータの実装オブジェクトを渡すのではなく、リストの最初の要素をそのまま渡すように修正します。
これは、どのオペレータが呼び出されるかが、評価時に決定されるようにするためです。
続いて、CallOperatorクラスを以下のように書き換えます。
public class CallOperator implements IExpression {
private Object operator;
private List<?> args;
public CallOperator(Object operator, List<?> args){
this.operator = operator;
this.args = args;
}
@Override
public Object eval(Engine engine) {
// evalが呼ばれてから、オペレータオブジェクトを取得し call する。
IOperator op = (IOperator)engine.eval(this.operator);
return op.call(engine, args);
}
}
evalメソッド内で式を評価してオペレータを取得して、それを呼び出すようにします。
以上の修正により、次のコードが実行できるようになります。
(step
(set add +)
(print (add 1 2 3)))
+に代入されている加算を行うオペレータを、addにも代入しています。
(add 1 2 3) は (+ 1 2 3) と等価になり、結果として 6 を返します。
関数の定義：所要時間10分
いよいよ、関数の定義を行えるようにしましょう。
無名の関数を作成する lambda オペレータを追加します。
作った関数に名前を付けたければ、変数に代入すればよいのです。
なにせ、orelangの関数は第１級オブジェクトなのだから。
理解しやすいように、まずはどんなコードを実行したいのかを載せます。
(step
(set square_a
(lambda () (* a a)))
(set a 5)
(print (square_a)))
lambdaオペレータは、新しい関数を作成して返します。これを square_a という変数に代入します。
lambdaオペレータへ引数として渡すのは、作成する関数に渡す引数リストと、関数の本体の2つです。今回の例 (lambda () (* a a))でいくと、()が引数リストで (* a a)が関数本体となります。
lambdaで作成した関数に引数を渡す仕組みを作るには、もう少し準備が必要です。今のところは、引数のない関数のみ作成可能です。
この例では、グローバル変数aを引数のように使用しています。
square_aは、aの値を2乗して返す関数です。
では、実装していきましょう。
lambdaオペレータは呼び出されると、以下のProcOperatorのインスタンスを生成して返します。
これが、生成される関数の実体となります。
package orelang.operator;
import java.util.List;
import orelang.Engine;
public class ProcOperator implements IOperator {
private List<?> argNames;
private Object procedure;
public ProcOperator(List<?> argNames, Object procedure){
this.argNames = argNames;
this.procedure = procedure;
}
@Override
public Object call(Engine engine, List<?> args) {
return engine.eval(procedure);
}
}
引数リスト(argNames)と、関数本体(procedure)をメンバとして持ち、callメソッドで呼び出されると、procedureをそのまま評価して値を返します。
argNamesは定義しただけで使っていないので、警告が出ると思いますが、今の時点では放置して下さい。
続いて、LambdaOperatorの実装を以下に示します。
package orelang.operator;
import java.util.List;
import orelang.Engine;
public class LambdaOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
return new ProcOperator((List<?>)args.get(0), args.get(1));
}
}
引数リストと、関数本体を渡してProcOperatorを生成するだけです。
Engineクラスのvariablesマップに lambda という名前で登録しておきます。(コードは割愛）
サンプルコードを再掲します。このコードが、実行できるようになっているはずです。
(step
(set square_a
(lambda () (* a a)))
(set a 5)
(print (square_a)))
実行すると 25 を返します。
ローカル変数の定義：所要時間10分
lambdaで定義した関数に、引数を渡すにはどうすればよいか？
引数は、その関数の内部だけで利用可能なローカル変数です。
しかし、orelangには今のところ、グローバル変数しかありません。
Engineクラスが持つ、たった一つのvariablesマップで全てを管理しているためです。
引数を実現する前に、まずはローカル変数を定義する仕組みを考えます。
説明のため、以下のJavaScriptコードをご覧ください。
var v = 'global';
(function(){
var v = 'local';
console.log(v); // local
})();
console.log(v); // global
このコードにおいて、関数外の変数 v と、関数内の変数 v とは、名前は同じですが実体は別物です。それぞれ var を付けて定義しているので、定義されている場所のスコープにおいて、別個に作られます。
そのため、関数内部で v = 'local' という代入を行っても、外部では v の値は 'global' のままとなります。
つまり、関数内部の v はローカル変数となります。
以下のコードではどうでしょうか。
var v = 'global';
(function(){
v = 'local'; // varを書かなかった
console.log(v); // local
})();
console.log(v); // local
関数内部で v への代入を行う際に var を書かなかったため、このスコープで変数 v が新しく定義されることはありません。
関数外のスコープへ変数を探しに行き、結果としてグローバル変数 v の値を 'local' という値で上書きします。
ちなみにJavaScriptでは、定義されていない変数に対して var を付けずに代入を行うと、グローバル変数として定義されます。
まとめると、こういうことになります。
- varによって、現在のスコープ内に変数を定義する。
- 変数を参照する際は、現在のスコープから外側へ順に、指定した名前の変数を探す。
- 変数への代入時も、参照時と同様の方法で検索する。見つからなければグローバル変数として定義する。
では、同様の機能を orelang にも実装しましょう。
変数のスコープは、関数（オペレータ）が呼ばれたときに新しく作られます。
orelangでは、Engineオブジェクトがスコープに対応するものとします。
つまり、関数呼び出しの度に新しいEngineオブジェクトを生成することになります。
また、ローカルのスコープからさかのぼってグローバル変数を参照できるよう、
Engineオブジェクトには親のオブジェクトへの参照を持たせます。
これらのことを行うために、Engineクラスへ以下の内容を加えます。
public class Engine {
private Engine _super = null;
public Engine(Engine _super){
this._super = _super;
}
// 省略
// ...
}
親オブジェクトへの参照を _super メンバに保持します。さらに、_superを受け取るコンストラクタを追加します。
Engineオブジェクトは、自身をコンストラクタの引数にすることで、子スコープに対応するオブジェクトを作成することができます。
ProcOperatorのcallメソッドを次のように書き換えることで、関数呼び出しの際に新しいスコープが生成されるようになります。
@Override
public Object call(Engine engine, List<?> args) {
Engine _engine = new Engine(engine); // 新しいスコープを作る。
return _engine.eval(procedure);
}
続いて、Engineオブジェクト（つまりスコープ）をトラバースして変数を参照する仕組みを作りましょう。
変数に対しては、次の3つの操作が考えられます。
-現在のスコープに変数を定義する(defineVariable) ※ JavaScriptにおける var に相当
-既存の変数に代入する(setVariable)
-既存の変数値を参照する(getVariable)
それぞれに対応するメソッドを、Engineクラスのメンバとして定義します。
public class Engine {
// 省略
// ...
public Object defineVariable(String name, Object value){
variables.put(name, value);
return value;
}
public Object setVariable(String name, Object value){
Engine engine = this;
while(true){
if (engine.variables.containsKey(name)){
engine.variables.put(name, value);
return value;
}else if (engine._super != null){
engine = engine._super;
}else{
// 変数が見つからなければ、最も外側のスコープに
// （グローバル変数として）変数を定義する
return engine.defineVariable(name, value);
}
}
}
public Object getVariable(String name){
Engine engine = this;
while(true){
if (engine.variables.containsKey(name)){
return engine.variables.get(name);
}else if (engine._super != null){
engine = engine._super;
}else{
throw new RuntimeException("Unknown variable:" + name);
}
}
}
}
続いて、変数の定義を行う DefineOperator を追加します。
package orelang.operator;
import java.util.List;
import orelang.Engine;
public class DefineOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
return engine.defineVariable(
(String)args.get(0),
engine.eval(args.get(1)));
}
}
ここで行っていることは、Engineの defineVariable を呼ぶだけです。
作成したら、Engineクラスの variables に def という名前で登録しておきます。（コード割愛）
今後、orelangにおいて変数を扱う際は def と set を使い分ける必要があります。変数を定義するなら def を使い、既存の変数に代入するなら set を用いることになります。
さらに、今まで作成してきた、変数への参照および代入を行う処理を書き換えます。
public class SymbolValue implements IExpression {
private String symbol;
public SymbolValue(String symbol){
this.symbol = symbol;
}
@Override
public Object eval(Engine engine) {
// getVariableメソッドを利用するよう修正
return engine.getVariable(symbol);
}
}
public class GetOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
// getVariableメソッドを利用するよう修正
return engine.getVariable((String)args.get(0));
}
}
public class SetOperator implements IOperator {
@Override
public Object call(Engine engine, List<?> args) {
// setVariableを利用するよう修正
return engine.setVariable(
(String)args.get(0),
engine.eval(args.get(1)));
}
}
これで、以下のコードを実行できます。
(step
(def v 1)
((lambda ()
(step
(def v 2)
(print v))))
(print v))
関数内部の (print v) では 2 が出力され、外側では 1 が出力されます。
関数内部の v がローカル変数になっていることがわかります。
引数の受け渡し：所要時間5分
ローカル変数の仕組みができてしまえば、引数の受け渡しは簡単です。
ProcOperatorを、以下のように書き換えます。
public class ProcOperator implements IOperator {
private List<?> argNames;
private Object procedure;
public ProcOperator(List<?> argNames, Object procedure){
this.argNames = argNames;
this.procedure = procedure;
}
@Override
public Object call(Engine engine, List<?> args) {
Engine _engine = new Engine(engine);
// 引数を関数スコープのローカル変数として設定する。
for(int i = 0;i < this.argNames.size();i++){
_engine.variables.put(
(String)this.argNames.get(i), engine.eval(args.get(i)));
}
return _engine.eval(procedure);
}
}
callメソッド内で、新しいスコープ(_engine)に、引数として渡された値を設定します。
引数が使えるようになると、やっと関数らしい関数が作れるようになります。
(step
(def square
(lambda (v) (* v v)))
(print (square 5)))
実行すると 25 を返します。
クロージャを作れるようにする：所要時間10分
クロージャというものをご存知でしょうか？
例として、以下のJavaScriptコードをご覧ください。
var counter =
(function(){
var c = 0;
return function(){
c += 1;
return c;
};
})();
console.log(counter()); // 1
console.log(counter()); // 2
console.log(counter()); // 3
console.log(counter()); // 4
console.log(counter()); // 5
counterという関数は、変数 c を含むスコープの中で作られました。そして、counter関数は実行されるたびに、c の値をインクリメントして返します。
このようなことが可能なのは、counterは関数そのものだけでなく、その関数が作られた時点でのスコープを一緒に持っているからです。
こうしたオブジェクトをクロージャと呼びます。
現時点の orelang でクロージャを作ることは可能でしょうか？
以下のコードを実行してみましょう。
(step
(def counter
((lambda ()
(step
(def c 0)
(lambda () (set c (+ c 1)))))))
(print (counter))
(print (counter))
(print (counter))
(print (counter))
(print (counter)))
counter関数の呼び出しで、cという変数はないとのエラーになるはずです。
つまりcounterは、作られた時点でのスコープを持っていません。
考えてみれば、そんな風には作ってないのであたりまえですね。
JavaScriptのように、関数が定義された時点でのスコープが利用される仕組みを、静的スコープ（またはレキシカルスコープ）といいます。
現時点の orelang のように、評価時(実行時)のスコープが利用される仕組みを、動的スコープといいます。
クロージャを作るには、静的スコープが必要です。
クロージャが使えれば、orelangはさらに強力になります。使えるようにしましょう。
ようするに、関数とスコープをセットで持っておけばよいということです。
これを行うClosureクラスを作りましょう。
package orelang;
import java.util.List;
import orelang.operator.IOperator;
public class Closure {
private Engine engine;
private IOperator operator;
public Closure(Engine engine, IOperator operator){
this.engine = engine;
this.operator = operator;
}
public Object eval(List<?> args){
return operator.call(engine, args);
}
}
スコープに対応する engine と、関数に対応する operator をメンバとして持っておき、evalメソッドで評価できるようにします。
続いて、Engineクラスの eval メソッドを、以下のように書き換えます。
public Object eval(Object script){
Object retVal = getExpression(script).eval(this);
if (retVal instanceof IOperator){
// 式を評価した結果がオペレータならば、クロージャにして返す。
return new Closure(this, (IOperator)retVal);
}else{
return retVal;
}
}
評価した結果、得られた値が関数(IOperator)ならば、クロージャに包んで返します。
これにより、evalの戻り値としてIOperatorオブジェクトが返ってくることはなくなります。
代わりにClosureオブジェクトが返ってくるので、これを評価するように CallOperator を修正します。
public class CallOperator implements IExpression {
private Object operator;
private List<?> args;
public CallOperator(Object operator, List<?> args){
this.operator = operator;
this.args = args;
}
@Override
public Object eval(Engine engine) {
// クロージャが返ってくるはずなので、これを実行する。
Closure closure = (Closure)engine.eval(operator);
return closure.eval(args);
}
}
サンプルコードを再掲します。
(step
(def counter
((lambda ()
(step
(def c 0)
(lambda () (set c (+ c 1)))))))
(print (counter))
(print (counter))
(print (counter))
(print (counter))
(print (counter)))
counterを呼び出すたびに、値が 1 ずつ増えて出力されるはずです。
おまけ：クラス(のようなもの)を作ってみる
クロージャを活用することで、一緒に扱いたい値や関数をまとめて管理できるようになります。
つまり、クラス（のようなもの）も作れるのです。
(step
(def PI 3.14159)
(def create_circle
(lambda (radius) (step
(def get_radius
(lambda () radius))
(def set_radius
(lambda (r) (set radius r)))
(def circumference
(lambda () (* 2 PI radius)))
(def area
(lambda () (* PI radius radius)))
get)))
(def c (create_circle 5))
(print ((c get_radius)))
(print ((c circumference)))
(print ((c area)))
((c set_radius) 10)
(print ((c get_radius)))
(print ((c circumference)))
(print ((c area))))
このコードでは、円(circle)のクラスを定義しています。
メンバとして半径(radius)を持ち、getter/setterメソッドも定義されています。
実は(c radius)という式で、隠蔽されてるはずの変数 radius に外部から参照できちゃうという問題は含んでいますが。。。
さらに、円周(circumference)と、面積(area)を計算するメソッドもあります。
これを可能にしているのは create_circle の戻り値としている get オペレータです。
getオペレータ越しに、クロージャが保持する値や関数に参照することができるようになっています。
終わりに
楽しんでいただけましたか？
処理系の開発は、作った本人でも追い切れないような処理を、プログラムがひとりでに実行してくれるような感覚があって、非常に楽しいものです。
その分デバッグはつらい時がありますが。
orelangについては、クロージャまで実現したので、やり切った感があります。
これ以上の続編はないと思いますが、やるとすれば末尾再帰の最適化とか？