JavaScriptでNode.JS/ブラウザ上で動くArc処理系を作った。

去年の夏ぐらいに、NodeJS/ブラウザ上で動くArc言語*1処理系「ArcJS」を作りました。
全体として2500行ぐらいでStackVMまで実装してあるので、処理系を作りたい人は参考になるかもしれません。

http://smihica.github.io/arc-js/

既に実際に仕事で部分的に使ってみていて、結構使えているので紹介します。
(仕事では、ArcJS上を使い、ブラウザ上でDSLを走らせ、DSL->Pythonコードを生成するのに使っています)

ArcJS特徴としては以下のようになっています。

  • 逐次実行方式ではなく、JavaScriptでStackVMを作って動かしているので高速。*2
  • コンパイラのセルフホスティングを実現している。(つまりArc言語自身でコンパイラが書いてある)
  • Macro, Object, FirstClass継続など めぼしい機能は一通り実現されている。
  • Arcに特徴的な機能 オブジェクトのデフォルト関数、ssyntax などももちろん実現されている。

本家のArcにないArcJS独自の機能として、

  • symbol-syntaxのユーザー定義
  • ネームスペース

などを使う事が出来ます。

以下にNodeJS動かしてみる際の簡単なチュートリアルを書きます。*3

インストール

npmからインストールできます。

$ npm install -g arc-js

これでarcjsとarcjscというコマンドが用意されます。

$ arcjs --version
0.1.2

では早速やってみましょう。

$ arcjs

と打つと以下のようにREPLが起動します

arc>

ちょっとREPLに色々打ち込んで試してみます。

ArcJSのprimitiveの値は、シンボル, 数値, コンス, 文字, 文字列, 正規表現, Hash, Tagged, 関数, 継続 などがあります。

;; シンボル
arc> t
t
arc> nil
nil
arc> 'a
a
arc> 'u-nk_~o#abc$$%%moemoe
u-nk_~o#abc$$%%moemoe
arc> '|a b c| ;; delimiterを含んだ文字列のsymbol
|a b c|

;; 数値
arc> 0
0
arc> 3.14
3.14
arc> -inf.0
-inf.0
arc> #x10 ;; 16進数
16

;; 文字
arc> #\a
#\a
arc> #\あ
#\あ

;; 文字列
arc> "abc"
"abc"
arc> "あいう"
"あいう"
arc> "a\nb"
"a\nb"
arc> "\u000A"
"\n"

;; コンス
arc> '(a b)
(a b)
arc> '(a . (b . c))
(a b . c)

;; 正規表現 (ArcJSによる拡張)
arc> #/a/
#<regex /a/>
arc> #/^\w+@[a-zA-Z_]+?\.[a-zA-Z]{2,3}$/
#<regex /^\w+@[a-zA-Z_]+?\.[a-zA-Z]{2,3}$/>

;; Hash
arc> (table)
#<table n=0>

