Javascriptでプログラミング言語Grassを実装してみた（限定版）

Javascript（JScript）でプログラミング言語Grassを実装してみました。ちなみに限定版というのは機能限定版という意味です。

ソースコード

//List
function Cell(x,y){
    this.car = x;
    this.cdr = y;
}

var cons = function(x,y){
    return new Cell(x,y);
}

var nth = function(list,n){
    var tmp = list;
    for(var i = 1;i < n;i++){
        tmp = tmp.cdr;
    }
    return tmp.car;
}

//Array to List
var atol = function(array){
    var result = null;
    for(var i = array.length - 1;i >= 0;i--){
        result = cons(array[i],result);
    }
    return result;
}
//

//Abs
function Abs(n,c){
    this.n = n;
    this.code = c;
}

var abs = function(n,c){
    return new Abs(n,c);
}
//

//App
function App(m,n){
    this.m = m;
    this.n = n;
}

var app = function(m,n){
    return new App(m,n);
}
//

//Parser
var parser = function(s){
    var insns = [];
    var res = [];
    
    var wideToASCII = function(c){
        switch(c){
            case "ｗ":
                return "w";
            case "Ｗ":
                return "W";
            case "ｖ":
                return "v";
        }
    }
    
    var parseApps = function(s){
        var index = 0;
        var apps = [];
        var bigW = 0;
        var smallw = 0;
        var ch = "";
        var nextch = "";
        
        if(s === ""){return [];};
        
        ch = s.charAt(index);
        
        while(ch){
            if(ch === "W"){
                bigW += 1;
                
                nextch = s.charAt(index + 1);
                if(nextch === ""){
                    if(bigW === 0 || smallw === 0){
                        WScript.Echo("関数適用には1つ以上のWまたはwが必要です。");
                        WScript.Quit(1);
                    }
                }
            }
            else{
                smallw += 1;
                
                nextch = s.charAt(index + 1);
                if(nextch === "W" || nextch === ""){
                    apps.push(app(bigW,smallw));
                    bigW = 0;
                    smallw = 0;
                }
            }
            index++;
            ch = s.charAt(index);
        }
        return apps;
    }
    
    var parseAbs = function(s){
        var index = 0;
        var ch = "";
        var n = 0;
        var code = [];
        
        ch = s.charAt(index);
        
        while(ch === "w"){
            n += 1;
            index++;
            ch = s.charAt(index);
        }
        code = parseApps(s.substring(index));
        return abs(n,atol(code));
    }
        
    s = s.replace(/[ｗＷｖ]/g,wideToASCII);
    s = s.substring(s.indexOf("w"));
    s = s.match(/[wWv]/g).join("");
    
    insns = s.split("v");
    
    for(var i = 0;i < insns.length;i++){
        if(insns[i].charAt(0) === "w"){
            res.push(parseAbs(insns[i]));
        }
        else{
            res = res.concat(parseApps(insns[i]));
        }
    }
    return atol(res);
}
//

//Util
var getSource = function(){
    var fso = WScript.CreateObject("Scripting.FileSystemObject");
    var fs = null;
    var args = WScript.Arguments;
    var filename = "";
    var source = "";
    
    for(var i = 0;i < args.length;i++){
        if(fso.FileExists(args(i))){
            filename = args(i);
            break;
        }
    }
    if(filename === ""){
        for(i = 0;i < args.length;i++){
            source += args(i);
        }
    }
    else{
        try{
            fs = fso.OpenTextFile(filename);
            source = fs.ReadAll();
            fs.Close()
        }
        catch(e){
            WScript.Echo("Error: " + e.description);
            fs && fs.Close();
            WScript.Quit(1);
        }
    }
    if(source === ""){
        var scriptname = WScript.ScriptName;
        WScript.Echo("Usage:\ncscript " + scriptname + " <Filename>\nor\ncscript " + scriptname + " <Source>");
        WScript.Quit(0);
    }
    return source;
}

var putChar = function(c){
    WScript.StdOut.Write(c);
}

