吉田武, 素数夜曲¶
Schemeコード¶
メモ¶
プログラミング言語の発見¶
\hyperref[toc]{【目次へのリンク】} \setcounter{tocdepth}{2} \localtableofcontents
はじめに¶
ここでは集合論などいくつか関連する数学の議論があります. 公理的集合論に関する議論についての詳しい議論はそちらまたは本に任せ, このノートではプログラミングに関わる議論に集中します.
A.1無からはじめる¶
数学でいう$0$の代わりに何もないリスト(空リスト)として()を導入します. Haskellでの空リストは[]です. 空リストは空集合\index{くうしゅうごう@空集合} (empty set)とみなせます.
A.1.1無から括弧へ¶
Lisp系の言語では空リストはnilとしても使われます. これはtrue, falseのfalseを表す概念としても転用されます.
先程空リストは空集合とみなせるとも書きました. これを使うと$0 = ()$, $1 = (()) = (0)$としてフォン・ノイマン流の自然数の構成につながります.
A.1.2括弧から自然数へ¶
数2は2 = (1 0) = ((()) ())と書けます. これより大きい数も同じように再帰的に定義します.
0 = ()1 = (0)2 = (1 0)3 = (2 1 0)4 = (3 2 1 0)
このあたりはプログラミング言語の基礎概念といったテーマや本で詳しく議論されています.
プログラミング言語が配慮するべき対象として次の段階的な区分があります.
- 無意味な対象: meaningless
- 意味はあるが間違っている対象: meaningful & incorrect
- 正しい意味と結果を持つ対象: meaningful & correct
それぞれ次のような例があります.
)(3=(1+*2)2+3=11+2=3
A.2裏で支える集合論¶
構成的に集合論を展開するとき基礎にする概念・記号が必要で, それが空集合です. この意味で「初めに空集合が在った」と言えます.
先の数の構成を集合論の形式に持っていくのも簡単です. 形式的に丸括弧を中括弧に置き換えて空集合は{}と表します. 数学ではふつう空集合には記号$\emptyset$をあてます.
A.2.1集合の定義¶
集合論では集合を無定義語として採用します. そして属す・属さないという帰属関係が二つの集合の関係を規定します. 特に数学では集合$a$が$A$に属することを$a \in A$, 属さないことを$a \notin A$と書きます.
A.2.2要素から対へ¶
ふつう集合は具体的には異なる要素の順序を問わない並びとして表します. 特に外延記法と呼びます.
二つの要素$a,b$を持つ集合$\setone{a,b}$を特に対と呼びます. 対の存在は対の公理と呼ばれます. 対で$a=b$のとき$\setone{a,a} = \setone{a}$と書き, これを\coloredtextbf{シングルトン}\index{しんぐるとん@シングルトン} (sigleton)と呼びます.
シングルトン$\setone{a}$に対して $a$は集合$\setone{a}$の(ただ一つの)要素である一方, $\setone{a}$は$\setone{a}$の要素ではありません. 特に$a \in \setone{a}$かつ $\setone{a} \notin \setone{a}$です.
A.2.3対から順序対へ¶
リスト内包表記のようにプログラムの文脈でも出てくるので簡単にコメントしておくと, 内包は対象の性質を説明する手法で, 外延は対象を具体物として例示する手法です. 集合で言えば$\set{n}{n\text{は偶数}}$のように書くのが内包, $\setone{0,2,4,\cdots}$のように具体的に書くのが外延です.
ここでは順序対を$\opair{x,y}$と角括弧で書いています. 順序対の実装法はいくつかありますが詳しい議論は省略します. 大事な性質は順序対の等号$\opair{a,b} = \opair{c,d}$は $a = b$, $c = d$と定義されることです.
A.3集合を操る¶
ここまでは集合の要素, 要素の組としての対を与えて思考の対象を増やしてきました. 次は与えられた対象の\coloredtextbf{計算}, 特に和集合(合併)と共通部分を考えます. これらについて詳しくは\ref{expedition02314}節を参照してください.
A.3.1合併¶
集合$A,B$は$\cup$の\coloredtextbf{前置記法} (prefix notation)を使って \begin{align} \bigcup \setone{A,B} \end{align} と書きます. 言われてみると確かに前置記法による演算記号・定義で, Scheme・Lispの視点からは基本的です.
プログラミングとしても大事なので一つ例を考えましょう. 集合$A = \setone{a_1, a_2}$, $B = \setone{b_1, b_2}$に対してこの和集合は \begin{align} \bigcup \setone{A,B} = \bigcup \setone{\setone{a_1, a_2}, \setone{b_1, b_2}} = \setone{a_1, a_2, b_1, b_2} \end{align} です. Schemeでは(append '(:a1 :a2) '(:b1 :b2))を実行すると求める (:a1 :a2 :b1 :b2)が得られます.
ここでのポイントは(:a1 :a2 :b1 :b2)と((:a1 :a2) (:b1 :b2))の違いです. 数学で言えば$\setone{a_1, a_2, b_1, b_2}$と $\setone{\setone{a_1, a_2}, \setone{b_1, b_2}}$の違いです.
ちなみに和集合は$\bigcup \setone{A,B} = \setone{A} \cup \setone{B}$と\coloredtextbf{中置記法} (infix notation)で書くこともあります.
A.3.2共通部分¶
共通部分は和集合を上下反転させた記号 \begin{align} \bigcap \setone{A,B} = A \cap B \end{align} と書きます. 本にはSchemeと順序対に関する大事な指摘があります. ここでは必要なときが来たら触れることにして先を急ぎます.
順序対は要素の並び順を保てる大事なデータの保管庫です. 各データにアクセスするには順序対の共通部分と, そこから定義される差集合をうまく使って議論します. Schemeでいうcarとcdr, Haskellでいうheadとtailの姿が見えて面白いところです.
A.4命題と論理式¶
計算機を理解する上で大事なのは論理から集合, 集合から現実へのパスをきちんと理解することが計算を理解するポイントだそうです. 計算機にできることは何か, 具体的な回路にできることは何か, 計算で現実を再現できるか, こうした問題を論理の問題として議論するのが大事です.
TODO A.4.1命題¶
命題は「客観的に検証可能な陳述(statement)あるいは主張」を指します.
- TODO この定義確認.
- 真偽
- 排中律
- 二値原理
- 公理
- 原子式(原子論理式?)
- 論理式
A.4.2命題論理¶
- 述語
- 論理結合子: 否定・論理和・論理積・含意
- 古典命題論理
A.4.3論理式の意味¶
- 排他的論理和
- ベン図
- 逆・裏・対偶
- 恒真式
A.4.4万能結合子¶
- ド・モルガンの法則
- シェーファーの棒(Sheffer stroke)は$P | Q = \lnot (P \land Q)$
A.5自然数の構造¶
- 無限公理
- 空集合の存在公理
A.6 再帰による定義¶
- 無限に直接触れずに無限にまで行き渡る
A.6.2自己言及の定式化¶
A.6.3括弧と自然数¶
A.7関数とラムダ記法¶
A.7.1関数の定義と記法¶
A.7.2ラムダ記法¶
記法$x \mapsto ax+b$の代わりに $\lambda x.ax+b$と書く記法を指します. 一般化すると $x \mapsto f(x)$と$\lambda x.f(x)$が等価です.
関数への代入は $(\lambda x. ax+b)2 = 2a+b$と書きます. 文字$a$も変数とみなしたいときは, 例えば $(\lambda a. (\lambda x. ax + b)) (3 2) = 6+b$と書きます. これについてカリー化のような概念も関係します.
A.7.3ラムダの来歴¶
次のような経緯だそうです.
- 変数への強調として文字上に二行にわけてハットをつけて$\hat{x}(x+1)$のように書いた.
- 一行にするべく$\wedge x (x+1)$と書いた.
- 類似のギリシャ文字の大文字の$\Lambda$で$\Lambda x(x+1)$とした.
- 記号の混同を避けるために小文字で$\lambda x (x+1)$とした.
A.8リストから始まる¶
ここではSchemeまたはLispの視点から説明します. 集合論での順序対を基礎に対象をスペース区切りで並べて(2 1 0)のように書いた対象がリストです. これを実際のScheme上でデータとしてのリストとみなすには'(2 1 0)とシングルクォートを先につける必要があります. これは先頭のシンボルを関数名とみなすルールがあるからです. 実際にプログラムを書くときには注意してください.
ここで先の(2 1 0)の2はheadと呼び, それ以降の部分である\coloredtextbf{リスト}(1 0)をtailと呼びます. これらはそれぞれcarとcdrで取れます. 他の言語, 例えばHaskellではcarはhead, cdrはtailという関数になっています.
二つの要素を括弧でくくることにあたる関数をconstructから取ってconsと呼びます. 関数としてもconsです. \myquotefile{primenocturne/scheme/37501.scm}
A.9 LISP is not LISt Processor¶
A.9.1 S-表記¶
このSはSymbolicのSです. 再帰的に定義します. この本, アトムと(空)リストのきちんとした定義がないようなので, 適当なタイミングで追記します.
- 基底部: アトムと空リストはS-表記である.
- 再帰部: もし$e_1,e_2$がS-表記ならば$(e_1 \cdot e_2)$もS-表記である.
このデータ構造はS-式と呼ばれる方が多いように思います.
TODO・メモ: 定義が雑で読むに堪えないので, 大事そうな要素・言葉・概念のメモとプログラム部分だけ読もう.
文字の代わりに使う数として素数を使うとよいという話が書いてある. ちょっと採用してみよう.