13

プログラムの骨組み（の主なパターン）

1 イベント駆動

初級で学ぶこと：名前のある関数を呼び出す
```
function abc() {
   console.log("hello")
}
SetTimeout(abc,5000)          // ５秒後に発火させる
// 訂正 最初、SetInterval(abc,5000) と書きましたが誤り。
//    setInterval は５秒おきに繰返し発火するので
//    （これらの遅延関数は目的に応じて適宜使い分けて下さい）
```
- HTMLのタグ（＝要素）に onClick 属性を付与したり、 JavaScript側から get した要素に addEventListener などのメソッドでイベントに対する動作を記述したり、様々な使い方が用意されている。
- 上記のコードでは、 SetTimeout('console.log("hello")',5000) のようにコード（を表す文字列）を直接渡すこともできる（が、安全性や安定性の観点から、初心者以外に好んで使う人はいない）。

中級以降の常識：　手続きをコードの形で（文字列ではなく無名関数として）渡す

SetTimeout(function(){
   console.log("hello")
},5000)
// または
SetTimeout(()=>{
   console.log("hello")
},5000)
// 或いは、無名関数の中の式が１つならば
SetTimeout(()=>console.log("hello"),5000) // ブレース省略

2 範囲を指定してループ変数を変化させる

1 から 10 までの整数を（この順に）出力させる：
```
for(let i=1 ; i<=10 ; i++) console.log(i)
```
- for の後ろのカッコ内にセミコロンで区切って置かれた３つの式は、
  1. ループ変数の宣言と初期値設定。
  2. ループの中身の実行が継続されるための（毎回冒頭で検査される）条件式。
  3. 次の周回に入る（ループの中身の先頭部に制御を戻す）直前に実行される、変化を起こすための式（ループ変数の値を少し変化させることが多い）。
- このように（読みやすさを犠牲にして）細かい指定をできるので自由度が高い。
- が（追々述べていくが）最近のプログラミングでは好まれない（while を使った繰り返しも同様）。
範囲を指定して繰り返させる（いくつかの言語での実例）
- 様々な言語の入門紹介資料はプログラミング言語論やネットワークプログラミングのページに若干用意してある。
```
for i in range(1,11): print(i)   # pythonでは範囲の上限値が範囲に含まれない
```
```
for i in 1..10 do puts i end # do ～ end の代わりに { ～ } で囲んでもいい
```
- この { ～ } （do ～ end でも同様）で囲んだものを Rubyでは「ブロック」と呼び、無名関数に似た使い方をしている。
```
for i in [1..10] 
   console.log i
```
```
mapM print [1..10]
```

3. 繰り返しのための道具：　メソッドと内包表記

範囲、またはそれを実体化した（データが実際に並んだ）配列やリスト、を繰り返しのガイドレールのように扱い、

map や each系のメソッド（または関数）を使って繰り返させる（これもいくつかの言語で紹介する）
あわせて、２乗の数列を得る書き方（map または内包表記）も併記しておく。

(1..10).each{|i|puts i}
(1..10).map{|i|i**2}      # ２乗の数列
# rubyには内包表記はない

# python では each系のメソッドはなく、繰り返し動作は for を使う
list(map(lambda i:i**2, range(1,11)))
[i**2 for i in range(1,11)]

python の糖衣言語 coconut の例も

range(1,11)|>map$(i->i**2)|>list
# 内包表記はpythonと同じ

pythonでは範囲の第２引数は範囲に含まれない（ので11を指定した）。

map (^2) [1..10]
[i^2|i<-[1..10]]

たとえば paiza で実行するなら、

main=print ( map (^2) [1..10] )
-- または
main=print $ map (^2) [1..10]

のように呼び出す。

javascriptの場合は、範囲を表すオブジェクトがないので、配列を生成する独自の記法を出発点にすることになる。

[...Array(10).keys()]     // => 0 ～ 9の配列
// 1 ～ 10 にするには以下のような方法がある
[...Array(10).keys()].map(i=>i+1)
[...Array(11).keys()].slice(1)  
// 
[...Array(11).keys()].slice(1).map(i=>i**2)

4. 再帰

4.1 再帰の例（メソッドでも書けるケース）

階乗
```
function fact(n) {
  return n>1 ? n*fact(n-1) : 1
}
```
- 関数の中で同じ名前の関数を呼び出している。これが再帰。
- 再帰関数の中では必ず条件分岐が行われ、
  - 道半ば（この先がある）ならば再帰呼び出しを行い、
  - 末端に達した（条件が満たされた）なら、呼び出さない（で何か値を返す）。
- 再帰呼び出しでは引数に少し変化が起きる筈
  - でないと同じ呼び出しを無限に堂々めぐりすることになる。
  - fact の場合は n を１つ減らしている（１つ減らした値を渡して再帰呼び出し）。
- その変化の果てに必ず終了条件（末端となる条件）が満たされる場面に至る筈。
  - fact の場合は n が１以下になる。
  - 変化の方向と条件式が適切でないと無限再帰になる（大抵の言語ではスタックオーバーフローで停止する筈だが）。
  - なお、上記の式は reduceメソッドを使っても書ける
```
[...Array(n+1).keys()].slice(1).reduce((a,b)=>a*b)
```

4.2 末尾再帰

前の定義では、

