Hasche
Haskell製のSchemeインタプリタ
Hasche (/hæʃ/): Haskell + Scheme
HascheはHaskellで書かれたScheme(のような言語)のインタプリタです．REPL，パターンマッチ，非衛生的マクロ，call/cc，第一級継続が特徴です．
目次
動かし方
Hascheを動かすにはCabalが必要です．
git clone https://github.com/wasabi315/Hasche.git
cd Hasche
cabal buildexecコマンドでSchemeファイルを実行できます．
$ cabal exec hasche -- exec ./programs/hello.scm
Hello, world!replコマンドではREPLセッションでHascheを対話的に動かせます．
$ cabal exec hasche -- repl
Welcome to the Hasche REPL!
enter :? for help
hasche> (+ 1 1)
2
hasche> (display "Hello, world!\n")
Hello, world!特徴
パターンマッチ
関数型言語としてはやはりパターンマッチが欲しいですよね．Hascheでは特殊形式matchを使うとパターンマッチできます．
(define nested-data '((1 2 3) (4 5 6)))
; 1 が表示される
(match nested-data
[((m . _) (4 5 6))
(begin (display m) (newline))]
[_
(display "Failed to match\n")])HascheはLisp系言語以外ではあまり見かけないパターンを使えます．
一つは述語パターン(? <predicate>)です．マッチされる値に対して<predicate>を適用し#tが返ったらマッチ成功です．
HaskellやOCaml，Rustのガード節とは違って，述語パターンは他のパターンの中に入れ子にできます．
(define nested-data '((1 2 3) (4 5 6)))
; (zero? 2) は #f なので "m is not 0" が表示される
(match nested-data
[((_ (? zero?) _) . _)
(display "m is 0\n")]
[_
(display "m is not 0\n")])もう一つは残余パターン(<pattern> ...)です．マッチされる値がリストであり，かつ各要素が<pattern>にマッチする場合に，残余パターンのマッチも成功します．
<pattern>の中に変数パターンが含まれている場合，リストの各要素からその変数パターンに対応する値を集めたリストが変数に束縛されます．
下の例では，nested-dataの要素が全て3要素のリストであるためパターンマッチが成功します．
そして，一番目，二番目，三番目を集めてできるリストがそれぞれm，n，oに束縛されます．
(define nested-data '((1 2 3) (4 5 6)))
(match nested-data
[((m n o) ...)
(begin
(display m) (newline) ; (1 4) が表示される
(display n) (newline) ; (2 5) が表示される
(display o) (newline))]) ; (3 6) が表示されるリストが基本のデータ構造となっているLisp系言語だからこそのパターンですね． もちろん，残余パターンも入れ子にできます．
(define nested-data2 '(((1 2) (3 4)) ((5 6) (7 8) (9 10))))
(match nested-data2
[(((m n) ...) ...)
(begin
(display m) (newline) ; ((1 3) (5 7 9)) が表示される
(display n) (newline))]) ; ((2 4) (6 8 10)) が表示される非衛生的マクロ
Hashceは特殊形式define-macroによるマクロ定義をサポートしています．構文はdefineと同じです．
しかし，defineで定義された手続きが値を操作するのに対し，define-macroで定義されたマクロはプログラムをリストとして受け取り，新しいプログラム(これもリスト)を返すようなもので，返されたプログラムは評価されます．
例えば，下に定義されているandマクロは連続したifに展開されてから評価されます．
(define-macro (and . l)
(match l
(() #t)
((test1 . test2) `(if ,test1 (and ,@test2) #f))))
; (and t1 t2 t3)
; => (if t1 (and t2 t3) #f)
; => (if t1 (if t2 (and t3) #f) #f)
; => (if t1 (if t2 (if t3 (and) #f) #f) #f)
; => (if t1 (if t2 (if t3 #t #f) #f) #f)
(and t1 t2 t3)ここでは ` (backquote)，, (unquote)，そして,@ (unquote-splicing)が使われています. これらはquoteに似ていますが，値を補間(interpolate)することができます.
Hashceでは，特殊形式のbeginやlet， condはインタプリタに組み込まれものではなく，標準ライブラリにマクロとして実装されています.
上述したパターンマッチの機能とbackquoteのおかげで，これらの特殊形式を簡単に実装できました!
; In lib/stdlib.scm
(define-macro (cond . clauses)
(match clauses
[()
(error "cond with no arms")]
[(('else body ...))
`(begin ,@body)]
[((pred body ...))
`(if ,pred (begin ,@body))]
[(('else _ ...) _ ...)
(error "else is not allowed here")]
[((pred body ...) rest ...)
`(if ,pred (begin ,@body) (cond ,@rest))]
[_
(error "invalid cond syntax")]))Hascheのマクロは非衛生的で，変数名の衝突を自動的に防ぐような機構が入っていません．
代わりに，ユニークなシンボルを生成するgensymを使って手動で変数名の衝突を防ぐことができます．
(define-macro (incr v)
`(let ([x 1]) (set! ,v (+ ,v 1))))
(define x 0)
; (let ([x 1]) (set! x (+ x 1))) に展開されるので，
; defineされたxがincrの中ではshadowingされてしまう
; 結果としてxは1増えず0のまま
(incr x)
(display x) (newline) ; 0 が表示される．
(define-macro (incr2 v)
`(let ([,(gensym) 1]) (set! ,v (+ ,v 1))))
(incr2 x) ; 今回はxはshadowingされない
(display x) (newline) ; 1 が表示されるcall/cc と第一級継続
Schemeの特徴的な機能の一つにcall/cc (call-with-current-continuation)があり，Hascheでもサポートされています．
call/ccはとても強力で，例外処理やジェネレータといった複雑な制御構造を実装するのに使えます．
call/ccは現在の継続(call/ccの呼び出しを取り囲む文脈)を取ってきて，それを実引数として与えられた手続きに渡します．
そして，その継続へは，引数を与えて呼び出すことで復帰することができます．
下の例では，call/ccの継続(display ...)がkに束縛され，1でkを呼び出しているので...の部分に1が渡り，結果として1が表示されます．(k 1)を取り囲んでいる(+ ... 2)が捨てられていることもわかりますね．
hasche> (display (call/cc (lambda (k) (+ (k 1) 2))))
1継続は第一級なので，手続きの入出力にしたり，データ構造に格納したりできます．
hasche> (define save '())
hasche> (display (call/cc (lambda (k) (set! save k)))) ; (display ...) がsaveに保存される
#<undef>
hasche> save
#<continuation>
hasche> (save 1)
1
hasche> (save 2)
2
hasche> (save 3)
3実装のハイライト
Hascheはシンプルなtree-walkingインタプリタです．
評価器はモナドスタックReaderT Env (ContT r IO)で実装されています．
ContTが入っているのでcall/ccは簡単に実装できました．