星にゃーんのブログ

ほとんど無害。

iotaからunfoldをつくる Common Lisp編

Lisp

まず、iotaを定義する。 簡潔にするため、オプション引数は使わない。

(defun iota (limit seed step)
  (if (> seed limit)
    nil
    (cons seed (iota limit (+ seed step) step))))

(> seed limit)を一般化して、終了条件を指定できるよう変更する。

(defun func1 (pred seed step)
  (if (funcall pred seed)
    nil
    (cons seed (func1 pred (+ seed step) step))))

(+ seed step)を一般化して、seedの変化を指定できるよう変更する。

(defun func2 (pred next-gen seed)
  (if (funcall pred seed)
    nil
    (cons seed (func2 pred next-gen (funcall next-gen seed)))))

最後に、mapcar関数と合成する。

(defun func3 (pred fn next-gen seed)
  (if (funcall pred seed)
    nil
    (cons (funcall fn seed)
          (func3 pred fn next-gen (funcall next-gen seed)))))

もっと単純に、こうしてもいい。

(defun func3 (pred fn next-gen seed)
  (mapcar fn (func2 pred next-gen seed)))

これでunfold関数の完成。

(defun unfold (p f g n)
  (if (funcall p n)
    nil
    (cons (funcall f n)
          (unfold p f g (funcall g n)))))

参考URL

Scheme 継続

技術メモ Lisp

もうひとつのScheme入門 16. 継続を写経した。

「継続」は、計算において必ず存在する。 しかし、明示的に扱われることが少ない。

例えば、

(* 3 (+ 1 2))

のような計算があるとき、(+ 1 2)を評価した後の残りの計算は、(* 3 _)である。 この部分を継続と呼ぶ。

継続渡しスタイル

継続は、第一級関数をもつ言語であれば、CPS(継続渡しスタイル)によってあつかうことができる。

これは、関数が値を返す部分に、計算結果をどんな関数に渡すのかを引数で指定する方法。

(define (id x)
  x)

(define (k+ a b k)
  (k (+ a b)))

(define (k* a b k)
  (k (* a b)))

この関数群を使って、先ほど示したコードを書くとこうなる。

(k+ 1 2 (lambda (x) (k* 3 x id)))

関数適用の順番が入れ替わっている。

再帰関数のCPS化

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(define (kfact n k)
  (if (= n 1)
      (k 1)
      (kfact (- n 1) (lambda (x) (k (* n x))))))

一つ目が通常の階乗。二つ目がCPS階乗。 CPS版は末尾再帰になっている。 このように、再帰関数をCPS化することで、末尾再帰に変換できる。 Schemeは末尾再帰をループに最適化するので、とても嬉しい。

call/cc

call/ccを使うと、継続によるジャンプができる。

> (* 3 (call/cc (lambda (k) (+ 1 2))))
9 ;継続が呼ばれていないので、普通の式と同じ
> (* 3 (call/cc (lambda (k) (+ 1 (k 2)))))
6 ;継続kが呼ばれ、(* 3 2)を計算し、トップレベルに6が返る

(define cc)
(* 3 (call/cc (lambda (k)
                 (set! cc k)
                 (+ 1 2))))

> (+ 100 (cc 3))
9
> (+ 100 (cc 100))
300

継続を呼ぶと、その後の式を無視してトップレベルに戻る。

具体的な使用方法は後でまとめる。

SBCLで(progn (princ hoge) (read))の実行順序が入れ替わるときの対処法

Lisp

問題のコードがこれ

(defun read-with-prompt ()
  (princ "> ")
  (read))

CLISPではきちんと動く。

[1]> (read-with-prompt)
> hoge
hoge

SBCLではこうなる。

* (read-with-prompt)
hoge
> 
hoge

princよりも先にreadが実行されてしまう。 この問題は、SBCLの最適化が原因らしい。 (finish-output)で出力の終了を明記するとうまく動く。

修正後のコード

(defun read-with-prompt ()
  (princ "> ")
  (finish-output)
  (read))

下記のコードを書いている時にこの問題を発見した。

じゃんけん

declaim

Lisp 覚え書き 
(declaim (inline function-name))

declaimはマクロ。 型宣言したり、インライン展開したり、コードの最適化に使われる。

http://cl.cddddr.org/index.cgi?%e6%9c%80%e9%81%a9%e5%8c%96#H-1yksz98dk7cep ここが詳しい。

Land of Lisp 読んでみた。

Lisp

Land of Lisp

Land of Lisp

これを買った。 表紙にいる緑色の怪物はLispエイリアンというらしい。 キモカワ。

ざっと見た感じ、すごいH本とかリーダブルコードみたいな雰囲気。

"はじめに"のイラストに爆笑した。 「お宅の床下にはストラウストラップの大きな巣があるようです 。」 Amazonのプレビューでも見れる。

軽快なノリと愉快な漫画でさくさく読み進めると、いつの間にかLispエイリアンが脳内に住み着く、そんな感じの本。 他のプログラミング言語の経験があって、Common Lispで遊んでみたいという人におすすめしたい。

また時間があいたら、Lispのマクロについてまとめたい。