UNIXの歴史とか思想とかの本

book

スラッシュドットでUNIX 40 歳おめでとう！ という記事がありました。たった40歳！！ここ数年前にUNIXに出会った私にはびっくりのニュースでした。そこで40年前、UNIXはどのように生まれたのか気になったので本を探してみました。


UNIXの1/4世紀 (Ascii books)
UNIXの1/4世紀 (Ascii books)

  • OSやコンパイラ、プログラミング言語などのコンピュータの一通りの知識がないと読み通すのは難しい。
  • コンピュータ自体の歴史とプログラミング言語の歴史を知っていると、なお読みやすい。
  • 登場人物や略語が多くでてきて、純粋に読みずらくなっている。
  • UNIX系のコマンドがどのような背景から作りだされたのかという所はおもしろい。
    • 特に、C言語の構文チェッカの「lint」やawkなどの開発経緯を作者みずから語ってくれている。
  • 副読本としてlife with UNIXが読みやすいらしい。





UNIXの思想的なことを教えてくれる本はUNIXという考え方―その設計思想と哲学がおすすめ。題名のとおりUNIXがどのような意図と持って作られているかが書いてある。実はこの本は、UNIXに触る前に読みました。それでも「あ〜、UNIXってこんななのか」というぐらいはわかるので、UNIXに興味があるが触ったことがないという人にもオススメできます。






UNIXのソースに興味がでてきたら，Lions’ Commentary on UNIX (Ascii books) , オペレーティングシステム 第3版の二つがソース付きで解説されている。Lions'sの方は今ではあまり使われていないC言語でかかれているので、読むのに少し苦労すると思う。オペレーティングシステムの方はMINIXというOSの最低限の機能を実装したシステムなので、いきなりLinuxなどのソースを読むより楽に学習できる。しかしやっぱりこの二つの本は内容が重いため、もっと簡単な本がないか探しているところでです。


また、@ITの自分戦略研究所で連載している「IT業界の冒険者たち」が、コンピュータの歴史の有名人物について解説している。ここにもUNIXに関係のある人が解説されている。もともとは、本によって売られていた文が転載されているようなので、読みやすく、まとまっていてわかりやすいです。バックナンバーのインデックスページが見つからなかったので、UNIXの神様 − ＠IT自分戦略研究所のリンクを貼っておきます。

SICP独習会 並びの演算2 (問題2.36〜)

SICP


問題2.36
さっぱりわからず、解答を見ることに。

define(accumulater-n op init seqs)
  (if (null? (car seqs))
    '()
    (cons (accumulater op init (map car seqs))
          (accumulater-n op init (map cdr seqs)))))

