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 |

2008-01-31

末尾再帰的DEFUN (2)

| 04:53 | 末尾再帰的DEFUN (2) - わだばLisperになる を含むブックマーク はてなブックマーク - 末尾再帰的DEFUN (2) - わだばLisperになる

何となく釈然としないまま、一旦放置した末尾再帰的DEFUNですが、何となく眺めていると末尾再帰をgo-toに変換するんじゃないのかなあ、という気がしてきました。

つまり明示的に末尾再帰で書かれたものを、完全なループに変換するという目的のものだったのではないかと思えてきました。

そう考えると、関数呼び出しの個所をgo-toに変換すれば良いのですが、

(defun fib (n &optional (a1 1) (a2 0))
  (if (< n 2)
      a1
      (fib (1- n) (+ a1 a2) a1))))

のような末尾再帰の定義は

(defun fib (n &optional (a1 1) (a2 0))
  (prog ()
    L   (if (< n 2)
	    (return a1)
	    ((lambda (t1 t2 t3) (setq n t1 a1 t2 a2 t3) (go L)) (1- n) (+ a1 a2) a1)))))

のようにすれば、マクロで置き換えるのも、そんなに大変でもないかなと。

本当は、

(defun fib (n &optional (a1 1) (a2 0))
  (prog ()
    L   (if (< n 2)
	    (return a1)
	    (progn (setq n (1- n) a1 (+ a1 a2) a2 a1) (go L))))))

という風にするべきな気もします。スタックの使われ方とか、その辺に違いがありそうですが、disassemしても良く分からなかったので、とりあえず、lambdaの方で行くことにしました。

それで、この場合、PROGの中に展開されるので、最終的に値を返すところには、returnを付けないといけない訳なのですが、それがどこなのか判別するのは至難の技なので、逆にRETURNの中に展開してしまうことにしました。オリジナルもこういう感じなのですが、こういうことなのかも知れません。

(defun fib (n &optional (a1 1) (a2 0))
  (prog ()
    L   (return (if (< n 2)
		    a1
		    ((lambda (t1 t2 t3) (setq n t1 a1 t2 a2 t3) (go L)) (1- n) (+ a1 a2) a1))))))

そんなこんなでいつものごとくガチャガチャと自分なりに作ってみました。

RETURN式の中から外にgotoとかして良いのかしら、とか思ったりしますが、これって手法としてはありななんですかねえ。

;; 動作
(tail-recursive-defun fib (n &optional (a1 1) (a2 0)) 
  (if (< n 2)
      a1
      (fib (1- n) (+ a1 a2) a1)))

