プログラミング言語を作る。1時間で。

  • 485
    いいね
  • 9
    コメント

あなたは、プログラミング言語を作ったことがありますか?
エッ!?ない!?
それはいけない。いますぐ作りましょう。1時間ぐらいで。

10/3追記 続編を書きました。
http://qiita.com/shuetsu@github/items/23d5194cf821402bfadf

どんな言語を作るのか

オレの言語なので、名前はorelangです。
orelangはJavaで作ります。他の言語でも作れると思います。

文法は1種類しかありません。これで十分です。

(operator arg1 arg2...)

オペレータ(operator)に、引数(argN)を渡して呼び出します。ネスト可能です。
例えば以下のようなイメージになります。

(+ 1 2 (* 3 4)) => 15 // 1 + 2 + 3 * 4 を計算

+や、*が、オペレータです。
後々ちゃんと、流れ制御文とかも作ります。1時間で、そこまで行きます。

が、このような式を解析しようとすると、さすがに1時間じゃ足りません。この記法は、あくまでイメージです。

実際は、構文解析にJSONライブラリ(JSONIC)を使います。
したがって、先ほどの式はorelangで書くと以下のようになります。

["+", 1, 2, ["*", 3, 4]]

これでは例が簡単すぎるのでもう一つ。
1から10までの和を計算するorelangプログラムを紹介します。

["step",
  ["set", "i", 10],
  ["set", "sum", 0],
  ["until", ["=", ["get", "i"], 0], [
    "step",
    ["set", "sum", ["+", ["get", "sum"], ["get", "i"]]],
    ["set", "i", ["+", ["get", "i"], -1]]
  ]],
  ["get", "sum"]
]

ではさっそく、作っていきましょう!

言語エンジンクラスのひな形を作る:所要時間5分

orelangの中心となるのは言語エンジン(Engine)クラスです。
Engineクラスにはorelangプログラムを評価・実行するメソッドevalがあります。

とりあえずのコードを、以下に示します。

Engine.java
package orelang;

import orelang.expression.IExpression;

public class Engine {

    public Object eval(Object script){
        return getExpression(script).eval(this);
    }

    private IExpression getExpression(Object script){
        return null; // TODO 式オブジェクトを生成します。
    }

}

evalには、JSONICによってデコードされたorelangプログラムが渡され、getExpressionメソッドによって中間形式である式オブジェクトに変換された上で評価されます。

まだ定義していない、式(IExpression)インターフェース が利用されていますが、この後すぐ作ります。また、getExpressionメソッドの実装も、後ほど行います。

最終的にorelangプログラムは、以下のようなコードで実行できるようになります。

Engine engine = new Engine();
Object result = engine.eval(JSON.decode("[\"+\", 1, 2, [\"*\", 3, 4]]"));
System.out.println(result);

式のインターフェースを作る:所要時間5分

式オブジェクトは、以下のインターフェースIExpressionを満たす必要があります。

IExpression.java
package orelang.expression;

import orelang.Engine;

public interface IExpression {
    Object eval(Engine engine);
}

式オブジェクトはevalメソッドによって評価することができ、結果を戻り値として返します。evalメソッドは、言語エンジン(engine)を引数として受け取ります。

式クラスを作る:所要時間10分

orelangの式は、以下の2種類しかありません。

  • オペレータ呼び出し (CallOperator)
  • 即値 (ImmediateValue)

式がリスト型だった場合、それはオペレータ呼び出しとなります。
例えば ["+", 1, 2] は、+オペレータに引数 1 2を渡して呼び出すという式です。
リストの最初の要素がオペレータで、それ以降は引数となります。

式がリストでないなら、それは即値となります。
即値とは、値そのものを表す式です。例えば 1 という式は数値の1を表します。

では、それぞれに対応したクラスを作りましょう。

オペレータ呼び出しの式クラスを作る

オペレータ呼び出しクラス CallOperator の実装は以下のようになります。

CallOperator.java
package orelang.expression;

import java.util.List;

import orelang.Engine;
import orelang.operator.IOperator;

public class CallOperator implements IExpression {

    private IOperator operator;
    private List<?> args;

    public CallOperator(IOperator operator, List<?> args){
        this.operator = operator;
        this.args = args;
    }

    @Override
    public Object eval(Engine engine) {
        return operator.call(engine, args);
    }

}

まだ定義していないオペレータ(IOperator)インターフェース が利用されていますが、この後すぐ作ります。

CallOperatorは、オペレータ(operator)と引数(arg)をメンバとして持ち、評価されるとオペレータの呼び出しを行って、その戻り値を返します。

即値の式クラスを作る

即値クラス ImmediateValue の実装は以下のようになります。

ImmediateValue.java
package orelang.expression;

import orelang.Engine;

public class ImmediateValue implements IExpression {

    private Object value;

    public ImmediateValue(Object value){
        this.value = value;
    }

    @Override
    public Object eval(Engine engine) {
        return value;
    }

}

自身を表す値(value)をメンバとして持ち、評価されるとそれを返します。

オペレータのインターフェースを作る:所要時間5分

