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

f:id:ympbyc:20150907225639p:plain

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を適用するとクロージャに評価されます。
ここでちょっと寄り道して car と cdr を少しシンプルにした -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"