var getChar = function(){
    var rst = 0;
    return function(){
        var ret = "";
        
        if(rst === 0){
            rst = WScript.StdIn.ReadLine();
        }
        while(rst !== ""){
            ret = rst.charAt(0);
            rst = rst.substring(1);
            if(ret.charCodeAt(0) < 256){return ret;};
        }
        rst = 0;
        return "";
    }
}();
//

//machine
var machine = {code:null,env:null,dump:null};
//

//Continuation
var makeCont = function(c,e){
    return {code:c,env:e};
}
//

//Function
var makeFunc = function(c,e){
    return function(x){
        machine.dump = cons(makeCont(machine.code,machine.env),machine.dump);
        machine.code = c;
        machine.env = e;
        return x;
    }
}

var CTrue = makeFunc(atol([abs(1,atol([app(3,2)]))]),atol([makeFunc(null,null)]));
var CFalse = makeFunc(atol([abs(1,null)]),null);

var makeChar = function(cp){
    return function(x){
        if(x === undefined){
            return cp;
        }
        
        if(typeof x() === "number"){
            return x() === cp ? CTrue : CFalse;
        }
        else{
            WScript.Echo("'Char'の引数には'Char'を指定してください");
            WScript.Quit(1);
        }
    }
}

var W = makeChar(119);

var Out = function(x){
    if(typeof x() === "number"){
        putChar(String.fromCharCode(x()));
        return x;
    }
    else{
        WScript.Echo("'Out'の引数には'Char'を指定してください");
        WScript.Quit(1);
    }
}

var Succ = function(x){
    var next = 0;
    if(typeof x() === "number"){
        next = x() < 255 ? x() + 1 : 0
        return makeChar(next);
    }
    else{
        WScript.Echo("'Succ'の引数には'Char'を指定してください");
        WScript.Quit(1);
    }
}

var In = function(x){
    var c = getChar();
    
    if(c){
        c = c.charCodeAt(0);
        return makeChar(c);
    }
    else{
        return x;
    }
}
//
//Initialization
var e0 = atol([Out,Succ,W,In]);
var d0 = atol([makeCont(atol([app(1,1)]),null),makeCont(null,null)]);

var source = getSource();

machine.code = parser(source);
machine.env = e0;
machine.dump = d0;
//
//Run
//一時変数
var ctmp = null;
var etmp = null;
var dtmp = null;
var fun = null;
var arg = null;

//Main
while(true){
    if(machine.code === null){
        if(machine.dump === null){
            break;
        }
        else{
            dtmp = machine.dump.car;
            etmp = machine.env.car;
            
            machine.code = dtmp.code;
            machine.env = cons(etmp,dtmp.env);
            machine.dump = machine.dump.cdr;
        }
    }
    else{
        ctmp = machine.code.car;
        if(ctmp instanceof Abs){
            if(ctmp.n === 1){
                etmp = makeFunc(ctmp.code,machine.env);
            }
            else{
                etmp = makeFunc(atol([abs(ctmp.n - 1,ctmp.code)]),machine.env);
            }
            machine.env = cons(etmp,machine.env);
            machine.code = machine.code.cdr;
        }
        else if(ctmp instanceof App){
            fun = nth(machine.env,ctmp.m);
            arg = nth(machine.env,ctmp.n);
            
            machine.code = machine.code.cdr;
            machine.env = cons(fun(arg),machine.env);
        }
        else{
            WScript.Echo("eval内で問題が発生しました。");
            WScript.Quit(1);
        }
    }
}
//

使い方

適当にメモ帳にでもコピペして拡張子jsの適当な名前（例えばGrass.js）で保存（文字コードはシフトJIS *1）して、コマンドプロンプトで

cscript Grass.js <Grassのプログラムを書いたテキストファイル>

とかやれば実行されます。（ファイルはシフトJISで保存してください）また、コマンドライン引数内に存在するファイルがない場合は、コマンドライン引数を連結したものをGrassのプログラムだと解釈して実行します。

