Lisp

半年ほど前からLispを勉強し始めて、だらだらとS式で遊んでおります。
で、先日ニコ動にニワン語によるLispインタプリタが投下されたんですが ( http://blog.bugyo.tk/lyrical/2008/05/lisp_1.html) 　昨日lambdaやdefun等が追加されて大変楽しげになったので遊んでみた。

掛け算と冪乗

(defun * (m n) (if (eq n 1) m (+ m (* m (- n 1)))))
(defun ** (m n) (if (eq n 1) m (* m (** m (- n 1)))))

(** 3 2)の時点で時間ぎりぎり。

正負判定・比較

(defun r (a b) (if (eq a 1) 1 (if (eq b 0) 0 (r (- a 1) (- b 1))))) ;補助
(defun +? (n) (if (eq (r n (- 0 n)) 0) () n))

(defun <= (m n) (+? (- n m)))
(defun < (m n) (+? (- (+ n 1) m)))

商・剰余

(defun / (m n) (if (< m n) 0 (+ 1 (/ (- m n) n))))
(defun % (m n) (if (< m n) m (% (- m n) n)))

と、ここまで書いて文字数制限で正負判定の補助関数が使えないことに気付くorz 助けてゴルファー。
まあ、短くできたところで再生時間が足りないか…
とりあえずxyzzyで動作確認したけど、CL処理系で試す時はeqを=とかequalに替えないと死ぬので注意。

チャーチ数

(defun zero () (lambda (f) (lambda (x) x)))
(defun one () (lambda (f) (lambda (x) (f x))))
(defun two () (lambda (f) (lambda (x) (f (f x))))
(defun pow () (lambda (n) (lambda (m) (m n))))

succ,plus,mult等は字数オーバー。
((((two) (two)) (lambda (i) (+ i 1))) 0) がなんとか時間内に答え出た。

リスト

(defun last (l) (if (cdr l) (last (cdr l)) l))
(defun nth (i l) (if (eq i 0) (car l) (nth (- i 1) (cdr l))))
(defun member (i l) (if (eq i (car l)) l (member i (cdr l))))

nth, memberは関数名変えないと字数オーバー。

バグ?

(defun if0 (n a b) (if (eq 0 n) a b))
(if0 0 1 2) ;=> 2
((lambda (n) (if (eq 0 n) 1 2) 0) ;=> 2
((lambda (n) (if (eq n 0) 1 2) 0) ;=> 1