gosh> (accumulater-n + 0 (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
CALL accumulater-n #[proc] 0 ((1 ...) (4 ...) (7 8 ...) (10 11 12))
 CALL map #[proc] ((1 2 ...) (4 5 ...) (7 8 9) (10 11 12))
 RETN map (1 4 7 10)
 CALL accumulater #[proc] 0 (1 4 7 10)
  CALL accumulater #[proc] 0 (4 7 10)
   CALL accumulater #[proc] 0 (7 10)
    CALL accumulater #[proc] 0 (10)
     CALL accumulater #[proc] 0 ()
     RETN accumulater 0
    RETN accumulater 10
   RETN accumulater 17
  RETN accumulater 21
 RETN accumulater 22
 CALL map #[proc] ((1 2 ...) (4 5 ...) (7 8 9) (10 11 12))
 RETN map ((2 3) (5 6) (8 9) (11 12))
 CALL accumulater-n #[proc] 0 ((2 ...) (5 ...) (8 9) (11 12))
  CALL map #[proc] ((2 3) (5 6) (8 9) (11 12))
  RETN map (2 5 8 11)
  CALL accumulater #[proc] 0 (2 5 8 11)
   CALL accumulater #[proc] 0 (5 8 11)
    CALL accumulater #[proc] 0 (8 11)
     CALL accumulater #[proc] 0 (11)
      CALL accumulater #[proc] 0 ()
      RETN accumulater 0
     RETN accumulater 11
    RETN accumulater 19
   RETN accumulater 24
  RETN accumulater 26
  CALL map #[proc] ((2 3) (5 6) (8 9) (11 12))
  RETN map ((3) (6) (9) (12))
  CALL accumulater-n #[proc] 0 ((3) (6) (9) (12))
   CALL map #[proc] ((3) (6) (9) (12))
   RETN map (3 6 9 12)
   CALL accumulater #[proc] 0 (3 6 9 12)
    CALL accumulater #[proc] 0 (6 9 12)
     CALL accumulater #[proc] 0 (9 12)
      CALL accumulater #[proc] 0 (12)
       CALL accumulater #[proc] 0 ()
       RETN accumulater 0
      RETN accumulater 12
     RETN accumulater 21
    RETN accumulater 27
   RETN accumulater 30
   CALL map #[proc] ((3) (6) (9) (12))
   RETN map (() () () ())
   CALL accumulater-n #[proc] 0 (() () () ())
   RETN accumulater-n ()
  RETN accumulater-n (30)
 RETN accumulater-n (26 30)
RETN accumulater-n (22 26 30)
(22 26 30)
gosh> (map * (list 1 2 3) (list 4 5 6))
CALL map #[proc] (1 2 3) (4 5 6)
RETN map (4 10 18)
(4 10 18)

これはすごいなあ。「map car seq」で第一要素だけ取りだすことができるのか。これはmapが「必ず要素に作用させてリストを返す」という性質をうまく使った例だと思う。

SICP独習会 並びの演算(問題2.33〜)

SICP

問題2.33

この問題を解くには、定義する手続きを、accumulate(積み上げる)という単語を使って説明できなければ解くことができないと思う。


で、mapは最初このように定義した。

現在の要素と、次の要素を、与えられた手続きを作用させる。作用させた要素をaccumulateとしてlist形式で返す。次の要素がナルの場合、「cons x '()」でlistを閉じる。

この定義にしたがって、最初に書いたコードがこれ。

(define (my-map p sequence)
  (accumulater (lambda (x y)
                 (if (null? y)
                   (cons (p x)'())
                   (cons (p x) (p y))))
               '()
               sequence))

実行をトレース。



gosh> (my-map (lambda (x) (* x x)) (list 1 2 3 4))

CALL my-map #[proc] (1 2 3 4)

 CALL accumulater #[proc] () (1 2 3 4)

  CALL accumulater #[proc] () (2 3 4)

   CALL accumulater #[proc] () (3 4)

    CALL accumulater #[proc] () (4)

     CALL accumulater #[proc] () ()

     RETN accumulater ()

    RETN accumulater (16)




    
ERROR: operation * is not defined between (16) and (16)

ぉぉう。これは初めてのエラーだ。原因を探ってみたが、いまいちわからなかった。「にゅお~！！」と悔やしく叫びながら、解答を参考させてもらうことに。

(define (my-map p sequence)
  (accumulater (lambda (x y)
                (cons (p x) y))
               '()
               sequence))
関数型言語の勉強にSICPを読もう - (13) 2章 - データによる抽象の構築(65-69ページ) - higepon blog


トレースした結果。



gosh> (my-map (lambda (x) (* x x)) (list 1 2 3 4))

CALL my-map #[proc] (1 2 3 4)

 CALL accumulater #[proc] () (1 2 3 4)

  CALL accumulater #[proc] () (2 3 4)

   CALL accumulater #[proc] () (3 4)

    CALL accumulater #[proc] () (4)

     CALL accumulater #[proc] () ()

     RETN accumulater ()

    RETN accumulater (16)

   RETN accumulater (9 16)

  RETN accumulater (4 9 16)

 RETN accumulater (1 4 9 16)

RETN my-map (1 4 9 16)

(1 4 9 16)


あ〜そうか。yはまた再帰的に呼び出されているから、そのままconsしてしまえばよいのか。深く考えすぎたか。

accumulateを使ってのappend手続き

言葉による定義。

第一引数の並びを初期値としての第二引数をconsでaccumulateして返す。

(define (my-append seq1 seq2)
  (accumulater cons
               seq2
               seq1))




CALL my-append (1 2 3) (4 5 6)

 CALL accumulater #[proc] (4 5 6) (1 2 3)

  CALL accumulater #[proc] (4 5 6) (2 3)

   CALL accumulater #[proc] (4 5 6) (3)

    CALL accumulater #[proc] (4 5 6) ()

    RETN accumulater (4 5 6)

   RETN accumulater (3 4 5 6)

  RETN accumulater (2 3 4 5 6)

 RETN accumulater (1 2 3 4 5 6)

RETN my-append (1 2 3 4 5 6)

(1 2 3 4 5 6)

accumulateを使ってのlength手続き

言葉による定義。

与えられた要素の個数分だけ1をaccumulateする。

(define (my-length sequence)
  (accumulater (lambda (x y) (+ 1 y))
               0
               sequence))




CALL accumulater #[proc] 0 (1 2 3 4)

 CALL accumulater #[proc] 0 (2 3 4)

  CALL accumulater #[proc] 0 (3 4)

   CALL accumulater #[proc] 0 (4)

    CALL accumulater #[proc] 0 ()

    RETN accumulater 0

   RETN accumulater 1

  RETN accumulater 2

 RETN accumulater 3

RETN accumulater 4

4

うまく動いてはいるが、使わない引数を取るのはうまく抽象化できていないと思う。と、思ったので解答集を見てみると、私の解答を同じだった。う〜む。

問題2.34

多項式を計算するhornerの方法というのがでてきた。これは多項式を計算するアルゴリズムとして最適な方法らしい。

このhornerの方法は後ろの方(指数部の大きい方)から計算していくから・・・

(define (horner-eval x coefficient-sequence)
  (accumulater (lambda (this-coeff higher-terms)
                 (+ this-coeff (* x higher-terms)))
               0
               coefficient-sequence))




CALL accumulater #[proc] 0 (1 3 0 5 0 1)

 CALL accumulater #[proc] 0 (3 0 5 0 1)

  CALL accumulater #[proc] 0 (0 5 0 1)

   CALL accumulater #[proc] 0 (5 0 1)

    CALL accumulater #[proc] 0 (0 1)

    RETN accumulater 2

   RETN accumulater 9

  RETN accumulater 18

 RETN accumulater 39

RETN accumulater 79

79
ここまでaccumulateを利用して手続きを定義してきたけど、accumulateは反復プロセスとなんだか似ているなあと感じて来た。

問題2.35

またもや、accumulateを使っての問題。

最初に書いたコード。

(define (count-leaves t)
  (accumulate +
              0
              (map
                (lambda (x)
                  (cond ((null? x) 0)
                        ((not (pair? x)) (/ x x))))
                t)))

信号処理的に考えてみたところ

  • mapを使って要素の数を全て1に替る。
  • accumulateする

という構想のもと書いてみたが、あえなくエラーが返って終了。解答集を見ることに。

(define (count-leaves t)
  (accumulater +
               0
               (map
                 (lambda (x)
                   (if (pair? x)
                     (count-leaves x)
                     1))
                 t)))

なんだろう・・・考えかたとしてはなんとなくあってる気がするが、mapの結果をlistで返すことを意識するべきだったのな。どうやったらこのようなコードを思い付けるのだろうか。以下がトレースした結果。

  

CALL count-leaves (1 (2 (3 4) 5))

 CALL map #[proc] (1 (2 (3 4) 5))

  CALL count-leaves (2 (3 4) 5)

   CALL map #[proc] (2 (3 4) 5)

    CALL count-leaves (3 4)

     CALL map #[proc] (3 4)

     RETN map (1 1)

     CALL accumulater #[proc] 0 (1 1)

      CALL accumulater #[proc] 0 (1)

       CALL accumulater #[proc] 0 ()

       RETN accumulater 0  

      RETN accumulater 1   

     RETN accumulater 2

    RETN count-leaves 2

   RETN map (1 2 1)

   CALL accumulater #[proc] 0 (1 2 1)

    CALL accumulater #[proc] 0 (2 1)

     CALL accumulater #[proc] 0 (1)

      CALL accumulater #[proc] 0 ()

      RETN accumulater 0   

     RETN accumulater 1

    RETN accumulater 3

   RETN accumulater 4

  RETN count-leaves 4

 RETN map (1 4)

 CALL accumulater #[proc] 0 (1 4)

  CALL accumulater #[proc] 0 (4)

   CALL accumulater #[proc] 0 ()

   RETN accumulater 0

  RETN accumulater 4

 RETN accumulater 5

RETN count-leaves 5

5

ポメラのような、vimが使用できる「書く」という作業に特化したOSという妄想

自作OS

数ヶ月前に、ポメラという機器がネット界隈で話題になりました。このポメラ、「書く」という作業にだけ特化しているコンピュータでブログなどを書いている方に愛用されているそうです。

しかし、僕などのがそうなのですが、「エディタを自由に選べたらいいなあ。」という欲求がふつふつと湧いてきました。自分の使いなれているエディタ(私の場合はvim。)で作業できればストレスなく作業できるのになあ、と思っています。

そこで最近こんなOSあったらどうだろう、と妄想しています。あ、ここで使用するPCはEeePCなどのネットブックを想定しています。

  • 起動は爆速。2秒くらいで起動する。
  • vim,またはEmacsが起動できる。
  • データの移動手段をUSBや無線LAN経由で行うことができる。

う〜ん、作ってみたいけど、難しそうだなあ・・・でもSSDがもっと安くなれば、案外現実的な気がする。

SICP独習会 木の写像 (問題2.30〜)

SICP

問題2.30

高階手続きを使わない版
(define (square-tree tree)
  (cond
    ((null? tree) '())
    ((not (pair? tree)) (* tree tree))
    (else (cons (square-tree (car tree))
                (square-tree (cdr tree))))))
高階手続きを使う版
(define (square-tree tree)
  (map
    (lambda (sub-tree)
      (if (pair? sub-tree)
        (square-tree sub-tree)
        (* sub-tree sub-tree)))
    tree))

問題2.31

定義はすらすらっと書けた。

(define (square-tree tree)
  (tree-map (lambda (x) (* x x)) tree))

(define (tree-map proc tree)
  (map
    (lambda (sub-tree)
      (if (pair? sub-tree)
        (tree-map proc sub-tree)
        (proc sub-tree)))
    tree))

以下がtraceしてみた結果。



gosh> (square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))

CALL square-tree (1 (2 (3 ...) 5) (6 7))

 CALL tree-map #[proc] (1 (2 (3 ...) 5) (6 7))

  CALL tree-map #[proc] (2 (3 4) 5)

   CALL tree-map #[proc] (3 4)

   RETN tree-map (9 16)

  RETN tree-map (4 (9 16) 25)

  CALL tree-map #[proc] (6 7)

  RETN tree-map (36 49)

 RETN tree-map (1 (4 (9 ...) 25) (36 49))

RETN square-tree (1 (4 (9 ...) 25) (36 49))

(1 (4 (9 16) 25) (36 49))
気付いたのだけれど、再帰してる手続きは後ろから結果ができていくみたいね。当たり前といえば、そうなのだけれど。

SICP独習会 階層構造(問題2.24〜)

SICP


この節では、リストを使って木構造を表現しています。ここから、込みいったリストの使い方をしてくるので、リストについて理解しておかないと、キツくなってきます。(←私)

続きを読む