マイクを持てば酔っぱらい

~カラオケをこよなく愛するITシステムエンジニアのブログ~

2019年09月

フィギュアスケートスコア計算説明図 2019/20シーズン版

 スコアの算出方法を1枚の図にまとめた「フィギュアスケートスコア計算説明図」の今シーズン版です。

FigureSkateScoreStructureV2.1

 昨シーズンとほぼ変わっていません。変更点は,ジャンプの回転不足またはエッジ違反があった場合の減点がやや緩和されたことです。

  • 昨シーズン: 基本点数 × 0.75 (25% 減点)
  • 今シーズン: 基本点数 × 0.820% 減点)

 回転不足とエッジ違反が同時に発生したジャンプの点数は,基本点数の 0.6 倍で,これは昨シーズンと変わりません。減点が緩和されるのは,回転不足だけ,エッジ違反だけという場合です。

 以下,説明図に沿ったスコア算出ロジックを説明します。 (2018/19シーズンに掲載したものを再掲)


 スコアの骨格は,説明図の右側に縦に書かれた式で表されます。

  総得点 = 技術点 + 演技構成点 - 減点

 以下,この3つがどのように算出されるかを,説明図の言葉を追いながら説明していきます。図中記号 A を,以下 [A] と表記します。

◆技術点

 技術点は,ジャンプ,スピン,ステップといった個々の技(これを「要素」と呼ぶ)の難易度や出来ばえを評価したスコアです。

[A] 基本点数

 技術点は,要素を1つずつ点数付けし,それらを合計したものです。要素の種類やレベルは審判が判定しますが,各要素の点数(説明図では「基本点数」と呼ぶ。筆者造語)は,その難易度に応じてあらかじめ定められています。各要素の基本点数を図の左側に記しています。

 ジャンプは,回転数踏み切り方の種類(記号で書くと A,Lz,F,Lo,S,T)によって点数が決まります。連続ジャンプ(コンビネーションジャンプ)は,各々のジャンプの点数を合計した点数になります。ジャンプシークエンスとは,あるジャンプの後すぐにアクセルジャンプを飛ぶもので,各々のジャンプの合計の 0.8 倍の点数が与えられます。

 スピンの点数は,スピンの種類付加要素レベルによって決まります。付加要素とは,スピンに入る際に跳ねるような動作を入れる「フライング」,スピンの途中で軸足を換える「足換え」のことを指し,1つのスピンでその両方が実施されることもあります。レベルは,その定義が決められており,実施されたスピンに対して審判がレベルを判定します。

 ステップは,レベルによって点数が変わります。レベルの定義が決められており,審判がレベルを判定する点はスピンと同様です。

 振付の自由な表現要素である「コレオグラフィックシークエンス」(略称:コレオ)は基本点数が固定で,出来ばえ評価が選手によって変わります。

 通常は,基本点数がそのまま基礎点[F]になります。ただし,以下のようなケースでは基礎点が上下します。

[B] ペナルティ

回転不足(アンダーローテーション:Under Rotation)
 正しい回転より90度(角度)以上回転が少ない場合,回転不足と判定され基礎点[F]が本来の点数の 0.8 倍に減点されます。ちなみに,180度以上少ないとダウングレード(Down Grade)といって1回転少ないジャンプの基礎点になります。

《例: 3A (トリプルアクセルジャンプ)》

  • 回転OK: 8.0 点
  • 回転不足: 6.4 点 (= 8.0 × 0.8)
  • ダウングレード: 3.3 点 (= 2A の点数)

エッジ違反(エッジエラー:Edge Error,エッジ誤り:Wrong Edge)
 ジャンプの踏み切りの際に,Lz(ルッツ)はスケートの刃を体の外側に倒す(アウトサイドエッジ),F(フリップ)は体の内側に倒す(インサイドエッジ)のが正しい飛び方です。これらの体の倒し方(エッジの使い方)をにしてしまうと基礎点[F]が本来の点数の 0.8 倍に減点されます。

回転不足とエッジ違反が同時に発生した場合は,基礎点[F]が本来の点数の 0.6 倍に減点されます。

【改定点】 昨シーズンはこれらの減点は 0.75 倍でしたが,やや緩和されました。

[D] ジャンプ後半実施

 演技時間の後半に実施するジャンプのうち,SP(Short Program,ショートプログラム)では最後の1回FS(Free Skating,フリースケーティング)では最後の3回に対して,基礎点[F]1.1 倍に加点されます。このボーナスはジャンプにだけ適用されます。

《例》 3A: 8.8 点 (=8.0×1.1)