先ほどの、オペレータ呼び出し(CallOperator)クラスで使われていた、オペレータのインターフェース IOperator の実装は以下のようになります。

IOperator.java
package orelang.operator;

import java.util.List;

import orelang.Engine;

public interface IOperator {
    Object call(Engine engine, List<?> args);
}

オペレータは、callメソッドによって呼び出すことができ、結果を戻り値として返します。callメソッドは、言語エンジン(engine)と引数(args)を受け取ります。

式オブジェクト生成メソッド getExpression を作る:所要時間10分

ここまでくれば、先ほど後回しにしていた、言語エンジン(Engine)クラス内の、式オブジェクト生成メソッド getExpression を実装することができます。

getExpressionを実装したEngineクラスのコードは、以下のようになります。

Engine.java
package orelang;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import orelang.expression.CallOperator;
import orelang.expression.IExpression;
import orelang.expression.ImmediateValue;
import orelang.operator.IOperator;

public class Engine {

    public Map<String, IOperator> operators = new HashMap<String, IOperator>();
    public Map<String, Object> variables = new HashMap<String, Object>();

    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(
                    operators.get(scriptList.get(0)), 
                    scriptList.subList(1, scriptList.size()));
        }else{
            return new ImmediateValue(script);
        }
    }

}

まず、利用可能なオペレータを格納する operators というハッシュマップを、Engineクラスのメンバとして定義しておきます。
operatorsの中身は今はカラですが、後ほど追加します。

さらに、orelangは変数を扱えるようにします。
そのため、変数の値を格納する variables というハッシュマップを、メンバとして定義します。これは、後ほどオペレータの実装を行う際に利用します。

getExpressionメソッドでは、先ほど説明したとおり、リストならば、オペレータ呼び出し (CallOperator)を生成し、そうでないなら即値(ImmediateValue)の式オブジェクトを生成します。

CallOperatorオブジェクトを生成する際は、リストの最初の要素をキーとして operators マップからオペレータを取り出し、さらに残りの要素を引数としてコンストラクタに渡します。

ImmediateValueオブジェクトを生成する際は、値をそのままコンストラクタに渡します。

オペレータクラスを作る:所要時間20分

それではいよいよ、orelangに魂を入れていきましょう。

オペレータを作ることで、orelangにどんどん機能を追加することができます。

足し算を行うオペレータ AddOperator

AddOperator.java
package orelang.operator;

import java.math.BigDecimal;
import java.util.List;

import orelang.Engine;

public class AddOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        BigDecimal retValue = BigDecimal.ZERO;
        for(Object arg: args){
            Object v = engine.eval(arg);
            retValue = retValue.add((BigDecimal)v);
        }
        return retValue;
    }
}

JSONで書くとわかりずらいので、簡単形式で例文を表します。

(+ 1 2) => 3

引き算は用意していません。ぜひ自分で作ってみてください。
ここでは、負数との足し算で代用します。

(+ 2 -1) => 1

掛け算を行うオペレータ MultiplyOperator

MultiplyOperator.java
package orelang.operator;

import java.math.BigDecimal;
import java.util.List;

import orelang.Engine;

public class MultiplyOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        BigDecimal retValue = BigDecimal.ONE;
        for(Object arg: args){
            Object v = engine.eval(arg);
            retValue = retValue.multiply((BigDecimal)v);
        }
        return retValue;
    }
}

(* 2 3) => 6

比較して同じ値ならばTrueを返すオペレータ EqualOperator

EqualOperator.java
package orelang.operator;

import java.util.List;

import orelang.Engine;

public class EqualOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        return engine.eval(args.get(0)).equals(engine.eval(args.get(1)));
    }
}

(= 1 2) => False
(= 2 2) => True

変数への代入を行うオペレータ SetOperator

SetOperator.java
package orelang.operator;

import java.util.List;

import orelang.Engine;

public class SetOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        Object value = engine.eval(args.get(1));
        engine.variables.put((String)engine.eval(args.get(0)), value);
        return value;
    }
}

代入を行い、さらに代入した値を戻り値として返します。

(set "x" 1) => 1 変数 x に 1 が代入される。

変数の参照を行うオペレータ GetOperator

GetOperator.java
package orelang.operator;

import java.util.List;

import orelang.Engine;

public class GetOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        return engine.variables.get(engine.eval(args.get(0)));
    }
}

変数の値を返します。

(get "x") => 1

指定された条件がTrueになるまで、繰返しを行うオペレータ UntilOperator

UntilOperator.java
package orelang.operator;

import java.util.List;

import orelang.Engine;

public class UntilOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        Object retVal = null;
        while(!(boolean)engine.eval(args.get(0))){
            retVal = engine.eval(args.get(1));
        }
        return retVal;
    }
}

流れ制御文です。こういうのが出てくると言語っぽくなりますね。
条件がTrueになるまで、式を繰り返し評価します。

(until 条件式 繰り返し実行する式)

繰り返しの最後に評価した式の結果を戻り値にします。
!を無くしたバージョンを作れば、そのままwhileオペレータとして使えます。

渡された式を順に評価するオペレータ StepOperator

StepOperator.java
package orelang.operator;

import java.util.List;

import orelang.Engine;

