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の作法は、このマニュアルに従うところが多い気がする。

DOMAP-AND,DOMAP-OR (Maclisp/LET.LSP)

| 15:02 | DOMAP-AND,DOMAP-OR (Maclisp/LET.LSP) - わだばLisperになる を含むブックマーク はてなブックマーク - DOMAP-AND,DOMAP-OR (Maclisp/LET.LSP) - わだばLisperになる

今回も前回と同じMaclispのLET.LSPからDOMAP-AND、DOMAP-ORに挑戦してみることにしました。

お題:

;;; DOMAP-AND evaluates a form, on successive tails of a list, returning ()
;;;  if any of the evaluations if (), and returning the last one if not.
;;; DOMAP-OR returns the first non-() one, or () if all are ().
;;; Syntax is (DOMAP-and/or (VAR1 <first-form>) ... (VARn <last-form>) <pred>)
;;;   Items in angle-brackets are evaluated, and the names "VARi" are used
;;;   as the stepping variables to use;  <pred> is a "predicate" form.
;;;   Typical use -  (DOMAP-AND (TEMP DATA-LIST) (NOT (LOSEP (CAR TEMP))))
(macro DOMAP-AND (x) 
  (bind-let ((forms (cdr x)) pred (g (gensym)))
	    (setq pred (car (setq forms (reverse forms)))
		  forms (nreverse (cdr forms)))
	    `(DO ((,g)
		  ,.(mapcar #'(lambda (x) `(,(car x) ,(cadr x) (CDR ,(car x))))
			    forms))
		 ((NOT (AND ,.(mapcar #'CAR forms))) ,g)
	       (OR (setq ,g ,pred) (RETURN () )))))

(macro DOMAP-OR (x) 
  (bind-let ((forms (cdr x)) pred (g (gensym)))
	    (setq pred (car (setq forms (reverse forms)))
		  forms (nreverse (cdr forms)))
	    `(DO ((,g)
		  ,.(mapcar #'(lambda (x) `(,(car x) ,(cadr x) (CDR ,(car x))))
			    forms))
		 ((NOT (AND ,.(mapcar #'CAR forms))) () )
	       (AND (setq ,g ,pred) (RETURN ,g)))))

初見時の感想:

  • どういう時に便利なマクロなのかいまいち想像がつかない…。
  • コードの内容はdomap-and/orの違いはちょっとの違いしかない。

暗記で再現:

(defmacro DOMAP-AND (&body forms)
  (let (pred (g (gensym)))
    (setq pred (car (setq forms (reverse forms)))
	  forms (nreverse (cdr forms)))
    `(DO (,g
	  ,.(mapcar (lambda (x) `(,(car x) ,(cadr x) (CDR ,(car x)))) forms))
	 ((NOT (and ,.(mapcar #'car forms))) ,g)
       (OR (setq ,g ,pred) (RETURN () )))))

(defmacro DOMAP-OR (&body forms)
  (let (pred (g (gensym)))
    (setq pred (car (setq forms (reverse forms)))
	  forms (nreverse (cdr forms)))
    `(DO (,g
	  ,.(mapcar (lambda (x) `(,(car x) ,(cadr x) (CDR ,(car x)))) forms))
	 ((and ,.(mapcar #'car forms)) () )
       (AND (setq ,g ,pred) (RETURN ,g )))))

また、これもdefmacroに翻訳してみました。細かいところはちょっと違うけど、なんとかできました。

使い方:

(domap-and (tem '(1 2 3 4 5))
	   (tem2 '(10 20 30 40 50))
	   (print (* (car tem) (car tem2))))
=>
10 
40 
90 
160 
250 

みたいになるのだろうか。やっぱり「これは便利だ!」という使用法が思い付かない…。

技法的なこと:

(setq pred (car (setq forms (reverse forms)))
      forms (nreverse (cdr forms)))

妙に巧妙で妙に感心してしまう。自分なら、

(setq pred (car (last forms))
      forms (butlast forms))

と書いてしまいそう。

BIND-LET (Maclisp/LET.LSP)

| 14:33 | BIND-LET (Maclisp/LET.LSP) - わだばLisperになる を含むブックマーク はてなブックマーク - BIND-LET (Maclisp/LET.LSP) - わだばLisperになる

今回は、MaclispのLET.LSPのBIND-LETをお題にしてみました。

これも大体30年位前のコードです。

お題:

(macro BIND-LET (x)
   ((lambda (ll w vars vals)
	    (do ((l ll (cdr l)))
		((null l))
		(push (cond ((atom (car l)) (push () vals) (car l))
			    ('T (push (cadar l) vals) (caar l)))
		      vars))
	    `((LAMBDA (,.(nreverse vars)) ,.w) ,.(nreverse vals)))
       (cadr x) (cddr x) () () ))

初見時の感想:

  • macroの動作は多分、
(defmacro macro (name (arg) &body body)
  `(defmacro ,name (&whole ,arg &rest bvl-decls-and-body)
     (declare (ignore bvl-decls-and-body))
     ,@body))

のようなものだと思う。

再現:

(defmacro BIND-LET (binds &body body)
  ((lambda (ll w vars vals)
     (do ((l ll (cdr l)))
	 ((endp l))
       (push (cond ((atom (car l)) (push () vals) (car l))
		   ('T (push (cadar l) vals) (caar l)))
	     vars))
     `((lambda (,.(nreverse vars)) ,.w) ,.(nreverse vals)))
   binds body () () ))

感想:

macroの個所をdefmacroに読み替えて再現してみました。

bind-letは要するに普通のletでした。

マクロの中で、letの代わりにlambdaを使って変数を束縛するというのも、場合によってはありなのかもしれないと思ったり。まあ、今回の場合は、letが無い環境なので、lambdaを使っているわけではありますが…。

技法的なこと:

(push (cond ((atom (car l)) (push () vals) (car l))
            ('T (push (cadar l) vals) (caar l)))
      vars)

pushを入れ子にすることで、atomかどうかの判定を一回にまとめている。

どうでも良いこと:

  • 「condのelse節のtは、大文字にしてクオートを付ける」派
  • 「nilも'()も、とにかく()と書く」派