[E] 同種単独ジャンプ重複
 FSでは,3回転以上の同じジャンプを2回飛ぶ場合,少なくとも1回は連続ジャンプにするというルールがあります。しかし,転倒や着氷の乱れ等で2回とも単独ジャンプになってしまった場合,2回目のジャンプの基礎点[F]0.7 倍に減点されるという,ペナルティの一種です。

[F] 基礎点(BV: Base Value)

 各要素の難易度をベースに,実施状況(上述の後半ボーナスやペナルティ)を加味したスコア。算出方法は,上述[A][E]をご参照ください。

[G][H][I] 出来ばえGOE: Grade Of Execution)

 各要素がどのくらい良い出来だったかを評価してスコアに反映します。9人の審判が各々 +5 ~ -5 の11段階で評価[G]し,最高点と最低点を除外した7人評価点を平均[H]し,評価±1ごとに 10% ずつ基礎点を加減するように出来ばえ点[I]を算出します。GOE 評価平均値が +5 ならば +50%,-5 ならば -50% となります。ただし,コレオは例外で,基本点数 3.0 に対して出来ばえ点は最大 ±2.5 となっています。

《出来ばえ点の計算例》

  • 評価対象要素: 3Lz(トリプルルッツジャンプ)
  • 審判9人の出来ばえ評価[G]3, 3, 3, 2, 2, 2, 1, 1, 0
  • 最高点(3)と最低点(0)を除外: 3, 3, 3, 2, 2, 2, 1, 1, 0
  • 平均点[H] = (3×2 + 2×3 + 1×2) / 7 = 2
  • 3Lz の点数[C]5.9 (回転不足,エッジ違反なし)
     ⇒ 出来ばえ点[I] = 5.9 × (2 × 0.1) = 1.18
 GOE という言葉は,+5 ~ -5 の評価点[G]を意味する場合と,出来ばえ点[I]を意味する場合があるので要注意です。Grade という言葉の意味からすると前者が真の GOE で,後者は「GOE による加点/減点」と呼ぶべきと考え,この説明図では前者を GOE としています。

 出来ばえ点がどの値に基づいて計算されるかについて,よく「基礎点の最大 50% の出来ばえ点が付く」というような説明がされますが,「基礎点」という言葉もまた,文脈によっていくつかの意味で使われるので,正確な点数を考えるときは要注意です。

  • 各要素に元々付与されている点数(説明図では「基本点数」[A]と呼ぶ。筆者造語)に,回転不足やエッジ違反の減点[B]を加味した点数(説明図では「実施点[C]と呼ぶ。筆者造語)が,出来ばえ点の算出に用いられます。すなわち,回転不足やエッジ違反があると,プラスの GOE でも出来ばえ点が伸び悩むことになります。
  • ジャンプの後半実施ボーナス[D]や,同種単独ジャンプ重複による減点[E]は,出来ばえ点には影響しません。これらは基礎点[F]の算出にのみ用いられます。
  • 説明図において「基礎点」という言葉は,要素の難易度をベースに,実施状況(後半ボーナスやペナルティ)を加味した,出来ばえ点を加算する直前のスコア[F]を意味します。説明図における「基本点数」や「実施点」のことを,試合中継やニュースで「基礎点」と表現される場合が多々ありますので,文脈に応じた解釈が必要です。

[J][K] 技術点TES: Technical Element Score)

 基礎点[F]出来栄え点[I]加算したものが各要素の技術点[J]で,これを全要素分合計したものが,演技全体の技術点[K]です。シングル競技では,SPの要素は7つ(ジャンプ3,スピン3,ステップ1),FSの要素は12個(ジャンプ7,スピン3,ステップ1,コレオ1)です。

