標高+1m

Don't be rational

Lispから可変長引数を引き算したらできること

f:id:ympbyc:20150907225639p:plain

Schemeから可変長引数を引き算したら -- Island Life

Shiroさんが面白い記事書かれてたので、前に実際に可変長引数をなくしたLispを作って発見したことを紹介します。*1

実装者とは全く別の、遊ぶ人の視点からの記事です。

この記事では意図的にマクロを一切使わないという制約のもと、いわばラムダ計算パズルをします。

左結合のカッコを省略する

少々恣意的ですが、

((compose f g) x)

;;こう書ける
(compose f g x)

こういうこと、引数の数が固定なのでカッコを省略しても一意に評価できます。関数を返す高階関数を使うときに便利。以下の例では全てこの仕組みを存分に活用します。

list関数もクオートも使わずにリストを作る

Shiroさんの記事で言及されていたように、可変長引数がないと (list 1 2 3 4) ができなくて不便です。これも一工夫でうまいことできます。要するに1つずつ cons していけばいいって話ですが、それでは面倒なので前項の仕組みを活用します。

まず cons, car, cdrの仕組みを思い出してみます。

(define (cons x xs)
  (lambda (f) (f x xs)))

(define (car xs)
  (xs (lambda (y ys) y)))

(define (cdr xs)
  (xs (lambda (y ys) ys)))

こうですね。*2 2値にconsを適用するとクロージャに評価されます。
ここでちょっと寄り道して carcdr を少しシンプルにした -car-cdr を作ります。

(define (-car x xs) x)

(define (-cdr x xs) xs)

;;すると

(cons 1 (cons 2 '()) -cdr -car) ;;=> 2

こうやって後置のリスト関数が作れるわけですね。同じ理屈で中置バージョンのcons、 <: を作ってみます。

(define (<: x xs)
  (lambda (y) (cons y (cons x xs))))

時間がかかりましたがこれを左結合カッコの省略と組み合わせると、やりたかったことが実現できます。

(cons 1 '() <: 2 <: 3 <: 4 <: 5) ;;=> '(5 4 3 2 1)

;;おまけ

(define (list x)
  (cons x '()))

(list 5 <: 4 <: 3 <: 2 <: 1) ;;=> '(1 2 3 4 5)

まあ普通の list よりはちょっと不便ですが見た目は綺麗でしょ?

リスト関数の後置、中置化

同じように他のリスト関数も後置または中置バージョンを作ると便利です。予め引数の順番を変更したリスト関数を作っておきます。

(define (map* xs f) (map f xs))
(define (filter* xs f) (filter f xs))
;;etc

(define (prefix f)
  (lambda (x xs) (pa$ f (cons x xs))))

(define -map (prefix map*))
(define -filter (prefix filter*))
(define -take (prefix take))
;;etc

こうすると

(list 6 <: 5 <: 4 <: 3 <: 2 <: 1
 -filter even?
 -map    (pa$ * 2)
 -take   2
 -fold   + 0)      ;;=> 20

便利でしょ?

パイプライン演算子

この仕組みで中置化できるのはなにもリスト関数だけではありません。関数合成 compose を中置化してF#のパイプライン演算子 |> や、clojureのスレッドマクロ -> のような関数を作ります。例によってマクロではなくただの関数です。

(define (-> x)
  (lambda (f)
    (lambda (g)
      (f (g x)))))

(define <- identity)

(-> 2
 -> (pa$ + 3)
 -> (pa$ * 4)
 <- number->string)   ;;=> "20"

中置とは言っても最初の値をラップする仕組みのためにちょっと不思議な見た目になります。 -> で計算をつないでいって、 <- で結果を取り出します。

まとめ

  • 可変長引数を撤廃することで、左結合のカッコを省略できます。
  • するといろいろ面白いことができます。

Land of Lisp最高です。

続き: Gaucheで実験できるようにしてみました。

ympbyc.hatenablog.com

ちなみに、もうずっと触ってなくて動くかわからないんですが、実験に使ったオレオレLispはこれです。

github.com

*1:この処理系ではデフォルトのカリー化もやっていて、これを使うともっと面白いこともできるんですが今回は割愛します。

*2:実際のScheme処理系ではconsセルをクロージャで表現するということはしないと思いますがここでは忘れます。