;; マクロ展開=>
(DEFUN FIB (N &OPTIONAL (A1 1) (A2 0))
  (PROG ()
     #:G3105
     (RETURN
       (IF (< N 2) 
	   A1
	   ((LAMBDA (#:G3106 #:G3107 #:G3108)
	      (SETQ N #:G3106 A1 #:G3107 A2 #:G3108)
	      (GO #:G3105))
	    (1- N) (+ A1 A2) A1)))))

;; 定義 --------
;; 関数呼び出し部分をgo-to付きのlambda式で置き換え
(defun fn-to-lambda (new old expr)
  (flet ((self (x) (fn-to-lambda new old x)))
    (cond ((atom expr) expr)
	  ((and (consp expr) (eq (car expr) old))
	   (cons new (mapcar #'self (cdr expr))))
	  ('T (cons (funcall #'self (car expr)) (mapcar #'self (cdr expr)))))))

;; 関数をgo-to付きのlambda式に変換
(defun funcall-to-goto (args gotag)
  (let ((syms (mapcar (lambda (x) `(,x ,(gensym))) args)))
    `(lambda ,(mapcar #'cadr syms) (setq ,@(mapcan #'identity syms)) (go ,gotag))))

;; 余計なパラメータを削除
(defun remove-&param (expr)
  (mapcar (lambda (x) (if (consp x) (car x) x))
	  (remove-if (lambda (x) (member x '(&optional &rest &key))) expr)))

;; 本体
(defmacro tail-recursive-defun (name args &body body)
  (let ((go-tag (gensym))
	(decl (if (eq 'declare (and (consp (car body)) (caar body)))
		  `(,(pop body))
		  ())))
    `(defun ,name ,args
       ,@decl
       (prog ()
	  ,go-tag
	  (return
	    ,@(fn-to-lambda (funcall-to-goto (remove-&param args) go-tag) name 
			    body))))))
 ;

末尾再帰的DEFUN

| 02:12 | 末尾再帰的DEFUN - わだばLisperになる を含むブックマーク はてなブックマーク - 末尾再帰的DEFUN - わだばLisperになる

今日は、Arcもいじっていたのですが、なんとなくSAILのMACLISPのコードも漁っていました。

SAILのものは非常に野心的というか、変態的というか、妙なコードが多いのですが、ふと以前から気になっていたTAIL-RECURSIVE-DEFUNのコードを追っ掛けてみることにしました。

実際のコードはこちらです。

SAILの変態っぷりは、恐らくRichard P.Gabriel氏によるところが非常に大きいと思うのですが、何となくこのTAIL-RECURSIVE-DEFUNもそんな香りがします。

とりあえず、探ってみたいのは、このコードです。

(DEFUN (TAIL-RECURSIVE-DEFUN MACRO)(X)
  ((LAMBDA(?F-NAME *TYPE)
    ((LAMBDA(*ARGS *DEFINITION)
      ((LAMBDA(?GO-LABEL)
	(α-GRAB-TAILS *ARGS *DEFINITION ?GO-LABEL)
	(CCODE (DEFUN ?F-NAME *TYPE (*ARGS) (PROG NIL
						  ?GO-LABEL
						  (RETURN (PROGN *DEFINITION))))))
       (GENSYM)))
     (COND (*TYPE (CADDDR X))(T (CADDR X)))
     (COND (*TYPE (CDDDDR X))(T (CDDDR X)))))
   (CADR X)
   (COND ((MEMQ (CADDR X) '(EXPR FEXPR))
	  (LIST (CADDR X)))
	 (T NIL))))
 ;

これは一体何をするものなのか。自動で末尾再帰に変換してくれるのか。それとも他に末尾再帰的な何かの特長があるのか、謎です…。

とりあえず、もの凄くLAMBDAがネストしているのですが、これはLETの役割です。それで、DEFUNになっているのですが、MACLISPでは、DEFUNでマクロも定義でき、この場合、マクロを定義しています。

最終的には、(defun foo (n) ...body)のように展開されたものができるんじゃないかと思います。

それでこのTAIL-RECURSIVE-DEFUNが依存している関数で独自に定義されたものを追っ掛けてみます。

とりあえず、MACLISPからCLへ移植してみました。CLにないMACLISP標準は自作しています。

(DEFUN ANY-MEMQ(X Y)
  (COND ((NULL Y)NIL)
	((ATOM Y)(EQ X Y))
	(T(OR (ANY-MEMQ X (CAR Y))
	      (ANY-MEMQ X (CDR Y))))))

;(any-memq 'x '(y (((((x(((())))))))) z))
;=> t

(defmacro ccode (X) `(DO-CODE ,x))

(DEFUN DO-CODE(X)
  (COND ((NULL X)NIL)
	((ATOM X)
	 ((LAMBDA(CHAR1)
	   (COND ((MEMQ CHAR1 '(? *))X)
		 (T (LIST 'QUOTE X))))
	  (GETCHAR X 1)))
	((AND (ATOM (CAR X))(EQ '* (GETCHAR (CAR X) 1)))
	 (LIST 'APPEND (DO-CODE (CAR X)) (DO-CODE (CDR X))))
	(T(LIST 'CONS (DO-CODE (CAR X)) (DO-CODE (CDR X))))))

(DEFUN α-GRAB-TAILS (ARGS DEF ?GO-LABEL)
 (COND ((ATOM DEF)NIL)
       ((AND (ATOM(CAR DEF)) (EQ 'TAIL-RECUR (CAR DEF)))
	(COND ((EQUAL ARGS (CDR DEF))		;calling with same args!
	       (RPLACA DEF 'GO)
	       (RPLACD DEF (LIST ?GO-LABEL)))
	      (T(DO ((ARGS ARGS (CDR ARGS))
		     (NEWARGS (CDR DEF) (CDR NEWARGS))
		     (SETS NIL (NCONC SETS
				      (COND ((EQ (CAR ARGS) (CAR NEWARGS))
					     NIL)
					    (T (NCONS
						((LAMBDA(SYM)
						  (CONS (CONS (CAR ARGS)SYM)
							(LIST 'SETQ
							      (CAR ARGS)
							      (SUBLIS (MAPCAR 'CAR
									      SETS)
								      (CAR NEWARGS)))))
						 (GENSYM))))))))
		    ((NULL ARGS)
		     ((LAMBDA(L-EXP)
		       (RPLACA DEF (CAR L-EXP))
		       (RPLACD DEF (CDR L-EXP)))
		      (α-OPTIMIZE-λ (MAPCAR 'CDAR SETS)
				    (NCONC (MAPCAR 'CDR SETS)
					   (NCONS(LIST 'GO ?GO-LABEL)))
				    (MAPCAR 'CAAR SETS))))))))
       (T(MAPC (FUNCTION(LAMBDA(DEF)
			 (α-GRAB-TAILS ARGS DEF ?GO-LABEL)))
	       DEF))))

(DEFUN α-OPTIMIZE-λ (VARS BODY BINDINGS)
  (DO ((VARS VARS (CDR VARS))
       (BINDINGS BINDINGS (CDR BINDINGS))
       (NVARS NIL (NCONC NVARS
			 (COND ((ANY-MEMQ (CAR VARS) BODY)(NCONS (CAR VARS)))
			       (T NIL))))
       (NBINS NIL (NCONC NBINS
			 (COND ((ANY-MEMQ (CAR VARS) BODY)(NCONS (CAR BINDINGS)))
			       (T NIL)))))
      ((NULL VARS)(CONS (CONS 'LAMBDA (CONS NVARS BODY))
			NBINS))))

;; オリジナルに割と忠実版
(defmacro TAIL-RECURSIVE-DEFUN (&whole X &body body)
  (declare (ignore body))
  ((LAMBDA(?F-NAME *TYPE)
     ((LAMBDA(*ARGS *DEFINITION)
	((LAMBDA(?GO-LABEL)
	   `(progn
	      ,@(α-GRAB-TAILS *ARGS *DEFINITION ?GO-LABEL)
	      (DEFUN ,?F-NAME ,*TYPE (,@*ARGS) (PROG NIL
						  ,?GO-LABEL
						  (RETURN (PROGN ,@*DEFINITION))))))
	 (GENSYM)))
      (COND (*TYPE (CADDDR X))(T (CADDR X)))
      (COND (*TYPE (CDDDDR X))(T (CDDDR X)))))
   (CADR X)
   (COND ((MEMQ (CADDR X) '(EXPR FEXPR))
	  (LIST (CADDR X)))
	 (T NIL))))

;; バッサリとMACLISP特有の部分を切り捨てた版
(defmacro TAIL-RECURSIVE-DEFUN (?f-name *args &body *definition)
  (let ((?GO-LABEL (gensym)))
    `(progn
       ,(α-GRAB-TAILS *ARGS *DEFINITION ?GO-LABEL)
       (DEFUN ,?F-NAME (,@*ARGS) 
	 (PROG NIL
	    ,?GO-LABEL
	       (RETURN (PROGN ,@*DEFINITION)))))))


;; ML標準の関数達
(defun ncons (n) (list n))

(defun memq (x y)
  (member x y :test #'eq))

(defun getchar (x index)
  (values (intern (string (char (string x) (1- index))))))
 ; 

中身の動作なのですが、とりあえず、

(α-GRAB-TAILS '(x y z) '(tail-recur) 'go)
;-> ((LAMBDA () (SETQ X NIL) (SETQ Y NIL) (SETQ Z NIL) (GO GO))) 

(α-GRAB-TAILS '(x y z) '(tail-recur x) 'go)
;-> ((LAMBDA () (SETQ Y NIL) (SETQ Z NIL) (GO GO))) 

(α-GRAB-TAILS '(x y z) '(tail-recur y z x) 'go)
;-> ((LAMBDA (#:G2999) (SETQ X Y) (SETQ Y Z) (SETQ Z #:G2999) (GO GO)) X) 

(α-GRAB-TAILS '(x y z) '( y z x) 'go)
;-> (Y Z X) 

(do-code '(?foobarbaz hello one))
;(CONS ?FOOBARBAZ (CONS 'HELLO (CONS 'ONE NIL))) 

(do-code '(*foobarbaz hello one))
;(APPEND *FOOBARBAZ (CONS 'HELLO (CONS 'ONE NIL))) 

(tail-recursive-defun xyz (x y z)
  tail-recur
  (list x y z))
; マクロ展開結果
;->
(PROGN
 ((LAMBDA () (SETQ X (LIST X Y Z)) (SETQ Y NIL) (SETQ Z NIL) (GO #:G2995)))
 (DEFUN XYZ (X Y Z)
   (PROG ()
    #:G2995
     (RETURN
      (PROGN
       ((LAMBDA ()
          (SETQ X (LIST X Y Z))
          (SETQ Y NIL)
          (SETQ Z NIL)
          (GO #:G2995))))))))

という感じです。

α-OPTIMIZE-λは、どうやら不要な変数束縛を取り除いて簡略化するもののようで、これは理解できました。

これを呼び出しているα-GRAB-TAILSが良く分からないのですが、名前からすると、末尾部分を抽出するもののようなのですが、動きが良く分からない…。

何がどう末尾再帰なのか…、纏められないままエントリを終わります(笑)

2008-01-28

LOOPマクロと内包表記とINTERLISP

| 20:05 | LOOPマクロと内包表記とINTERLISP - わだばLisperになる を含むブックマーク はてなブックマーク - LOOPマクロと内包表記とINTERLISP - わだばLisperになる

言語内に組み込まれたミニ言語の代表格として語られることが多い、LOOPマクロ

Common Lispの特長を良く表わしているとも言われますが、このLOOPマクロが初めて導入されたのは、Common Lispより以前のMACLISP系の処理系で、Lisp Machine Lisp、MACLISP、NIL等の共通の繰り返し機構として使われていたようです。*1

そんなLOOPマクロですが、CLtLでは、最初にloopという無限ループの枠組だけ提供して、後にフルセットで提供されることになったようです。

CLより前に後にフルセットのLOOPマクロはあったので、最初からフルセットで導入すれば良いようなものですが、導入された後も好き嫌いで色々言われる位なので、当時も色々あったのでしょう。

それで、そのオリジナルのLOOPマクロですが、MACLISP起源ではなく、INTERLISPの繰り返し機構の"FOR"とのこと。*2

構文は大体、Common LispのLOOPと同じ感覚で、

INTERLISP-10  31-Dec-84 ...
Hi.
3_(for i from 0 to 100 collect i)

(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)
4_

のように機能します。

LOOPというキーワードが無いだけで割とそのまんまです。

そんなINTERLISPのFORなのですが、

(for i from 0 to 100 collect i)

だけでなく、

(collect i for i from 0 to 100)

(do (print (cons i (times 2 i))) for i from 0 to 10)
;=>
;(0 . 0)
;(1 . 2)
;(2 . 4)
;(3 . 6)
;(4 . 8)
;(5 . 10)
;(6 . 12)
;(7 . 14)
;(8 . 16)
;(9 . 18)
;(10 . 20)
;NIL
;

のようにキーワードをひっくり返して書いても良かったりします。

自分的には、CLのLOOPよりこっちの方が読み易くて好きだったりするのですが、このひっくり返した構文って最近流行りの内包表記っぽいですよね。

それで、その内包表記のCL版なのですが、やっぱり便利なので最近になって色々実装してみたりしている人が沢山いるようです。

等々

大体のものは、1991年に発表されたGuy Lapalme氏のImplementation of a “Lisp comprehension” macroという論文を参考にしていてCLのLOOPをマクロで包んだものが多いようです。

それで形としては、結局INTERLISPのFORループみたいなものができてしまっていて30年ぐるっと回って元に戻って来ちゃったという感が強く、感慨深いものがあります(笑)

おまけ

Common Lisp対Schemeで比較されてあれこれ言われる今日ですが、色々違いこそあれMITのMACLISP系の流れのもので所詮似た者同士に思えます。

XEROX系のINTERLISPは、ほぼ絶滅してしまいましたが、これらのMIT系とは大分違い、現在のLISP観からするとかなり逸脱したものになっているので、変ったものが好きな方には是非お勧めしたいです。*3

*1:Chinual 3rd ed. 1981

*2:ちなみに、INTERLISPのFORのMACLISPへの移植は1976年にされていたようです。

*3:例えば、LOOPマクロの英文として読み下せるような文法というのは、INTERLISPの一つの特長のように思えます。

2008-01-16

Lispの変な関数名

| 01:07 | Lispの変な関数名 - わだばLisperになる を含むブックマーク はてなブックマーク - Lispの変な関数名 - わだばLisperになる

自分の好きな話題なのでトラックバックを打たせてもらいます!

確かに、古来のLispから引き継がれた変な名前の関数名は結構ありますよね。

そこで自分の分かる範囲で調べてみたことを書いてみたいと思います。

  • SETQのQ

これは、(set (quote foo))が縮まったもののようです。

qで終る系統は、quoteの略と、eqのqの系統があるようでeqの系統は、Common Lispでは滅びましたが、SRFI-1では復活したりしています。memqとか。

また、INTERLISP系にはquoteのq系統が沢山あるのですが、Maclisp系統にはそんなにないようです。

  • SETのF

これは、Kent Pitman氏によれば、"set field"の略だそうです。

onjoさんのLispy Days経由、ClikiのKent Pitman氏のcomp.lang.lispのポストであらましが読めます。

また、The Evolution of Lispによれば、これはPeter Deutsch氏のアイディアだそうで、当初setfqだったものが、Lispマシンでsetfになったとのこと。

リーダーで読み出した場所に値をセットするというアイディア自体は、Deutsch氏によれば、かの有名なアラン・ケイだそうです。

  • PRINCのC

これは、調べてみても解説がみつかりませんでした。princが一番最初に登場するのは、自分が調べた限りではPDP-6 LISP(AIM-116a)なのですが、どうも、characterのcなんじゃないかという感じです。PDP-6 LISPでは、print、prin1とprincの違いは、Common Lispでもそうですが、read入力にかなった文字列を出力するかどうか、とのことですが、princは、文字通りそのまま印字するということなので…。print、prin1では、特殊文字は/によってエスケープ処理して出力されます。

  • prin1の1

そもそもprin1の1は謎なのですが、自分が調べた限りでは、PDP-1 LISPに登場するのが最初のようです。printとの違いは、前後にスペースを出力したりしない、とのこと。もしかしたら、後述の名前の後の1系の補助関数的ネーミングなのかもしれません。

  • NCONC、RPLACA

mokeheheさんのお察しのとおりで、破壊的操作系の、n〜は、no consingで、rplacaは、replace carのようです。

ちなみに、LISP 1.5には、conc(恐らくconcatenateの略)という今のappendと同じ働きをするものが存在していました。当時APPENDは、引数を2つしか取らなかったためと思われます。PDP-6 LISPで、APPENDが拡張されたためか消滅してしまいました。

おまけ

  • mapcar、maplist

大元のLISP 1.5には、MAP、MAPLIST、MAPCONとあるのですが、MAPは、'(foo bar baz)というリストがあった場合に、'(foo bar baz)→'(bar baz)→'(baz)というようにリストを処理するもので、返り値には期待しない処理に使うものだったようです。(Common Lispでの、mapl)

このMAPを規準にして考えると、各要素をCARで処理して結果をリストで返せば、MAPCAR、LISTで処理すればMAPLIST、継げれば(CONcatenate)、MAPCONということなんじゃないかと思います。また、引数の[関数 リスト]という今日のCommon Lisp、Schemeでお馴染みの順番は、PDP-6 LISPからのようです。LISP 1.5、PDP-1 LISPまでは逆でした。(INTERLISPUtilispでも逆です。)

  • 名前の後の1

foo-bar1のような名前も良くみかけますが、これは、PDP-1 LISP位からの伝統のようで、foo-barの補助関数という意味で付けられることが多いようです。似たところでは、foo-bar-1、foo-bar-aux、foo-bar*等。引数を一つとるという意味で、Gaucheのlet1などもありますね。

以上、殆ど憶測の域を出なかったりするのですが、AIメモ等を読んだりして調べてみたところでした。

2008-01-11

関数名にハイフンを使うようになったのはいつ頃からなのか

| 23:32 | 関数名にハイフンを使うようになったのはいつ頃からなのか - わだばLisperになる を含むブックマーク はてなブックマーク - 関数名にハイフンを使うようになったのはいつ頃からなのか - わだばLisperになる

LISPでは、関数や変数の名前にハイフンを使いfoo-if-barのような名前を付けたりして、これが、それなりにLisp的な特徴とみなされているかと思います。

非常にどうでも良いことなのですが、急に、関数名にハイフンを使うようになったのはいつ頃からなのか、ということが気になり出して仕方なくなってしまい、色々調べてみました。本当にどうでも良いことなのですが…。

そもそもなんで疑問に思うかといえば、LISP 1.5をちょっといじってみて、マニュアルや古い文献のプログラム等を眺めてみているのですが、今だったらハイフンで区切るような、例えば、SUPER-REVERSEのような関数名が、SUPERREVERSEだったりするのです。これだと、読み難いのですが、しかし、他の長い名前も全然ハイフンが使われていないのです。

LISP 1.5では、変数や関数にハイフンを含められないのかといえば、そういう制限もなく、普通に使ってプログラムも書けます。

そうなってくると、じゃあ、一体いつからなんだということになってきてしまうのです。

それで、とりあえず、調べてみたのですが、PDP-1 LISPは、ハイフン抜き、直系のPDP-6 LISPも抜きで、手元のソースを眺める限りでは、その次のMACLISPで初めて登場するようです。

大体、1974年位が境なんですが、なんでその辺なのかは良く分かりません。

それで、その後1978以降MIT Lispマシン周辺で、やたら長い名前をハイフンでつなげた名前が爆発的に増えます。

ちなみに、INTERLISP系ですが、こちらは、BBN-LISPから、INTERLISP-Dまであんまりハイフンで継げた名前はみかけません。

以上、まったく役に立ちようもない探究でした。

ちなみに、これも非常にどうでも良いことなのですが、過去のMITのAIメモを眺めたりしている過程で、内部的な関数の頭に%ではなく、*を付けるという習慣を発見しました。PDP-6からMACLISP初期のことで、大体40年前のことなのですが、例えば、2引数しか取らない限定的なGREATERPは、*GREAT、といった風になっています。頭に%を付けるのは、多分これもLispマシン周辺から来てるんじゃないかと思うんですが、これまた、本当にどうでも良いことでございまして…。