◆演技構成点

 演技構成点は,演技全体の完成度を評価したスコアです。以下に説明する5つの評価観点(コンポーネント)があり,これらはよく,ファイブコンポーネンツ(5 components),あるいは単に「コンポーネンツ」と呼ばれています。

  1. Skating Skill(略記記号 SS)… スケート技術
     スケーティング全体の正確さと確実さを,下記の観点で評価します。
    ・ 深いエッジ,ステップおよびターンの利用
    ・ バランス,リズミカルな膝の動き,足運びの正確さ
    ・ 流れと滑り
    ・ パワー,スピード,加減速の多様な利用
    ・ あらゆる方向へのスケーティングの利用
    ・ 片足でのスケーティングの利用
  2. Transitions(同 TR)… つなぎ
     すべての要素をつなぐ,複雑なフットワーク,ポジション,動作が多様であることと,これらをはっきりとした目的を持って用いることを,「ある要素から別の要素への動作の連続性」「多様さ」「難しさ」「質」といった観点で評価します。
  3. Performance(同 PE)… パフォーマンス
     
    音楽と構成の意図を伝える際にスケーターの体の動き,感情の表現,知性の表出が十分にあることを,下記の観点で評価します。
    ・ 体の動き,感情の表現,知性の表出および投射
    ・ 身のこなしと動作の明確さ
    ・ 動作とエネルギーの多様さとめりはり
    ・ 個性/人柄
  4. Composition(同 CO)… 構成
     計画的,発展的,独創的な各種動作の構成に関して,下記の観点で評価します。
    ・ 目的(アイデア,コンセプト,ビジョン,雰囲気)
    ・ パターン/氷面の十分な利用
    ・ 空間の多次元的な利用と動作のデザイン
    ・ フレージングと形式(動作および部分が音楽のフレーズに合っていること)
    ・ 構成の独創性
  5. Interpretation of the Music(同 IN)… 音楽解釈
     音楽のリズム,特徴,内容を個性的に,創造的に,偽りなく,氷上の演技へ移し換えることを,下記の観点で評価します。
    ・ 音楽(タイミング)にあった動作とステップ
    ・ 音楽の特徴/感情の表現,およびはっきりと識別できるときにはリズムの表現
    ・ 音楽の細部とニュアンスを反映するフィネス(スケーターによる音楽の細部とニュアンスの動作を通じた技巧的かつ洗練された取り扱い)の利用

 上記説明はやや格式張っていますが,下線を引いた箇所と箇条書きの箇所は,国際スケート連盟(ISU)発行の「技術規程」の翻訳(日本スケート連盟発行)の表現を引用しています。

[L] 評価点

 上記5つの項目各々について,10点満点0.25点刻みで9人の審判(GOE の審判と同じ人)が採点します。

[M] 演技構成点(項目別)

 最高点と最低点を除外した7人評価点[L]平均した点数。テレビや新聞記事で解説者が「構成点が8点台後半」などと言った場合,8点台後半とはこの点数を指しています。この点数が9点台なら超一流の証で,世界で男女シングル各数名しかいません。

[N] 係数

 技術点[K]と演技構成点[O]の比率が,ほぼ1:1になるように調整するための係数で,女子SP: 0.8 倍女子FS: 1.6 倍男子FS: 2.0 倍と定められています。男子SPは,係数を適用しません(係数1倍)。

[O] 演技構成点PCS: Program Component Score)

 5項目の点数[M]を合計(満点は50点)し,演技種目に応じた係数[N]を掛け算した点数。演技構成点満点は,

  • 男子 SP: 50 点,FS: 100
  • 女子 SP: 40 点,FS: 80
です。係数が掛けられるため,同じ演技構成点でも種目により価値が異なり,例えばSPの演技構成点40点は,男子なら満点の8割ですが,女子は満点を表します。

◆減点[P]

 最も多い減点は転倒です。1回ごとに1点減点で,3~4回目は2点減点になります。例えば,3回転倒すると4点減点になります。他には,

  • 演技時間超過: 1点
  • 演技の開始姿勢を取るまでの準備時間超過: 1点
  • 衣装の一部がリンクに落下: 1点
などの減点があります。

◆総得点の見方

 係数[N]の調整の意味からわかるように,

  • 男子 SP:100 点,FS:200
  • 女子 SP:80 点,FS:160

満点に相当することになります。実際には,以前より難しいジャンプが入っているため技術点が上昇し,満点相当以上の点数が出ています。

計算って何だろう?(その2)

 前回の記事では,AIを考える上で欠かせない「計算とは何か?」という話題を始めて,途中になっていました。そこで紹介した3種類の「計算とは何かを考えるためのルール」を,今後,二重括弧を用いて『計算のルール』と書くことにします。

 『計算のルール』はいずれも「0以上の整数」だけを計算の対象にしていましたが,それでどこまで計算の対象が広がるのでしょうか? 当然のことながら,数は「0以上の整数」以外にも様々な種類がありますが,これらの数は0以上の整数を用いて表すことができます。

