Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Prolog入門
Search
Masaki Hara
September 12, 2024
Programming
5
1.3k
Prolog入門
10分でPrologの雰囲気と応用をざっくり紹介します。
Masaki Hara
September 12, 2024
Tweet
Share
More Decks by Masaki Hara
See All by Masaki Hara
Arm移行タイムアタック
qnighy
0
320
Quine, Polyglot, 良いコード
qnighy
4
640
Rubyのobject_id
qnighy
6
1.5k
Getting along with YAML comments with Psych
qnighy
2
2.1k
状態設計から「なんとなく」を無くそう
qnighy
84
27k
日付時刻A to Z
qnighy
1
580
Hands-on Native ESM @ JSConf JP 2022
qnighy
0
5.7k
computed_modelの紹介 / Introducing computed_model (2)
qnighy
0
590
computed_modelの紹介 / Introducing computed_model
qnighy
0
350
Other Decks in Programming
See All in Programming
詳細解説! ArrayListの仕組みと実装
yujisoftware
0
580
OnlineTestConf: Test Automation Friend or Foe
maaretp
0
110
Creating a Free Video Ad Network on the Edge
mizoguchicoji
0
120
WebフロントエンドにおけるGraphQL(あるいはバックエンドのAPI)との向き合い方 / #241106_plk_frontend
izumin5210
4
1.4k
Webの技術スタックで マルチプラットフォームアプリ開発を可能にするElixirDesktopの紹介
thehaigo
2
1k
광고 소재 심사 과정에 AI를 도입하여 광고 서비스 생산성 향상시키기
kakao
PRO
0
170
RubyLSPのマルチバイト文字対応
notfounds
0
120
エンジニアとして関わる要件と仕様(公開用)
murabayashi
0
280
ピラミッド、アイスクリームコーン、SMURF: 自動テストの最適バランスを求めて / Pyramid Ice-Cream-Cone and SMURF
twada
PRO
10
1.3k
GitHub Actionsのキャッシュと手を挙げることの大切さとそれに必要なこと
satoshi256kbyte
5
430
みんなでプロポーザルを書いてみた
yuriko1211
0
260
Contemporary Test Cases
maaretp
0
130
Featured
See All Featured
YesSQL, Process and Tooling at Scale
rocio
169
14k
Embracing the Ebb and Flow
colly
84
4.5k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
9.1k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
131
33k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
BBQ
matthewcrist
85
9.3k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
232
17k
How GitHub (no longer) Works
holman
310
140k
How to Think Like a Performance Engineer
csswizardry
20
1.1k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
126
18k
5 minutes of I Can Smell Your CMS
philhawksworth
202
19k
Building Applications with DynamoDB
mza
90
6.1k
Transcript
© 2024 Wantedly, Inc. Prolog入門 現代プログラマのための Sep. 12 2024 -
Masaki Hara @ Tech Lunch
© 2024 Wantedly, Inc. 今回話すこと • Prologは論理型プログラミング言語 • 古くは人工知能として持て囃された •
その実態は「単一化」と「バックトラック」を持つ特殊な手続き型 言語 • 現代では型推論器など記号処理タスクの実行エンジンとして 大いに役に立っている 10分でPrologのことを理解するのはさすがに無理なので、大まかな特徴や応用 をざっくり掴んでもらえたらなと思います。
© 2024 Wantedly, Inc. Prolog入門
© 2024 Wantedly, Inc. Prolog 起動と終了 $ brew install swi-prolog
$ swipl ?- halt. またはCtrl+Dで終了
© 2024 Wantedly, Inc. Prolog # test1.pl parent(taro, hanako). parent(jiro,
hanako). sibling(X, Y) :- parent(X, Z), parent(Y, Z). ?- [test1]. ?- sibling(taro, X). X = taro ; SPACE X = jiro. Enterで中断 Spaceで続行 ファイル名を指定して ロード
© 2024 Wantedly, Inc. Prologの基本的な使い方 • ファイルに定義を書き、コマンドラインで命令を行う • Prolog処理系は、「条件を満たす変数を全て見つける」処理 を行う
◦ 前ページの例では X が変数になっている ◦ sibling(taro, X) という条件は、 X = taro または X = jiro を入れれば成立する
© 2024 Wantedly, Inc. 項 (term): Prologの主役となる構文 構文 foo foo(x,
y) アトム 小文字始まり 関数のような形式 'foo' シングルクオートで囲む 複合項 変数 X 大文字始まり 定数のように 振る舞う
© 2024 Wantedly, Inc. 項 (term): Prologの主役となる構文 構文 1 +
2 123 複合項の糖衣構文 [1, 2] リテラル [X | Y] '+'(1, 2) = = .(1, .(2, [])) [] 空リスト = .(X, Y)
© 2024 Wantedly, Inc. 項と述語 項の一番外側は「命令 (述語, 条件)」として振る舞う halt. 項の一番外側は
halt というアトム。 haltは命令として振る舞う。 append([1, 2], [3], X). 項の一番外側は append という複合項。 appendは命令として振る舞う。
© 2024 Wantedly, Inc. 変数 最上位以外、どこに変数を書いてもいい ?- append(X, Y, [1,
2]). X = [], Y = [1, 2] ; X = [1], Y = [2] ; X = [1, 2], Y = [] ; false.
© 2024 Wantedly, Inc. 変数 Append自体もPrologコードで書ける % 空リストを足しても変わらない append([], X,
X). % 第一引数が1要素増えると、結果リストも1要素増える append([X|Y], Z, [X|W]) :- append(Y, Z, W).
© 2024 Wantedly, Inc. Prologの実行モデル
© 2024 Wantedly, Inc. 理想と現実 Prologの理想 • 条件を宣言的に書く • 解を全て探してくれる
Prologの現実 • 命令列を並べる ◦ 命令順が重要 • 単純なバックトラックによる 探索 宣言的なメンタルモデル 命令的なメンタルモデル
© 2024 Wantedly, Inc. 順序依存 命令順によって結果が異なる (命令的な側面) ?- Y =
[], append(X, Y, Y). Y = X, X = [] ; false. ?- append(X, Y, Y), Y = []. ERROR: Stack limit (1.0Gb) exceeded
© 2024 Wantedly, Inc. Prologの実際 • (宣言的な視点) Prologは論理式ソルバーである。 • (命令的な視点)
Prologは「単一化」と「バックトラック」を備え た命令的プログラミング言語である。 ◦ 単一化 = 自由変数を含む等式を解く ◦ バックトラック = 分岐の片方を試し、探索が終わったら状態を巻き戻して、分岐のもう一 方も試す
© 2024 Wantedly, Inc. 項 • 項 (term) は関数の積み重ね •
この関数は一般の関数ではなく、互いに重なり合わない性質 を持つ ◦ 単射かつ相互排他 ◦ コンストラクタとも呼ばれる • Prologの項としての 1 + 3 は 2 + 2 とは等しくない ◦ 関数名(+)が同じで、引数も同じときだけ同じとみなす
© 2024 Wantedly, Inc. 単一化 • 単一化 (unification) = 項に関する連立方程式を解く問題
• ある種の唯一解 (最汎単一化子; MGU) を求めることができ る ◦ 解がない(矛盾)ケースもある • たとえば f(X, a) = f(b, Y) なら X = b, Y = a
© 2024 Wantedly, Inc. バックトラック • Prologでは1つの述語を実行するのに複数の実行経路があ る • 普通の分岐と異なり、どちらに進めばいいのか開始時点では
わからないことがある ◦ たとえば append/3 は append([], X, X). と append([X|Y], Z, [X|W]) :- append(Y, Z, W). の2つの分岐があるが、第一引数が自由変数だとどちらに進めばい いかわからない
© 2024 Wantedly, Inc. バックトラック • Prologでは1つの述語を実行するのに複数の実行経路があ る • 普通の分岐と異なり、どちらに進めばいいのか開始時点では
わからないことがある • 両方の分岐を試すためにバックトラックを行う
© 2024 Wantedly, Inc. バックトラック バックトラックの手順 • 分岐1に進む • 分岐1が終わったら、分岐地点まで巻き戻す
• 次の分岐を同様に試す
© 2024 Wantedly, Inc. 単一化とバックトラック • 組み込みのバックトラックを持つ言語では、「巻き戻される副 作用」と「巻き戻されない副作用」を区別する必要がある ◦ これはWeb開発におけるトランザクションの取り扱いとも似ている
(トランザクション中に 外部APIを叩くと巻き戻せない問題) • 単一化は「巻き戻される副作用」として扱う ◦ そのためにも単一化とバックトラックを抱き合わせて言語処理系で取り扱う必要がある
© 2024 Wantedly, Inc. バックトラックと非決定性 • バックトラックは非決定性計算を実現する方法のひとつ ◦ Listモナドと呼ばれることもある •
非決定性計算自体も副作用のひとつ
© 2024 Wantedly, Inc. 非決定性と対称性 • 数学的には、非決定性計算とは1つの値のかわりに集合を返 す関数ということになる ◦ f:
A → B のかわりに f: A → P(B) を考える (Pは羃集合) ◦ 圏論的に言うと、羃集合モナドの Kleisli射を考えている • 「集合を返す関数」 = 「2項関係」 ◦ f: A → P(B) を考えるのではなく R ⊆ A × B を考える • 2項関係では定義域と終域が対称の関係になる ◦ Kl(P) = Rel
© 2024 Wantedly, Inc. 非決定性と対称性 • 定義域と終域が対称の関係 → 逆計算の正当化 ◦
append(X, Y, [1, 2]). のような計算をする発想
© 2024 Wantedly, Inc. Prologの応用
© 2024 Wantedly, Inc. Prologの応用 Prologの応用について以下を紹介 • 初期の人工知能 • Datalog
• 型推論
© 2024 Wantedly, Inc. 人工知能黎明期 • PrologはLispとともに、初期の人工知能研究で使われた ◦ 逆問題を解くなど、現在の人工知能にも通じる共通点もみられる ◦
プログラムとデータの同型性という意味では PrologとLispにも似た面がある • 比較的最近の応用ではWatsonの自然言語処理に使われて いたらしい ◦ ここ数年で深層学習ベースの自然言語処理が強くなってしまったので今後同様の応用が 出る見込みは少なそう • 今でもProlog = 人工知能という印象は強いかも
© 2024 Wantedly, Inc. Datalog • Prologから計算的な側面を排除したサブセット ◦ 本スライドの parent
/ sibling の例がこれに当たる • 一種のグラフデータベースのように使うことができる • SQLに影響を与えたとも言われている
© 2024 Wantedly, Inc. 型推論 • Hindley-Milner型の型推論では、型変数を置くことで宣言 順によらない型推論を可能にしている。 これはPrologの単一化と同じもの •
型クラスを持つHaskellやRustの型推論では、複数の実装 のなかから制約を充足できるものを探索する。 これはPrologのバックトラックと対応
© 2024 Wantedly, Inc. 型推論 • 型推論器をPrologに見立てることで、Rustの型システムを強 化する試み https://speakerdeck.com/nik omatsakis/hereditary-harro
p-formulas-papers-we-love -boston
© 2024 Wantedly, Inc. まとめ
© 2024 Wantedly, Inc. 今回話すこと • Prologは論理型プログラミング言語 • 古くは人工知能として持て囃された •
その実態は「単一化」と「バックトラック」を持つ特殊な手続き型 言語 • 現代では型推論器など記号処理タスクの実行エンジンとして 大いに役に立っている