« プログラミングを始めるには(10) | Main | プログラミングを始めるには(12) »

July 29, 2014

プログラミングを始めるには(11)

プログラミングを始めるには、たいていの人が言語仕樣書やその言語に關する學習書を買うに違いない。閒違ってもこのブログを讀んで勉强しようなどと考える人は居ない。しかし、言語仕樣書を讀むことほど退屈なことは無い。これはプログラミング言語書籍の宿命みたいなもので、書いた人がどれほどユニークで面白いこと發想したり考えたりする人であっても、書籍を書くと面白くも何ともなくなる。まあ、たまに吉田弘一郞のような人も居るわけだが...。

私のこれまでの經驗では、言語仕樣書でも言語學習書でも似たようなものだが、それを讀んでプログラムが書けるようになるわけではない...というと少し言い過ぎだろうか。もし假に、その本を讀んだだけでプログラムをスラスラ書けるようになるのなら、大ベストセラー閒違いなしだろう。

スコップを持ったことがない人に穴掘りが出來ないのと同樣に、プログラムを書いたことない人がどれほど素晴らしい言語書籍を讀んだとしても、ある日突然プログラムを書けるようになるなどということはあり得ない。習うより慣れろと常套句的に言われるが、プログラミングスキルはプログラムを書くことによって向上するのであり、讀んだ本の多寡によるものではない。

さて、Lispを學び始めるときに最初にやるのが純Lisp(最小のLisp)というやつらしい。これでプログラムを書くことがLispらしいプログラムを書く早道なのかもしれないが、私はこれに贊成ではない。その理由として、再歸的なロジックを書くことを前提にしているようなフシがあるからだ。中には再歸でなければアルゴリズムではないと考えている人も居るような氣がする。

その例として「Lispでエラトステネスのふるい」(神戸大学)というのを檢討してみる。

(defun range (m n)
  (if (> m n)
      ()
    (cons m (range (+ m 1) n))
    ))
range

(range 2 332)
(2 3 4 5 6 7 8 9 10 11 12 13 ...)

このrangeという關數は自身を再歸的に呼び出して、m~nまでの數値のリストを作り出す。例として2~332で實行しているのは、それ以上のリストを作ろうとするとmax-lisp-eval-depthというEmacs特有の制限値にひっかかってエラーになるからである。この制限値は再歸の深度を制限するもので、無限に再歸呼び出しをしてしまわないためのストッパーのようなものだ。

で、再歸に關しては、内部でループ處理に變換される處理系であれば安全とかいう話以前に、そもそも再歸は好きではない(私は別に學者でも識者でもないので批判はしない)。

(defun range (m n)
  (do ((i m (1+ i))
       (to nil (cons i to)))
      ((> i n) (reverse to))))
range

(range 2 65535)
(2 3 4 5 6 7 8 9 10 11 12 13 ...)

ただ、こう書けば良いのに...と思うだけだ。これならばnを65535だろうが10000だろうが、處理が終わるまでに機械的な閒はあってもエラーにはならない。

(defun filter (n xs)
  (if (null xs)
      ()
    (if (= (% (car xs) n) 0)
        (filter n (cdr xs))
      (cons (car xs) (filter n (cdr xs)))
      )))
filter

(filter 2 (range 2 284))
(3 5 7 9 11 13 15 17 19 21 23 25 ...)

(defun filter (n xs)
  (dolist (elm xs xs)
    (and (= 0 (% elm n))
	 (setq xs (delete elm xs)))))
filter

(filter 2 (range 2 65535))
(3 5 7 9 11 13 15 17 19 21 23 25 ...)

エラトステネスのふるいSTEP2は、range關數で作成した數値リストから、nで割り切れる數値を取り除くfilter關數の作成である。例によって、再歸版とそうでない版を。再歸版の方はrangeのmaxを285以上にすると深度深過ぎエラーになるが、そうでない版の方はエラーにならない代わりにmazeったかな?というくらい時閒がかかる。もちろんこれはmaxを65535にしているからで、285だったら一瞬で終わる。

(defun sieve (xs)
  (if (null xs)
      ()
    (cons (car xs) (sieve (filter (car xs) (cdr xs))))
    ))
sieve

(sieve (range 2 2212))
(2 3 5 7 11 13 17 19 23 29 31 37 ...)