;; Tagged
arc> (annotate 'my-type (table))
#<tagged my-type #<table n=0>>

Taggedはオブジェクト指向的な事をするのに使えます。

式 (S式を使います)

arc> (+ 1 2)
3
arc> (+ (/ 1 2) 3)
3.5

let / with

局所変数束縛には、let, withを使います。

;; (let var val body)
arc> (let a 10
       (+ a (* a 2)))
30
;; (with (var1 val1 var2 val2) body)
arc> (with (x 3 y 4)
       (sqrt (+ (expt x 2) (expt y 2))))
5

let, with ではリストのパターンマッチも使えます。

arc> (let (a . (b . (c . d))) '(1 2 3 . 4)
       (* a b c d))
24

=

変数定義、束縛には = を使います。

arc> (= s '(f o o))
(f o o)
arc> s
(f o o)

= は場所を指定して代入する事も出来ます

arc> (= (s 0) 'm)
m
arc> s
(m o o)

if

arcではnon-nilな値はすべてtrueと評価されます

arc> (if 0 'a 'b)
a
arc> (if nil 'a 'b)
b

論理反転は (no x) です。

arc> (if (no nil) 'a 'b)
a
arc> (if (no (odd 2)) 'a)
a

ここで、

(if a b c d e)

(if a
    b
    (if c
        d
        e))

と同じです

is / iso

is は同値であるかを見ます

arc> (is 'a 'a)
t
arc> (is "xxx" "xxx")
t
arc> (is (list 'x) (list 'x))
nil

iso は同一構造(isomorphic)であるかどうかを見ます

arc> (iso (list 'x) (list 'x))
t

def

defで現在のネームスペースにグローバル関数を定義します。

arc> (def translate (sym)
       (case sym
         apple 'mela
         onion 'cipolla
         'che?))
#<fn:translate>
arc> (translate 'apple)
mela
arc> (translate 'syzygy)
che?

for, each, while, repeat, map

様々なイテレート機能があります。

arc> (for i 1 10
          (pr i " "))
1 2 3 4 5 6 7 8 9 10 nil
arc> (each x '(a b c d e) 
       (pr x " "))
a b c d e nil
arc> (let x 10
       (while (> x 5)
         (= x (- x 1))
         (pr x)))
98765nil
arc> (repeat 5 (pr "la "))
la la la la la nil
arc> (map (fn (x) (+ x 10)) '(1 2 3))
(11 12 13)
arc> (map [+ _ 10] '(1 2 3))
(11 12 13)

ここで、[+ _ 10] という表記がありますが、これは (fn (_) (+ _ 10)) に展開されます。
Arcでは [... _ ...] は (fn (_) (... _ ...)) に展開されます。

mac

マクロはmacで定義出来ます。

arc> (mac when2 (tes . then) `(if ,tes (do ,@then)))
#<tagged mac #<fn:when2>>
arc> (when2 t 1 2 3)
3

レガシーマクロなので、暗黙の変数束縛も作れます

arc> (mac aif2 (tes then else)
       `(let it ,tes
          (if it ,then ,else)))
#<tagged mac #<fn:aif2>>
arc> (aif2 (car '(a b c)) it 'x)
a

w/uniqでワンタイムなシンボルに束縛できます。(ユニークなシンボルを返す関数は(uniq)です)
これによって一度しか評価されない式を作れます。( (++ i)は評価されるたびに i をインクリメントしてしまう)

arc> (mac prn-x-times (form times)
       (w/uniq v
         `(let ,v ,form
            (do ,@(map (fn (_) `(prn ,v)) (range 1 times))
                nil))))
#<tagged mac #<fn:prn-x-times>>
arc> (let i 5 (prn-x-times (++ i) 3))
6
6
6
nil

continuation

継続はcccで作れます。cccに渡される関数の第一引数に、継続が渡されます。
大域脱出の様なことが実現できます。

arc> (ccc
       (fn (c)
         (do (c 10)
             (err))))
10

yieldの様なことも実現できます。

arc> (ccc
       (fn (return)
         (let x 0
           (while t
             (ccc (fn (c)
                    (= next c)
                    (return x)))
             (++ x)))))
0
arc> (next nil)
1
arc> (next nil)
2

symbol-syntax

Arcの特徴的な機能として、シンボル名がある形だったときに展開されるマクロがあります。
これをsymbol-syntaxと言います。
例えば (car:cdr x) は (car (cdr x)) に展開されます。(コロン「:」がある場合に展開される)

;; 実際は (car (cdr '(1 2 3))) に展開されている。
arc> (car:cdr '(1 2 3))
2

ほかには、たとえば、 ~x は (complement x) に展開されます。

;; 実際は (~no 'a) は ((complement no) 'a) に展開されている。
arc> (if (~no 'a) 'b 'c)
c

ssexpand関数でsymbol-syntaxの展開を確認することができます。

arc> (ssexpand 'abc:def)
(compose abc def)
arc> (ssexpand '~no)
(complement no)

ArcJSの拡張で、symbol-syntaxをユーザーが定義できる機能 defss があります。

試しに、例として、 (caadaar x) や (cadadadadadar x) が car と cdr の連続の式、つまり (car (cdr ... x)) に展開できるようなsymbol-syntaxを定義してみましょう。
以下のようにします。

arc> (defss cxr-ss #/^c([ad]{3,})r$/ (xs)
       (let ac [case _ #\a 'car #\d 'cdr]
         `(fn (x)
            ,((afn (xs) (if xs `(,(ac (car xs)) ,(self (cdr xs))) 'x))
              (coerce (string xs) 'cons)))))
#<tagged special-syntax (#<regex /^c([ad]{3,})r$/> 12 #<fn:cxr-ss>)>

ssexpandで試してみましょう。

arc> (ssexpand 'caaar)
(fn (x) (car (car (car x))))
arc> (ssexpand 'cadadar)
(fn (x) (car (cdr (car (cdr (car x))))))

つまり、 caaar => (fn (x) (car (car (car x)))) になるという事です。
defssは以下のように使います。

(defss symbol-syntaxの名前 マッチする正規表現 正規表現でグルーピングした文字列のシンボルが渡される引数 body)

の順で、s式かシンボルを返すようにします。
では、実際に使ってみます。

arc> (cadddr '(1 2 3 4 5 6))
4

namespace

ArcJSの拡張で、Gaucheのモジュールシステム*4にちょっと似た独自のネームスペースが使えます。
ネームスペースを定義するには(defns)を使用します

arc> (defns A)
#<namespace A>

また、(ns namespace)というスペシャルフォームで、該当ネームスペースに入る事が出来ます。

arc> (ns 'A) ;; この他にもstringやnamespace-objectを取れる。 (ns "A") でもいいし、 (ns (defns A)) でもいい。
#<namespace A>
arc:A> 

見ると分かるように、プロンプトが、arc:A>になり、現在入っているネームスペースが表示されます。

現在のネームスペースを見るには、(***curr-ns***) 関数を使います。

arc:A> (***curr-ns***)
#<namespace A>

ちなみに、この ***...*** のような名前に束縛した場合、ネームスペース関係なく、すべてのネームスペースで同一の値にアクセスできるようになります。

名前をエクスポートするには、

arc> (defns A :export fn1 macro1 fn2)

の様に書きます。こうすると、このネームスペース「A」をインポートしたネームスペースの内部では、fn1 macro1 fn2 にアクセスする事が出来ます。
export節を書かなかった場合は、すべての名前がエクスポートされます。

また、他のネームスペースをインポートするには、

arc> (defns A :import B C)

の様に書きます。このとき、ネームスペースBやCは既に読み込まれていなければなりません。
このとき、BやCの内部でインポートされている名前にはAからはアクセスできません。
Aに明示的にインポートするか、BやCにエクスポートさせてブリッジする必要があります。

さらに、extendを使うと、既にあるネームスペースを拡張する事が出来ます。
extendした場合は、extendされたネームスペースのすべての名前にアクセスできます。

arc> (defns A :extend B)

では、ちょっと軽くやってみましょう。

;; 名前 a, b をエクスポートするネームスペース「A」(以下ns)を定義して入る。
arc> (ns (defns A :export a b))
#<namespace A>
;; 値定義 a = 10, b = 20, c = 30
arc:A> (= a 10 b 20 c 30)
30
;; A をインポートして c をエクスポートする ns「B」を定義して入る。
arc:A> (ns (defns B :import A :export c))
#<namespace B>
;; a, b は A がエクスポートしている a, b なので、それぞれ 10, 20
arc:B> a
10
arc:B> b
20
;; c は 定義もされていないし、Aからエクスポートもされていないので、unbound error
arc:B> c
Error: Unbound variable c
Stack Trace:
_______________________________________

;; ネームスペース指定の symbol-syntax「::」でアクセスできる。
arc:B> A::c
30
;; ns B にも 名前 c を定義。
arc:B> (= c 40)
40
arc:B> c
40
arc:B> B::c
40
;; ns A に戻ると、c は Aに束縛されている c なので 30
arc:B> (ns 'A)
#<namespace A>
arc:A> c
30
;; A と B をインポートした C を作る。
arc:A> (ns (defns C :import A B))
#<namespace C>
;; a, b は A がエクスポートしている a, b なので、それぞれ 10, 20
arc:C> a
10
arc:C> b
20
;; c は B がエクスポートしている c なので、40
arc:C> c
40

こんな感じです。extendは各自試してみてください。

Object System

この他、generic-functionを定義することで、オブジェクト指向っぽい事も出来ますが、
長くなりそうなので、また次の日記で書こうと思います。

*1:Arc自体については以下に作者のポールグレアム氏の記述があります。http://ycombinator.com/arc/tut.txt

*2:このページに行って、run>>を押すと、StackVMが(gcd 77 22)の命令列を実行する様子を見る事が出来る http://smihica.github.io/arc-js/stack_visualizer.html

*3:ブラウザで使う場合はこちらを参照してください http://smihica.github.io/arc-js/

*4:http://practical-scheme.net/gauche/man/gauche-refj_32.html