逆引きxyzzy lisp(関数) - circleratio/xyzzy GitHub Wiki
defun, lambda
labels, flet
interactive 関数を使う． この関数の引数に与える文字列で対話の行いかたを指示する．
*複数個の引数を与えるには "\n" で区切る． *数値の引数としては整数しか与えることができないため，浮動小数点を与えたい場合には文字列を経由する必要がある．
(defun bmi (weight height)
"Calculate BMI."
(interactive "sWeight(kg): \nsHeight(m): ")
(let* ((w (if (numberp weight)
weight
(read-from-string weight)))
(h (if (numberp height)
height
(read-from-string height)))
(b (/ w (* h h))))
(message "BMI: ~,1F" b)
b))
高階関数とは関数を引数に取る関数。 個々の問題に対して関数を書くのでなく、多くの問題に共通する部分を取り出しておけば再利用がしやすくなる。 たとえば、ソートにおいて並べ替えのロジックと大小判定を切り離しておくことで、さまざまな条件のソートを簡単に行えるようになる。
主な形としては、ソート、フィルタ、マップ、畳み込み、解きほぐしがある。
(sort '(3 1 5 2 4) #'<)
=> (1 2 3 4 5)
畳み込みの例題のひとつとして取り上げているので，そちらを参照すること．
(map 'list (lambda (x) (+ 1 x)) '(1 2 3 4 5))
=> (2 3 4 5 6)
畳み込みを行う関数 reduce は関数型言語を学ぶ上での重要ポイント。 なぜなら、大抵のリスト処理を書くことができる一般的な関数だから。
(1 2 3 4 5) => (5 4 3 2 1)
を実現したいとする。
まずは、同じ操作の重ね合わせで表現できないか考える(それがまさに畳み込み)。 すると次のように書ける。
(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 nil)))))
=> (5 4 3 2 1)
これを式で表現すればよい。
(defun my-reverse (lst)
(reduce (lambda (x y) (cons y x))
lst
:initial-value nil))
(my-reverse '(1 2 3 4 5))
=> (5 4 3 2 1)
同様に考える。 やりたいことは
(1 2 3 4 5) => (1 2 3 4 5)
であるが、これは
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil)))))
=> (1 2 3 4 5)
と書ける。 したがって式での表現は次のようになる。
(defun my-copy-list (lst)
(reduce #'cons
lst
:from-end t
:initial-value nil))
(my-copy-list '(1 2 3 4 5))
=> (1 2 3 4 5)
やりたいこと:
(1 2 3 4 5) => ((f 1) (f 2) (f 3) (f 4) (f 5))
書き下す。
(cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) (cons (f 5))))))
式に置き換える。
(defun my-mapcar (func lst)
(reduce (lambda (x y) (cons (funcall func x) y))
lst
:initial-value nil
:from-end t))
(my-mapcar #'1+ '(1 2 3 4 5))
=> (2 3 4 5 6)
やりたいこと
(1 2 3 4 5) => 5
書き下す。
(+ (+ (+ (+ (+ 0 1) 1) 1) 1) 1)
=> 5
結果。
(defun my-length (lst)
(reduce (lambda (x y) (+ x 1))
lst
:initial-value 0))
(my-length '(1 2 3 4 5))
=> 5
わかりやすくするために「条件: 奇数」として、やりたいこと。
(1 2 3 4 5) => (1 3 5)
書き下す。
(cons 1 (cons 3 (cons 5 nil)))
=> (1 3 5)
式にする。 このタイミングで「奇数」の部分は一般化する。
(defun my-filter (func lst)
(reduce (lambda (x y)
(if (funcall func x)
(cons x y)
y))
lst
:initial-value nil
:from-end t))
(my-filter #'oddp '(1 2 3 4 5))
=> (1 3 5)
やりたいこと．
'(1 2 3) '(4 5 6) => '(1 2 3 4 5 6)
書き下す．
(cons 1 (cons 2 (cons 3 '(4 5 6))))
=> (1 2 3 4 5 6)
結果．
(defun my-append (ls1 ls2)
(reduce (lambda (x y) (cons x y)) ls1
:initial-value ls2
:from-end t))
=> my-append
(my-append '(1 2 3) '(4 5 6))
=> (1 2 3 4 5 6)
畳み込み関数の一般形は次のように書ける． reduce は，:from-end オプションの指定により，両方の動作を切り替えて実行できる．
(defun fold-left (fn a ls)
(if (null ls)
a
(fold-left fn (funcall fn a (car ls)) (cdr ls))))
(defun fold-right (fn a ls)
(if (null ls)
a
(funcall fn (car ls) (fold-right fn a (cdr ls)))))
リストを生成する関数の一般形は次のようになる。 仕様は SRFI-1 から。
(defun unfold (p f g seed &optional (tail-gen #'(lambda (x) nil)))
(if (funcall p seed)
(funcall tail-gen seed)
(cons (funcall f seed)
(unfold p f g (funcall g seed) tail-gen))))
(defun unfold-right (p f g seed &optional (tail nil))
(labels ((iter (seed acc)
(if (funcall p seed)
acc
(iter (funcall g seed) (cons (funcall f seed) acc)))))
(iter seed tail)))
p は終了条件、tail-gen は終端を与える。 g は seed を更新するために使い、f は適用される関数。
( (f (g seed)) ; g を 1 回適用
(f (g (g seed))) ; g を 2 回適用
(f (g (g (g seed)))) ; g を 3 回適用
...
(f (g (g ... (g seed) ...))) ) ; g を n 回適用
以下は使用例。
(unfold #'(lambda (x) (> x 10)) #'identity #'1+ 1)
=> (1 2 3 4 5 6 7 8 9 10)
(unfold-right #'(lambda (x) (> x 10)) #'identity #'1+ 1)
=> (10 9 8 7 6 5 4 3 2 1)
(unfold #'(lambda (x) (> x 10)) #'(lambda (x) (* x x)) #'1+ 1)
=> (1 4 9 16 25 36 49 64 81 100)
(apply #'+ '(1 2 3))
=> 6
(funcall #'+ 1 2 3)
=> 6
xyzzyでは末尾再帰の最適化はない。
例題:
(defun fact (n)
(if (= n 0) 1
(* n (fact (1- n)))))
(fact 5)
=> 120
末尾再帰に変換するには、累積変数に値を格納するのが定石。
(defun fact-tail-recursion (n result)
(if (= n 0) result
(fact-tail-recursion (1- n) (* n result))))
(fact-tail-recursion 5 1)
=> 120
さらにループに変換するには、ループ変数を用いて繰り返しに書き換える。
(defun fact-loop (n &optional (step 1))
(do ((i 1 (+ i step))
(result 1))
((> i n) result)
(setq result (* result i))))
(fact-loop 5)
=> 120
ある関数が何度も同じ引数で呼び出されるケースでは、一度計算した値はメモしておき、2度目以降では計算なしで値をすぐ返すようにすると効率がよい。
このテクニックをメモ化という。 具体例は「アルゴリズムxyzzy lisp(メモ化再帰)」を参照すること。
遅延評価は関数型言語の強力な武器である． 遅延評価は「ある関数について，まさにそれが必要になった時にしか評価しない」ことであるが，これによりプログラムのモジュール化，並列化を行えるからである．
また，不必要な関数評価を省くことにより，性能の向上も期待できる．
ただし，xyzzy lisp は遅延評価を組み込みでは備えていないため，自分で処理を書く必要がある．
(defconstant unforced (gensym))
(defstruct delay forced closure)
(defmacro delay (expr)
(let ((self (gensym)))
`(let ((,self (make-delay :forced unforced)))
(setf (delay-closure ,self)
#'(lambda () (setf (delay-forced ,self) ,expr))) ,self)))
(defun force(x)
(if (delay-p x)
(if (eq (delay-forced x) unforced)
(funcall (delay-closure x))
(delay-forced x))
x))
; delay をかますと、1+ がすぐには計算されない
(let ((x 2))
(setq d (delay (1+ x))))
=> #S(delay forced #:G1 closure #<lexical-closure: (anonymous)>)
; force を使った時点で、1+ が評価される
(force d)
=> 3
呼ぶ側で cons を行い、呼ばれる側では終端で nil を返す。 nil を cons や append してもリストが変わらないことを利用する。