週末デッドエンド

勉強と日記と怪文書

2021-06-02 Wed .—プログラミング in OCaml

プログラミング 日記 プログラミング in OCaml OCaml

勉強

プログラミング in OCaml (–3.5 再帰関数まで)

再帰関数難しい。練習問題は明日以降やる。

let 定義

# let one = 1;;
val one : int = 1
# let one = "One";;
val one : string = 1

この場合、one の値が 1 から "One" に更新されたわけではなく、後から行った変数束縛により、前の束縛が隠されて見えなくなったと考えます（そもそも更新されたと考えると、ふたつの one = ... の右辺の方が一致していないので変ですね）。

がわかりにくい。C言語などと違ってメモリ領域に名前をつけているわけではなく、値に名前をつけているので

# one;;

とするときはOCamlは直近のoneをチェックして

- : string = "One";

と出力する。「束縛が隠れて見えなくなった」という奥歯に物が挟まったような表現の意味は、あとで変数のスコープや環境の話をするときにわかる。

let 式

let 関数名 パラメータ = 式で関数を定義できる。if式 if 条件 then 式　else 式も式なので関数定義の式の部分に書いていい。

let 変数 = 式1 in 式2

演算の評価は左結合的になってる。

  1. 式1を評価
  2. let 変数 = 式1の値と束縛する。
  3. 式を評価

という順。計算の途中結果に名前をつけている(let 式)。

let 定義とlet 式は名前がややこしいけど異なるので注意。 - let 定義で定義された変数は大域変数(プログラムのどこでも使える)。 - let 式内のinのあとの変数は局所変数。有効範囲(スコープ)はinのあとの式だけ。

変数のスコープ

変数と値の組(どの変数に何の値が束縛されているかの一覧表)がメモリ上に(場所は見えないけど)保存されている。この一覧表を環境と呼ぶ。 let x = e1 in e2のようなlet 式では、e2の式を評価する一時的な間だけxの束縛が環境に追加される。

関数の仮引数を実引数に束縛するときの環境は、関数を定義した時点での環境。

let pi = 3.1415926535;;
let area_c r = r *. r *. pi;; (* pi の値が 3.1415...に束縛される *)
let pi = 1;; (* pi の値は 1 に束縛される *)
let area = area_c 2.0;; (* area_c 2.0を評価する時の pi の値は 3.1415... *)

これ以後にpiを使った関数を定義するとpiの値は1になる。

関数定義時点ではなく、関数を呼び出したときの環境を参照するような言語もあるので注意。

練習問題3.5

トップレベルでの以下の2種類の宣言の違いは何か？(e2がxを含む場合を考えよ)

let x = e1 and y = e2;;
let x = e1 let y = e2;;

ヒントを参考にコンパイルしてみる。

# let x = 2 and y = (x + 2);;
Error: Unbound value x

# let x = 2 let y = (x + 2);;
val x : int = 2
val y : int = 4

これはなぜか。

前者の同時束縛について

3.3節の最後に同時束縛の記述がある。

同時定義の場合、=の右辺はそこで宣言されるどの変数の有効範囲にも入りません。

つまり、let x = 2 and y = (x + 2)のような場合、and以下のy = (x + 2)のxはまだ束縛されていないので、束縛されていないというエラーが出る。

後者の束縛について

また、2.3節の最後に、

複数のlet定義はその境目がはっきりしている（次のletが来る直前で切れる）ので、間に;;をつけずに並べることができます。

# let pi : float = 3.1415926535
  let e = 2.718281828;;
val pi : float = 3.1415926535
val e : float = 2.718281828

とあるのに注意しよう。つまり、let x = 2 let y = x + 2;;の場合、最初のlet x = 2でxの値が束縛された後に、let y = x + 2となっているので普通に走る。

3.4.3 組を用いた関数

# let average p = (* 仮引数 p *)
    let (x, y) = p in (* 仮引数 p の値を (x, y) に束縛するので、 p は組でなくてはいけない  *)
    (x +. y) /. 2.0;; (* 与えられた引数 (x, y) を使って相加平均を計算する *)

averageは、組を引数とする1引数関数。

数学で例えると、2次元ベクトル v = (x, y) \in \mathbb{R}^2 の絶対値を取る関数 f を、2変数関数ではなくベクトルの関数 f \colon \mathbb{R}^2 \to \mathbb{R} とみなすのと同じ。

再帰関数

recをつけないとエラーが出る。

# let fact n =
  if n = 1 then 1 else fact (n - 1) * n;; (* rec をつけないと = 以後の fact は束縛されない *)
Error: Unbound value fact
フィボナッチ数列fib_pair

n 番目のフィボナッチ数列を計算する関数fib_pairを定義しているが、何をしているかよくわからないので追跡する。

