檜山正幸のキマイラ飼育記 メモ編 このページをアンテナに追加 RSSフィード

この「はてなダイアリー」は、
2019年1月18日の記事を最後に更新を停止します。
しかし、
「檜山正幸のキマイラ飼育記 メモ編」は保存され、新規ブログに移行します。
新しい「檜山正幸のキマイラ飼育記」と関連ブログについては、
こちらの記事 をごらんください。
連絡は hiyama{at}chimaira{dot}org へ。

2018-11-26(月)

基本スキルの確認と練習 (A6P5)

| 16:05 |

※この記事は「記事6 問題集5」

※ この練習問題は、特に予備知識を要求しません。どの時点(12月1日以前)でも出来ますし、早めにやればそれだけ有効だと思います。

今回のテーマは、記号の取り扱いに十分に慣れること。

我々がすることは、様々な記号を操作することと、その記号/操作の意味を考えることである。対象物である記号を自由に操れる技量が必要になる。トレーニングしよう。

既に知っている/出来る問題はスキップしてよい。ほとんどの人が知らない(であろう)事や、やったことがない(であろう)練習問題も含まれる。

[追記]繰り返し同じ注意をするが、この練習問題を全部やる必要はない。問題文を眺めて、「やったほうがいい」と判断したら選択的にやる。「分かった」と思ったらやめる。分かっていることを繰り返しやっても時間の無駄。[/追記]

内容:

  1. 記法の多様性への対応能力のトレーニング
  2. 演算子の書き方を変更する練習
  3. 書字方向/描画方向の多様性への対応能力のトレーニング
  4. 構文解析木の練習(推論の計算のための準備)
  5. セクション記法とポイントフリースタイル (追記あり 2018-11-28)
  6. 結合の記号を取り替える(追記あり 2018-11-27, 2018-11-28)

記法の多様性への対応能力のトレーニング

「書き方〈記法〉が変わると分からなくなってしまう」と感じる方は、次の“バカバカしくも手間がかかる練習”を、一度は愚直にやってみることをオススメする。ただし、「いくら何でももういいだろう」と思えばやめてよい。

記法の多様性への対応に問題がない方は、この手間のかかるトレーニングをあえてやる必要はない。

リスト(何かを並べたモノ)の書き方は多様である。書き方が変われば意味が変わる場合もあるが、意味が変わらないこともある。以下の72種の書き方は、違う意味で使われるかもしれないし、同じ意味で使われるかもしれない。

横方向に書く書き方 36種
  • 囲み括弧 4種: 丸括弧〈小括弧〉, 角括弧〈大括弧〉, 波括弧〈中括弧〉, 括弧なし
  • 区切り記号 3種: カンマ, 縦棒, なし(空白)
  • インデックスの記法 3種: 下付き添字, 角括弧, 丸括弧

例: (x1, x2, ..., xn), {x[0], x[1], ... x[n-1]}, (x(1) x(2) ... x(n)), (x1 | x2 | ... | xn)

縦方向に書く書き方 9種
  • 囲み括弧 3種: (縦長の)丸括弧, (縦長の)角括弧, 括弧なし
  • 区切り記号 1種: なし
  • インデックスの記法 3種: 下付き添字, 角括弧, 丸括弧
方向に無関係な書き方 27種
  • 囲み括弧 3種: 丸括弧, 角括弧, 波括弧
  • インデックスの記法 3種: 下付き添字, 角括弧, 丸括弧
  • インデックスの範囲指定 3種: 縦棒の左側にインデックス集合, 縦棒の右側にインデックス集合, 右下に小さくインデックス集合

以下は、リストをあるひとつの書き方で書いたものである。同じ(あるいは対応すると思われる)リストを、残り71種の書き方で書け。n..m は 整数の区間で n..m := {k∈Z | n ≦ k ≦ m} である。列挙しない書き方(方向に無関係な書き方)の場合、動くインデックスを表す変数は適当に選んでよい。

  1. (a1, a2, a3, a4, a5)
  2. {X[i]}i∈{1,2,3}
  3. [A[1] | A[2] | A[3]]
  4. (δ(x) | x∈1..4)
  5. [k∈0..2 | Ψk + Θk]
  6. u1, u2, ..., un

演算子の書き方を変更する練習

