Scheme 手習い（９）~ Y コンビネータ~

第9章：…… もう一度、もう一度、もう一度、……（続き）

第9章の最後は Y コンビネータについて。 リストの要素数を数える length を題材にして Y コンビネータを学ぶ。

length

リストの要素数を数えるなんの変哲もない関数 length を定義する。

(define (length l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))]))

length を define を使わずに定義できるだろうか？

define がなければ、関数名を定義できないので定義内で自身を参照できない。 これでは再帰ができないので length は定義できなくなってしまう。

でも、方法はある。それが Y コンビネータだ。 順を追って考えよう。

length-0, length-1, ..., length-n

まずは空リストの要素数を数えることができる関数を定義しよう。 ここで重要なのは define を使わず、lambda だけを使うことだ。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1 (eternity (cdr l)))]))

空リスト以外だと無限ループするが、これで空リストの要素数は数えられるようになった。 これを length-0 と呼ぶことにする。

では、次に要素 1 以下のリストを数えられる関数を定義してみる。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1 (length-0 (cdr l)))]))

define がないのだから length-0 は参照できない。 そこで、length-0 の定義をそのまま lambda を使った表記に置き換えることにする。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1
                ((lambda (l)
                  (cond [(null? l) 0]
                        [else (add1 (eternity (cdr l)))]))
                 (cdr l)))]))

これを length-1 と呼ぼう。

同じようにしていけば length-2、length-3、...、length-n を定義できるはずだ。

ただ、見ての通りどんどん関数定義が長くなってしまう。 このままでは length は定義できない。

mk-length

そこで共通のパターンを抽象化して、同じ関数定義を繰り返し書かなくてもよいようにしたい。 さきほどの length-n の次の部分を共通化することを考える。

(lambda (l)
  (cond [(null? l) 0]
        [else (add1 (length (cdr l)))]))

定義内の length はどこにも存在しないため、このままでは参照できない。 そこで引数として length を外から与えられるようにする。

(lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))

こうすれば length-n を定義できる。 例えば length-0 を作りたいなら eternity を渡せばよい。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 eternity) ; = length0

length-1 なら次のように length-0 を与えれば良い。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 length-0)

ただ、ここでも length-0 は参照できないので lambda を使った表記に置き換える必要がある。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 ((lambda (length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 (length (cdr l)))])))
   eternity)) ; = length1

さらに length-2 は次のようになる。

((lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
 ((lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))])))
  ((lambda (length)
     (lambda (l)
       (cond [(null? l) 0]
             [else (add1 (length (cdr l)))])))
   eternity)))

ここまでの変形で同じような部分が連続するようになった。

共通する部分 (lambda (length) ... が何をしているかといえば、「外から次の再帰呼び出しの関数を受け取り length 関数を生成する」という処理だ。

(lambda (length)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (length (cdr l)))])))
; => これに名前を付けたい

そこでこの関数に make length を意味する mk-length という名前を付けることにする。

名前を付けるにはどうしたらよいか。 lambda を用いて引数としてさきほどの関数を与え、引数に mk-length と名前をつけることにする。

そうすると length-0 は次のようになる。

((lambda (mk-length)
   (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

length-1 は次のようになる。

((lambda (mk-length)
   (mk-length
     (mk-length eternity)))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

length-2 は次のとおり。

((lambda (mk-length)
   (mk-length 
     (mk-length
       (mk-length eternity))))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

ここまでの変形でだいぶシンプルになった。念のため実行してみる。

(((lambda (mk-length)
    (mk-length 
      (mk-length
        (mk-length eternity))))
  (lambda (length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 (length (cdr l)))]))))
  '(1 2)) ; => 2

ただしく実行することができた。 しかし、まだ要素数が多くなるほど関数定義も増えてしまう点に変わりはなく、このままでは length は定義できない。

(mk-length mk-length)

今のままでは mk-length を何度も書かないと length を定義できない。 あともう少し、関数を変形すればこれを回避することができる。

まず、eternity について。 eternity は無限ループする関数なので、呼び出した時点で処理は終了しなくなる。 どうせ、eternity を呼んでしまったらそこで終わりなのだから、eternity ではなく何か別の関数、たとえば mk-length 自体を渡すように変更してみる。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (length (cdr l)))]))))

こうすると mk-length には length ではなく、mk-length が渡ってくるようになる。 そこで引数名を length から mk-length に変更する。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (mk-length (cdr l)))]))))

この時点では mk-length に (cdr l) を渡してしまっている。 mk-length は関数を引数に受け取る関数なので、mk-length を渡す必要がある。

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 ((mk-length mk-length) (cdr l)))]))))

