Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2007-10-03

rev (Lisp 1.5マニュアルより)

| 16:49 | rev (Lisp 1.5マニュアルより) - わだばLisperになる を含むブックマーク はてなブックマーク - rev (Lisp 1.5マニュアルより) - わだばLisperになる

今回は、Lisp 1.5のマニュアル*1の中のrevに挑戦してみます。

1962年出版のようなので、恐らく45年前のコードです。

お題:

; function rev, which reverses a list and all its sublists is an example of this.
rev[x] = prog[[y;z];
A    [null[x] → return[y]];
     z:= car[x];
     [atom[z] → go[B]];
     z:= rev[z];
B    y: = cons[z;y];
     x:= cdr[x];
     go [A]];

The function rev will reverse a list on all levels so that
rev[(A ((B C) D))] = ((D (C B)) A)

初見時の感想:

  • 動作としては、入れ子になったリストも全部反対にするreverseの様子.
  • S式じゃなくてM式だ。
  • gotoと再帰の共存を初めて目にした。

暗記で再現:

(defun rev (lst)
  (prog (x y res)
        (setq x lst)
     a  (cond ((endp x) (return res)))
        (setq y (car x))
        (cond ((atom y) (go b)))
	(setq y (rev y))
     b  (setq res (append (list y) res))
        (setq x (cdr x))
	(go a)))

まあ、大体同じに再現できたと思う。返り値のリストの作成は、consで可能だった。

お題をS式に書き直したもの:

(defun rev (x)
  (prog (y z)
     a  (cond ((null x) (return y)))
        (setq z (car x))
	(cond ((atom z) (go b)))
	(setq z (rev z))
     b	(setq y (cons z y))
	(setq x (cdr x))
	(go a)))

考察:

doで書き直してみる(goあり)

;; 
(defun rev (lst)
  (do ((x lst (cdr x))
       y
       res)
      ((endp x) res)
    (setq y (car x))
    (cond ((atom y) (go B)))
    (setq y (rev y))         ;非共通処理
  B (setq res (cons y res))))

要約するとBに飛ぶのは、共通でない処理をスキップするためなので、

(defun rev (lst)
  (do ((x lst (cdr x))
       y
       res)
      ((endp x) res)
    (setq y (car x))
    (setq y (if (atom y) y (rev y)))
    (setq res (cons y res))))
→圧縮
(defun rev (lst)
  (do ((x lst (cdr x))
       y
       res)
      ((endp x) res)
    (setq y (if (atom (setq y (car x))) y (rev y)))
          res (cons y res)))

とか

(defun rev (lst)
  (let (res)
    (dolist (l lst res)
      (setq l (if (atom l) l (rev l)))
      (push l res))))

と今なら書けるところかもしれない。

しかし、45年前のLisp 1.5で同じことができるのかは謎。

どうでも良いこと:

  • 古代LISPのPROGの作法は、このマニュアルに従うところが多い気がする。