分け入ってもコード

on github pages

Grass on SQL

| Comments

Overview

ちょっと草植えときますね型言語 GrassをSQLで実装しましたという話.

Grassはλ計算をベースにした関数型プログラミング言語です.公式ページの仕様を元にSQL(PostgreSQL)で実装しました.

他Grassについては上記の公式ページとかここら辺を参照.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14

SELECT run_grass('wwWWwv wwwwWWWwwWwwWWWWWWwwwwWwwv wWWwwwWwwwwWwwwwwwWwwwwwwwww');

 run_grass
-----------
 ww
(1 row)


SELECT run_grass('wWWWwwwwWWWw');

 run_grass
-----------
 x
(1 row)

Homuhomu

ついでに「ほむほむ」も入れておきました. 表現が異なるだけで中身はGrassとほぼ一緒.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

SELECT
    run_homu($$
        ほむ ほむほむほむ ほむ ほむほむほむほむ ほむ
        ほむ ほむほむ ほむ ほむほむほむ ほむ
        ほむ ほむほむ ほむ ほむほむほむ ほむ
        ほむ ほむほむ ほむ ほむほむほむ ほむ
        ほむ ほむほむ ほむ ほむほむほむ ほむ
        ほむ ほむほむ ほむ ほむほむほむ ほむ
        ほむ ほむほむ ほむ ほむほむほむ ほむ
        ほむ ほむほむ ほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむ ほむ ほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ ほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむほむ
    $$)
;
   run_homu
---------------
 Hello, world!
(1 row)

Technique

主に利用したテクニックを紹介

入れ子集合モデル

ASTなどを表現するために木構造が必要になります。

SQLで木構造を扱うために入れ子集合モデルを採用しています。

CASE

SQLにおけるIFのようなものです

再帰SQL

WITH RECURSIVEという構文を用いて、再帰的にSQLを実行することができます。

前回のSQLで定義された集合にたいして、再度問い合わせをしていくようなイメージです。

型定義

PostgreSQLでは列挙型や構造体のような型をユーザーで定義して用いることができます。

これらは列の別名のようなものなので、必須ではないのですが見やすさのために利用しています。

例)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

CREATE TYPE Operation AS ENUM (
    'Abs'
    ,'App'
    ,'Out'
    ,'Succ'
    ,'Char'
    ,'In'
);
CREATE TYPE App AS (
    func Int
    ,arg Int
);

CREATE TYPE Node AS (
    l Int
    ,r Int
    ,op Operation
    ,app App -- for 'App'
    ,ascii Int -- for 'Char'
);

Source Code

全部載せると長いのでgithubのリポジトリを見てみて下さい.

https://github.com/choplin/grass_on_sql

以下簡単に概要を説明.

Functions

run

Grassの実行を行うrun_grass関数ですが,大きく二つのステップに分けて実行しています.

  • parse関数でソースコードからASTへの変換
  • exec関数でASTを受け取って実行
1
2
3
4
5

CREATE OR REPLACE FUNCTION run_grass (Text) RETURNS text AS $$
SELECT
    exec( parse($1) )
$$ LANGUAGE SQL
;

parse

parse関数ではASTの構築

メインであるASTの構築はbuild_tree関数で行なっています。

動きはこんな感じです

  • srcでw,Wのまとまり毎に区切って長さを取得
  • recでWITH RECURSIVEを使ってまとまりを順番に消費し、長さをもとにASTを組み立てる
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