数の種類0以上の整数での表現の例
負の数(マイナス)符号(マイナスなら1,0以上なら0になる数)と絶対値の2つの整数で表現。(例)-3:符号=1,絶対値=3
分数分子分母の2つの整数で表現
小数浮動小数点表記による2つの整数で表現。(例)123.45 = 1.2345×10の乗 … 123452 の2つの整数。1つめの整数は小数点を除去した数
複素数整数係数の場合,実部虚部の2つの整数で表現。(例)2+3i:実部=2,虚部=3。係数がマイナス,分数,小数の場合は上記ルールを準用

 例えば,複素数 (4-5i)/3 は以下のように表現できます。記法の説明は割愛しますが,雰囲気はわかると思います。

  • 分数[ 分子:複素数[ 実部:整数[0,4], 虚部:整数[1,5] ], 分母:整数[0,3] ]
  • 複素数[ 実部:分数[4,3], 虚部:分数[ 整数[1,5], 整数[0,3] ] ]

 このように,一般的に私たちが「数」として認識しているものは,いくつかの「0以上の整数」に分解できることから,『計算のルール』を適用することができます。なお,√やπなどの無理数は,無限小数なので実際の値(円周率πなら 3.1415926535…)を正確に取り扱うことは不可能ですが,ある桁までの近似値を使うか,記号のまま(円周率なら「π」)にしておけば『計算のルール』の範疇で扱うことができます(なぜ記号のままなら扱えるのかについては後述)。

 以上は数1個の話ですが,「ベクトル」「行列」「集合」といった複数個の数の集まりでも原理は同じです。3つの要素を持つ集合であれば,集合[ 要素1, 要素2, 要素3 ] の各要素を(上述の要領で)0以上の整数で表現すればよいわけです。

 さて,四則演算よりも難しい計算にはどのようなものがあるでしょうか? 計算の分類といったものは世の中に定義がないようですので,高校数学からキーワードを拾ってみると「方程式・不等式」「数列」「三角比」「指数・対数」「微分・積分」「順列・組合せ」「確率」「平均・分散・標準偏差・相関係数」「論理・証明」などがあります。これらはいずれも,極論すれば四則演算の組み合わせと応用によって計算することができます。「証明」は文章の解読や解釈が必要なように思われるかもしれませんが,数学的にモデル化すると簡単な計算で済みます。大学以降で扱う煩雑な計算もこれらの応用で成り立つものであり,『計算のルール』の範疇で扱えるものです。

 こういったいわゆる計算らしい計算に加え,データを入力・保持・出力するための処理が計算にとって不可欠です。データ処理の基本として「参照」「整列(ソート)」「検索・探索」「追加・挿入・削除」「変更」といった処理があります。これらは,複数のデータの中から適切なデータを参照したり,効率よく参照・更新できるようにデータを保持したりする処理であり,変数の参照,変数への代入,条件判定(比較)などで成り立っています。これらも『計算のルール』の範疇で実行可能です。

 データ処理となると,対象となるデータは数だけではなく,「文字」「画像」「動画」「音声」といったデータも扱います。様々な種類のデータが混在すると「オブジェクト」と呼ばれたりします。しかし,もう皆さんご存じのように,これらのデータは数値に変換することができますので,やはり『計算のルール』で取り扱うことができます。

 数学の計算に話題を戻すと,計算で使うものは数だけではなく,+や≧といった記号(演算子),√やπといった特別な数を表す記号,sin や∫(積分記号)などの関数記号,x,y,z といった変数記号など,実は文字が多く使われています。それでも文字が数値に変換できる(=文字にコードを割り当てる)ことを考えれば,これらの記号を含む数式も『計算のルール』の範疇で処理できることがわかると思います。

 現実の計算機は0と1,すなわち電気的な ON/OFF でデータを扱っています。これは数値を最終的に(0と1だけなら成る)2進数で扱うことにより,計算機で処理することができます。上述した各種データが数値化,そして2進数化されることで計算機は機能します

 『計算のルール』はいずれも0以上の整数しか扱わないシンプルなルールでありながら,上述のようにあらゆる計算やデータ処理をカバーできることが(かなり強引な説明でしたが)ご理解いただけたと思います。さて,『計算のルール』の3種類である「チューリングマシン」「Nプログラム」「λ表現可能」の計算のカバー範囲に差はあるのでしょうか? 装置(仮想機械),手続き型プログラミング,関数型プログラミングという3つの分野から,全く異なるアプローチによって「計算とは?」を考察していますが,実はこの3つ,計算できる範囲が全く同じであることが数学的に証明されています。これら3つの仕組みで計算可能なもの(および計算不可能なもの)が完全に合致していることに,私はたいへん驚きました(大学時代には全く理解できていませんでした…)。この合致した計算の範囲が,計算の厳密な定義として最も一般的なものと考えられていることから,これら3種類の『計算のルール』の範疇で実行できるものが「計算可能」,実行できないものが「計算不可能」と定義されています。

 「計算可能な関数」を数学で定義したものが「帰納的関数」です。帰納的関数は以下のように定義されます。

