komorebikoboshiのブログ

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

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

JavascriptJScript)でプログラミング言語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 "w":
                return "w";
            case "W":
                return "W";
            case "v":
                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(/[wWv]/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)

はいはいわろすわろす(公式サイトより)

wwwwvwvwwWWwvwwWwwvwwwwWWWwwWwwWWWWWWwwwwWw
wvwWWwWwwvwWWWwwwwwWwwwwwwWWwWWWwWWWWWWwW
WWWWWWWwwwWwwWWWWWWWWWWwWwwwwwWWWWWWWW
WWWwwwwwWWWWWWWWWWWWwwwwWWWWWWWWWWWWW
wwwWWWWWWWWWWWWWWwwwWWWWWWWWWWWWWWWwW
WWWWWWWWWWWWWWWWWwwwWwwwwwwwwwwwwwwWWWW
WWWWWWWWWWWWWWWwwwwwwwwWwwWWWWWWWWWWW
WWWWWWWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwwWwwww
wwwwwwwwwwwwwwwww             wwwwwwwwWWwwwwwww
wwwwwwwwwwwwwwwww          は   wwwwwWWWWWWWWWW
WWWWWwWwwwWWWW    わ   い   WWWWWWWwwwWwwWW
WWWWWWWWWWwwww    ろ   は   wWwwwwwwwWWWWWWW
WWWWWWWWWWwwww    す   い   wwwWwwWWWWWWWWW
WWWWWWWWWwwwww     わ       wwwwWwwWWWWWWWW
WWWWWWWWWWWWW    ろ       WWWWWWWWWwwwwww
wwwwwWwwWWWWWWW    す       WWWWWWWWWwwwwww
wwwwwwwWwwwwwwwww             wwwwwwWWWWWWWWW
WWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwWwwwwwwwwwwwwwwWWwwwwwwwwwWWWwwWWWWwww
wwwwwwwwwwwwWWWWWwwWWWWWWwwwwWWWWWWWwwWWW
WWWWWwwwwWWWWWWWWWwwWWWWWWWWWWwwwwwwwww
wwwwWWWWWWWWWWWWWWWWWWWWWWWWWWWWwwwwww
wwwwwWwwwWWwwwwwwwwwwwwwwwwwwWWWwwWWWWwwwwww
wwwwwwwwwwwwwwwwwwWWWWWwwWWWWWWwwwwwwwWWWW
WWWwwWWWWWWWWwwwwwwWWWWWWWWWwwWWWWWWWW
WWwwwwwwWWWWWWWWWWWwwwwwwwwwwwwwwwwwwwwwww

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

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

wWWWWwwwww
 WWWWWWWwwwwww
 WWw
 WWWWWw
 Wwwww
 Wwwwwwwwwww
 WWWWWWWWWw

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

おわりに

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

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

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

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