これも、「書き方〈記法〉が変わると分からなくなってしまう」と感じる方のための練習。中置、前置、後置の演算子の使い方に慣れていれば、このトレーニングをあえてやる必要はない。

演算子/関数に、様々な書き方があるのは、習慣と視認性だけの理由。理論的にはすべて一緒。

  • 中置方式
    • 標準的な中置方式 xfy
    • 左右下付き方式 xfy
  • 前置方式
    • 純ポーランド方式(区切り記号/囲み記号なし) fxy
    • 標準的な関数呼び出し方式=タプル・ポーランド方式 f(x, y)
  • 後置方式
    • 純・逆ポーランド方式(区切り記号/囲み記号なし) xyf
    • タプル逆ポーランド方式 (x, y)f
  • 特殊配置方式 演算子記号を使わずに位置関係で示す
    • 左右併置方式 xy
    • 右上付き方式 xy
    • 右下付き方式 xy
    • 左上付き方式 xy
    • 左下付き方式 xy
  • 括弧方式
    • 全体を囲む方式
      • 単一引数を囲む (x)
      • 複数引数を左右配置 (x, y)
      • 複数引数を上下配置 書けない
    • 片一方を囲む方式
      • 右を囲む x(y)
      • 左を囲む (x)y

意味はすべて一緒、何の違いもない、書き方の違いに惑わされるな!

特殊配置 → 中置