public class StepOperator implements IOperator {
    @Override
    public Object call(Engine engine, List<?> args) {
        Object retVal = null;
        for(Object arg: args){
            retVal = engine.eval(arg);
        }
        return retVal;
    }
}

渡された式を順に評価し、最後に評価した式の結果を戻り値にします。

(step 式1 式2 式3)

変数への代入を行うsetは、副作用を持つオペレータです。
こうした機能を活用するには、プログラムを順に実行する仕組みが必要になります。

(step
  (set "a" 5)
  (set "b" 10)
  (+ (get "a") (get "b"))) => 15

ここでは、サンプルの実行に必要最小限なオペレータのみを作りました。自分で工夫して、オリジナルのオペレータをぜひ作ってみてください。

作成したオペレータは、Engineクラスのコンストラクタで operatorsマップに追加します。最終的に、Engineクラスのコードは以下のようになります。

Engine.java
package orelang;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import orelang.expression.CallOperator;
import orelang.expression.IExpression;
import orelang.expression.ImmediateValue;
import orelang.operator.AddOperator;
import orelang.operator.EqualOperator;
import orelang.operator.GetOperator;
import orelang.operator.IOperator;
import orelang.operator.MultiplyOperator;
import orelang.operator.SetOperator;
import orelang.operator.StepOperator;
import orelang.operator.UntilOperator;

public class Engine {

    public Map<String, IOperator> operators = new HashMap<String, IOperator>();
    public Map<String, Object> variables = new HashMap<String, Object>();

    public Engine(){
        operators.put("+", new AddOperator());
        operators.put("*", new MultiplyOperator());
        operators.put("=", new EqualOperator());
        operators.put("set", new SetOperator());
        operators.put("get", new GetOperator());
        operators.put("until", new UntilOperator());
        operators.put("step", new StepOperator());
    }

    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(
                    operators.get(scriptList.get(0)), 
                    scriptList.subList(1, scriptList.size()));
        }else{
            return new ImmediateValue(script);
        }
    }

}

ついに、orelang言語エンジンが完成しました。

実行する:所要時間5分

さっそく実行してみましょう。

Engine engine = new Engine();
Object result = engine.eval(JSON.decode("[\"+\", 1, 2, [\"*\", 3, 4]]"));
System.out.println(result);

エスケープが含まれるため、ちょっとわかりずらいですが、このコードは1 + 2 + 3 * 4を計算し、15を返します。

複雑なプログラムは、外部ファイルに書いておいたほうが読みやすくなります。
1から10の和を計算するプログラムを再掲しましょう。
これを、example.jsonという名前で保存しておきます。

example.json
["step",
  ["set", "i", 10],
  ["set", "sum", 0],
  ["until", ["=", ["get", "i"], 0], [
    "step",
    ["set", "sum", ["+", ["get", "sum"], ["get", "i"]]],
    ["set", "i", ["+", ["get", "i"], -1]]
  ]],
  ["get", "sum"]
]

以下のコードで実行できます。

Engine engine = new Engine();
Object result = engine.eval(JSON.decode(new FileReader("example.json")));
System.out.println(result);

結果として 55 という値が出力されます。

終わりに

いかがでしたか?

簡単なものとはいえ、処理系を1つ作ったにしては、書いたコードの量はごくわずかだと思っていただけたのではないでしょうか。
orelangには、新しい機能や記法を追加することも可能なはずです。応用していけば、あなたが行っている仕事を、より簡潔に計算機へ伝える方法が実現できるかもしれません。

開発技法としてメタプログラミングやドメイン特化言語(DSL)といったものが活用されている現在、プログラミング言語を自分で作ってみるという経験は、一見お遊びのようですが、決して無駄にはならないと思います。

9/29追記 OrelangをTypeScriptで実装。関数定義も可能に。そのうえ高階関数まで実現。
http://qiita.com/alpha_kai_NET/items/aa4c71a09f853fda7011

9/30追記 こちらはRuby版。無名関数(lambda)活用でとっても簡潔。
http://qiita.com/arc279/items/816ff67737b79c45ae82

9/30追記 どうせすぐ評価するだけなんだから式オブジェクトとかいらなくないか?ということで簡単になったJava版。
http://blog.64p.org/entry/2016/09/30/014358
Go言語版。こちらの作者様は、偶然にもOrelangという名の言語を過去に作られていたようです。どうも失礼しました。
http://mattn.kaoriya.net/software/lang/go/20160930110535.htm
Vim Script版。
http://qiita.com/mattn/items/96d79fc0b50af2bf5572
Groovy版。
https://gist.github.com/nobeans/c16a89a10d0abc30f357b07d8ecbb795
Common Lisp版。。。というか、Common Lispをorelang化。誰得?
http://lizx.hatenablog.com/entry/2016/09/30/175458

10/1追記 Rust版。Rustのコード初めて読みました。
http://qiita.com/ubnt_intrepid/items/79392297af7282fcd4b3

10/2追記 C++版。JSONパーサーからして自作とのこと。
http://qiita.com/soramimi_jp/items/aa99c00a65579c2e25a2

いろんな方に(コードで)反応していただいて、うれしい限りです。