型理論 ラッセルのパラドックス: 「集合の集合」は矛盾を引き起こす。 ラッセル、ホワイトヘッド 「プリンキピアマセマティカ」

Slides:



Advertisements
Similar presentations
Maximal likelihood 法に基づく Matched filter について 田越秀行(阪大理) LCGT コヒーレンス解析 WG 修正 Ref: Finn, PRD63, (2001) Pai, Dhurandhar, Bose, PRD64,
Advertisements

2.5 プログラムの構成要素 (1)文字セット ① ASCII ( American Standard Code for Interchange ) JIS コードと同じ ② EBCDIC ( Extended Binary Coded Decimal for Information Code ) 1.
一階述語論理 (first-order predicate logic) 一階述語論理入門 構文論(論理式の文 法) 意味論(論理式の解 釈) 認知システム論 知識と推論(4) 知識と論理でを組み合わせて問題を解決する.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
人工知能特論2011 No.4 東京工科大学大学院 担当教員:亀田弘之.
人工知能特論2007 No.4 東京工科大学大学院 担当教員:亀田弘之.
密な演算子呼び出しで実現した 内部DSLの前処理による 実行速度改善の試み
Riding the Design Wave II
ラベル付き区間グラフを列挙するBDDとその応用
ソフトウェア基礎科学 授業資料: 論理関係(logical relations)のお話
知的インタフェース 例示によるプログラミング 予測インタフェース 制約インタフェース.
チュートリアル 形式的検証技術 Logical Framework と Modal Logic
プログラム理論特論 第2回 亀山幸義
プログラミングパラダイム さまざまな計算のモデルにもとづく、 プログラミングの方法論 手続き型 関数型 オブジェクト指向 代数 幾何.
充足不能性と導出原理 充足不能性の証明 スコーレム標準形 エルブラン解釈 導出原理 基礎節に対する導出 導出原理の完全性と健全性.
Survey: A Type System for Certified Binaries
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
Natural Semantics 実行過程の、最初と最後の状態(state)の関係を考える。
プログラム理論特論 第2回 亀山幸義
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
米澤研究室 全体ミーティング 2010/12/22 M2 渡邊裕貴.
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
論文紹介: A Second Look at Overloading
Solving Shape-Analysis Problems in Languages with Destructive Updating
数理論理学 第11回 茨城大学工学部情報工学科 佐々木 稔.
寄せられた質問: 演習問題について この講義の範囲に含まれる適切な演習問題が載っている参考書がありますか? できれば解答や解説が付いているものがあると良いのですが… 第3回の授業の中で、演習問題に取り組む方法を説明します.
PROGRAMMING IN HASKELL
“Purely Functional Data Structures” セミナー
プログラミング言語論プログラミング言語論 プログラムの意味論 水野嘉明
論文紹介 Query Incentive Networks
PROGRAMMING IN HASKELL
“Separating Regular Languages with First-Order Logic”
Macro Tree Transducer の 型検査アルゴリズム
国立情報学研究所 ソフトウェア研究系 助教授/
 型推論1(単相型) 2007.
依存型で型付けされた 副作用のある関数のための 型保存コンパイラ
Structural operational semantics
ATTAPL輪講 (第4回) 続 Dependent Types
論理と推論 命題論理 推論 命題論理体系の健全性と完全性 構文と意味 → 同値関係と標準形(節形式) 決定問題と意味木 推論規則
知能情報システム特論 Introduction
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
 型推論3(MLの多相型).
モデル検査(5) CTLモデル検査アルゴリズム
Type Systems and Programming Languages
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
国立情報学研究所 ソフトウェア研究系 助教授/
Type Systems and Programming Languages ; chapter 13 “Reference”
The Facilitative Cues in Learning Complex Recursive Structures
第7回  命題論理.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
PROGRAMMING IN HASKELL
プログラミング言語論 第10回 情報工学科 篠埜 功.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
述語論理式の構文と意味 一階述語論理式の構文 一階述語論理式の意味 述語,限量記号 自然言語文の述語論理式表現 解釈 妥当,充足不能
矛盾した知識 デフォルト推論 仮説を用いた推論 準無矛盾推論 デフォルト規則 デフォルト理論の拡張 → デフォルト証明 シナリオ
PROGRAMMING IN HASKELL
Eijiro Sumii and Naoki Kobayashi University of Tokyo
関数型言語の基礎 型なしl計算 型理論 構成的プログラミング GUIにあらわれる関数概念 PBD VL
18. Case Study : Imperative Objects
全体ミーティング 2010/05/19 渡邊 裕貴.
Haskell Programming Language
全体ミーティング(9/15) 村田雅之.
 型理論の初歩 2007 fall.
1.2 言語処理の諸観点 (1)言語処理の利用分野
プログラミング言語論 プログラミング言語論 演習7 解答と解説 演習7 解答と解説 1.
数理論理学 最終回 茨城大学工学部情報工学科 佐々木 稔.
Static Enforcement of Security with Types
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

型理論 ラッセルのパラドックス: 「集合の集合」は矛盾を引き起こす。 ラッセル、ホワイトヘッド 「プリンキピアマセマティカ」 プログラミング言語のコンパイル時チェック

型つきl計算 型 Type::= BaseType | Type → Type | Type ×Type BaseType ::=a | b | …    (基底型は型) l項 Var ::= v | Var ’ Term ::= Var | (Term Term) | (l Var:Type. Term)       | < Term, Term> 略記法は型なしと同様

型判定 型判定式 型推論法則

breduction

構成的プログラミング 型を命題と考え, と解釈すれば(Curry-Howard Isomorphism) 、 型つきλ項は述語論理の証明。 自動証明器にかければ自動的にプログラムができる? Martin-Lof, P. : Constructive mathematics and computer programming, in Logic, Methodology, and Philosophy of Science IV, Cohen, L. J. et al. eds., North-Holland(1982), pp.153-179.

型つきl計算の性質 無限の長さのb簡約列は存在しない (強正規化可能) 計算が必ず止まる 不動点演算子が存在しない

GUIにあらわれる関数概念 例示によるプログラミング (Programming by Demonstration, PBD) 作業の再帰定義 (Rule-Based) Visual Languages

Dependency Tree Data Structure

Fixpoint Operator on Dependency Tree

Fixpoint figure and its semantics = Fix/3: fixpoint figure of arity 3