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-03-17

大文字と小文字を区別しない

| 06:06 | 大文字と小文字を区別しない - わだばLisperになる を含むブックマーク はてなブックマーク - 大文字と小文字を区別しない - わだばLisperになる

先日のPAIP読書会でNorvig先生がRETURNだけ見易いように大文字で書いている例から、もちらっと話題になったのですが、Common Lispは歴史的なLISP処理系と同様に大文字と小文字を区別しません。(設定すれば可能ですが…)

この辺は古臭いという風にも捉えられますが、区別しないということを利用して色々とコードを読み易いように工夫をしている例があります。

ということで、適当に色々なスタイルを列挙してみます。

  • コードはとりあえず全部小文字。コメントは、普通の文章と一緒
(defun hello-world ()  
  "Hello, World!")              ;Hello, World!

最近はこれが主流だと思います。他の言語もこれが普通なので、その影響だと思われます。

  • コードはとりあえず全部大文字。コメントは、普通の文章と一緒
(DEFUN HELLO-WORLD ()
  "Hello, World!")              ;Hello, World!

1970年代後半位までは、こっちが主流だったようです。

Zmacs(LispマシンのEmacs)には、こういうスタイルを支援する、Electric Shift Lock ModeというCAPS Lockが掛ったような動作をするマイナーモードがありました。コードの部分では、シフトキーの役割が引っくり返るんですが、コメントや、文字列の中では、普通という秀逸なモードです。

  • とにかく全部大文字