定義の分類説明
基本関数以下は帰納的関数である。 ・(ゼロ) ・ある整数より1大きい整数を求める関数(後者関数) ・複数個の変数の中から1つを取り出す関数(射影関数)
関数合成f(x1,x2,…,xn), g1(x), g2(x), …, gn(x) が帰納的関数f(g1(x),g2(x),…,gn(x))帰納的関数 (引数 x は複数個でも可)
原始帰納法g(x), h(x) が帰納的関数f(x,0) = g(x), f(x,y+1) = h(x,y,f(x,y)) で定義される関数 f(x,y) は帰納的関数 (引数 x は複数個でも可)
最小解関数g(x,y) が上述の「基本関数」「関数合成」「原始帰納法」の組み合わせ・繰り返しで得られた関数 ⇒ f(x) = { g(x,y) = 0 を満たす y が存在するy の最小値 ; g(x,y) = 0 を満たす y が存在しない未定義 } は帰納的関数 (引数 x は複数個でも可)

 「原始帰納法」は,拡張する計算を作り出す手段であり,例えば「足し算から掛け算を作る」「掛け算から階乗やべき乗を作る」ようなときに適用されます。「最小解関数」は,判定条件を満たす数を見つけ出す手段であり,例えば「文字列の中で,ある文字が何文字目に出現するか」を調べる場合,1文字目から順に判定していき,最初に一致した場所が答えになりますが「順に判定」を実施する所が最小解関数らしさと言えます。

 「帰納的関数」は3種類の『計算のルール』で実行可能です。逆に,3種類の『計算のルール』で実行可能な関数は「帰納的関数」になります。3種類の『計算のルール』で実行可能な範囲が一致することの数学的な証明は,「帰納的関数」を介して行われます。高橋正子 著「計算論」では,(AとBの計算能力が一致することの証明を A ⇔ B で表すと) λ表現可能帰納的関数Nプログラムチューリングマシン という関係性で証明が記述されています。

 今回の記事で書いた内容を要約します。

  • 『計算のルール』では0以上の整数だけを扱っているにもかかわらず,それだけであらゆる種類の数や,様々なデータを扱った計算が実行可能になる。
  • 3種類の『計算のルール』は,計算を探究するアプローチが異なるが,これらの計算能力は完全に同等である。これらの『計算のルール』で実施できるものを「計算可能」という。
  • 計算可能な関数は,数学では「帰納的関数」として定義されるものである。

 では「計算可能」とはどのくらい複雑なことまでできるのか?みたいなことを書いて,AIの脅威を考える一助にしたいと思っているのですが,またまた長くなってしまったので,ここで区切りたいと思います。情報系の数学の中でもかなり基礎理論的な内容なので,かみ砕いて書くのに腐心しています。皆さんにどこまで伝わっているのでしょうか…。(続く)

計算って何だろう?

 AIは東大受験に合格できるか?という人工知能プロジェクトでの知見から,AIによるシンギュラリティ(ここでは「AIが人間の能力を超えること」を指すとします)はしばらく来ないと断言する 新井紀子 氏は,著書「AI vs. 教科書が読めない子どもたち」の中で,その理由を以下のように述べています。(いずれも著書より引用)

  • AIは意味を理解しているわけではありません。AIは入力に応じて「計算」し,答を出力しているに過ぎません
  • AI(コンピューター)が計算機であるということは,AIには計算できないこと,基本的には,足し算と掛け算の式に翻訳できないことは処理できないことを意味します
  • がどのような方法で,私たちが認識していることを「0,1」の世界に還元しているのか。それを解明して数式に翻訳することができないかぎり,「真の意味でのAI」が登場したりシンギュラリティが到来したりすることはないのです (筆者注:「真の意味でのAI」とは「人間の一般的な知能と同等レベルの知能」という意味)

 この主張のキーワードは「計算」です。計算とは人間の能力の一部分であり,いくらAIが発達してもそれは計算を極めただけで,意味の理解,感情,直感や第六感といった能力までAIに取って代わられるわけではない,ということなのですが,こういった主張を聞いてもまだ「やっぱり近い将来シンギュラリティが来るのでは?」「AIを甘く見ると人間は痛い目に遭うのでは?」と思う方もいるでしょう。そういう方は「計算」とは何かをきちんとわかっていないから,漠然と不安になるのではないでしょうか。「計算とは何か?」を知ることは,21世紀というITの時代における基礎教養と言えるでしょう。そこで今回は「計算」をテーマにしてみようと思います。

 ちなみに,新井 氏は「AIのシンギュラリティは来なくても,約半数の人たちが仕事を奪われる世界は現実になる」と警告しています。東大受験は無理でも,MARCHレベルの大学なら現在のAIは合格できるそうです。そして,AIが苦手とする「意味の理解」に関して,現在の学生も実は苦手という事実から,「AIができない創造的な仕事を人間がやればいいと言うが,その仕事をできる能力のある人間がどれほどいるのか?」と 新井 氏は問いかけます。AIはロマンやSFではなく現実的な脅威なんだ,ということがこの著書を読むととてもよくわかります。

 さて「計算」の話。四則演算から台風の進路予測まで,計算と言っても実に様々なものがあります。計算する機械としてコンピューター(以後「計算機」)が誕生しましたが,これだけ計算機が身近になっている現代においては,逆説的に「計算機が実行しているものが計算である」と考えることもできます。計算機が存在しなかった時代に「こういう仕組みがあれば(自分たちが普段「計算」だと思っている)計算が自動的にできるのではないか」と考え,現在でも計算機の基本モデルとなっているのが「チューリングマシン」(Turing Machine)です。