(mk-length mk-length) は length を生成する呼び出しであり length 関数を返してくれる。 mk-length 関数に自分自身（mk-length）を渡すようにしたおかげで、再帰してリストを数える length が定義できるようになった。

これで define を使わずに length を定義できた。

(((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((mk-length mk-length) (cdr l)))]))))
 '(1 2 3 4)) ; => 4

これで一応、「define を使わずに length を定義する」という目的は達成することができた。

Y コンビネータ

ここまで define を使わずに length を定義できた。 さて、これを一般化して length に限らず、任意の再帰関数を define を使わずに定義できるか考えてみよう。

任意の再帰関数を定義するためには「再帰を行うための関数部分」と「再帰関数自体の定義部分」に分けることを目標とする。

さきほどの length から一つずつ関数を変形していこう。

((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((mk-length mk-length) (cdr l)))]))))

(add1 ...) の中にある (mk-length mk-length) は、length を生成する関数呼び出しになっている。 そこで、この関数を呼び出した結果を length という名前をつけて扱うことにする。

例によって、lambda の引数を使って、length という名前を付けることにする。

((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond [(null? l) 0]
               [else (add1 (length (cdr l)))])))
     (mk-length mk-length))))

(mk-length mk-length) を事前に評価し、length という名前の引数に渡す形に変えた。 しかし、この定義では定義を評価しようとすると無限ループしてしまう。 引数の (mk-length mk-length) を評価する段階で、無限に展開しようとしてしまうためだ。

(mk-length mk-length) は必要な時に一度だけ評価されるようにしたい。 そこで、遅延評価されるように lambda を使って (mk-length mk-length) を呼び出せるようにする。

((lambda (mk-length)
  (mk-length mk-length))
 (lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond [(null? l) 0]
               [else (add1 (length (cdr l)))])))
     (lambda (x) ((mk-length mk-length) x)))))

これで無限ループすることなく length が定義できた。あともう少しだ。

次に、内部のまさに length 特有の処理を定義している部分を le という引数名にして、一番外側にくくり出す。

(lambda (le)
  ;; 再帰を行うための関数部分
  ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     (le (lambda (x) ((mk-length mk-length) x)))))
  ;; 再帰関数自体の定義部分。le という名前になる
  (lambda (length)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 (length (cdr l)))]))))

これで「再帰を行うための関数部分」の部分と「再帰関数自体の定義部分」に分けることができた。

一般的にこの「再帰を行うための関数部分」を 適用順 Y コンビネータ と呼ぶ。 引数を mk-length のような名前ではなく、より一般的な f とすると次のようになる。