フィボナッチ数列は F_n = F_{n - 1} + F_{n - 2}と計算できる。つまり、

  • 1個前と2個前の項がわかれば計算できる( F_n \leftarrow (F_{n - 1}, F_{n - 2}) )。
    • 1個前の項は、2個前と3個前の項がわかれば計算できる。( F_{n - 1} \leftarrow (F_{n - 2},F_{n - 3}) )
    • 2個前の項は、3個前と4個前の項がわかれば計算できる。( F_{n - 2} \leftarrow (F_{n - 3},F_{n - 4}) )

2数の組から1数への関数が再帰的に定義されるけど、結果を繰り返し用いたいので2数の組から2数の組への関数として書こう。

\begin{aligned} (F_n, F_{n-1}) &= (F_{n - 1} + F_{n - 2}, F_{n - 1}) \\ & \longleftarrow (F_{n - 1}, F_{n - 2}) = (F_{n - 2} + F_{n - 3}, F_{n - 2}) \\ & \quad \longleftarrow (F_{n - 2}, F_{n - 3}) = (F_{n - 3} + F_{n - 4}, F_{n - 3}) \\ & \qquad \longleftarrow (F_{n - 3}, F_{n - 4}) = (F_{n - 4} + F_{n - 5}, F_{n - 4}) \\ & \quad \qquad = \cdots \end{aligned}

という列ができる。わかりそう。

例えば (F_{n - 1}, F_{n - 2}) \longrightarrow (F_{n - 1} + F_{n - 2}, F_{n - 1}) に注目して i = F_{n - 1} , j = F_{n - 2} と置き換えると (i, j) = (i + j, i) という計算を繰り返し行っていることがわかる。

let rec fib_pair n =
    if n = 1 then (1, 0) (* 初項を設定 *)
    else
        let (i, j) = fib_pair (n - 1) in (* 前の項 fib_pair (n - 1) の組を (i, j) とおいて、 *)
        (i + j, i);; (* (i, j) --> (i + j, i) を置き換える計算をする *)

という関数をつくればよい。

実際にどうなってるか。

fib_pair 2を追跡してみる。

fib_pair 2 --> if 2 = 1 then (1, 0) else let (i, j) = fib_pair (2 - 1) in (i + j, j)
--> let (i, j) = fib_pair 1 in (i + j, i)
--> let (i, j) = (1, 0) in (i + j, i)
--> (1 + 0, 1)
--> (1, 1)

この結果を使ってfib_pair 3を追跡する。

fib_pair 3 --> if 3 = 1 then (1, 0) else let (i, j) = fib_pair (3 - 1) in (i + j, j)
--> let (i, j) = fib_pair 2 in (i + j, j)
--> let (i, j) = (1, 1) in (i + j, j)
--> (2, 1)

処理の途中でfib (n - 1) = (13, 8)のとき。

let (i, j) = (13, 8) in (i + j, i)
--> (13 + 8, 13)
--> (21, 13)

次の項が出てきた。

末尾呼び出し

let rec fact n =
    if n = 1 then 1 else fact (n - 1) * n;;

と定義している。関数定義の一番最後のelse fact (n - 1) * n は関数を適用する順に書くとelse * (fact (n -1), n)となる。再帰的に呼び出されるfact (n - 1)(再帰呼び出しという)は関数*の引数。

このとき、「再帰呼び出しの後で*を適用する」という後でやるべき作業をスタックに記録してから再帰呼び出しをする。

一方、

let fact n =
    let rec iterfact (i, res) =
        if i = n + 1 then res
        else iterfact (i + 1, res * i)
    in
    iterfact (1, 1);;

では再帰呼び出しの式がelse節全体で、このif式が関数本体。したがって、i = nのときは再帰呼び出しの値に何も手を付けずに(*をスタックに詰んだりせずに)関数の返り値になる。このように本体中の計算の最後にある関数呼び出しを末尾呼び出しといい、再帰呼び出しがすべて末尾呼び出しである再帰関数を末尾再帰的(tail recursive)という。

日記

断酒22日目。私が神だ。

  • VSCodeでC++のデバッガと戦っていたけどよくわからなかった。

  • C言語みたいにメモリのアドレスを出力したくて(C言語のprintf(%p, &one)みたいなことがしたい)調べたけど、OCamlは低レベルなことに向いてないのか、難しい記事ばっかりで理解できなかった。

  • 電子書籍を読むのにKindle for Macというアプリを使っているのが、とにかく使いづらい。Kindle Paperwhiteを買わせようとしていると思うほど使いづらい。
    例えば、リンクをクリックしようとすると、その文字がドラッグされてしまうので、クリックすらできない。というか文字以外の場所をクリックしてもなぜか文字列がドラッグされて「メモを追加」とかポップアップする。他の場所をクリックしても同じように文字列がドラッグされるので、ポップアップを消すこともできない。ページも満足にめくれない。

  • 再帰関数が難しい。小さい n のときどう走るかをいくつか追跡するのがよさそう。