TuringMachine

 チューリングマシン(詳細は Wikipedia専門家の記事をご参照ください)は,テープ・ヘッド・本体(状態を記憶)を持ち(上図参照),テープの内容を読み取り,シンプルなルールに基づいて動作し,答えをテープに書き出す装置です。テープの読み書きが1文字ずつで,ヘッドの移動も1文字分しか行えないため,計算の機械としては極めてシンプルですが,その計算能力は現代の計算機(そして今後登場する量子コンピューターでさえも)でできることは,全てチューリングマシンで実行可能と言われているほど強力なものです。この考え方が1930年代に考案されていたというのですから驚きです。

 その後,時が流れてソフトウェアやプログラミングという概念が誕生すると,プログラミングってどこまでの処理ができるのか?という疑問が出てきました。プログラム言語の中でも「手続き型」と呼ばれる,現在でも主流であるプログラミング手法の基本モデルとなるのが「Nプログラム」と呼ばれるものです。Nプログラムは,以下のルールに基づき命令を処理する手順です。

  • 複数個(0個~有限個)の「0以上の整数」を入力する「入力命令」で開始し,
  • 代入命令」または「判定命令」を複数回(有限回)順次実施し,
  • 「0以上の整数」を1個出力する「出力命令」で停止する

 「代入命令」は,数式の計算結果を変数に格納する処理のことで,Nプログラムにおける数式は,変数,0以上の整数,および四則演算(引き算と割り算は答えが0以上の整数になるよう制限されたもの)の組み合わせだけです(この数式のルールは入力/判定/出力処理にも適用される)。「判定命令」はいわゆる IF 文(IF ~ THEN ~ ELSE ~)のことで,「数式=数式」という形式の判定条件が正しい(真,true)か誤り(偽,false)かによって次に実行する命令を振り分ける処理のことです。判定命令の次に実行する命令は前に戻るようなものでも構わないので,処理がループする可能性もあります。ループを抜けることができない場合そのNプログラムは停止しないので,答えが出ないということになります。

 Nプログラムは,0以上の整数と四則演算しか使えないため,かなりシンプルです。この程度の仕組みでどれだけの計算ができるのか?と思うかもしれませんが,現存するプログラム言語で実行できることは,全てNプログラムで実行可能と言われるほど強力な仕組みです。

 さて,プログラム言語には Lisp や Haskell のような「関数型」と呼ばれる種類があります。これは「数学で言うところの関数」に準じた形でプログラミングを行うという考え方で,手続き型は命令の連鎖,関数型は関数の合成(例えば y = f( g(x,y), h(z,p(m),n) ) のような感じ)によってプログラムを実行します。関数型プログラミングの基本モデルになっているのが「λ計算」(ラムダ計算,λ-Calculus)という数学的体系です。これは数学の関数の一般的な性質を探究するための体系ですが,実践面ではプログラム言語,インタープリター,コンパイラーの基本的性質も表現しています。λ計算では,以下の文法で定義される「λ式」を使って関数を表現します。

  • 変数はλ式である。
  • M:λ式,x:変数 のとき,λx.M はλ式である。
  • M, N:λ式 のとき,MN はλ式である。

《λ式の例》
λx.(λy.(((λz.zw)(λt.(ty)t))y)x)
= λxy.(λz.zw)(λt.tyt)yx (括弧を省略した表記)

 λx.M は変数が1つですが,変数が複数ある場合は λx.(λy.(λz.M)) = λxyz.M とすれば3変数の関数が表現できることからわかるように,上述の文法だけで関数の変数が多くなっても対応できます。そしてλ計算には,変数に値を代入して関数を計算する行為を意味する「β変換」というルールがあります。β変換を ->>,変数 x への値 A の代入を [x:=A] と表記し,変換の例を以下に示します。