cscript Grass.js wWWwwww

これで「w」が出力されます。

サンプル

wを出力（公式サイトより）

wWWwwww

（=> w）

はいはいわろすわろす（公式サイトより）

ｗｗｗｗｖｗｖｗｗＷＷｗｖｗｗＷｗｗｖｗｗｗｗＷＷＷｗｗＷｗｗＷＷＷＷＷＷｗｗｗｗＷｗ
ｗｖｗＷＷｗＷｗｗｖｗＷＷＷｗｗｗｗｗＷｗｗｗｗｗｗＷＷｗＷＷＷｗＷＷＷＷＷＷｗＷ
ＷＷＷＷＷＷＷｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷＷｗＷｗｗｗｗｗＷＷＷＷＷＷＷＷ
ＷＷＷｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷ
ｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ　　　　　　　　　　　　　ｗｗｗｗｗｗｗｗＷＷｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ　　　　　　　　は　　ｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷｗＷｗｗｗＷＷＷＷ　　　　わ　　　い　　ＷＷＷＷＷＷＷｗｗｗＷｗｗＷＷ
ＷＷＷＷＷＷＷＷＷＷｗｗｗｗ　　　　ろ　　　は　　ｗＷｗｗｗｗｗｗｗＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷｗｗｗｗ　　　　す　　　い　　　ｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷｗｗｗｗｗ　　　　わ　　　　　　　ｗｗｗｗＷｗｗＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷ　　　　ろ　　　　　　　ＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗＷｗｗＷＷＷＷＷＷＷ　　　す　　　　　　　ＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗｗｗＷｗｗｗｗｗｗｗｗｗ　　　　　　　　　　　　ｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷｗｗｗｗｗｗｗｗｗＷＷＷｗｗＷＷＷＷｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷＷｗｗＷＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷｗｗＷＷＷ
ＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷＷＷｗｗＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗ
ｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗＷｗｗｗＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷｗｗＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷＷｗｗＷＷＷＷＷＷｗｗｗｗｗｗｗＷＷＷＷ
ＷＷＷｗｗＷＷＷＷＷＷＷＷｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷｗｗＷＷＷＷＷＷＷＷ
ＷＷｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

（=> ・Í・¢・Í・¢・í・ë・·・í・ë・·）
……というわけで、ASCII文字セットの範囲しか扱えません。（ここが限定版）

入力した一文字目がxだったらxを表示して、それ以外だったらwを表示する。

wwwWWWwwWwwv

wWWWWwwwww
 WWWWWWWwwwwww
 WWw
 WWWWWw
 Wwwww
 Wwwwwwwwwww
 WWWWWWWWWw

ChurchBooleanのテスト用。多バイト文字の入力は無視されます。

Hello,World!

世界で最初のGrassプログラム - Garage uenoB

おわりに

プログラミング言語の処理系を書いたのはこれが初めてです。Brainf*ck？それが書けなくて「もっと命令の少ない言語はないかな？」って辿り着いたのがGrassなんだっ。実際はずっと難しかったですけどね。それだけに動いた時は本当にうれしかったです。まあ、見ての通り本当にひどいコードですが、それでもとりあえず動くものが作れたことで少しは自信が持てました。いつかLispやMLなんかも実装してみたいなあ。*2
最後に、Grassを勉強するにあたってこの記事を大いに参考にしました。
うはｗｗｗ Mosh で Grass 実装したｗｗｗｗ - Higepon’s blog
この記事がなければそもそも手を出すことすらできなかったでしょう。ありがとうございます。
また、公式サイトのRuby実装を書き写してやっと動作がつかめました。*3実装した（の前にそもそもGrassを作った）id:uenoBさん、本当にありがとうございました。

*1:メモ帳ではANSIとなっている

*2:そのまえにリファクタリングしなきゃ

*3:Rubyしか読めないのです

komorebikoboshiのブログ

プログラミング記事（趣味レベル）が多め。