次の特殊配置方式(左右併置と右上付き)を含む式を、中置方式の演算子だけの式に書き換えよ。掛け算〈積 | 乗法〉の中置演算子記号は'×'、指数〈累乗 | ベキ〉の中置演算子記号は'^'〈ハット | サーカムフレックス | カレット | キャレット〉とする。

  1. ab
  2. aabbb
  3. a2b3
  4. a2x
  5. cba (TeXでレンダリングなら:  c^{b^a}
  6. x2y2 + 2xy
  7. ax2 + bx + c
  8. ex2 + y2
前置、後置

前問と同じ式を、純ポーランド記法に書き換えよ。次の表に従え。

中置二項演算子 前置演算子(の名前)
+ A
× M
^ E

同様に、純・逆ポーランド記法に書き換えよ。

関数呼び出し

前々問と同じ式を、関数呼び出し方式〈タプル・ポーランド記法〉だけの式に書き換えよ。次の表に従え。

中置二項演算子 関数名
+ sum
× prod
^ pow
関数呼び出し → 色々

関数 foo, bar, baz, hoge, piyo の呼び出しを次の演算子を使った演算子記法に直せ。

  • foo(x, y) = x◆y
  • bar(x, y) = (x | y)
  • baz(x) = x$
  • hoge(x, y) = (x)y
  • piyo(x) = 《x》

演算子の優先順位は:

  • 強:《x》, x$
  • 中: (x)y, (x | y)
  • 弱: ◆

以下に関数呼び出し記法の式(等式もある)。

  1. foo(1, piyo(3))
  2. piyo(foo(hoge(a, b), baz(bar(s, t))))
  3. hoge(hoge(a, b), c)
  4. hoge(a, hoge(b, c))
  5. foo(foo(a, b), c)
  6. foo(a, foo(b, c))
  7. foo(foo(a, b), c) = foo(a, foo(b, c))
  8. piyo(piyo(x)) = piyo(x)
  9. bar(x, y) = -bar(y, x)
  10. piyo(baz(w)) = w

書字方向/描画方向の多様性への対応能力のトレーニング

数理論理学では、縦方向のテキスト・図が多用される。書字方向/描画方向の多様性に戸惑う人は多い。縦方向の書字・描画に慣れる必要がある。

書字方向/描画方向の多様性への対応に問題がない方は、このトレーニングをあえてやる必要はない。

次は連立不等式である。

x + y ≦ 7
x - y < 3

ひとつの不等式は左から右に書く。この方向を「不等式の方向」と呼ぶことにする。複数の不等式は上から下に並べる。この方向を「併置の方向」と呼ぶことにする。

不等式の方向(不等式を書く方向)を変えると:

方向→
  x + y ≦ 7

方向←
  7 ≧ y  +  x

方向↓
  x
  +
  y
‖∧
  7

方向↑
  7
 ∨‖
  y
  +
  x

併置の方向(不等式を並べる方向)も同様に ↓, ↑, →, ← がある。不等式の方向と併置の方向の組み合わせの可能性は、→↓, →↑, ←↓, ←↑, ↓→, ↓←, ↑→, ↓← の8種がある。

最初の連立不等式をすべての方向で書け。また、以下の連立不等式も同様に、すべての方向で書け。

x + 3 ≦ 15
x ≧ 1
x + y < 3

x + y + z > 0
x2 + y2 + z2 ≦ 1
z ≧ 0

構文解析木の練習(推論の計算のための準備)

整数式の構文解析木では、非負整数、文字(整数を表す変数)と +, ×, - を含む式を扱った。

構文解析木は、文字や演算子記号の意味が分からなくても描ける。ここでは、;, ¥otimes, ¥oplus という3つの演算子記号を含む式を扱う。演算子記号の意味は不明のままでよい。

注意: ひょっとすると、檜山が語った ;, ¥otimes, ¥oplus の意味をあなたは知っているかもしれない。だが、この問題を解く上でその知識は不要だ。;, ¥otimes, ¥oplus は無意味な記号と思え。

;, ¥otimes, ¥oplus は、(+, ×と同様な)中置演算子記号として、優先順位は ; が一番高く、¥otimes がその次、¥oplus は優先順位が一番低い。

  • 例: f¥otimesg;h¥oplusj¥otimesk = (f¥otimes(g;h))¥oplus(j¥otimesk)

問題: 次の式の構文解析木を(標準的な描画法で)描け。

  1. a¥otimesb
  2. a¥otimesb ¥oplus c¥otimesd
  3. f;(g¥otimesh) ¥oplus F;G
  4. x;y;z ¥oplus z¥otimesw
  5. A;(B¥oplusC)¥otimesA¥otimesC;D
  6. a;(b¥otimesc);(d¥otimese¥otimesf) ¥oplus x;(y¥otimesz);(s¥otimest¥otimesu)

問題: 構文解析木は、習慣的に末端を下に描くが、末端が上になるような横棒記法の図で、横棒を二重線(デジタルテキストでは'='を並べる)として、前問の構文解析木を描け。

整数式の構文解析木では、-(マイナス記号)は引き算ではなくて反数を表す前置単項演算子であった。同様に、Λ(ギリシャ文字・大文字ラムダ)を前置単項演算子とする。;, ¥otimes, ¥oplus, Λ で、Λが一番優先順位が高いとする。

問題: 次の式の構文解析木を(標準的な描画法で)描け。

  1. Λ(f;g)
  2. Λf¥otimesΛ(g¥oplush)
  3. f¥otimesΛ(g¥oplush);F
  4. Λ((a¥otimesb);Λk;(s ¥oplus t))

問題: 末端が上になる横棒記法の図で、横棒を二重線として、前問の構文解析木を描け。

セクション記法とポイントフリースタイル

中置演算子 + , × などに対して、対応する関数名を準備することがある。例えば:

  • sum(x, y) = x + y
  • prod(x, y) = x×y

しかし、新しい名前を決めるのがめんどうなので、記号 +, × をそのまま使い、

  • (+)(x, y) = x + y
  • (×)(x, y) = x×y

とすることがある。つまり、「中置演算子を丸括弧で囲むと関数名として前置で使える」というルールである。(+1), (3×) などは次の意味で使う。

  • (+1)(x) = x + 1
  • (3×)(x) = 3×x

このルールは、ポイントフリースタイルのときに威力を発揮する。f(x, y, z) = ((x + y)×z)/5 という関数をポイントフリーで書くと:

  • f = ((+)¥otimesid);(×);(/5)

次の図も参照。

x  y    z
---- +  -- id
 x+y    z
 --------- ×
  (x+y)×z
  ------------- /5
  ((x+y)×z)/5

(+), (+1), (3×) のような書き方をセクション記法という(プログラミング言語Haskellの書き方)。

問題: 次の関数定義を、中置演算子 +, × からのセクション記法を使ったポイントフリースタイルで書け。id(何もしない)、dup(複製する)、swap(入れ替える)関数は使ってよい。もちろん、直列結合記号 ; と並列結合記号 ¥otimes も使う。式は変形せずにそのまま、書き方を変えるだけ。

  1. f(x) = x2
  2. f(x) = x2 + 10
  3. f(x) = x2 + 5x + 10
  4. f(x, y) = 2x + 3y + 1
  5. f(x, y) = x2 + xy
  6. f(x, y, z) = z2 + (2x + 3y + 1)z

[追記 date="2011-11-28"]

セクション記法は、中置二項演算子記号を関数名のように扱うためのものだが、前置単項演算子記号、後置単項演算子記号にも使ってみよう。

以下の式に登場する -(マイナス記号)は引き算ではなくて反数〈opposite〉を取る(符号を反転する)演算子だとする。後置の !(感嘆符)は階乗を意味する。

  • 3! = 3×2×1 = 6

単項演算子記号であるマイナス記号、感嘆符にもセクション記法が使えるとする。

  • (-)(5) = -5
  • (!)(3) = 3!

問題: 次の関数定義を、セクション記法を使ったポイントフリースタイルで書け。

  1. f(x) = (x + 1)!
  2. f(x) = (x + 1)! + x! + (x + -1)!
  3. f(x, y) = x! + -y
  4. f(x, y) = (x + -y)!
  5. f(x, y) = x!×y!
  6. f(x, y, z) = x!(y + -1)!(z + -2)!

[/追記]

結合の記号を取り替える

記号の意味を強く固定せずに、柔軟に運用することが重要である。セクション記法を使ったポイントフリースタイル式では、もともと在った演算子記号は(セクション記法になって)残る。さらに、関数の直列結合の演算子記号 ; と並列結合の演算子記号 ¥otimes が含まれる式になる。例: ((+)¥otimesid);(×);(/5)

もともとの演算子記号が ;, ¥otimes, ¥oplus のとき、これをセクション記法を使ったポイントフリースタイル式に直そうと思うと、演算子記号がかち合う*1。このような場合は、直列結合の演算子記号と並列結合の演算子記号を変更する。例えば:

  • 直列結合の演算子記号は *
  • 並列結合の演算子記号は ¥odot

問題: 上記の演算子記号 *, ¥odot を使って、次の関数定義をセクション記法を使ったポイントフリースタイルで書け。いつものように、id, dup, swap は使ってよい。

  1. f(x) = (x¥otimesx);x
  2. F(x, y) = a¥otimesx ¥oplus b¥otimesy
  3. ξ(f, g, h) = f;(g¥otimesh) ¥oplus f;G
  4. g(x, y, z) = x;y;z ¥oplus z¥otimesw
  5. Ω(a, b, f, g) = a;(f¥oplusf)¥otimes(g¥oplusg);b
  6. k(α, β, γ, δ, ε) = α;((β¥oplusβ)¥otimes¥oplusγ));(δ¥otimesδ);ε

