3. 計算の理論的背景
チャーチの提言（Church’s thesis）
般帰納的関数を計算可能な関数という」
「一般帰納的関数を計算可能な関数という」
により定義
等価な数学モデルと言語
チューリングマシン
→ 手続き型言語
帰納的関数（recursive function）
→ 関数型言語
第一階述語論理（first-order predicate logic）
→ 論理型言語
計算の意味論
操作的意味、表示的意味、証明論的意味、最小不動点
操作的意味 表示的意味 証明論的意味 最小不動点
意味など
3
4. よくある並列処理
ベースはチューリングマシン
フォン?ノイマンボトルネックとの戦い
分類
対称性
扱いやすいのは 物理メモリを共有する対称型（SMP: Symmetric Multi
扱いやすいのは、物理メモリを共有する対称型（SMP:
Processing）
命令とデータの流れ
MIMD（Multiple Instruction/Multiple Data）
複数の命令を複数のコンテキストで実行。通常のマルチプロセッサ
SIMD（Single Instruction/Multiple Data）
同 の命令を複数のコンテキストで実行。ベクトル計算機
同一の命令を複数のコンテキストで実行 ベクトル計算機
プロセッサの結合
密結合
バス結合 → 結合できるPEの数に限界
クロスバースイッチ → PE数の2乗に比例して回路の複雑度がアップ
疎結合
高速ネットワ クによりクラスタを結合 GRIDなど
高速ネットワークによりクラスタを結合。GRIDなど
4
6. データフロー型
問題は、
伝播するデ タフロ をどう制御すべきか
伝播するデータフローをどう制御すべきか
プログラミングが容易ではない
ベクトル計算と同じで、通常のプログラムをデ タフロ
ベクトル計算と同じで 通常のプログラムをデータフロー
化するコンパイラを作るのは簡単ではない
計算モデルがないなど、実践が先行し理論的なアプロ
計算モデルがないなど、実践が先行し理論的なアプロー
チが追いついてこないのも問題?
6
8. でも歴史は...そう進まなかった
1982～1992年頃のお話
第5世代プロジェクトが起こり、超並列AIマシンの開発が国家目標に
Prologという言語が流行ってしまった
が
不完全な導出の実装により完全性が欠如
完全性の補償のため、プログラマが余計な制御文を書く羽目に
完全性の補償のため プログラマが余計な制御文を書く羽目に
節とatomのならびに逐次的な意味を与えてしまった。
このため並列性がことごとく破壊される
並列処理の方式研究は AND並列の困難さとOR並列の爆
並列処理の方式研究は、AND並列の困難さとOR並列の爆
発に阻まれる
GHCというデ タフ
GHCというデータフローの扱いやすい言語が出てくるなど、並列化の
の扱いやすい言語が出てくるなど、並列化の
対象が別の方向に...
第5世代プロジェクトは、ICOTを中心に精力的に研究が進
んだが、応用や発展的研究が出ないまま終わりを迎えた
んだが 応用や発展的研究が出ないまま終わりを迎えた
論理プログラムにおける並列処理の研究は頭打ちに...
論理プログラムにおける並列処理の研究は頭打ちに
8
9. その頃、私は...
1981年 論理プログラムの並列処理を研究テーマに選ぶ
所属の研究室では以前から論理プログラムの計算についての研究
を行っていた（M1の時期）
1982年 「考えるビーカー」を着想
この年、第5世代プロジェクト起こる
1983年 ユニファイア分離導出の定式化を開始
フ イア分離導出の定式化を開始
combination演算の可換性の証明に苦労する
結局、定式化と証明に3年費やす
論文誌に採択されるのが、さらに3年後の1989年
1984年 論理プログラムの計算モデル（UPモデル）を発案
超並列に向く（逐次処理部分がない）
unifierだけで計算を完結（シンプル）
ある意味、「考えるビーカー」のために作ったもの
評価は、
得られず。（時すでに遅し。発表するも理解を示してくれる人なし）
旬を逃し、そのまま凍結（吉田のライフワークに）
9
10. ユニファイア分離導出（U-導出）とは
きっかけはAND並列と両方向推論（みんな難しいというから
トライしてみた...）
AND並列とは、call f, call g,..と続く手続きを並列に行うもの。fの副
並列とは ll f ll と続く手続きを並列 行うも f 副
作用がgに影響するため困難とされていた
推論には帰結から進めていくもの（トップダウン）と公理から積み上
げていくもの（ボトムアップ）がある。両方から詰めていくのが両方向
推論。meet処理が難しい
問題を分析すると、
AND並列の難しさは、導出の持つ逐次性にある
両方向推論の難しさは、論理的に同等であるトップダウンとボトム
アップの推論過程が異なるものと捉えられてしまうところにある
U-導出とは、大雑把に言えば、導出の持つ逐次的な制約を
とっぱらったもの
ぱら たも
これにより、AND並列と両方向推論の困難さがなくなり、「一般化計
算モデル」という新しい概念が生まれる
でも、見かけは導出と同じなので、よほど挑戦的なことをしないとあり
でも 見かけは導出と同じなので よほど挑戦的なことをしないとあり
がたみは出ない
10
11. 鲍-导出の特徴
U-導出は導出と互換な拡張
unifierを別に扱える（+はcombinatorと呼ぶ演算）
導出
(A <- B, C) λ
(P <- Q, R)μ
θ
θ= mgu(Bλ, Pμ)
mgu(Bλ
Aλθ <- Qμθ, Rμθ, Cλθ
U-導出
U 導出
(A <- B, C) λ
(P <- Q, R)μ
φ
φ= mgu(B, P)
(A <- Q, R, C)(λ+μ+φ)
11
12. 鲍-导出の特徴
計算木においては、縮約（reduction）に相当する操作
+演算（combinator）に交換則と結合則が成り立つことから、
演算（ ） 交換則 結合則 成り ら、
縮約はどの順序で（さらには同時に）行ってもよい
A <-
B, C λ
φ= mgu(B,
φ mg (B P)
A <-
P <- Q, R, C λ+μ+φ
Q, R μ
縮約
reduction
12
14. SLD導出の例
プログラム
F: append([], x, x) <-
R: append([x|y], z, [x|w]) <- append(y,z,w)
計算 G0: <- append([1,2], [3], q)
append([x|y], z, [x|w]) <- append(y,z,w)
σ1={1/x, [2]/y, [3]/z, [1|w]/q}
G1: <- append([2] [3] w)
append([2], [3],
append([x’|y’], z, [x’|w’]) <- append(y’,z’,w’)
σ2={2/x, []/y, [3]/z, [2|w’]/w}
G2: <- append([], [3], w’)
append([], x”, x”)
σ3={[3]/x”, [3]/w’}
G3: □
解
σ1σ2σ3|{q}={[1,2,3]/q}
14
15. 础狈顿/翱搁グラフでは
G0: <-
append([1,2], [3], q) 節ノード
ANDアーク
R: append([x|y], z, [x|w]) <
<- ORアーク
append(y, z, w)
F: append([], x, x) <-
計算 = グラフの展開と縮約 → 展開
? 縮約
G0 G1
G0 G1 G1 G2 G2
R’ R” G2
R → ? R → ? R → G3
R R F
F F F
F F
15
16. UP (Unifier Plate)
節とユニファイアのテンプレート表現
UP（節ノード） UP（ORアーク）
q
G0 G0-R 1 [2] [3] ?
1
q
x
F R-R ? ?
x y z w
R R-F []
y z w
16
17. 鲍笔グラフ
q AND/ORグラフと違い、
G0 変数とtermしか現れな
q い
combinationの失敗に
1 [2] [3] ?
より、不要なORア ク
より、不要なORアーク
1 は除外される
x y z w
R
y z w
? ?
[]
x
F
17
18. 鲍笔グラフの縮約
グラフの展開?縮約過程でUPのcombinationが起こる
一連のcombinationの結果、解が得られる
連の の結果、解 得られる
q
q q
1 [2] [3] ?
1 ? [2] [3]
1
?
x y z w y z w
q
y z w
[] [3] ?
? [1,2]
? ?
y z w
q
x y z w
?
[1,2,3]
[]
y z w
x
18
19. 「考えるビーカー」
液体計算機
生体における生化学反応にヒント
体 おける 化学反応 ント
combinatorを酵素、UPを反応によって生まれる高分子化合
物とみなすと、生化学反応はある種の計算とみなせる
計算は以下の手順で進む
combinatorの働きをする高分子化合物（酵素）の溶液を用意
factおよびruleに相当するUP（高分子化合物）を数滴落としておく（こ
の時点で計算は進む）
goalに相当するUP（高分子化合物）を数滴落とすと、目的の計算が
goalに相当するUP（高分子化合物）を数滴落とすと 目的の計算が
スタートする
答えは、 UP（高分子化合物）で得られる
答えとなる高分子化合物に反応する酵素か何かを用意しておくこと
で、計算結果を得ることができる
19
21. 分子計算への期待
極超並列計算のためのポテンシャルが高い
既存の ン
既存のコンピュータに縛られる必要はない
タ 縛られる必要はな
計算不可能世界へのチャレンジもある
ハードウェアが異なれば、計算原理も変わる
例えば、ニューラルネットワークのプログラミングは全然違うもの
分子計算の特性から新たな計算原理を作ってもよい
今の計算可能世界の枠組みで人工知能はできっこないし...
今 計算 能世界 枠組 人 知能は き な し
生化学反応との親和性が高い
薬品開発にも影響を与える
シナプスとのインタフェースが取れれば、SFちっくな話に
攻殻機動隊の世界
身体障害者には朗報
21
22. 余談：SFといえば
バイオ?ニューラル?ジェルパック
スタートレック
脳を模した手のひらに乗るほどの小さなジェルパック
たくさん集めて、バイオ神経回路と呼ばれるコンピュータ?ネットワー
ク?システムを形成
風邪を引いたりするが、ワクチンや熱消毒などを使った治療が可能
風邪を引いたりするが ワクチンや熱消毒などを使った治療が可能
である
有機コンピュータ
新世紀エヴァンゲリオン
新世紀エヴ ンゲリオン
第7世代コンピュータ
培養した神経細胞を利用して構築するコンピュータ
3台のスーパーコンピュータで構成されるMAGIのための技術
ピ
攻殻機動隊もバイオシステムが前提?
なんか、どれも計算モデルは、ニューラルネットワーク（or
パーセプトロン）だなあ...
22
![SLD導出の例
プログラム
F: append([], x, x) <-
R: append([x|y], z, [x|w]) <- append(y,z,w)
計算 G0: <- append([1,2], [3], q)
append([x|y], z, [x|w]) <- append(y,z,w)
σ1={1/x, [2]/y, [3]/z, [1|w]/q}
G1: <- append([2] [3] w)
append([2], [3],
append([x’|y’], z, [x’|w’]) <- append(y’,z’,w’)
σ2={2/x, []/y, [3]/z, [2|w’]/w}
G2: <- append([], [3], w’)
append([], x”, x”)
σ3={[3]/x”, [3]/w’}
G3: □
解
σ1σ2σ3|{q}={[1,2,3]/q}
14](https://image.slidesharecdn.com/kibayos-beaker-070829-100525034426-phpapp02/85/kibayos-beaker-070829-14-320.jpg)
![础狈顿/翱搁グラフでは
G0: <-
append([1,2], [3], q) 節ノード
ANDアーク
R: append([x|y], z, [x|w]) <
<- ORアーク
append(y, z, w)
F: append([], x, x) <-
計算 = グラフの展開と縮約 → 展開
? 縮約
G0 G1
G0 G1 G1 G2 G2
R’ R” G2
R → ? R → ? R → G3
R R F
F F F
F F
15](https://image.slidesharecdn.com/kibayos-beaker-070829-100525034426-phpapp02/85/kibayos-beaker-070829-15-320.jpg)
![UP (Unifier Plate)
節とユニファイアのテンプレート表現
UP（節ノード） UP（ORアーク）
q
G0 G0-R 1 [2] [3] ?
1
q
x
F R-R ? ?
x y z w
R R-F []
y z w
16](https://image.slidesharecdn.com/kibayos-beaker-070829-100525034426-phpapp02/85/kibayos-beaker-070829-16-320.jpg)
![鲍笔グラフ
q AND/ORグラフと違い、
G0 変数とtermしか現れな
q い
combinationの失敗に
1 [2] [3] ?
より、不要なORア ク
より、不要なORアーク
1 は除外される
x y z w
R
y z w
? ?
[]
x
F
17](https://image.slidesharecdn.com/kibayos-beaker-070829-100525034426-phpapp02/85/kibayos-beaker-070829-17-320.jpg)
![鲍笔グラフの縮約
グラフの展開?縮約過程でUPのcombinationが起こる
一連のcombinationの結果、解が得られる
連の の結果、解 得られる
q
q q
1 [2] [3] ?
1 ? [2] [3]
1
?
x y z w y z w
q
y z w
[] [3] ?
? [1,2]
? ?
y z w
q
x y z w
?
[1,2,3]
[]
y z w
x
18](https://image.slidesharecdn.com/kibayos-beaker-070829-100525034426-phpapp02/85/kibayos-beaker-070829-18-320.jpg)