① (λxyz.y)ABC ->> (λxyz.x)[x:=A][y:=B][z:=C] = B
② (λxy.yx)FG ->> (λxy.yx)[x:=F][y:=G] = GF
③ (λxy.yx)(λxyz.x)(λxyz.y)(λxy.y)(λx.x)
 ->> (λxy.yx)[x:=(λxyz.x)][y:=(λxyz.y)](λxy.y)(λx.x)
 = (λxyz.y)(λxyz.x)(λxy.y)(λx.x) …②と同じ形
 ->> (λxyz.y)[x:=(λxyz.x)][y:=(λxy.y)][z:=(λx.x)]
 = λxy.y …①と同じ形

 ①を見るとわかるように,λの右に書かれた変数の順に,λ式の並びに沿って値を渡します。β変換は単なる式の変形ですが,これを見ていると何か意味があるように見えてきます。①の (λxyz.y) は3つの入力値を取り2つめの値だけを返す関数,②の (λxy.yx) は2つの関数の順序を入れ替える関数だと解釈することができます。③は似たような式の羅列に見えますが,②と①を連続的に計算しているイメージです。長い式がβ変換によって短い式に変化する様子は,コンパイラーによるプログラムの最適化を意味していると考えるとわかりやすいでしょう。以上をふまえてλ計算の数式の意味をまとめると,
  • λx.M … 「x を変数に持つ関数 M」 「x を入力とするプログラム M」
  • MN … (1) M:(数学で f(x) と表記される)関数,N:値 と解釈すれば,MN は f(N) に相当する。
    (2) M:関数 f(x),N:関数 g(x) と解釈すれば MN は関数 f(g(x)),すなわち f と g の関数合成に相当する。
  • β変換計算の実行。左辺:関数の記述。右辺:関数の計算結果。

となります。λ式の文法は極めてシンプルで,β変換も「変数への値の代入」という操作を忠実に実行しているに過ぎません。ここまでを見る限り,λ計算で何ができるのか,さっぱり見当がつかない方も多いと思います。

 λ式には数値も演算も含まれていませんので,このままでは四則演算や真偽といった具体的な計算に関する議論ができません。そこで,これらを擬似的に表現するλ式を考えます。上述のNプログラムでは0以上の整数だけを扱いましたので,ここでもまずは0以上の整数を考えます。数値 n を表現するλ式を [n] と表記とし,以下の定義を与えます。

※ 高橋正子 著「計算論」より引用。この定義は,数値を表現するλ式でよく用いられる「チャーチ数」とは別のものです。

  • [0] = λz.z
  • U = λxy.y
  • 《M, N》 = λx.xMN …《意味》 M と N の対(ペア)
  • [SUC] = λn.《U, n》 …《意味》ある数字よりも1だけ大きな数字を返す関数(後者関数)
  • [TRUE] = λxy.x …《意味》真
  • [FALSE] = λxy.y …《意味》偽
  • [ZERO?] = λn.n[TRUE] …《意味》数値が0かどうかを判定する関数

 ここからλ計算の真の威力が明らかになってきます。まず,整数を表現するλ式を作ってみます。

[1] = [SUC][0] = (λn.《U, n》)[0] ->> 《U, [0]》
[2] = [SUC][1] = (λn.《U, n》)[1] ->> 《U, [1]》 = 《U,《U, [0]》》
[3] = [SUC][2] = (λn.《U, n》)[2] ->> 《U, [2]》 = 《U,《U,《U, [0]》》》

 このように,整数は《U, 《…, 《U, [0]》》》となり,U の個数数値の大きさを表します。これらの数値が0かどうかを判定すると,

[ZERO?][0] = (λn.n[TRUE])(λz.z) ->> (λz.z)[TRUE] ->> [TRUE]

(1以上の整数 [n] = 《U, 《…, 《U, [0]》》》 を 《U, X》 と書くと)
[ZERO?][n] = (λn.n[TRUE])《U, X》 = (λn.n[TRUE])(λx.xUX)
 ->> (λx.xUX)[TRUE] ->> [TRUE]UX = (λxy.x)UX ->> U = λxy.y = [FALSE]

となり,正しく判定できていることがわかります。さらに,λ式 P,M,N を並べて P に(上記の0判定のような)判定条件を入れると,

PMN =
【 P が真 】  [TRUE]MN = (λxy.x)MN ->> M
【 P が偽 】  [FALSE]MN = (λxy.y)MN ->> N