CREATE OR REPLACE FUNCTION build_tree (Text) RETURNS tree AS $$
WITH RECURSIVE
src(chr, len) AS (
    SELECT
        array_agg(substring(s[1] from 1 for 1))
        ,array_agg(char_length(s[1]))
    FROM
        regexp_matches($1, '(w+|W+)', 'g') AS t(s)
)
,rec(tree, idx, nextl) AS (
    SELECT
        tree( ARRAY[]::Node[] )::Tree
        ,1::Int
        ,1::Int
    UNION ALL
    SELECT
        CASE chr[idx]
            WHEN 'w' THEN add_abs_node_n_times(tree, len[idx])
            WHEN 'W' THEN add_node(tree, app_node(nextl,nextl+1,(len[idx],len[idx+1])))
        END
        ,CASE chr[idx]
            WHEN 'w' THEN idx + 1
            WHEN 'W' THEN idx + 2
        END
        ,CASE chr[idx]
            WHEN 'w' THEN nextl + len[idx]
            WHEN 'W' THEN nextl + 2
        END
    FROM
        rec, src
    WHERE
        idx <= array_length(chr, 1)
)
SELECT
    tree
FROM
    rec
ORDER BY
    idx DESC
LIMIT 1
$$ LANGUAGE SQL
;

exec

exec関数では

  • initで初期状態の用意
  • evalでWITH RECURSIVEを使ってASTを辿って実行

の様な動作になっています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

CREATE OR REPLACE FUNCTION exec (Code) RETURNS Text AS $$
WITH RECURSIVE
init(machine) AS (
    SELECT
    machine(
        $1
        ,env( ARRAY[ 4,3,2,1 ] )
        ,dump(
            ARRAY[
                dump_elem(
                    code( ARRAY[ tree( ARRAY[app_node(1,2,(1,1))] ) ] )
                    ,env( ARRAY[ ]::Int[] )
                )
                ,dump_elem(
                    code( ARRAY[ tree( ARRAY[]::Node[] ) ] )
                    ,env( ARRAY[ ]::Int[] )
                )
            ]
        )
        ,closure(
            ARRAY[
                closure_elem(
                    code( ARRAY[ tree( ARRAY[in_node()] ) ] )
                    ,env( ARRAY[ ]::Int[] )
                )
                ,closure_elem(
                    code( ARRAY[ tree( ARRAY[char_node(119)] ) ] )
                    ,env( ARRAY[ ]::Int[] )
                )
                ,closure_elem(
                    code( ARRAY[ tree( ARRAY[succ_node()] ) ] )
                    ,env( ARRAY[ ]::Int[] )
                )
                ,closure_elem(
                    code( ARRAY[ tree( ARRAY[out_node()] ) ] )
                    ,env( ARRAY[ ]::Int[] )
                )
            ]
        )
    )
)
,eval (idx, machine, output) AS (
    (
        WITH sub (tree) AS (
            SELECT
                (machine).code.trees[1]
            FROM
                init
        )
        SELECT
            1::Int AS idx
            ,machine
            ,''::Text
        FROM
            init,sub
    )
    UNION ALL(
        WITH
        prev(idx, machine) AS (
            SELECT
                idx
                ,machine
                ,output
            FROM
                eval
            LIMIT 1
        )
        ,sub(idx, tree, root) AS (
            SELECT
                idx
                ,tree
                ,root(tree)
            FROM(
                SELECT
                    idx
                    ,(machine).code.trees[1] AS tree
                FROM
                    prev
            )t
        )
        SELECT
            idx + 1
            ,CASE
                WHEN isEmpty((machine).code) THEN ret(machine)
                WHEN (sub.root).op = 'Abs' THEN exec_abs(subtrees(sub.tree), machine)
                WHEN (sub.root).op = 'App' THEN exec_app(sub.root, machine)
                WHEN (sub.root).op = 'Out' THEN ret(machine)
                WHEN (sub.root).op = 'Succ' THEN exec_succ(machine)
            END
            ,CASE
                WHEN (sub.root).op = 'Out' THEN output || get_char(machine)
                ELSE output
            END
        FROM
            prev
        INNER JOIN -- 直前以外のprevとJOINされてしまうためINNER JOINを行う
            sub USING(idx)
        WHERE
            NOT (isEmpty((machine).code) AND isEmpty((machine).dump))
    )
)
SELECT
    output
FROM
    eval
WHERE
    output IS NOT NULL
ORDER BY
    idx DESC
LIMIT 1
$$ LANGUAGE SQL IMMUTABLE STRICT
;

Limitation