(define Y
  (lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

ついによく見かける Y コンビネータにたどり着いた。

これを使って階乗 fact は次のように定義できる。

(define fact
   (Y (lambda (f)
        (lambda (n)
          (cond [(= n 1) 1]
                [else (* n (f (- n 1)))])))))
(fac 5) ; => 120

どうやら正しく Y コンビネータを定義できたようだ。

ずいぶんと長くなってしまったが、一応 Y コンビネータについて理解した。 一通り書いてあることは理解したつもりだけど、本質的に理解できてはいないなという感じ。 もっと深い理解にたどり着くためにはもっと努力が必要なようだ。

これで Scheme 手習いもあと1章を残すのみとなった。

Scheme 手習い（８）

第9章：…… もう一度、もう一度、もう一度、……

keep-looking

(define (pick to lat)
  (cond [(= to 0) (car lat)]
        [else (pick (- to 1) (cdr lat))]))
        
(define (keep-looking a to lat)
  (cond [(number? to)
         (keep-looking a (pick to lat) lat)]
        [else (eq? a to)]))

引数のインデックスの要素が数字かシンボルかを判定する。 数字だった場合にはさらにその数字をインデックスとして要素を取得して同じ事を繰り返す。もし、シンボルだったら渡された a と一致するかを調べる関数。

この再帰は常にリストが短くなっていくわけではないので、無限ループする可能性がある。

これを「不自然な再帰」と呼んでいる。

eternity

(define (eternity x)
  (eternity x))

値を返さない関数。このような関数を部分関数というらしい。 入力に対して一部しか値が定義されないから部分関数と呼ぶのか？

shift

(define (build a b)
  (cons a (cons b '()))) 
(define (first a)
  (car a))
(define (second a)
  (car (cdr a)))
 
(define (shift x)
  (build (first (first x))
    (build (second (first x))
      (second x))))

第１要素がペアであるペアをとり、第２要素に第１要素の先頭をつけてペアを作る関数

align

(define (align para)
  (cond [(atom? para) para]
        [(a-pair? (first para))
         (align (shift para))]
        [else (build (first para)
                (align (second para)))]))

ペアで構成されたリストを整列させる関数。 たとえば ((a b) ((c d) (e f))) という入力の場合、出力は (a (b (c (d (e f))))) となる。

length* と weight*

(define (length* para)
  (cond [(atom? para) 1]
        [else (+ (length* (first para))
                 (length* (second para)))]))
(define (weight* para)
  (cond [(atom? para) 1]
        [else (+ (* (length* (first para)) 2)
                 (length* (second para)))]))

ペアで構成されたリストの要素を数える関数。 また、第一要素に重みをつけたのが weight* 関数。

weight* を使うと align が再帰するたびに、重みが軽くなっていることが分かるので、再帰が収束することが分かるらしい。 なんとなく理屈は理解できるけど、すべてのケースに置いて本当にそうなのかは不明。

C

(define (C n)
  (cond [(one? n) 1]
        [(even? n) (C (/ n 2))]
        [else (C (add1 (* 3 n)))]))

いわゆるコラッツ問題の関数。 この関数はすべての引数に対して値を返すかどうかはまだ分かっていない。

A

(define (A n m)
  (cond [(zero? n) (add1 m)]
        [(zero? m) (A (sub1 n) 1)]
        [else (A (sub1 n)
                 (A n (sub1 m)))]))

アッカーマン関数。 コラッツ問題と違いこの関数は全関数（必ず値を返す）ことが分かっているらしい。 ただし、計算量が膨大なため計算機では計算に時間がかかり現実的な時間で計算できないことが多い。

will-stop?

与えられた関数が停止するかどうかを調べられる関数 will-stop? が存在するかどうかを問う思考実験。

(define (last-try x)
  (and (will-stop? last-try) (eternity x)))

will-stop? が存在すると仮定して、上記のような関数を定義する。

last-try が停止すると仮定した場合、(will-stop? last-try) は true となる。 すると、(eternity x) が評価され、結果として (last-try x) は (eternity x) によって停止しない関数となってしまい、仮定と矛盾する。

一方、last-try が停止しないと仮定した場合、(will-stop? last-try) は false となる。 (last-try x) は false となるため (eternity x) は評価されずに停止してしまうので、仮定と矛盾する。

結果として、will-stop? が存在するという仮定が間違いだったことが分かる。

いわゆる停止性問題。

Y コンビネータ

この章の残りは、リストの要素数を数える length を使って Y コンビネーターについて説明している。 長くなるので、それは次回に。

『超予測力』を読んで

『超予測力』を読みました。9 月の読書。

超予測力　不確実な時代の先を読む10カ条 (早川書房)

超予測者

『超予測力』は未来の予測についての本。

• 「ロシアは今後三ヶ月以内に新たなウクライナ領土を正式に併合するか」
• 「来年ユーロ圏を離脱する国はあるか」
• 「北朝鮮は今年度中に核兵器を使用するか」

このような未来の問いに対する「予測の正しさ」についての研究成果がまとめられている。 著者はこのような問いに対して予測をしてくれるボランティアを広く集め大規模な実験を行った。 その結果、一部の予測者は統計的にも有意に優れた予測をし、CIA などの諜報機関で働くプロの情報分析官すら上回る成績を残した。

筆者は彼等を「超予測者」と呼ぶ。

彼らは以下のような特徴を持っていた。

• 確率的にものごとを考える
• 予測をサブ問題に分割して考える
• 外側の視点と内側の視点を持っている
• 常に予測を検証し必要に応じてアップデートする
• 知的な誠実性を持っている

彼等の職業はばらばらで、専門分野も異なった。 筆者は超予測力は生まれつきの才能ではなく、その「やり方」や「考え方」に秘密があると述べる。 その方法を模倣することで、誰でも優れた予測力を身につけることができるのだ。

“専門家”と我々

一方、世間で予測を商売にしているアナリストや評論家などのいわゆる“専門家”は、超予測者とはならなかった。 予測の成績が振るわなかったのだ。 筆者がいうところによると「平均的な専門家の正確さは、チンパンジーが投げるダーツとだいたい同じぐらいである」ということだ。

新聞やテレビのニュース番組を見れば、専門家が今後どうなるか予測している。 ただほぼ例外なく、彼等がカメラの前にあっているのは予測力に優れているという何らかのお墨付きを得ているためではない。 予測の正確さが問題になることなどほとんどない。

そもそも評論家やコメンテーターに求められていることは、その正確性ではなく「予測に説得力があるかどうか」だと述べる。 人は説得力やつじつまが合うことを求める気質があり、正確性などは二の次になる場合が多い。

過去の予測は過去のニュースと同じで、すぐに忘れ去られ、評論家が過去の予測と現実に起きたこととを照合するよう求められることはまずない。 コメンテーターが明らかに持っておいる才能は、説得力ある節を確信持って語る能力であり、それだけで十分なのだ。

予測の消費者となる我々が予測の結果に対して無頓着であることに著者は警笛をならす。 経営者や政治家から我々に至るまで、有効性の確認されない薬は飲まないが、予測に関しては行商人が出してくる不老不死の薬と同じくらい怪しい者でもお金を払ってしまう。

予測が企業や政府など、社会にとって重要な位置付けであることは間違いない。 だからこそ、エビデンスを重視する科学的プロセスを取り入れて検証を行うことが社会にとって必要である。

余談

「人は説得力やつじつまが合うことを求める気質がある」という話は、カーネマンの『ファスト＆スロー』のシステム１とシステム２の話に繋がっていて、この本でもよく引用されている。

www.thekingsmuseum.info

以前、読んだことがある本がいくつか引用されていてこの分野への興味がまた沸いてきた。

『ワークシフト』を読んで

ワークシフトを読みました。8月の読書。

ワーク・シフト　─孤独と貧困から自由になる働き方の未来図<2025>

ワークシフトは2011年に書かれた本。 未来の働き方、具体的には 2025 年の働き方について予測し、そこで起こっているであろう＜シフト＞について書かれている。 筆者は働き方において、これから 3 つのシフトが起こるだろうと述べている。

1. ゼネラリストが評価される時代が終わり、高い専門性を持つスペシャリストが求められるようになる
2. 人的関係に基づいたコラボレーションによるイノベーションが重要になる
3. 経済的な成功と消費を求める画一的なキャリアゴールから、やりがいを求めるキャリアを築く必要がある

これら 3 つのシフトの具体例として筆者が想像した悲観的なストーリーと楽観的なストーリーが語られる。 悲観的なストーリーはこれらのシフトにうまく適応できなかった人々のストーリー、楽観的なストーリーはこれらのシフトにうまく適応できた人々のストーリだ。 そして、これらの想像上のストーリーを踏まえて 3 つのシフトをうまく乗りこなす術が書かれている。

ゼネラリストエンジニア

3 つのシフトはそれぞれ「確かにその通りだ」と感じたが、中でも特に気になったのが 1 つ目のシフト。

第一に、ゼネラリスト的な技能を尊ぶ常識を問い直すべきだ。 世界の50億人がインターネットにアクセスし、つながり合う世界が出現すれば、ゼネラリストの時代が幕を下ろすことは明らかだと、私には思える。

どうやらゼネラリストの価値は下がっていく一方のようだ。 反面、高い専門性を持つスペシャリストが求められるようになる。

省みて自分のキャリアはどうだろうか。 自分はプログラマー/エンジニアだと思っているが、世間的には技術職にあたるわけだしある程度の専門性がある職業だと思う。

でも、ソフトウェアエンジニアとして専門性の高いスペシャリストではないと最近感じる。 職業人生はそろそろ 10 年を迎えるが、何か一つの領域を長くやってきたわけではない。 Java の GUI を書き、C++ で HPC のミドルウェアを書き、Android もやったし Web のフロントエンドもそこそこやった。 サーバーサイドもそれなりにいじれるし、インフラ構築もそれなりにできる。 フルスタックエンジニアとポジティブに呼ぶこともできるが、端的にいえばソフトウェアエンジニアの世界でのゼネラリストなのかもしれない。

ゼネラリストの価値は下がっていく。 さて、自分のキャリアは大丈夫だろうか？ でも、この本にはこんなことも書かれている。

新しい時代には、本書で提唱する「専門技能の連続的習得」を通じて、自分の価値を高めていかなくてはならない。 未来にどういう技能と能力が評価されるかを知り、その分野で高度な技術を磨くと同時に状況に応じて柔軟に専門分野を変えることが求められるのだ。

専門性は高めていかなければならないが、専門領域も時代に合わせて変化させていく必要がある。 なるほど。専門性を維持しつつ求められている専門領域にキャリアを常にシフトさせていく、というのは説得力がある。

自分のキャリアをポジティブに捉えるのならば、ずっと「ソフトウェア開発」には携わってきたわけで、それを軸にして時代に合わせた技術を習得すればよいのではないか。 勉強を続けなければいけないことは大変といえば大変だけど、この仕事は今でも楽しいと思えるのでそれほど苦にはならなさそうだ（能力的な限界が先にくるかもしれないが）。 ただ、どの能力・技術が評価されるかを見極めるのはとても難しく、常にアンテナを高く立てておく必要はあるだろうし、経験を思い切って捨てるようなキャリアを選ぶ柔軟性も必要になってくるだろう。

そうやって、自分のキャリアを見つめ直した一冊だった。

『リーダブルコード』を読んで

『リーダブルコード』を読みました。7月の読書。

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

内容はかなり初歩的で特に目新しいことはなかったかな。 ただ、これを実践できてるかは別で、書かれていることを意識してコード書いていきたいと思った。

日々、コードはシンプルで分かりやすくなるように気をつけているけど、他者からの視点を意識するというのは少し抜け落ちてた気がする。

最近、まとまったコード書いてなくてあまり良くないな〜と思う今日この頃…

『エンジニアのためのマネジメントキャリアパス』を読んで

『エンジニアのためのマネジメントキャリアパス』を読みました。

エンジニアのためのマネジメントキャリアパス ―テックリードからCTOまでマネジメントスキル向上ガイド

「今年は毎月本を読む」と決めていたので五月中に読み終えたかったけど、五月中は忙しくて読み切ったのは六月。 けっこうボリュームがあったっていうのも一因だけど。

インターンのメンターから CTO まで

この本はその名の通りエンジニアのマネジメントキャリアパスについて書かれた本。 インターンの監督（メンター）から始まり、CTO に至るまでのエンジニアのマネジメント職について幅広く書いてある。 エンジニアの管理職のキャリアラダーを登り始めた人にはとても役に立つ本だろう。

印象的だったのは、エンジニア求められるスキルとはまったく違うスキルが必要だという点。 言われてみれば当然なのだが、テックリード、技術部長や CTO に至るまで、エンジニアの延長線上にあるように見えていて実はまったく違った役割が求められる。 その上、エンジニアとしての技術力は必要とされており（コードを直接書くことは求められていないが）、そのことがより一掃これらの職位のハードルを高くする。

それぞれの職位の役割がかなり詳細に書かれているので、その職位に就いたときには参考書としてとても役に立つ本だと思う。 仕事についてかなり細かく具体的に書いてあるし、ありがちな失敗や筆者自身の経験などが書かれていてとても親切だ。 たとえば、技術部長になって複数のチームを管理するようになったら「手一杯で何も成果があげられていないように感じるのが普通」というようなことも書かれている。 きっと新米の技術部長はこれを読んで少し安心するのではないだろうか。（逆に手一杯だと感じない場合は、仕事がちゃんとできてない可能性があるとも書かれているが）

いつか CTO になったら

最初に「読み切ったのは六月」と書いたけど、実はこの本全部読んでない。 後半の四割くらいは斜め読みして飛ばしてしまった。

とても細かく仕事について書いてあるけど、通して読むには記述が細かすぎて読み物として飽きてしまった。 翻訳の問題なのか、一部の文がすごく長ったらしいのもあって少し読みにくかった。 もう少しエッセンスを抜き出して書かれているとうれしかった。

より経営に近い職位については今の自分の立場とはレイヤが違うし、あまり頭に入ってこなかった。 それでも、そのレイヤの職位のあるべき姿みたいなのがぼんやりとは見えて勉強にはなった。 加えて、自分の上司やさらにその上の上司がどのような役割で働いて、どういう部下だったら嬉しいか？みたいなところを考えるきっかけになった。

自分がもし CTO になるようなことがあったらまたこの本に手を伸ばそうと思う。 今はそんな予定ぜんぜんないけど。

Cousera: Architecting with Google Kubernetes Engine Specialization の Course 1 & 2 を修了した

Architecting with Google Kubernetes Engine Specialization の前半を修了した。

• Course 1: Google Cloud Platform Fundamentals: Core Infrastructure
• Course 2: Architecting with Google Kubernetes Engine: Foundations

Course 1 は Kubernetes というよりも GCP の概要を演習つきで学習。 Course 2 は Container と Kubernetes の基礎、というか表面だけさらっと流した感じ。

正直、身になってる感じがあまりしないな。 演習もほとんど自分で考える要素がないし。 やっぱり自分でいろいろ試行錯誤して構築する経験を積まないと身につかない気がするな～。

残りは 2 コース。どうなることやら。