となります。これは「判定条件」「真のとき実行する式」「偽のとき実行する式」の3つのλ式を順に並べると(IF 文に相当する)条件分岐を表現できることを示しています。

 いかがでしょうか。β変換によってλ式がどんどん変形していく様子を見ても,ただの記号の羅列なのでちょっと狐につままれた感じがする方もいらっしゃるでしょう。ですが,各々のλ式に上記のような意味を持たせることで,λ計算が実際的な計算を表現できることがわかると思います。例えば,上述の「数値を表現するλ式」は,データ構造の「リスト」に準じた形になっています。ということは,リストに関する各種操作も以下のようにλ式で表現できるというわけです。(情報科学やソフトウェア工学の基本,もしくはプログラム言語 Lisp をご存じの方にしか理解できない内容ですみません)

  • リストを作成: [CONS] = λht.《h, t》
  • リストの先頭の要素を取得: [CAR] = λx.x(λht.h)
  • リストの後続リストを取得: [CDR] = λx.x(λht.t)

[CONS]X《Y, Z》 = (λht.《h, t》)X《Y, Z》 ->> 《X, 《Y, Z》》

[CAR]《X, 《Y, Z》》 = (λx.x(λht.h))《X, 《Y, Z》》
 ->> 《X, 《Y, Z》》(λht.h) = (λx.xX《Y, Z》)(λht.h) ->> (λht.h)X《Y, Z》 ->> X

[CDR]《X, 《Y, Z》》 = (λx.x(λht.t))《X, 《Y, Z》》
 ->> 《X, 《Y, Z》》(λht.t) = (λx.xX《Y, Z》)(λht.t) ->> (λht.t)X《Y, Z》 ->> 《Y, Z》

 λ計算において,0以上の整数(を表現したλ式)を複数個(有限個)与えると,β変換によって0以上の整数(を表現したλ式)の答えに到達することを「λ表現可能」と言います。「λ表現可能」な関数は計算が成立していると考えるわけです。

 ここまで「チューリングマシン」「Nプログラム」「λ表現可能」という3つの「計算とは何かを考えるためのルール」を紹介しました。これらのルールによって実行される「計算」はどこまで可能なのかを考えていきたいのですが,記事がとても長くなってしまったので,いったんここで区切ります。次回の記事では,計算という世界の広大さと限界を,できるだけわかりやすくお伝えしたいと思っています。

 これだけ長文になってしまったのは,皆さんになじみが薄い「λ計算」をきちんと紹介したいという思いが強く,そこに紙面を割いてしまったからなんですが,最近IT・ソフトウェア業界でよく目にするラムダ(λ,Lambda)という言葉は,このλ計算と同じ由来だと思われます。有名なのは AWS (Amazon Web Services) の Lambda というサービスですね。これは,端的に言えばサーバーを用意することなくソフトウェアを実行できるサービスで,一般的には FaaS (Function as a Service) と呼ばれています。Function すなわち「関数」を実行するから,関数を指す記号として使われるλ(なぜλなのかは実はよくわかっていません)から Lambda というサービス名に行き着いたのではないかと思います。また,最近になって多くのプログラム言語で lambda という命令(ステートメント)が実装されています。こういった背景があってラムダという言葉を目にする機会が増えています。

 2020年を目前にして再びラムダという言葉をこんなに聞くことになるとは思ってもいませんでした。というのも,実は私の大学での卒業研究のテーマλ計算だったのです。上述のλ計算の記載にあたり引用した「計算論」の著者 寶来正子 先生(高橋 は旧姓)は私の卒業研究の指導教官です。当時,私は研究嫌いを公言し,先生に「何か卒業研究のネタを下さい」とお願いしてしまうような体たらくだったのですが,寶来 先生は嫌な顔一つ見せずに,先輩の修士論文の続きをやってみないかと提案してくださいました。そのテーマがλ計算だったので,私はλ計算を詳しく知っている珍しい人になりました。

 今回の記事でλ計算をこれだけ書けたのはそんな経歴があるからなんですが,λ計算が計算に関して高い説明能力を持っていることを知ったのは,実は数年前です。学生当時は「λ計算は単純な割にけっこう強力な仕組みだな」「これがコンパイラーの理論的な基盤になってるんだ」という程度しか理解していませんでした。数年前に,そう言えば 寶来 先生の「計算論」をちゃんと読んでなかったことをふと思い出し,改めて精読したところλ計算ってこんなにすごかったのかと驚きました。ブログで「計算とは?」なんていうテーマを書くことになるとは思いませんでしたが,私の驚きを少しでも皆さんに伝えられたらと思います。

タグ絞り込み検索
記事検索
プロフィール

まっく・けぃ(Mak....

  • ライブドアブログ