現状ではGrassの仕様を全ては実装しておらず、サブセットになります。

  • SQLの制限上からINは実装してません
  • FとTはパスしてます

Pull Requestお待ちしてます

後、読みやすさを重視しているので遅いです。誰か最適化して下さい。

Turing Complete

また一つSQLがチューリング完全であることが証明されてしまいました。

Wikipediaのチューリング完全のページにはSQLはチューリング完全でないと堂々と書いてあるのでWikipedianの人は修正をお願いします。

Appendix

余談ですが、こういう “XでYを実装してみた” は早い者勝ちなので、流行り始めた途端に主要な言語は食いつぶされてしまい、僕のような一般人が実装する隙は中々ありません。

そうした中でもSQLは今回のように余りがちなので、悔しい思いをしたことがある方は是非SQLをマスターしてチャレンジしてみて下さい。

Github Pages + Octopressはじめました

| Comments

octopress!

乗るしかない！このビッグウェーブに！

はてな記法をいつまで経っても覚えられないので、最近話題のOctopress + github pagesを試してみます。 しばらく使ってみてよさそうならはてなダイアリーから移ろうかなと。

インストールとか

上の記事をはじめ、そこら中に情報があるので割愛。プログラマで普段からCLIを触っている、かつgithubを利用したことがあるのであれば、10分かからずにできるレベルです。楽勝です。導入が簡単なのはすばらしいですね。

移行するメリットは？

今までははてなを使っていたのではてなと比較して。

個人的にはやはり手元で全て完結するところが決め手ですね。それによって

  1. Vimで記事を書ける
  2. previewが簡単
  3. 原稿がそのまま記事になるため、意識せずとも原稿が手元に残る
  4. 記事作成→公開までブラウザの操作が必要ない

のような嬉しい点があげられます。特に1,2ははてなダイアリーをつかってストレスになっていた部分なのでありがたいです。

vimshellでrake new_postしてVimで編集してvimshellからrake deployで公開。VimVim。 記事が増えてくるとファイル選ぶのが面倒になりそうなので、その内unite化しようと思います。

あとは、

  1. Markdown記法で書ける

    オープンなMarkdownが使えるのはいいですね。はてな記法は表現力は高くていいのですが、はてなのサービスを利用する時しか使わないので、結局あまり覚えられませんでした。 本当はreStructuredTextの方が慣れているのですが、Markdownでも御の字です。

  2. gitベースである

    バックアップにもなるし、環境間での共有も簡単にできるしいいことづくめです。bitbucketにも登録して原稿はbitbucketにpush、githubには公開記事のみをpushするのがスタンダードなようです。

  3. ブログ以外のページも簡単に作れる

    rake new_pageで一発です。です。ブログの記事と同じ記法でページを作れます。

  4. プラグインで拡張できる

    Octopress Documentation - Octopressにいくつか載っていますが、プラグインで記法を拡張できるようです。 “A blogging framework for hackers“を標榜するだけあって、シンタックスハイライトやgistなどソースコード系はかなり充実しているようです。

ぱっと思いつくところだと、こんなところでしょうか。

逆にデメリットとしては、

  1. 管理系機能がない

    はてなだとアフィリエイト連携や、有料ならアクセス解析も使えるのですが、そこら辺はまだまだ弱いようです。Google Analyticsは_config.yamlに”UA-…”を書くだけで対応できるので、時間が経てば充実していくかもしれません。

  2. 歴史が浅い

    テンプレートを切り替える機能があるんですが、殆ど公開されていなかったり、プラグインの数もそれ程多くなかったり。まだ使われ始めたところなので、しょうがないですが。不便な点があれば自分で何とかするつもりでなければ、まだ手を出すのは早いかもしれません。

使っていくうちに不満は出てくると思いますが、今思い当たるのはこれくらいです。

まとめ

インストールはめちゃくちゃ簡単なので気になる人は使ってみるといいのでは。情報もぐぐればすぐ出てきます。

一部レイアウトやデザインで気に入らないところがあるので、当面はその辺りをすこしいじってみたいと思います。