化ける！S式

（この記事はLisp Advent Calendar 13日目のためのエントリです。）

こんにちは！冬休みに日本に帰るときに経由しているロサンゼルスの空港で書いています。アメリカ時間ではまだ13日ということで遅刻していないと言い張らせてください。

Lispアドベントカレンダーに参加するのは今回が始めてです。S式が大好きなのでS式についてつらつらと書いて行きます。

Carrot

この記事では、Carrotという、架空のLisp風言語の処理系を仮定します。 Carrotでは以下の文法が使われることとします。

;;;アトム
数値、文字、文字列、シンボル、etc

;;;関数適用
(f x)

;;;関数定義
(= name param ... expr)  ;;例: (= add x y (+ x y))

;;;無名関数
(^ param ... expr)       ;;例: (^ x y (+ x y))

カリー化してみる

各種Lispでは関数はデフォルトでカリー化されないのが普通ですが、CarrotではMLとかHaskellみたいに関数が全てカリー化されるとします。

利点としてはまず一つ、部分適用が簡単にできるという点があります。

(map (lambda (x) (* x 2)) '(1 2 3 4 5))  ;;Scheme
(map (* 2) '(1 2 3 4 5))                 ;;Carrot

ただ、こんなのはSchemeだったらcutを使ったりgaucheのpa$を使ったりすれば似たような事は簡単にできます。

一番の利点は、f(x)(y)(z)みたいな左結合の関数適用を表すS式が(((f x) y) z)みたいに括弧だらけである必要がなくなるという点だと思っています。 全ての関数がカリー化されているという事は、全ての関数は一つしか引数を取らないので、(f x y z)と書いたら、(((f x) y) z)と解釈して良くなるわけです。一番外側の括弧を無視すればHaskellの関数適用と同じルールですね。

普通のLispのコードに(((f x) y) z)みたいな形が出てくる事は稀な気がしますが、これの真の力はもう少ししたら説明できます。

欠点としては、可変長引数が使えなくなる事ですか。

遅延評価にしてみる

またHaskellを真似して、Carrotは遅延評価するということにします。 するとHaskellみたいにリストは勝手に遅延シーケンスになるので、delayだforceだとノイズを入れずに無限リストが作れます。また、普通のLispならマクロでないと実現できない事を関数として表現できたりします。

(= ints-from x (cons x (ints-from (inc x))))
(= integers (ints-from 0))
(take (map integers (* 2)) 5)  ;;=> [0 2 4 6 8]


(= or x y (if x true (if y true false)))
(or 5 (/ 1 0)) ;;=> 5   ...ちゃんとショートサーキットされる

型なしλ計算をしてみる

λ計算の評価戦略は名前呼び出しなので、遅延評価とは相性が抜群です。 とりあえず真偽値を型なしλ計算で表現してみます。

(= true  x y x)           ;;true  = λxy.x
(= false x y y)           ;;false = λxy.y

真偽値をこのように表現すると、ifは(= if b x y (b x y))となり、もはやifは必要なくなります。カリー化の時に、勝手に左結合になるようにしたので、真偽値を返す式に二つ式を与えてやればifの代わりになります。

;;Scheme
(define (fact n)
  (if (= n 0) 1 (* n (fact (dec n)))))

;;Carrot
(= fact n
   (=? n 0 1 (* n (fact (dec n)))))

次はリストを型なしλ計算で表現します。

(= cons x xs f (f x xs))  ;;cons = λxyf.fxy
(= car  xs (xs true))     ;;car  = λx.x(λyz.y)
(= cdr  xs (xs false))    ;;cdr  = λx.x(λyz.z)

ここで、consのfには通常carやcdrが与える関数が入るわけですが、別にcarとcdr以外だってこういうことしてもいいじゃないかと気付きました。

(= -map xs f
   (xs (^ x xs (cons (f x) (xs -map f)))))

(= -filter xs f
   (xs (^ x xs (f x (cons x (xs -filter f))
                    (xs -filter f)))))

(= -fold x xs f init ...)

([1 2 3 4 5] -map (* 2) 
             -map (+ 2) 
             -filter even?
             -fold + 0)

といった、一見メッセージパッシングみたいな式が書けたりします。ちょっと恰好良いでしょ。

型なしλ計算に型を付けてみる

静的に型付けできるならしておいた方がお得です。型チェッカが矛盾を見つけてくれるなら見つけてもらった方がいいですよね。

型なしλ計算のリストのような、クロージャで表現されたデータを型付けするのはわりかし難しいです。代数データ型を導入せずにクロージャで代数データ型のようなことをする方法を考えました。

関数定義の構文を拡張して、関数の型を書けるようにします。データを表現するクロージャのコンストラクタは、型宣言のところにコンストラクタが取る引数よりいくつか少ない数の引数の型と、データ型の名前を書きます。すると部分適用された状態のクロージャに型が付けられます。

いくつか明らかな問題点があるのでこれはまだアイディア段階です。

(= (true  Bool) x y x)
(= (false Bool) x y y)

(= (cons a (List a) (List a)) 
   x xs f (f x xs))
(= (nil (List a)) 'nil)
(= (car (List a) a) 
   xs (xs true))
(= (cdr (List a) (List a)) 
   xs (xs false))

今実験中の実装では、関数は型を必須にして、型チェッカはmain関数の中の式だけをチェックするようにしています。

全部総称関数にしてみる

せっかく関数の型宣言ができるようになったなら総称関数を書きたいです。 型チェッカがあるので、ある総称関数適用式がどの関数を使うのかは静的に決定できるというのも総称関数を導入するモチベーションの一つです。

(= (++ String String String) s1 s2 (string-append s1 s2))
(= (++ (List a) (List a) (List a)) xs ys (append xs ys))
(++ "Hello, " "world!")
(++ [1 2 3] [4 5 6])

MOP

せっかく総称関数を導入するなら、MOP的な仕組みを作りたくなります。例えば関数適用式を見つけたら呼ばれるcall関数とかを定義できるようにすると、Clojureでマップやセットがcallableになっているのと似たような事ができます。

(= (call (List a) (Fn (List a) b) b) xs f (__call__ f xs))
(= (call Number (Fn Number b) b) x f (__call__ f x))
(= (call (Fn a b) a b) f x (__call__ f x))

;;以下が全てvalidなS式になる
(car xs)
([1 2 3 4] map (* 2) map (+ 2) filter even? fold + 0)
(2 + 3 - 4 * 2)

まとめ

アイディア次第でS式は化けます