(defun sieve (xs)
  (do ((top (car xs) (car xs))
       (ans nil (cons top ans)))
      ((null top) (reverse ans))
    (setq xs (filter top xs))))
sieve

(sieve (range 2 65535))
(2 3 5 7 11 13 17 19 23 29 31 37 ...)

そして、このステップでエラトステネスのふるいが完成する。本當のふるいは數値リストの先頭がmaxの平方根より大きくなったらそこで探索をやめて良いが、その終了チェックは省かれている。

ちょっと長くなってきたが、私を含めedebugという便利なものを知ってしまった俄かLisperには、なぜ諸先輩方が再歸でプログラムを書くのか分からないかもしれない。實は元來Lisp屋さんというのは、どういうリストを處理すれば目的に達するかという發想でプログラムを書いている。

たとえば最初のrange關數で言えば、(range 2 10)の場合、(cons 2 (cons 3 (cons 4 (cons 5 (cons 6 (cons 7 (cons 8 (cons 9 (cons 10 ())))))))))というリストを評價すれば良いと考えるわけだ。このリストと再歸版のrange關數を見比べれば合點がいくと思う。たしかにこういう考え方で書くことに慣れていくとマクロも見い出し易いのであろう。さらに、元々emacs-lispのようにエディタと一體になった處理系などというのは無く、もちろんedebugなんていうデバッガはなかったわけで、處理の不具合を見つけるにはtraceを使って走行確認するしかなかった。
======================================================================
1 -> sieve: xs=(2 3 4 5 6 7 8 9 10)
| 2 -> filter: n=2 xs=(3 4 5 6 7 8 9 10)
| | 3 -> filter: n=2 xs=(4 5 6 7 8 9 10)
| | | 4 -> filter: n=2 xs=(5 6 7 8 9 10)
| | | | 5 -> filter: n=2 xs=(6 7 8 9 10)
| | | | | 6 -> filter: n=2 xs=(7 8 9 10)
| | | | | | 7 -> filter: n=2 xs=(8 9 10)
| | | | | | | 8 -> filter: n=2 xs=(9 10)
| | | | | | | | 9 -> filter: n=2 xs=(10)
| | | | | | | | | 10 -> filter: n=2 xs=nil
| | | | | | | | | 10 <- filter: nil
| | | | | | | | 9 <- filter: nil
| | | | | | | 8 <- filter: (9)
| | | | | | 7 <- filter: (9)
| | | | | 6 <- filter: (7 9)
| | | | 5 <- filter: (7 9)
| | | 4 <- filter: (5 7 9)
| | 3 <- filter: (5 7 9)
| 2 <- filter: (3 5 7 9)
| 2 -> sieve: xs=(3 5 7 9)
| | 3 -> filter: n=3 xs=(5 7 9)
| | | 4 -> filter: n=3 xs=(7 9)
| | | | 5 -> filter: n=3 xs=(9)
| | | | | 6 -> filter: n=3 xs=nil
| | | | | 6 <- filter: nil
| | | | 5 <- filter: nil
| | | 4 <- filter: (7)
| | 3 <- filter: (5 7)
| | 3 -> sieve: xs=(5 7)
| | | 4 -> filter: n=5 xs=(7)
| | | | 5 -> filter: n=5 xs=nil
| | | | 5 <- filter: nil
| | | 4 <- filter: (7)
| | | 4 -> sieve: xs=(7)
| | | | 5 -> filter: n=7 xs=nil
| | | | 5 <- filter: nil
| | | | 5 -> sieve: xs=nil
| | | | 5 <- sieve: nil
| | | 4 <- sieve: (7)
| | 3 <- sieve: (5 7)
| 2 <- sieve: (3 5 7)
1 <- sieve: (2 3 5 7)
このようにtraceを使うと、sieve關數やfilter關數をどう呼び出したかが分かる。Emacsのようなエディタでなく端末からLispを使っていた人たちは、こうやってプログラムをデバッグするしかなかったのだ。なので、再歸でプログラムを書いて何が面白い?などという言い方は全くのお門違いだったということになるわけだ。

|

« プログラミングを始めるには(10) | Main | プログラミングを始めるには(12) »

Comments

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/74224/60062374

Listed below are links to weblogs that reference プログラミングを始めるには(11):

« プログラミングを始めるには(10) | Main | プログラミングを始めるには(12) »