(DEFUN HELLO-WORLD ()
  'HELLO-WORLD)              ;HELLO, WORLD!

1970年代前半位までこんな感じです。というより、大文字しか扱えなかったシステムが多かったようだったようなので、必然かもしれません。

色々工夫している例

ここからは、大文字と小文字を区別しないシステムの失われつつある文化の領域になってきます。

目につくところだけ集めてみました。細かいこだわりになると無数にあるようで、眺めていると結構面白いです。

  • Tは大文字で書く(MacLISP等)
(cond ((< n 2) n)
      (T 'hello)))

(cond ((null lst) n)
      ('T 'hello))
... etc

Tにはクオートを付けたりもします。しかし対応するnilは小文字というのが謎。

  • gotoのタグは大文字で書く(MacLISP等)
(prog (lst)
   L  (cond ((null lst) (return 'hello)))
      (pop lst)
      (go L))

タグは大文字で書かれることが多かったようです。

(defun LIVE-ARRAYS (kind)
  ...)

これは今でもちらほらみかけます。

  • マクロの定義で、展開された結果になる所は大文字で書く(MacLISP等)
(defmacro SETQ-IF-UNBOUND (&rest args)
  (do ((a args (cddr a))
       (l () (cons `(OR (BOUNDP ',(car a)) (SETQ ,(car a) ,(cadr a))) l)))
      ((null a) 
       (cond ((null (cdr l)) (car l))
	     (`(PROGN ,.(nreverse l)))))))

(setq-if-unbound x 3 y 5)
;=> (PROGN (OR (BOUNDP 'X) (SETQ X 3)) (OR (BOUNDP 'Y) (SETQ Y 5)))

これは良く思い付いたなと感心しますが、MacLISPでは結構このスタイルで書いてる人がいます。

  • システム定義のものは大文字、ユーザ定義のものは小文字で書く(TI-Explorer)
(DEFUN search-and-or (substrings string)
  (DECLARE (optimize (compilation-speed 0) (safety 1) (SPACE 2) (speed 3))
	   (inline search-and-or simple-string-search))
  (LOOP for and in substrings
	unless (IF (ATOM and)
		    (simple-string-search and string)
		  (LOOP for or in and do
			(IF (ATOM or)
			    (WHEN (simple-string-search or string) (RETURN t))
			  (LOCALLY (DECLARE (notinline search-and-or))
			    (search-and-or or string)))))
	do (RETURN nil)
	finally (RETURN t)))

MacLISPとは逆でシステムが大文字な例です。

  • 上記に加え、なんでか知らないが、defun等、def-系だけ先頭を大文字にする(TI-Explorer)
(Defun ALL-ARGLIST-BEFORE-&AUX (arglist)  
;; return a copy of the arglist up to but excluding &aux
  (LET ((pos (POSITION '&aux (the list arglist) )))
    (IF pos 
	(FIRSTN pos arglist) 
	arglist)))

以上、大文字小文字を区別しないことを不自由と考えるか、自由と考えるか、様々だと思いますが、自由と考えている風な例を取り上げてみました。

2008-03-11

繰り返し構文からみる自分のコーディングスタイル (2)

| 17:22 | 繰り返し構文からみる自分のコーディングスタイル (2) - わだばLisperになる を含むブックマーク はてなブックマーク - 繰り返し構文からみる自分のコーディングスタイル (2) - わだばLisperになる

前回反響が少しでもあるとは全く考えていなかったのでデータについては適当にしていましたが、☆が2個付いたし折角なので、文字のデータですが公開してみることにしました! 見難いですが、とりあえず色々あります。これらから一体何が読み解けるのかは、全くの謎です!

見慣れない構文名があるので、変なものをざっと解説すると、DO-FOREVERはその名のとおり無限ループ用です。個人的には是非復活して欲しいですね(笑) Lispマシンでは人気がありましたが、Common Lisp以降どっかにいなくなりました。DO-NAMED系は、DOのブロックに名前が付いていて脱出時に指定します。これもCLで、BLOCKとして統一されたので姿を消してしまいました。

全然関係ないですが、ループ系の構文の名前を考える、ということでは、RRRSのメーリングリストで名前付きLETに適切な名前を付けよう!、というのが熱くて面白いです。もの凄く沢山の案が提案されているのですが、結局採用されずに今に至るという流れが特に好きです(笑)

現在の主なフリーの処理系

  • SBCL
構文名 総数 総行数行数/構文最大行数
DOLIST 1073 9956 9 152
DO 702 7463 10 170
MAPCAR 547 2082 3 45
LOOP 514 3574 6 57
DOTIMES 359 2161 6 88
LABELS 156 5339 34 306
DO* 65 821 12 81
MAP 53 340 6 103
MAPC 47 152 3 14
MAPCAN 23 229 9 64
PROG 7 568 81 366
MAPLIST 1 7 7 7
  • CLISP
構文名 総数 総行数行数/構文最大行数
DOLIST 382 4016 10 332
MAPCAR 304 1345 4 176
DO 282 4110 14 117
DOTIMES 144 729 5 62
LOOP 102 993 9 206
DO* 94 1871 19 250
MAP 70 184 2 12
MAPCAN 60 333 5 26
LABELS 52 4073 78 1233
MAPC 35 155 4 36
PROG 12 256 21 131
MAPL 8 45 5 35
MAPLIST 4 31 7 26
MAPCON 2 2 1 1
  • CMUCL
構文名 総数 総行数行数/構文最大行数
DOLIST 1570 12602 8 90
DO 1243 13010 10 179
DOTIMES 710 4565 6 91
MAPCAR 612 2361 3 47
PROG 424 7489 17 377
LOOP 405 2554 6 56
DO* 175 3335 19 132
LABELS 161 5755 35 230
MAPC 104 191 1 14
MAP 58 148 2 12
MAPCAN 18 88 4 11

古い処理系

  • Franz Lisp 1985頃?
構文名 総数 総行数行数/構文最大行数
DO 371 4462 12 195
PROG 205 5377 26 575
MAPCAR 69 213 3 16
MAPC 53 303 5 41
DOLIST 41 280 6 32
LOOP 24 104 4 11
MAPCAN 10 61 6 17
MAPLIST 3 33 11 11
DOTIMES 2 2 1 1
MAP 1 6 6 6
MAPCON 1 5 5 5
  • Rutgers PDP-10 CL 1985年頃
構文名 総数 総行数行数/構文最大行数
DO 368 3451 9 78
DOLIST 157 964 6 68
DOTIMES 78 361 4 28
DO* 74 874 11 61
MAPCAR 62 176 2 13
PROG 31 687 22 62
LABELS 11 244 22 59
MAPC 6 19 3 6
MAPCAN 6 37 6 8
LOOP 2 4 2 3
MAPL 1 4 4 4
構文名 総数 総行数行数/構文最大行数
DO 902 9181 10 251
PROG 359 14913 41 603
MAPC 275 1597 5 52
MAPCAR 184 628 3 29
MAPCAN 51 322 6 52
LOOP 30 166 5 28
DOTIMES 16 238 14 46
MAP(MAPL) 15 118 7 25
DOLIST 13 35 2 7
MAPLIST 6 19 3 6
MAPCON 3 5 1 2
DO* 1 1 1 1

Lispマシン系

  • LMI K-Machine 1986年頃
構文名 総数 総行数行数/構文最大行数
DO 614 5653 9 146
DOTIMES 392 2658 6 121
DOLIST 355 2441 6 62
MAPCAR 235 626 2 13
LABELS 137 1754 12 98
LOOP 92 303 3 16
MAPC 89 257 2 15
DO-FOREVER 46 548 11 58
DO* 42 571 13 56
MAP 26 43 1 6
PROG 16 333 20 58
MAPCAN 10 68 6 9
DO*-NAMED 6 48 8 9
MAPL 5 7 1 3
MAPCON 2 16 8 8
MAPLIST 1 5 5 5
DO-NAMED 0 0 0 0
  • LMI Lambda 1982年頃
構文名 総数 総行数行数/構文最大行数
DO 4018 46904 11 156
DOLIST 2049 12879 6 142
LOOP 1308 11002 8 119
DOTIMES 1127 5761 5 151
MAPCAR 662 1882 2 92
PROG 607 17999 29 404
DO-FOREVER 257 3782 14 183
MAPC 250 2581 10 1719
DO* 97 1716 17 114
MAP 84 255 3 44
MAPCAN 68 325 4 20
DO-NAMED 36 933 25 97
DO*-NAMED 6 27 4 9
MAPL 2 2 1 1
MAPCON 2 4 2 2
MAPLIST 0 0 0 0
  • MIT CADR 1979年頃
構文名 総数 総行数行数/構文最大行数
DO 2321 27545 11 142
DOLIST 806 4632 5 72
PROG 665 15177 22 253
LOOP 457 3360 7 54
DOTIMES 316 1775 5 142
MAPCAR 155 390 2 12
MAPC 114 306 2 17
DO-NAMED 46 1094 23 74
MAPCAN 16 56 3 9
MAP 12 17 1 5
MAPCON 2 4 2 2
  • Gigamos 1987年頃
構文名 総数 総行数行数/構文最大行数
DO 622 7827 12 140
DOLIST 362 2358 6 50
LOOP 233 1808 7 119
DOTIMES 191 1112 5 121
MAPCAR 151 380 2 48
LABELS 65 1949 29 199
PROG 64 2297 35 167
MAPC 56 126 2 25
DO* 21 267 12 32
DO-FOREVER 16 196 12 34
MAPCAN 9 49 5 8
DO-NAMED 7 283 40 90
MAP 4 4 1 1

コードの量が少ないので参考データとして

  • Peter Norvig (LTD) 1995年頃
構文名 総数 総行数行数/構文最大行数
LOOP 32 133 4 17
MAPCAR 29 64 2 7
MAP 8 17 2 6
DOLIST 7 42 6 13
LABELS 4 47 11 32
DO 3 3 1 1
MAPC 3 7 2 3
MAPCAN 3 9 3 7
MAPLIST 1 1 1 1
MAPCON 1 1 1 1
DOTIMES 1 9 9 9

繰り返し構文からみる自分のコーディングスタイル

| 01:50 | 繰り返し構文からみる自分のコーディングスタイル - わだばLisperになる を含むブックマーク はてなブックマーク - 繰り返し構文からみる自分のコーディングスタイル - わだばLisperになる

Common Lispせよ、Schemeにせよ繰り返しの構文は豊富に用意されているかと思うのですが、どんな構文を自分は好んで使っているのか、ふと、知りたくなりました。 ということで、DOやMAP、PROG等のめぼしい構文を抜き出して各々の構文の数を勘定するコードをCLで書いてチェック。自分が書いたメモ書きからスクラッチのごみのようなものまで含めて約4万行を対象にしてみました。グラフはGoogleDocsにお任せしました。ほんとはCLで完結させたかったんですが…。 主観的には自分は繰り返しにはDO構文を良く使っていて、LOOPはあまり使ったことがない、と思っているのですが、意外なことにMAPCARを一番多く使っていて、大体同じ位DOを使用。そして使ってない筈のLOOPも普通に使ってました(笑) 最近、LOOPで書く練習をしていて、できるだけLOOPで書くようにしているからかも知れません。PROGが多いのはレトロコンピューティングな趣味が反映されたものだと思われます。 ついでに、SBCL 1.0.15のソースコードも調べてみました。 DOLIST、DO、MAPCARで7割弱。何でもかんでもLOOPだろうと勝手に思っていたので意外でした。 ■ それで調子に乗って古い処理系から最近のCLの処理系まで色々調べてみたのですが、最近の傾向としては、ちょとした違いはありますが、DOLIST、DO、MAPCARの順で6割強を占めるようです。この35年位を通じDOは首位で安定している様子で、LOOPは大体4番手か5番手位。CMUCLでは、LOOPよりPROGが多かったりして何となく処理系の歴史を感じさせます。 また、調べてみてMacLISPのような古い処理系では、DOLISTの代わりにMAPCが好んで使われていたことが分かりました。MAPCは、Schemeで言えば、for-eachで、副作用主目的としたmapです。機能としては、あまりDOLISTと変わらないのですが、Lispマシン時代からDOLISTに取って代わられ始め、現在では殆んど使われなくなってしまいました。 また、LOOPはLispマシンから出て来ただけに、Lispマシンでは今より好んで使われていた様子で、今のCommon Lispの処理系より全体に占める割合は多いようです。これも意外でした。 ちなみに、再帰は、統計を取るのが面倒なので、LABELS位にしています。処理系のソースという性質もあるとは思いますが、眺める限りはLispマシン以前では殆ど使われずCommon Lisp以降から少しずつ増え始めている感じです。 以上、非常に下らないですが、統計を取ると存外色んなことが分かって来たりするもんだと思いました。 …分かってくると言っても、全く本質的でない事項だとは思いますが(笑)

2008-03-06

昔のLISPの関数名に記号が使われないのはなぜなのか

| 12:17 | 昔のLISPの関数名に記号が使われないのはなぜなのか - わだばLisperになる を含むブックマーク はてなブックマーク - 昔のLISPの関数名に記号が使われないのはなぜなのか - わだばLisperになる

昔のLISPの関数名(昔といっても、Lisp 1.5の話なのでかなり古いです)は(- 3 2)ではなく、(difference 3 2)と書きました。このように、やたら長いスペルの関数名はあるものの直感的に思い付くような-や+記号というのは、まったく見掛けません。

以前から何でなんだろうなあ、と思っていたのですが、昨日のifや、condのエントリで、M式を書いていて、もしかしたら!という理由を思い付きました。

それは、M式で書くと、

difference[3;2]

と書くのは、まあ普通に見て状況を把握できますが、

-[3;2]

だと、何が何だか良く分からない、ということなんじゃないかなと。

M式以外にも、Eval quoteという表記方法があるんですが、これはトップレベルは、M式のように書くというもの。Lisp 1.5や、INTERLISPで可能な表記形態だったのですが、これも同様に、

difference(3 2)

は良くても

-(3 2)

は何となく変。INTERLISPにも記号で書いた方が完結な長い関数名がずっと残っていましたが、この辺をずっと継承していたからなのではないか?!ということなのですね。

…しかし実際のところ、真相は知る由もございません。

以上、重箱の隅過ぎてトリビアにさえならないネタでした。

ちなみに改めて確認したところ、INTERLISPでは中間記法が使え、その場合は記号が使えました。

ということで、トップレベルでは、

3 - 2

と書くと、1となります。

お馴染のfibはINTERLISPだと

defineq((fib (n)
	     (if (lessp n 2)
	       then
		 n
	       else 
		 (fib n - 1) + (fib n - 2))))

fib(15)
;-> 610

と書けます。

2008-03-05

cond、ifの変遷

| 19:20 | cond、ifの変遷 - わだばLisperになる を含むブックマーク はてなブックマーク - cond、ifの変遷 - わだばLisperになる

ポール・グレアム氏のコア言語としてのArcについての最近のエッセイで、condの括弧の多さへの批判と、これを放置していたのは、既存の価値観に捕われていた所為じゃなかろうか?のような指摘があったのですが、いやいや、condや、ifも色々面白い変遷があったようだし、そうでもないんじゃないか?、と思ったので、適当に纏めてみました。

もちろんPGはそういうことが言いたいんじゃない!ということになろうかと思いますが、私は、プログラミングに興味はあまり無く、言語の歴史や変遷に興味があるので(笑)

まず私のスタンスですが、condの括弧は多いとは感じません。R6RS風の角括弧も読み難く感じます。この辺は全く感覚的なものだと思うので、どうしようもないですね。どこにも理由がないし(笑)

ということで、Arcのifはcondより読み難いと思っていて、cond万歳な価値観であり、下記にもそういうバイアスがかかっていると思います。

それはさておき、cond、ifの歴史的変遷を眺めてみたいと思います。

M式 1958年頃

[a[B;C] → prog2[d[E;F];g[H;I];
 j[K;L] → (M N O);
 T → prog2[p[Q;R];s[T;U]]

まず一番最初は、M式ですが、別にcondという名前もifという名前も付いていなくて、[]で纏められた条件式の集まりです。条件が真ならば、→の右側が評価されます。式はセミコロンで区切られます。

また、'(a b c)は、(A B C)と表現され、(list 'a 'b 'c)は、list[A;B;C]と表現されます。つまり括弧が2種類あって意味的に違ったものを表現しています。

無理にS式風に書いてみると、

[(a b c)(prog2 (d e f) (g h i))
 (j k l)'(m n o)
 'T(prog (p q r) (s t u))]

という感じです。つまりM式は既にR6RS風であり、また、PGが問題にしている括弧の多さ問題もなかった訳ですね。まあ、代わりに矢印があるわけなのですが。

上記を当時のS式で書くと

;; S式
(cond ((a b c) (prog2 (d e f) (g h i)))
      ((j k l) (quote (m n o)))
      ((quote t) (prog2 (p q r) (s t u))))

となります。condの実行節が暗黙のprognになっているかどうか不明なのですが、自分がエミュレータ試しても、論文を眺めても暗黙のprognになっているという記載は見当たりません、また、省略されるとnilが返るということもなく、省略できません。この辺本当はどうだったんでしょう。PG氏は、暗黙のprognだった、って書いてるんですけども…。M式でも暗黙のprognってどう表現して良いか分からないし。

それはさておき、ここからずっと下って、1978年頃なのですが、IFが登場して来ます。

MacLISP、Zetalisp、Emacs Lisp 1978年頃

(if (a b c)
    (progn
	(d e f)
	(g h i))
    (if (j k l)
	'(m n o)
      (p q r)
      (s t u)))

CONDがあるので、こういう書き方はされないのですが、敢えて書くとこうなります。

else節が暗黙のprognになっていますが、

(defmacro if (pred then &rest else)
  `(cond (,pred ,then)
	 (t ,@else)))

のようなcondに展開されるマクロになっているので、おまけでそうしてるんじゃないかと思ったりします。

このifの由来ですが、The Evolution of Lispによれば、schemeからの影響じゃないだろうかとのことで、Schemeには、1975の最初からifが存在します。

これは、else節は暗黙のprognになっていません。

SCHEME 1975年

(IF (A B C)
    (lambda ()
      (D E F)
      (G H I))
    (if (J K L)
	'(M N O)
	(lambda ()
	  (P Q R)
	  (S T U))))

これまた、若干無理矢理な書き方で、こういう時は素直にCONDを使うようです。

…ということで、最初の20年位はifがなく、whenやunlessと登場時期は一緒だったようなのですね。

MacLISP Multics Emacs 1978 / Bernard S. Greenberg

そういう経緯もあり、1980年台初頭位まで、LISPにおいてのifの首はまだ座っておらず、変種が結構あります。

(if (a b c)
    (d e f)
    (g h i)
    else
    (if (j k l)
	'(m n o)
	else
	(p q r)
	(s t u)))

これは、Multics Emacsの中のifマクロの例。

elseで区切り、then節もelse節も暗黙のprognになっています。

Franz Lisp 1980頃? John Foderaro

(if (a b c)
    then (d e f)
         (g h i)
  elseif (j k l)
         '(m n o)
    else (p q r)
         (s t u))

これは、Franz Lispのifマクロの例。Franz Lispの処理系のソースでは、condが殆ど使われておらず、殆どこのifマクロです。

最近のAllegro CLでも、if*として存在しています。

このifマクロは、condと機能的に完全に等価で、(if 'foo thenret)と表現することにより、(cond ('foo) )のようなことも可能です。

また、多重の括弧の読みやすさへの配慮として、R6RS風に角括弧も使えました。

(cond [(a b c) (prog2 (d e f) (g h i))]
      [(j k l) '(m n o)]
      ['T (prog2 (p q r) (s t u))])

INTERLISP

また、Interlisp系でもいつ頃なのかはっきりしませんが、

(if (a b c)
    then
    (d e f)
    (g h i)
    else
    (if (j k l)
	then
        '(m n o)
        else
	(p q r)
	(s t u)))

のように書けるようになりました。thenとelseのキーワードがあり、どっちの節も暗黙のprognです。

Common Lisp 1984

それで 1984年 Common Lispですが、Schemeと同じく実行節は暗黙のprognになっていません。

(if (a b c)
    (progn
	(d e f)
	(g h i))
    (if (j k l)
	'(m n o)
	(progn
	  (p q r)
	  (s t u))))

Arc 2008年

そして、2008年 Arcは、condから各節の括弧を省略した形をifという名前にしました。

(if (a b c)
     (do (d e f)
	 (g h i))
    (j k l)
     '(m n o)
    (do (p q r)
	(s t u)))

という風にcond、ifにも色々あったようなのです。

今日の状況からすれば、プログラミングをLISPから入門するということはないと思われ、condは異質なものと感じられることが多いと思います。

cond自体もifに展開されるマクロとなり、なんとなく寂しいですね。

…いや、別に寂しくはないか(笑)

2008-03-01

世の中にONEPは必要か?

| 10:48 | 世の中にONEPは必要か? - わだばLisperになる を含むブックマーク はてなブックマーク - 世の中にONEPは必要か? - わだばLisperになる

今回のエントリもくだらないネタなのですが、ONEPは世の中に必要なのかどうか、それが無性に知りたくなりました。

ONEPはZEROPの兄弟で、1かどうかを調べるものです。

ONEPは実はLISP 1.5にも存在し、その歴史は非常に古くもうすぐ50歳にもなろうかという大物なのです。

しかし、歴史の荒波に揉まれているうちにいつのまにやら姿を消してしまいました。

調べてみたところでは、標準でonepが存在した処理系は、LISP 1.5、UCI LISP、Franz Lisp等が確認できましたが、MIT系にはどうやら存在しなかったようで、その流れを引き継いだのかCommon Lispにも存在しません。

それで、存在意義を確かめてみたいと思い立ち、(= 1 ~)はどれだけ書かれているかを調べてみました。

ソース 1との比較zerop prog2onep/zerop=全体に占める割合
Google ソースコード検索 4000 19700400 1/5 5%
ラドガース大学のPDP-10用のCL26 77 0 1/5 11.5%
MIT CADR Lispマシン 178 1055 22 1/6 7%

ここで、比較対象にprog2を選んだ理由ですが、ANSI CLに無駄だと思うものを一つ挙げよ、と言われたときに個人的に真っ先に思い浮ぶのが、prog2ということでprog2にしてみました。prog1とprognの組み合わせで、prog2は置き換え可能だし、後方互換の維持という面でも役に立ってないと思われるので…。

それはさておき、=における1との比較ですが、上記のソースでは全体の5%〜12%位だったりして意外に多いんだなと感心しました。

zerop比べても約1/6位の様子。

まとめ

ということで、以上から、ONEPは世の中に必要なんだ! ということにしておきたいと思います。

新しい処理系を作るみなさんは是非一度onep、one?、1=などの採用をご検討なさってはいかがでしょうか!

2008-02-27

Symbolicsと闘っていた頃のRMSのLispコード

| 03:50 | Symbolicsと闘っていた頃のRMSのLispコード - わだばLisperになる を含むブックマーク はてなブックマーク - Symbolicsと闘っていた頃のRMSのLispコード - わだばLisperになる

RMSがGNUプロジェクトを始める前に、Symbolicsと闘っていたというのは伝説となっていますが、それは1980年代前半頃の話のようです。

Joe Marshall氏が公開しているLMI Lambdaのソースコードには、その時期のものがあるのですが、探してみるとRMSの署名があるものも何点か存在します。

等々…。

ソースの冒頭に信条的なものが書いてあるのですが、GNUプロジェクトを予感させるものだったりして興味深いです。

Lispマシンを知らない子ども達

| 02:58 | Lispマシンを知らない子ども達 - わだばLisperになる を含むブックマーク はてなブックマーク - Lispマシンを知らない子ども達 - わだばLisperになる

あまりも当たり前過ぎて21世紀に入ってから言葉にだしたことはあまりないのですが、当然のことながら、3D CGといえばSymbolicsのLispマシン、Silicon GraphicsのUNIXワークステーションなんかよりSymbolicsざます!という時代がありました。

とはいえ、IRIXもSymbolicsも今は亡きものになってしまったのですが…。

一体いつの時代の話なのかと言えば、1980年代後半から90年代前半位の話のようですね。それと、システムの金額も半端ではなく、一般のご家庭にも全然縁がないお値段でした。そりゃ知らないわ。

この動画もRainer Joswig氏のサイト経由で知ったのですが、1987年のCGの解説ビデオで、SymbolicsのLispマシンと、Lispマシンで作ったCGがばんばん登場しています。20年前ということをしっかりと念頭に置いて観賞すると、これは凄い!と感動できるかもしれません。

ちなみに、Silicon Graphicsのワークステーションが欲しいという奇特な方がいらっしゃいましたらどうか貰って下さい。Octane、Indigo2(紫/緑)、O2等々各種取り揃えております。Fuelもあるんですが、これは若干迷っています…。

あ、SunのUltra80も良かったら差し上げます。メモリ4GBで、4CPUです。450Mhzですけどね…。

梱包ができる気がしないので、手渡しだと最高なんですが…。

LISPでハードウェア周りの記述はできるのか?

| 02:15 | LISPでハードウェア周りの記述はできるのか? - わだばLisperになる を含むブックマーク はてなブックマーク - LISPでハードウェア周りの記述はできるのか? - わだばLisperになる

「LISPでハードウェア周りの記述はできるのか?」という疑問はわりと頻繁に繰り返されていると思いますが、ハードウェアの上に直にLISPが載っているLispマシンがあった位なので可能なんでしょう。

詳しくは自分も知らないのですが、The Evolution of Lispによれば、Lispマシンが開発された当初、MacLISPから枝分かれしたLispマシン用のLisp Machine Lispでは、システム記述力が足りなかったため一部アセンブリで記述する必要があったとのことで、この辺をを全面的にLISPで書けるように強化/改良したのが、Zetalispとのことです。

Lisp Machine LispとZetalispの違いは曖昧で、Symbolicsの3600シリーズと共に登場したのが、Zetalispのようなのですが、MITでもLMIでもZetalispと呼ばれていて、何がなんだか良く分かりません。マニュアルも共通ですし。

こちらのRainer Joswig氏のサイトには同氏がキャプチャした沢山のLispマシンの動画が沢山置いてあるのですが、このNXP1000の解説では、Lispで書かれたSCSIドライバのコードを開いて見せたりしています。ちなみにこの動画は非常に画面サイズが大きいです…。また、このサイトは自宅サーバで、Wgetも禁止だそうなので、ご注意願います。といっても動画のサイズも大きいのですが…。

CLtL->CLtL2->ANSI CLという流れではなかった

| 01:29 | CLtL->CLtL2->ANSI CLという流れではなかった - わだばLisperになる を含むブックマーク はてなブックマーク - CLtL->CLtL2->ANSI CLという流れではなかった - わだばLisperになる

自分は、ブログに書くLISPネタを思い付いたり見付けたりしたら、fixdapにメモしているのですが、ブログに書かないうちにどんどん埋没して行ってしまいます。

しかし、溜めておいてもしょうがないので、小ネタでもどんどん書いてみることにしました。

ということで、今回は、comp.lang.lispを眺めていて、おっ、と思ったことを。

Seriesのスレッドだったので読んでいたのですが、ANSI Common Lispに至る話で、Kent M. Pitman氏からCLtL2からANSI CLという流れではないんだよ、との指摘。

割とFAQなのかもしれませんが、自分は知りませんでした。そうだったのか!

ということで、CLtL2を確認してみたのですが、やっぱりそういう風な記述が序文等にありました。

CLtL -> ANSI CL

CLtL -> CLtL2

ってことみたいです。

2008-02-23

再帰が難しいのか、それとも考え方が難しいのか

| 03:39 | 再帰が難しいのか、それとも考え方が難しいのか - わだばLisperになる を含むブックマーク はてなブックマーク - 再帰が難しいのか、それとも考え方が難しいのか - わだばLisperになる

再帰は難しいと良く言われます。自分も再帰を使ったアプローチでは、何だかこんがらがることが多いです。

しかし、良く良く考えてみると、再帰が難しいというよりも、問題を解く方法がややこしいだけで、それをもって再帰がややこしいというのは何だか変な気がしてきました。

再帰するということと、問題に対するアプローチは別の物なのに、それが一緒くたにされて、「再帰は難しい」とされているような。

例えば、リストの長さを調べるlenという関数を作ってみるとします。

まず、この問題に対してアプローチは色々取れると思うのですが、

1. 要素を勘定していって、最後に勘定した数を返す

2. リスト中の要素を全部1に置き換えて、最後に内容を全部足し算する

3. リスト中の要素を全部1を足す関数に入れ子状に置き換えて、その一番内側の関数に0という引数を与える。

等々あるかと思います。

自分が単純に考えると、やはり1番のアプローチが一番最初に思い付くのですが、再帰の入門解説等では、一番単純なものとして

(defun len (lst)
  (if (null lst)
      0
      (+ 1 (len (cdr lst)))))

のようなものが取り上げられることが多いと思います。これは、

(defun len (lst)
  (if (null lst)
      0
      ((lambda (x) (+ 1 x)) (len (cdr lst)))))

ということで、考え方としては、3番目のものに該当するかと思いますが、再帰云々の前に、考え方が既にややこしいんじゃないかと思うんですよね。

それで、1番目のアプローチですが、これは再帰でも書けて

(defun len (lst acc)
  (if (null lst)
      acc
      (len (cdr lst)
	   (+ 1 acc))))

のようになるかと思います。

リストを一個ずつ手繰って行く部分と、合計を溜めて行くところがあって、リストが空になったら終了。最後に溜めていた合計を返すというもの。

2番目のアプローチも、1番目に似ていますが、合計を溜めて置く代わりに要素を1に置き換えたリストを溜めていって、最後に+という関数をリストに適用します。

(defun len (lst acc)
  (if (null lst)
      (apply #'+ acc)
      (len (cdr lst)
	   (cons 1 acc))))

ということで、再帰を使ったからといって難しくなる訳ではないのではないかと。

1番目と2番目のアプローチは普通のループに書き直すことも容易で、末尾再帰とも呼ばれ、ループ自体が再帰の特殊形であるということもなんとなく分かります。

逆に考え方としては分かりやすいと思われているループを使ったアプローチならば何でも簡単かというと、そうでもなく、例えば、lenを拡張して、中身にリストがある場合ば、中身の個数も全部数えるような、super-lengthというものを作るとします。

これもアプローチは色々あると思うのですが、

1. 要素がリストでないならば、1を足し、リストならば、今迄計算した内容をどこかに退避させて、そのリストを調べ、その合計を退避した内容と合計し…を繰り返す。

2. リスト中の要素を全部1を足す関数に置き換え最後に0という引数を与える。要素がリストの場合、そのリストに自分自身を適用する。

のようなものがあると思います。1はループで表現可能で、2は自分自身を再度呼び出すので、再帰でアプローチすると簡単です。

つまり、当然といえば当然ですが、問題というかデータ構造自体が再帰的な場合は、ループで考えることの方がややこしくなってきます。

(super-length '(1 2 3 (4 5 6 ((((((((7 8)9)10)))))))11))
;=> 11

;; 再帰で
(defun super-length (lst)
  (cond ((null lst) 0)
	((atom (car lst)) 
	 (+ 1 (super-length (cdr lst))))
	(:else 
	 (+ (super-length (car lst)) 
	    (super-length (cdr lst))))))

;; ループで
(defun super-length (lst)
  (prog (l stack len)
	(setq l lst)
	(setq len 0)
     L  (when (null l)
	  (if (null stack)
	      (return len)
	      (setq l (pop stack))))
	(if (atom (car l))
	    (incf len)
	    (push (car l) stack))
	(pop l)
	(go L)))

;; ループで その2
(defun super-length (lst)
  (loop :with l := lst :and stack :and len := 0
        :if (null l)
           :if (null stack)
              :return len
           :else
              :do (setq l (pop stack))
           :end
        :else
           :if (atom (car l))
              :do (pop l) 
                  (incf len)
           :else
              :do (push (pop l) stack)
           :end
        :end))

;; 末尾再帰で
(defun super-length (lst &optional (len 0) stack)
  (if (null lst)
      (if (null stack)
	  len
	  (super-length (car stack) len (cdr stack)))
      (if (atom (car lst)) 
	  (super-length (cdr lst) (1+ len) stack)
	  (super-length (cdr lst) len (cons (car lst) stack)))))

以上、難しさは、問題のアプローチに左右されるものであり「再帰」という概念とは別個のものなんじゃないかなあと、適当に考えたことを書いてみましたが、なんとなく纏め切れずに終わります…。

2008-02-19

LISPとリフレクション

| 02:20 | LISPとリフレクション - わだばLisperになる を含むブックマーク はてなブックマーク - LISPとリフレクション - わだばLisperになる

久々に2chのLispスレを眺めていて、3-LISPという処理系があるということを知りました。

3-LISPって一体何物と思って調べてみたら、リフレクションという概念が1982年にBrian Smith氏によって提唱された時に、その処理系として登場したとのこと。

とりあえず、面白そうだったので、処理系が公開されていないか探してみましたが、ぱっとしたものは見付からず。

それ以前にリフレクションが何だか分からなかったので、調べてみたところ、自己反映機能とも呼ばれていて、処理系自身で機能を拡張したり、実行速度を改善したりする機能のこと、とのこと。また、マクロはコンパイル時のリフレクションとも考えられる、という記述も。

何がなにやら、という感じでしたが、適当にリフレクションでヒットする論文を読んでみたところ、Common Lisp的に身近なところでは、eval-when等やコンパイル時に最適化する機構もリフレクションの一種らしいです。あと、CLOSの機能の一部とか。

例えば、define-compiler-macroはまさにそういう感じで、コンパイル時の状況によって最適化したりするのに使うようです。

(defun plus (&rest args)
  (apply #'+ args))

(define-compiler-macro plus (&whole form &rest args)
  (case (length args)
    (0 "引数がないので関数は呼び出さないで0に置き換えたいところ")
    (1 (car args))
    (t form)))

(defun foo (n)
  (plus n 3))
;=> 6

(defun bar ()
  (plus))

(print (bar))
;=> "引数がないので関数は呼び出さないで0に置き換えたいところ"

これは、CLtL2のコード例ですが、上記ではコンパイル時に引数が0か1個と判定できるならば、関数を呼びださないで、即値に置き換えてしまいます。

何となく面白いと思ったので、自分でも馬鹿っぽい例を考えてみました。

かなり無理矢理なのですが、実行結果が速く出る方を選択するdef-fasterというものを定義して、fib-slowと、fib-fastという、2種類のfibから速い方をfibという名前で呼び出せるようにする、というものです。

こういうのもリフレクションと呼べるのでしょうか…。

工夫すれば、何だか色々できそうです。

それはさておき、3-LISPがどういうものだったのか知りたい!

;; 動作
(defun fib-fast (n &optional (a1 1) (a2 0))
  (cond ((zerop n) 0)
	((< n 2) (values a1 'fast))
	('T (fib-fast (1- n) (+ a1 a2) a1))))

(defun fib-slow (n)
  (if (< n 2)
      n
      (+ (fib (1- n))
	 (fib (- n 2)))))

(def-faster fib 
    (fib-slow 30) (fib-fast 30))

(fib 10)
;=> 55, FAST

;; 定義
(defmacro run-time (fn)
  `(+ (- (get-internal-run-time)) 
      (progn
	,fn
	(get-internal-run-time))))

(defmacro def-faster (name x y)
  `(setf (symbol-function ',name)
	 (if (< (run-time ,x) (run-time ,y))
	     #',(car x)
	     #',(car y))))

2008-02-13

LET、LAMBDA、PROGN色々

| 17:11 | LET、LAMBDA、PROGN色々 - わだばLisperになる を含むブックマーク はてなブックマーク - LET、LAMBDA、PROGN色々 - わだばLisperになる

毎度、誰も興味を持たないであろうというLISPについての非常に局所的な何の役にも立たない考察をしておりますが、今回は、ローカルなブロックと変数の束縛機構の変遷について調べたことを書いてみたいと思います。

現在では、大概のところはLETで、他は、用途に応じて他はPROGNを使用する、位の感じで落ち着いていると思いますが、この流れに辿り着くまでには、それなりに変遷がございました。

とりあえず、無駄に年表的に纏めてみました。

処理系機構備考
1962Lisp 1.5PROG LAMBDA PROG2
1966PDP-6 LISPPROG2拡張引数は7つ迄の制限
1973MACLISPPROGN導入
1973MACLISP3番目のDO形式導入
1977-1979Zetalispラムダリストパラメータ&aux導入
Zetalisplet導入lambdaのシンタックスシュガー
Zetalispprog拡張 prog*導入
Zetalispprog1導入
Zetalispクロージャ導入
1983Zetalisp/CLtagbody、block導入

とりあえず、上から順に追って行くと、最初は、PROGとLAMBDAとPROG2しかありませんでした。

当初LAMBDAは、ボディ部が暗黙のPROGNではないので、式は1つしかとれず、PROG2は式が2つ取れて最後(当然2番目)の値を返してました。現在は、2番目の式の値を返すという解釈がされてますが、式が2つ取れるよ、という意味だったのかもしれません。

この時点で、ローカル変数の束縛と順次進行のブロックにおいて使い勝手が良いのは、PROGだけという感じなので殆どの関数にPROGが使われてる感じです。

;; やたらとPROG時代 - みんなこんな感じ
(defun fib (n)
    (prog (a1 a2 tem)
	  (setq a1 1)
	  (setq a2 0)
       L  (cond ((< n 2) (return a1)))
	  (setq tem a1)
	  (setq a1 (+ tem a2))
	  (setq a2 tem)
	  (setq n (1- n))
	  (go L)))

それで、1966年頃、PDP-6 LISPになって、PROG2が7つまでの式を取れるように拡張されました。互換性のためか2番目の値を返すのはそのまま。UCI LISP等は、LAMBDAのボディが暗黙のPROGNになり、今のLETの用途で、LAMBDAも使われ始めました。

;; 変数束縛にLAMBDA - 1970年台後半位まで
(defun foo (lst)
  ((lambda (x y) 
     (list x y)
     ...
     ...)
   (car lst) (cdr lst)))

その後、1973年にPROGNが登場。割と遅いです。そして、3番目の形式のDOですが、

(defun foo (lst)
  (do ((x (car lst)) (y (cdr lst))) nil
    (list x y)))

のようなもので、今のLETと同じ目的で導入されました。余計なnilが付いてることを除けば、形はLETと全く同じです。

しかし、殆ど使ってるコードがないので、流行らなかった様子です。まだまだ、PROG使用率が高い。

そして、1977頃からLispマシン登場近辺で一気に色んなものが花開いちゃってるんですが、ラムダリストパラメータの&AUX、LET、PROG1、PROG*等が導入されています。

どうも、LETより、&AUXの登場の方が古いのか、初期のLispマシンのコードでは、

(defun foo (lst)
  (let ((x (car lst)) (y (cdr lst)))
    (list x y)))

よりも

(defun foo (lst &aux (x (car lst)) (y (cdr lst)))
  (list x y))

の方が多かったりします。

当時のLETは今のSchemeと同じくマクロで、LAMBDAに展開されていました。

また、LETが浸透するにつれ&AUXの存在意義も薄れて行った感じです。

それと、MACLISPでは、LETは、destructuring-bindのように分割代入可能でした。

PROGの拡張については、

(prog ((x 0) (y 1))
      (list x y))

のように初期値が設定できるようになり、LET*からの類推からかPROG*も登場。

そして、PROG1登場。それ以前は、2つの値の交換は、

(setq x (prog2 nil y (setq y x)))

のように書かれてましたが、素直に

(setq x (prog1 y (setq y x)))

と書けるようになり、この段階でPROG2は何のために存在するのか分からないものになった模様。ちなみにPSETQの登場は、もう少し後になります。

また、LETや、LAMBDAのクロージャ的用法ですが、Zetalispもダイナミックスコープなので、レキシカルスコープのように、そのままではクロージャにならないので、それ専門のCLOSUREという構文がありました。

プリミティブとしては、CLOSUREを使うのですが、EMACSのlexical-letのようなLET-CLOSEDというマクロがあり、これを使うと

(let-closed ((a 5) b (c 'x))
   (function (lambda () ...)))

という風にクロージャが作れました。Zetalispのクロージャについては、色々操作できる謎の関数が沢山ありclosure-variablesで、中身の変数を取得したり、set-in-closureで外から中身の値を設定したり、closure-functionで、関数を取り出したり、copy-closureで複製できたり、意味なく色んなことができました。

;; Lisp Machine Lisp / Zetalisp
(defun make-accumulator (init)
  (let-closed ((acc init))
    #'(lambda (n)
	(setq acc (+ acc n)))))

(setq A (make-accumulator 5.))
(funcall A 10.)
=> 15.

(closure-variables A)
=> acc

(closure-function A)
=> (lambda (n) (setq acc (+ acc n)))

;; クロージャの中の変数Aの値を取得
(symeval-in-closure A 'acc)
=> 15

;; クロージャの中身を書き換え
(set-in-closure A 'acc 100.)
=> 100.

;; 変わっちゃいました
(funcall A 10.)
=> 110.

そして、Common Lispが最初なのか、Zetalispが最初なのか良くわかりませんが、1983年頃になると、TAGBODYと、BLOCKが登場し、基本的な構文は、LETとTAGBODYとBLOCKの組み合わせで表現するという流れになって行き、PROGを使う意義も薄れ、現在に至ります。

…という風に、お馴染のLETに辿り着くまでに割と色々あったということが分かったような、分からないような…。

以上、何のまとまりもないんですが、ローカルブロックの変遷でした。

2008-02-11

S式だった頃のDylan (2)

| 08:53 | S式だった頃のDylan (2) - わだばLisperになる を含むブックマーク はてなブックマーク - S式だった頃のDylan (2) - わだばLisperになる

ちょっと前のエントリでS式Dylanのマニュアルが見付けられない、ということを書きましたが、タイムリーなことに、comp.lang.lispで、同じようにS式Dylanのマニュアルを探してる、という方が、入手できる方法はないかを質問したところ、ほぼ即答で、ウェブからマニュアルを入手できるよ、との回答が!

昔は、AppleのftpでPS版も配布してたらしいんですが、それをHTML化したものでしょうか。

ということで、早速入手!

doが一般化された、forとか面白いです!

2008-02-09

その時代のパラダイム的なものとLISP

| 01:50 | その時代のパラダイム的なものとLISP - わだばLisperになる を含むブックマーク はてなブックマーク - その時代のパラダイム的なものとLISP - わだばLisperになる

プログラミングの初心者がこんなこと考えていて、またブログに書いてもしょうがないとは思うのですが、ふと、現在大多数の人が考えているLISP像というは、謂わば、Schemeのことなんじゃないかなと、思えてきました。

なんというか、今となっては、Unixといえば、Linuxのこと、みたいな、そんな感じで。勿論私は、Unixといえば、Linuxとは思ってないですが(笑)

レキシカルスコープじゃないLISPとか、GO TOがあったりとか、ガンガン代入文を使ったスタイルとか、それと、ちょっと違うかもしれないけれど、見た目がS式じゃなかったりとか。

そういうのは大多数の人にとってLISP的じゃないんじゃないかなと。

  • レキシカルスコープ

レキシカルスコープに関しては、Schemeが持ち込んで、その後のCommon Lispにも採用されました。

その前(1980年代初頭)は、ダイナミックスコープの処理系が主流で、MACLISP、Zetalisp、Franz Lisp(勿論Allegro CLじゃないです)等、ダイナミックスコープです。ただ、コンパイルした関数は、レキシカルスコープだったりしますが…。

  • GO TO

GO TOについては、これも70年代後半位から、GO TOの機能を提供していたPROGの使用が減少し、CLの登場で決定的になりました。ちなみにGO TOは後から取り入れられたものではなく、最初から存在します。

これについては、構造化プログラミングスタイルの啓蒙ってことも大きいとは思うのですが、その他には、PROGの果して来た機能が徐々に分解されて提供されるようになったということもあると思います、具体的には、progn、do、let、tagbody、block、等に分解されて行ったように見えます。これ以前のスタイルでは、lambdaとprogの組み合わせが主なものだったようです。主義というよりも、なんとなくPROGで書くより便利なので、そっちに乗り換えられていったという気がします。

構造化プログラミングスタイル云々より以前からLISPはあった訳なので、この辺はなんとなく独特な気がします。

また、GOTOとはいえ、関数内に限られているので、そんなに飛べる範囲は広くないので、そんなに恐しいことにはならないというのもあるでしょう。とはいえ、1つの定義で500行の壮観なGO TO多用型の関数もあったりしますが(笑)

  • ガンガン代入文を使ったスタイル

ガンガン代入文を使ったスタイルについては、割とCommon Lispでも見られると思いますが、Schemeじゃ好かれないですよね(笑)

  • プログラムの書式がS式じゃない

比較的ユーザに近い層で、S式にマッピングされたり、根底の考えがS式なのであれば、やっぱりLISPっぽくなる気がします。Dylanとか、やっぱりLISPな気がしますし、M式とか、CGOLとかユーザが直接S式を書かない方式もありました。

そういう意味で、Matz Lispは、LISPっぽいのかどうか、興味があります。自分はろくにRubyは読み書きできないのでなんとも言えないのですが、S式を感じられるなら、LISPなんじゃないでしょうか。今の私のレベルでは、あんまり感じないんですけども…。

それで何が言いたかったかということなのですが、書きたいように書けるのがLISPの良いところなんじゃないかなあ、と。

BASICみたいなスタイルで書いても良いし、SmallTalkみたいに書いても良いし、Schemeみたいに書いても良いし、Perlみたいに書いても良いし、個人のスタイルを変更しないで書くことが楽だと思います。

極論すれば、LISPには文法がないですが、限定されたスタイルもない、みたいな。

という、なんともまとまりのないエントリですいません。

もちろん、私は趣味プログラマだから、この考えは成り立つんだと思います。

2008-02-07

S式だった頃のDylan

| 10:23 | S式だった頃のDylan - わだばLisperになる を含むブックマーク はてなブックマーク - S式だった頃のDylan - わだばLisperになる

Lisp系言語でS式でないものといえば、Dylanが有名ですが、Dylanも当初はS式だったとのこと。

前々からS式だった頃のDylanってどんなものだったのか興味はあったのですが、Googleでも全然ヒットしないし、全く未知のものでした。

そんな今日、暇だったので、CMUのAIレポジトリを眺めていたのですが、Dylanのコーナーがあったのをみつけ、ファイルを漁っていたら、一番最初の古いマニュアルの中のサンプルコードが纏められているファイルをみつけました。

このexample.txtファイルでは、DylanがS式で記述されています。

ぱっと見たところでは、7割Scheme+3割CLOSのような不思議な感じですが、S式が好きな自分にとっては、結構良い感じなのでAlgol風になっちゃったのは非常に残念だったなあと思いました。マクロの仕様が決定したのは、Algol風になってからっぽいですが、Dylanのマクロは衛生的マクロなので、S式だったら、オブジェクト指向が強調されたSchemeって感じになってたんでしょうか。

それでまた全然関係のない方向に脱線していったのですが、当時Dylanにもcondがあって、デフォルト節がelse:ってことになってるのをみつけました。

Dylanでは、else:のような表記は、キーワードになり、Common Lispでいうと、:elseになります。

;; Dylan
(cond ((< new-position old-position)
        "the new position is less")
      ((= new-position old-position)
        "the positions are equal")
      (else: "the new position is greater"))

それで、考えてみれば、Common Lispでもデフォルト節は、非NILだったらなんでも良いので、

;; Common Lisp
(defun fib (n)
  (cond ((< n 2)
	 n)
	(:else
	 (+ (fib (1- n))
	    (fib (- n 2))))))

(defun fib (n)
  (cond ((< n 2)
	 n)
	(:default
	 (+ (fib (1- n))
	    (fib (- n 2))))))

でも大丈夫だなと。

結構ナイスなんじゃないかと思ったので、きっと他にもやってる人がいるに違いないと思い、Google Code Searchでも検索してみました。

予想通り同じことを考えてる人はいて、condに:elseを使ってる人は非常に少数ながら何人か見付けられました、が、しかし、年代が、大体1990年付近のコードばっかりなので、もしかしたら、Dylanの影響なのかもしれないなと、思ったり、思わなかったり。

2008-02-05

LISP-2とFUNCALL

| 01:05 | LISP-2とFUNCALL - わだばLisperになる を含むブックマーク はてなブックマーク - LISP-2とFUNCALL - わだばLisperになる

del.icio.us等のArc関連でブックマークされた記事を眺めていると、ArcがLISP-1で伝統的なマクロを採用したということが話題になっているようです。

確かに名前の競合に注意を払わなくてはいけないので、面倒という気がしますが、どれだけ大変になるものなのでしょう。

書いてはいけないパターンの一覧とかあると良いなあと思うのですが…。

それで、そういうことを考えていて、どんどん脱線してしまい、どういう訳かLISP-2のFUNCALLについて調べていました。

このFUNCALLですが、LISP-2のCommon Lispや、Emacs Lispではお馴染だと思います。

それで、導入されたのは、LISP OARCHI*1というMACLISPについての文献によれば、1973/9/15付けの記録で新しい関数の導入として説明されているので、1973年のようです。

導入の説明としては、

((CAR X) A B C)

と書くのも

(FUNCALL (CAR X) A B C)

と書くのも同じという説明があります。ただ、

((LAMBDA (CAR) (CAR X)) 'FOO)

のような場合、関数属性をもったシンボルだと、そっちが優先されてしまうので、意図した結果になりません。それで、

((LAMBDA (CAR) (FUNCALL CAR X)) 'FOO)

という風に書くことによって回避することができるようになる、と記録されています。

同じLISP-2である、MACLISP系のEmacs Lispでも、Common Lispでも、

((LAMBDA (CAR) (CAR X)) 'FOO)

という記述は意図した結果になりませんが、MACLISPでは、

('car '(1 2 3 4))

(#'car '(1 2 3 4))

((if t 'car 'cdr) '(1 2 3 4))

共にOKです。こういう記述をするとなんとなく見た目的にLISP-1に近いですが、

(let ((foo #'car))
  (foo '(1 2 3 4)))

は変数属性に値が入り、関数属性は空なのでエラーです。(fooが予め他で関数属性を持つ定義をされていれば、そっちが呼び出されます。)

MACLISPの場合を纏めると、

  1. リストの先頭を見て、アトムならばそのシンボルが関数属性を持つか調べ、あったらそれ以降を引数として、関数として実行。もしくはオブジェクトによりエラーとする。
  2. コンスならば、その式を評価して、結果を評価。

ということになるかと思います。

うまくオチが全く付けられないのですが、LISP-2にFUNCALLは必須というわけではなかったのか!ということに意味なく感動したので、このエントリを書いてみたのですが、どうにも纏まりませんでした…。

ちなみに、MACLISPでは、マクロ、コンパイル済み関数、依存ファイルのオートロード属性等々色々な属性がシンボルに付けられていて、それによって評価器が色々判断して動作していて、単純で分かりやすい気もします。Common Lispでは、この辺の動作は大分違っています。

*1:MITのAIラボのITSという当時メインで使われていたOS上のファイル

2008-02-04

idfnとidentityとcr

| 02:37 | idfnとidentityとcr - わだばLisperになる を含むブックマーク はてなブックマーク - idfnとidentityとcr - わだばLisperになる

ArcではCommon LispやSchemeのidentityが、idfnという名前になりました。

どうせなら、idくらい短かくなってしまえば良いのになどと思ってしまいますが、そんなに頻繁に使うわけでもないので、4文字位に収まっているのでしょう。

このidfnという省略名を見て思い出したのが、HHKでお馴染の和田英一先生の和田研究室が1980年代に開発したUtiLispのCRという関数。

このCRは、CAR、CDRと同じ系統のものです。

CARが1番目の要素を参照し、CDRがその残り…ということをC...Rと書けるならば、0番目を参照するということはCRと書けるんじゃないか、それで、0番目が指すものは何だってことになると、そのオブジェクト自身のことだ、ってことなのでしょうか。

それで、このCR関数なのですが、UtiLisp特有の物かと思っていたら、UNIVAC 1100 Lispという1960年代後半にUNIVAC 1100というメインフレームに移植されたLISP 1.5系のLispにも存在していました。

UtiLispは、UNIVAC 1100 Lispから影響を受けたのか、それとも、LISP 1.5にはそういう方言があったのか、はたまた、両者無関係にC...Rの類推から思い付いたのか、知る由もありません(笑)

※また、この上なくどうでも良いことなのですが、このUNIVAC 1100 LispにはDOがあるのですが、これは、Arcdoと全く同じもので、40年前に先輩がいたというのも面白い。

1960年代位までのCAR、CDR関数の捉えられかたは、今のFIRSTと、REST関数と同じもの、というものとは、ちょっと違っていたんじゃないのかなあと、個人的には思っています。

例えば、PDP-1 LISPでは、シンボルのCDRには、プロパティが収められていて、関数の場合は、関数の定義が入っていますし、PDP-6 LISPでは、それに加えて、シンボルのCARは、何に使うのか良く分かりませんが、オブジェクトのアドレス -1の数値です。何というかもっとアドレス演算子っぽい雰囲気があるんですが、CRもそういうところから出てきた気がしています。

ちなみに、UtiLispの最新版Utilisp/C 1.14は、ソースが公開されていて、32bit Linuxでさっくり動作します。綺麗なマニュアルも付いてきますので、是非お試しあれ!

2008-02-03

リーダーマクロも深すぎる

| 02:01 | リーダーマクロも深すぎる - わだばLisperになる を含むブックマーク はてなブックマーク - リーダーマクロも深すぎる - わだばLisperになる

Arcについてのブログ記事で、Common Lispのリーダーマクロでhash.keyとか、(hash => key)とか、(hash key)とかできるのか否か、という話題がありました。

面白そうだったので、自分もあれこれ考えて挑戦してみることにしました!

とりあえず、全然関係ないですが、Arcの[ _]構文から、

;; 動作
(mapcar [* 3 _] '(1 2 3 4))
;=> (3 6 9 12)

;; 定義
(set-macro-character #\[ 
		     (lambda (stream char)
		       (declare (ignore char))
		       (let ((body (read-delimited-list #\] stream t)))
			 `#'(lambda (,(intern "_")) ,body))))

(set-macro-character #\] (get-macro-character #\)))

次に、

  1. hash.key
  2. (hash => key)
  3. ("string" 1)
  4. ('(foo bar baz) 1)

のような記法。

本当は丸括弧にしたいところですが、{}で囲んでごまかしています。

丸括弧にも関数は対応しているわけなので、その関数を拡張すれば良いんだろうなと、なんとなくの見当は付いた気はしますが、荷が重いので、今後の課題とすることにしました…。本当に果てしないなあ…。

;; 動作
(let ((l '(foo bar baz))
      (ht (make-hash-table)))
  (setf (gethash 'key ht) 'val)
  (list
   {"foo" 1}
  {'(foo bar baz) 2}
  {l 2}
  {ht 'key}				;(ht 'key)
  {ht => key}				;(ht => key)
  {progn
     ht.key})) 				;ht.key
;=> (#\o BAZ BAZ VAL VAL VAL)

;; ごみごみとした適当な定義
(set-macro-character #\} (get-macro-character #\)))

(set-macro-character #\{
		     (lambda (str char)
		       (declare (ignore char))
		       (let ((body (read-delimited-list #\} str t)))
			 (cond ((eq '=> (cadr body))                 ; (hash => key)
				`(obcall ,(car body) ',(caddr body)))
			       ((some #'sym.bol-p body)              ; hash.key
				(mapcar (lambda (x)
					  (if (sym.bol-p x)
					      (hash.key->gethash x)
					      x))
					body))
			       ('T `(obcall ,@body))))))

(defun sym.bol-p (sym)
  (and (symbolp sym)
       (position #\. (string sym)) t))
      
(defun obcall (obj arg)
  (etypecase obj
    (hash-table (gethash arg obj))
    (sequence (elt obj arg))))

(defun hash.key->gethash (sym)
  (let* ((str (string sym))
	 (sep (position #\. str)))
    (flet ((intern-upcase (str) (intern (string-upcase str))))
      `(gethash ',(intern-upcase (subseq str (1+ sep)))
		,(intern-upcase (subseq str 0 sep))))))
;