ある呼び出しの実行（フレームと呼んでおく）の中で、
そこから呼び出した実行（親子関係になぞらえると「子フレーム」に相当する）から戻ってくる値（上の例では fact(n-1))に対して、
その値を使ったさらなる演算（ここでは n * その値 の乗算）を行ってから
当該フレームの値として呼び出し元（親フレーム）に返している。

そのため、子フレームが終了するまでその親フレームは処理の途中で待機しておく必要がある。

処理系の中ではその待機中の状況がスタックと呼ばれる記憶域に「積み上げられ」て保存されている。そのため、無限に再帰呼び出しが行われるとそのスタックの記憶域が足りなくて「スタックオーバーフロー」が発生する。

子フレームの値を（その後の演算をせずに）そのまま自フレームの値として返すようにプログラムすると、

待機しない → 待機中の状況をスタックに保存しなくていい → という原理で再帰呼び出しの実行が行われるよう工夫されている処理系も増えてきている。

前節のコードを末尾再帰に直すと以下のようになる。

function fact_t(n,r=1) { // 返すべき値の種 r の初期値は第２引数の省略値として渡す
    return n>1 ? fact_t(n-1,r*n) : r
} 
// または
function fact_t2(n) {       // 内部関数として末尾再帰関数を用意する
    function fact_t2_i(n,r) {
        return n>1 ? fact_t2_i(n-1,r*n) : r
    }
    return fact_t2_i(n,1)
}

4.3 二進十進変換

'100101001' などの文字列（以下の説明では変数 s とする）が与えられたときに、これを（２進数だと解釈して） Integer型の数値に変換することを考える。

このときは末尾再帰で文字列の先頭から見ていくと書きやすい
```
function b2d(s,r=0){
   return s.length>0 ? b2d(s.slice(1),r*2+(s[0]-0)) : r
} 
```
末尾再帰でない書き方だと文字列の末尾から見ていく書き方になる（コードは略）。
これは配列を使っても書ける
```
s.split('').reduce((r,c)=>r*2+(c-0),0)
```

4.3 再帰の例（メソッドでは書きにくいケース）

十進二進変換
- 二進十進変換のときには出発点として利用できる「並んでいるもの」（ここでは０，１の文字）があったが、今回はそれがないので、配列に対するメソッド呼び出しでは書きづらい。
```
function d2b(n) {
  return n>0? d2b(~~(n/2))+'01'[n%2] : ""
}
// または末尾再帰で
function d2b_t(n,r="") {
  return n>0? d2b_t(~~(n/2),'01'[n%2]+r) : r
}
```
フィボナッチ数
```
function fib(n){
  return n<2? 1 : fib(n-1)+fib(n-2)
}
```
たとえばこれを、 [...Array(n).keys()].map(fib) のように呼んでみよう。（n に適当な数を入れる。ただしｎが大きいと戻ってこなくなるのでご注意）。
- フィボナッチ数については（計算量増大の話や、それに対抗する方法とあわせて） 2019年度に行った「プログラミング小手調べ」の「例題３」でも言及しています。
マージソート
- 大枠
```
function mSort(ary) {
  // 再帰を前提にしましょう 詳細はこれから。

} // 与えられた配列を降順に並び替えた配列を返すことにしておく
```
- ストーリー：
  - mSort では配列 ary を２つの部分配列に分け、
  - それぞれを（再帰呼び出しで）ソートしたものを
  - mMrg （あとで作る関数）に渡して、１本の（ソートされた）配列にまとめる。
- 末端条件：
  - ary の長さが１以下になれば、これ以上分割する必要はないし、ソートもされているとみなすことができる。
    
    ので、ary をそのまま返せばいい。
- 末尾再帰について：
  - mSort は　再帰呼び出しで得た配列を２つ、このあとで mMrgに渡す必要があるので、末尾再帰にはならない（できない）。
  - ただ、この関数は、子フレームに渡すデータの長さがもとの半分（再帰呼び出し毎に要素が１つずつ減っていくタイプでなない）ので、ネスティングの深度は深くならない（ので末尾再帰を考える必要もない）
- マージ：こんな枠組みになる
```
function mMrg(a1,a2) {
  // これも再帰を前提にする（末尾再帰にできる）

} // １本にまとまった（ソート済の）配列を返すことになる
```
  - a1[0]とa2[0] を比べ、
  - 前者が大きければ a1と a2.slice(1) を子フレームに渡し（再帰）、
  - 後者が大きければ a2.slice(1) とa2 を子フレームに渡す。
  - いずれかの長さが０ならば、そうじゃない方をそのまま値として返せばいい。
    - どちらも長さ０という可能性はたぶんないが、そうであっても空配列を返しても問題はない筈。

ということを考えてプログラムを作ってみましょう。（サンプルへのリンクを前回資料末尾に置きました。)

（参考）このコードを書くにあたって私が行った検索（の主なもの）：
- 「javascript 整数除算」 ← これはこの言語な風変わりな点の１つ
- 「javascript 配列連結」 ← ここはわりとシンプル（でも用語がやや混乱ぎみ。「結合」のほうがいいかも）
JavaScript版は前回資料に掲載していなかったので、ここに置いときます（いろいろ考えてみてから答え合わせ的にコードを読んでもらうといいでしょう）。