[追記 date="2018-11-27"]

記号の選択は、まったく恣意的・無根拠に行われるものである。記号の意味を強く固定するがマズイのは、このような恣意的・無根拠な変更に対する反応が出来にくくなるからである。次のように記号の選択をしたとして、

  • 直列結合の演算子記号は |(縦棒)
  • 並列結合の演算子記号は &(アンド記号)

すぐ上の問題を再度やってみよ。つまり、

問題: 上記の演算子記号 |, & を使って、次の(上にある)関数定義をセクション記法を使ったポイントフリースタイルで書け。いつものように、id, dup, swap は使ってよい。

[/追記]

[さらに追記 date="2018-11-28"]

くどいのだが、記号と意味の結び付きを柔軟に変更しながら対処する能力は、極めて重要なので、同様な練習をもうひとつ。

もともとの演算子記号が ;, ¥otimes, ¥oplus であるなら、通常の算術演算子 ×, + は使われてない。次のように約束する。

  • 直列結合の演算子記号は × (掛け算記号)
  • 並列結合の演算子記号は + (足し算記号)

問題: 上記の演算子記号 ×, + を使って、上にある関数定義をセクション記法を使ったポイントフリースタイルで書け。いつものように、id, dup, swap は使ってよい。

使える記号の数が足りないので、既によく使われている記号を、意味を変えて流用する(オーバーロードする)事態は頻繁に起きる。既存の意味をサッと忘れて、新しい意味ですぐさま使える必要がある。

[/さらに追記]

*1:丸括弧で囲まれた記号と裸の記号で区別できる、のは事実だが、それで区別するのは辛すぎる。