# 『アンダースタンディング コンピュテーション』
- onwer todo
- repo に引っ越す
- repo https://github.com/mohira/understanding_computation
- motivation
- なんちゃらオートマトンとかをちゃんとわかりたい
- 計算理論とかちゃんと分かるふうになろう
## 関連
- [書籍紹介『アンダースタンディング コンピュテーション――単純な機械から不可能なプログラムまで』](https://magazine.rubyist.net/articles/0048/0048-BookUC_ja.html)
- [ko1/uc_ja: 書籍『アンダースタンディング コンピュテーション』のサポートリポジトリです。](https://github.com/ko1/uc_ja)
## 注意点
- 本書はRuby2.0対応。現時点(2023/09)でのRubyの最新版は3.2。
## 第1章 Ruby ひとめぐり
Rubyの基本文法なのでサラリと。特徴的なところだけさらう。
### Procオブジェクト
`f[x]`みたいな記述ができるから、かなり数式っぽい表現で書けて便利そう
```ruby
irb(main):001:0> -> x {x}
=> #<Proc:0x0000000102a991a8 (irb):1 (lambda)>
irb(main):002:0> f = -> x {x+1}
=> #<Proc:0x0000000102d18758 (irb):2 (lambda)>
irb(main):003:0> f.class
=> Proc
irb(main):004:0> f.call(1)
=> 2
irb(main):005:0> f[1]
=> 2
irb(main):006:0> f(1) # これはerror
(irb):6:in `<main>': undefined method `f' for main:Object (NoMethodError)
```
### モンキーパッチ
組み込みクラスに対してもモンキーパッチできる
```ruby
irb(main):016:1* class String
irb(main):017:2* def shout
irb(main):018:2* upcase + '!!!'
irb(main):019:1* end
irb(main):020:0> end
=> :shout
irb(main):021:0> 'hello'.shout
=> "HELLO!!!"
```
## 第Ⅰ部 プログラムと機械 第2章 プログラムの意味
- 計算のための3つの構成要素: 機械(Machine), 言語(Language), プログラム(Program)
- プログラム言語を**完全に**記述するためには2つ必要
1. 構文(syntax)
2. 意味論(semantics)
- 操作的意味論（operational semantics）
- わからん。抽象機械（abstract machine）ってなんぞ？
- 抽象機械とは、架空の理想化したコンピュータであり、ある言語で書かれたプログラムがどのように実行されるかを説明するために、特別に設計されたものです
## 2.3.1 スモールステップ操作的意味論
- わからん。簡約(reduce)と評価(evaluate)の違いはあるだろうけど、ちょっと謎。
- reduceは、手続きを1つ進めるみたいな感じ？
- evaluateは、これ以上reduceできない状態のやつ？
- 値(value)は専門用語！ 特殊な代数式
- 例: `(1x2)+(3x4)` → 簡約 →
- このとき `14` は 値(value)です
- valueとかいうものを定義することで、議論ちゃんとできるよねって感じ
- (日常では、ほぼ気にしないと言うか、かなりもっと雑な感じの定義で十分というか、まず困らない)
- rɪd(j)úːsəbl(米国英語), rɪˈdu:sʌbʌl(英国英語)/
- ざっくり「評価」ではなく、いちいち「簡約可能かどうか？」を考えることは、計算の規則を論じるときに便利ですね。なるほどね。解像度UPやんけ。
- 代入文(Assign)を簡約するという発想がなかった！
- else句が無い文法にも対応できる仕組みなるほどね。else句に«do-nothing»文があるという解釈にしているだけの話。それはそう！
- スモールステップ意味論においては、whileの簡約規則は、ifを使って簡単に実装できることに驚き！ 逆に、ビッグステップ意味論でどう実装するか、というか、他の簡約規則が全然思いつかん！ 気になる！
### «do-nothing»という何もしない文の重要性
- ex: 簡約可能である代入文が、簡約された(つまり、環境に変数が登録された)ときに、それが完了したことを意味するためにいるやつ。そういうこと！
- 気持ちとしては«do-nothing»は、EXIT_CODE=0みたいなように私はみています。
### `<<while>>`の簡約たのし〜〜〜
```ruby!
def test_while
# while (x < 5) { x = x * 3} | { x-> 1}
# -----------------------------------------
# if (x<5) { x=x*3; while(x<5) { x = x * 3 } } else {do-nothing} | { x->1 }
# if (1<5) { x=x*3; while(x<5) { x = x * 3 } } else {do-nothing} | { x->1 }
# if (true) { x=x*3; while(x<5) { x = x * 3 } } else {do-nothing} | { x->1 }
# x=x*3; while(x<5) { x = x * 3 } | { x->1 }
# x=1*3; while(x<5) { x = x * 3 } | { x->1 }
# x=3; while(x<5) { x = x * 3 } | { x->1 }
# do-nothing; while(x<5) { x = x * 3 } | { x->3 }
# while(x<5) { x = x * 3 } | { x->3 }
# -----------------------------------------
# if (x<5) { x=x*3; while(x<5) {x=x*3} } else { do-nothing } | { x->3 }
# if (3<5) { x=x*3; while(x<5) {x=x*3} } else { do-nothing } | { x->3 }
# if (true) { x=x*3; while(x<5) {x=x*3} } else { do-nothing } | { x->3 }
# x=x*3; while(x<5) {x=x*3} | { x->3 }
# x=3*3; while(x<5) {x=x*3} | { x->3 }
# x=9; while(x<5) {x=x*3} | { x->3 }
# do-nothing; while(x<5) {x=x*3} | { x->9 }
# while(x<5) {x=x*3} | { x->9 }
# -----------------------------------------
# if (x<5) {x=x*3; while(x<5) {x=x*3} } else { do-nothing } | { x->9 }
# if (9<5) {x=x*3; while(x<5) {x=x*3} } else { do-nothing } | { x->9 }
# if (false) {x=x*3; while(x<5) {x=x*3} } else { do-nothing } | { x->9 }
# do-nothing | { x->9 }
# -----------------------------------------
# while (x < 5) { x = x * 3} | { x-> 1}
expression = While.new(
LessThan.new(Variable.new(:x), Number.new(5)),
Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3)))
)
env = { x: Number.new(1) }
m = Machine.new(expression, env)
assert_equal [DoNothing.new, { x: Number.new(9) }], m.run
end
```
### `«while»`文の簡約は、SeqとIfでウマいこと表現されるのすごい
- «while» 文を簡約すると、条件や本体 を直接簡約せずに、条件文とシーケンス文を含んだ構文的により大きなプログラムになるのは興味深いところです。
- 確かに！
- 「whileを簡約したときに、whileが存在しないかたちに簡約されることを期待する」ってのは、わかるわ。
- whileを簡約するときに(無限ループでなければ)、ずーっとwhileが出てくるところの、テクニカルさというか、不思議感がすごいね。
### 意味論を変えることで、構文は同じだけれども実行時の振る舞いが異なる新しい言語を記述できるのです。
- たとえば、Rubyと同じSyntaxであるが、右から簡約するという規則の言語も作れたりするよね。それはそうだが、そういうことを考えたことがないのでメモっておきますね。
### ここまで読んでどうよ？
- 4hくらいで終わったけど、プログラムを理解する(？)のに、とても良い題材だと思いました。ホスト言語の知識が多少あれば十分。
- プログラミング言語がどのように実行されるのかとか、ちゃんと定義するとどうなるかを知るのにはとてもよさそう。
- テストコードは必須だ！
- 「ビッグステップ意味論」が一体何なのか！？ めっちゃ気になり。
- monkeyと違って、ASTを素で書くし、TokenizerやParserを作ってないから、意味にたどり着くまでが早い。これもよい。
## 2.3.2 ビッグステップ意味論
### 発見というかおさらい
- Expressionは、値を返すだけ。環境を返すことはないし、環境を変えることもない
- Statementは、環境を返す(変える)。
- で、スモールステップ意味論だと
- Do-nothingと環境をセットで返す
- で、ビッグステップ意味論だと
- 環境を返すだけ。Do-nothingがなくていいというか、なくなるというか、いつものプログラミング通りという感じ。
- そう考えると、式と文の区別がまた一段階わかってきた気がする
- Expressionは値を返すもの、Statementを値を返さないもの
- でもいいし、
- Expressionは環境に影響を及ぼさないもの、Statementは環境に影響を与え(う)るもの
- でも区別できる(Javaとかだとそう)
- ただし、Rubyとかになってくると、たぶん、すべてが式なので、この説明が怪しくなりそう。
### ビッグステップ意味論は、やりたいことをストレートに表現するというのが、スモールステップ意味論よりも得意ですね！
> 文がどのように動くのか、完結した話としてもっと直接的に説明できないのでしょうか
>
たとえば、「代入文ってどういう動きになるんですか？」という質問に対して、`Assign#reduce`、つまり、スモールステップ意味論で説明すると、相当難しいと思う。というか、「は？」ってなると思う。
```ruby=
class Assign
def reduce(environment)
if expression.reducible?
[Assign.new(name, expression.reduce(environment)), environment]
else
[DoNothing.new, environment.merge({ name => expression })]
end
end
end
```
一方で、ビッグステップ意味論(`#evaluate`)だと、非常に宣言的というか、そのまんまやんけ！ って説明になるよな〜。
```ruby=
class Assign
def evaluate(environment)
environment.merge({ name => expression.evaluate(environment) })
end
end
```
### 「反復ではなく再帰」とは → メソッド実行する人が誰？ 的な話
> 必然的に、これはプログラムの実行プロセスを、反復ではなく再帰（recursive）として見なすことになります。
>
スモールステップ意味論では、`#reduce`を呼び出すのは`Machine`であり、ExpressionやStatement本人じゃない！ 外部の人が必要なのが、反復みたいな気持ち。
ビッグステップ意味論では、`#evaluate`したときに、評価しつくすのが、ExpressionやStamement本人になる。オレ自身で、自己言及でやれるぜ！ ってのが、再帰みたいな気持ちだ。
### スモールステップ意味論では reducible かどうかを気にしていた！ が、ビッグステップ意味論では、気にしなくていい！
- スモールステップ意味論では
- NumberやBooleanは not_reducibleで、 `#reduce` を実装しなかったよね！？
- ビッグステップ意味論ではこう
- Number #evaluate -> Number
- Boolean #evaluate -> Boolean
- Expression #evaluate -> なにかの値
### 2.3.2.3 応用 スモールステップ意味論 と ビッグステップ意味論の違いを コールスタックの側面から考える
- スモールステップなら、1回潜る(#reduce)したから、抽象機械のループの場所に戻るから、コールスタックはとても浅い！
- ビッグステップだと、#evaluateしたその先で、また#evaluateして、またまた#evaluateしたら、1つ前の#evaluteの場所に戻るってことをしないといけないから、コールスタックが深くなる。
- 関数の中で関数呼び出しがあるのがめっちゃおおいからね。
で、だから何？
- 例: スタックの消費を抑えたいなら、きっとスモールステップのほうがいい。
- スモールステップなら、1回潜る(#reduce)したから、抽象機械のループの場所に戻るから
- ビッグステップだと、#evaluateしたその先で、また#evaluateして、またまた#evaluateしたら、1つ前の#evaluteの場所に戻るってことをしないといけないから、コールスタックが深くなる。
- 関数の中で関数呼び出しがあるのがめっちゃおおいからね。
- 例: プログラムの特性を証明したいなら、きっとスモールステップのほうがいい。
- スモールステップなら、途中の式がめちゃくちゃ見やすいし、計算過程の可視化をめちゃくちゃ実装しやすい
- 例: 実装しやすさや、記述の簡潔さ(宣言的な感じ)が大事なら、きっとビッグステップの方がいい
### SIMPLEをスモールステップ意味論とビッグステップ意味論で実装したけど、どうだった？
- 反復と反復の境界がよりはっきりした
- 式と文の境界がよりはっきりした
- 値が返る or 返らない
- 環境に影響がない or 影響がある
- そもそもスモールステップ意味論を明確に意識したことがなかったね！
- 違いをかなり比べた！
- 説明がだるい or 説明がスッキリする(宣言的)
- 計算規則が閉じている or 閉じていない的な感じ
- 抽象機械(Machine)いる or いらないじゃん！
- コールスタックが浅いor深い
- 実装のモチベーションによって、どちらの操作的意味論を採用するかを決める
## 2.4 表示的意味論
### 実装メタ言語と表示言語がどちらもRubyなので、頭をしっかり切り替える必要があります。
これは、まじで、そう！
SIMPLEはSIMPLEの世界でしかない。
たまたまSIMPLEの世界をRubyとかいう言語で実装してただけ！
実装したいやつの言語(to_rubyなのでRuby)と、ホスト言語が一致しているのは、知識が1つでいいけど、めちゃくちゃ切り替えがむずい！
### スモールステップ意味論 と ビッグステップ意味論 と 表示的意味論 は whileをみると違いがわかる！
逆に言うと、While以外の連中においては、`#to_ruby`と`#evaluate`はそっくりだった！ `.evaluate`を`.call(e)`に置き換えただけくらいの類似度合い。(ちなみに、スモールステップは最初から全然異なる形だった)
```ruby
class Sequence < Struct.new(:first, :second)
def evaluate(environment)
second.evaluate(first.evaluate(environment))
end
def to_ruby
"-> e { (#{second.to_ruby}).call( (#{first.to_ruby}).call(e) ) }"
end
end
```
で、whileは3つの意味論がぜんぜん違う。
```ruby
class While < Struct.new(:condition, :body)
def reduce(environment)
consequence = Sequence.new(
body,
While.new(condition, body)
)
[If.new(condition, consequence, DoNothing.new), environment]
end
def evaluate(environment)
case condition.evaluate(environment)
when Boolean.new(true)
self.evaluate(body.evaluate(environment))
when Boolean.new(false)
environment
end
end
def to_ruby
"-> e { while (#{condition.to_ruby}).call(e); e = (#{body.to_ruby}).call(e); end; e}"
end
end
```
Q. 違うのはわかったけど、だから何？
それぞれ、ちゃんと「意味」があるという気持ちがある。つまり、3つの観点があるから、いろいろ考えることができる！ 意味論を学んでいる感じがある。
どれも構文に「意味」を与えているのは同じだけど、アプローチが全然違う (えび)
### p.52 の 意味論のスタイルの比較の主張は激アツ！
Whileの話で考える(3つの意味論の違いが際立つから)。
スモールステップ操作的意味論(#reduce)をみても、 SIMPLEの`<<while>>`が、ループの挙動をするのはわからない！ ずるいツッコミかもしれないけど、抽象機械が、ずーっと、`#reduce`を呼び出してくれるから、`<<while>>`がループの挙動になるだけであって、スモールステップ操作的意味論の簡約の規則においては、`<<while>>`は`<<if>>`に簡約されるだけ！
一方、ビッグステップ操作的意味論(`#evaluate`)では、`self.evaluate`という事故の呼び出し、つまり、再帰がある。だから、いかにも「ループするぜ？」というのがモロに現れている(コードを読めばわかる)。
なんかさ、ここまでの話は言われてみればそうって感じだけど、こんなふうに考えること自体がすごいなーって思いました。
さらに！
表示的意味論では、そのままダイレクトに、Rubyの文法にしている。ので、Rubyのwhile文がわかるなら、SIMPLEの`<<while>>`も理解できる！
これは、英語のwalkと、フランス語のmarcheの話と同じ！ SUGOI
ところで、並行プログラミング入門の、π計算のところをよんでいて、「あー、ラムダ式で書いてくれればなあ〜」って思ったことがありました。これはまさに、表示的意味論が求められているということではないでしょうか！
## p.54 2.5 実際の形式意味論
### "本当"の形式意味論の重要なところ
> 形式意味論の重要な応用は、自然言語による仕様書や「実装による仕様」といった非形式的な仕様に頼らずに、プログラミング言語の意味にあいまいさのない仕様を与えることです。
これまでは、Ruby(=実装による仕様)に頼っていた！ で、それ自体はとても有用でした)。だけど、この節では、厳密なところにフォーカスしているよって話。
### 表示的意味論が、俺達にとって輝くときは、表示言語が理解できるものであるとき！(何らかの操作敵意味を持つ)
> 特に、表示佳意味 論が実際のプログラムの実行の手助けになるのは、表示言語が何らかの操作的意味を持つ場合に限ら れます。操
そりゃそうじゃんというかんじ。
表示規則が論理的に正しいものであっても、知らないものや、わけわからんものに変換されていたとしたら、それは、実際のところ、役に立たないよね。ってことだと思います。
逆に、ココまでの実装にように、(オレたちが理解できる)Rubyに変換されているようなものは、そりゃあ役立つじゃん？ そうだろ？
### 形式的な表示的意味論の具体的をみたいね
これとか役立つかも？
http://www2.toyo.ac.jp/~y-mizuno/Lang/pdf/proglang_09_semantics.pdf
序文が、対応してそう。
https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/96270/1/Tronso_35_16.pdf
### 用語のエイリアスはマジで助かる！
- スモールステップ操作的意味論
- 構造的操作的意味論（structural operational semantics） ← 微妙に違う意味かと思っていたが、同じ意味なので安心した
- 遷移意味論（transition semantics） ← 「簡約」を「(状態の)遷移」って表現したほうが良いでしょ派の人はたぶんこれ
- ビッグステップ操作的意味論
- 自然意味論（natural semantics）
- 関係意味論（relational semantics） ← これ、いみわからんw さすがに漠然としすぎでしょ！
- 表示的意味論(denotational semantics)
- 不動点意味論（fixed-point semantics）
- 数学的意味論（mathematical semantics）
### 他の意味論
公理的意味論（axiomatic semantics）【æksiəmˈæṭɪk(米国英語)】
あんまよくわからん
### パーサーがあると便利だけど、手動でのAST構築はやったほうが絶対いいと思う！
> `Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))` のような Rubyの式を手書きすることでSIMPLEプログラムの抽象構文木を構築してきましたが、 'x = x + 1' のようなSIMPLEのソースコードから、そのままパーサを使って構文木に変換できるとありがたい でしょう。
これは同意だけど、いきなりパーサーは、初心者にはおすすめしないよ！
ASTをいったりきたりするならいいよ！
### PEG(Treetop)の紹介で、whileをパースを例にしているのは、例の選び方が頭いいと思いました。
全部網羅しているから！
`while (x < 5) { x = x * 3 }` ← これね。
### Treetopで自分で書くのは今度にしょう！
ebiyoko会で見たし、ちょっと書いたら、このくらいのSKIPはええやろ！
## 3章 最も単純なコンピュータ
まずは、しょぼいコンピュータから始めようぜ！
## 3.1 決定性有限オートマトン
### 有限状態機械（finite state machine） と 有限オートマトン（finite automaton） は同じ意味だよ
へー
> 有限オートマトンには永続佳ストレージがなく、実のところ、RAMすらありません。
へー
> これは現在の状態という値1つを保持するだけのRAMを備えたコンピュータだと見なせる でしょう。
わかる
> 一度に1文字しか読めない外部入力ストリームを1つだけ持って います。
ほう。
オートマトンは
- 特定の状態で開始して、
- 入力ストリームから文字を読んでいきます。
- 文字を1文字読むたびに
- 規則にしたがって状態を移動していきます。
### 決定性有限 オートマトン（DFA：Deterministic Finite Automaton） は すごく単純ですね
わかるぞ！
### いいかんじ！
理解できたと思います！
あと、プログラミングの学習ステップとして、この本の解説順序や、小さな機能を1つずつ追加するスタイルは、とても良いと思います！ 良い本です。
## 3.2 非決定性有限オートマトン
### NFAの場合は、受理状態にいく可能性があれば「ある文字列は受理される」と考える
たどりつくパスがあればいい！
### その状態からのパスがない(==何も従うべき規則がない)ときは、受理されない
図3-5における `bbabb` がそう。
### 言語と正規言語
> 特定の機械が受理する文字列の集合は言語（language）と呼ばれ、この機械はその言語を認識すると言ったりします。
>
> すべての言語にそれを認識できる DFA や NFA が存在するわけでは ありませんが（詳細については４章を参照）、有限オートマトンが認識できる言語は正規言語 （regular languages）と呼ばれます。
### 「自発的に」という表現がいいね！
たしかに、これまで登場したオートマトンは、完全に、指示待ちキャラだったね！
### 自由移動(free move)では、「自発的に移動しない」も含意されてるっぽいぞ！？
別に、自分の状態に点線で表記することはなさそう。
### 自由移動がもっとあるときに、どれだけnilを読めば良いんだ？
課題として書いておく。
### 「不動点」、またお前かっ！
計算理論でめちゃくちゃよく出てくる概念！
定義はわかるし、(f(x)=xとなるx)
具体的なシーンにおいて、コレが不動点です、と言われたた、その例においてはまー、だいたいわかる。
が、そこでおわり。不動点ともっとなかよくなると、「あーそれね」ってなりそう。
> これは「自由移動にしたがって状態を追加する」関数の"不動点"を計算しています。
↑だから何？って思っちゃう(えび)
### 語彙！ この章で使っている用語の一部は慣習にしたがっていません！
- 有限オートマトンが読む文字は**シンボル**
- 状態間を移動する規則は**遷移（transition）**
- 機械を構成する規則の集合は、規則集ではなく**遷移関数（あるいは、 NFAの遷移関係）**
- 自由移動 は **ε遷移**。これは、空文字列の数学的シンボルはギリシャ文字のε（イプシロン）なので。
- 自由移動のある NFA は NFA-ε として知られています。
「自由移動」という語彙は、「ε遷移」よりもよっぽどニュアンスを表現していて良いと思うけどな〜。
なんていうか、意図的に語彙を変えているのは、攻めてるな〜とも思う。し、良い攻めだな〜って思う。
### 振り返り: DFA → NFA だし、めっちゃ制約を緩めた
- 遷移先が複数でもよい！
- 文字(シンボル)を受けつけなくてもよい！(図3-5の状態4; 遷移先がないやつね)
- 遷移する可能性があれば、受理としましょう！
- 勝手に動くことを許す！ 自由移動あらため、ε遷移。自我をもったオートマトン。
3.2の序文は回収している！
> 1つのやり方は、これまでの仮定や制約を少しずつ取り除いていくことです。
> まず第一に、決定性制約が制限になっているように見えます。
> 私たちはすべての状態ですべての可能な入力文字に関心があるわけではありません。
> 関心のない文字に関する規墟をなくしてしまい、想何外のことが起こると機械は失敗状態になる、と考えるのはどうでしょうか。
> より風変わりに、機械が矛盾する規則を持つことを 許して、複数の実行パスを可能にすると、どうなるでしょうか。
> 第二に、これまでは入力ストリームから読んだ文字に応じて状態を変更していましたが、何も読まなくても状態を変更できるとどうなるでしょうか。
もっと、ゆるめることはできる？
## 3.3 正規表現
# 未解決！ RUbyのtapメソッドの、tapの意味っって何？？？？？？ 調べといて！
水道の蛇口的なノリらしいという節
Sign in with Wallet
Connect another wallet