はじめに
MOOCのedXでParadigms of Computer Programmingという講座を受けた。
感動というものを頭に走る電撃と定義するならば、 このCourseは自分にとって、まちがいなく最高の感動だった。
内容
感動的な講義の展開
プログラム言語のパラダイムやコンセプトが紹介される。
5つのパラダイムが紹介される。
- Functional Programming(関数型プログラミング)
- Object-Oriented Programming(オブジェクト指向プログラミング)
- Deterministic Dataflow Programming(決定性データフロープログラミング)
- Multi-Agent Dataflow Programming(マルチエージェントデータフロープログラミング)
- Active Object Programming(アクティブオブジェクトプログラミング)
感動すべきは、その講義の展開だ。
はじめに、すべてのBaseになる関数型パラダイムからスタート。
そして、関数型パラダイムに、 State(状態)という概念を追加することで、 オブジェクト指向パラダイムに発展させる！
また、関数型パラダイムに Concurrency(並行性)、Thread(スレッド)という概念をを追加することで、 決定性データフローパラダイムに発展させる！
そして、決定性データフローパラダイムに Port(ポート)という概念をを追加することで、 マルチエージェントデータフローパラダイムに発展させる！
最後に、オブジェクト指向パラダイムとマルチエージェントデータフローパラダイムを 融合させることで、アクティブオブジェクト指向パラダイムへ発展させる！
新しいパラダイムやコンセプトが紹介されるごとに、 価値観を覆す感動が自分の頭の中で電撃としてピリピリ走った。 めくるめく感動体験の連続である。
こんな体験はそうめったにできるものではない。スゴい！
情熱的なビーターバンロイさん
レクチャーをするビーターバンロイさんの語り口がとても情熱的だ。
語り口にも感動した。重要な概念になるたびに、 声の音程と強さがあがり、情熱的に語りかけてくる。感動に拍車をかける。
Oz(マルチパラダイム言語)と参考書について
Ozというマルチパラダイム言語を利用する。
個人的には、MozartがEmacsをベースにしているところがとてもよかった。Emacs最高！
しかし、Ozの文法がわからない・・。
情報元やサンプルコードが少なくて、文法を調べるのに苦労した。 概念的にわかっていてもその実装するための文法がわからず時間かかったり。 loopを書くのに2時間つかったり。参考書とforumでサンプルコード漁りまくった。
参考書
分厚くて重い。。900ページある。しかし、これがないと辛い。実はEnglishが一番難しい言語。
通称、CTM本、CTMCP本、ガウディ本というらしい。
感想
モチベーション
講座のなかでは、以下のような利点を強調してモチベーションをあげようとしている。
- いくつものプログラミング言語がある。全てを学ぶことは不可能。
- プログラミング言語はパラダイムで分類できる。
- パラダイム、そこから導出れるコンセプトを抑えることで、多くの言語を理解できる！
なるほど、利にかなっている。
今は、オブジェクト指向が全盛だが、その天下もいつまで続くかは分からない。
技術が進めばマルチコアや並列処理に対応するために、それに適した言語が必要になるかもしれない。 HTMLなんかは宣言的プログラミングの典型で、オブジェクト指向ではどうにもならない。
プロフェッショナルなプログラマを目指すのならば、 オブジェクト指向だけでなくて、他の考え方も知っておきたいところだ。
また高校生のころにこんな本を読んで、とても感激を受けた。
パラダイムを学び、そしてその考えに触れることで自分の価値観が揺るがされる。 新たな世界が見えるようになる。そんな知的興奮をパラダイムは与えてくれる。
実際は、、
講座は2月からはじまったのだが、他のことが忙しくてスケジュールどおりには進められなかった。
なので、4末に講座が終了したあと、5月のGWの休みに集中して一気に勉強した。
AssignmentやExamは締切り後に解いたりして、点数にはならず。それが残念。
プログラミング言語の分類学
プログラミングパラダイムを分類したポスターが以下のサイトからダウンロードできる。
- Classification of the principal programming paradigms
今まで3つのパラダイムしかしらなかった。
- Declarative Programming(宣言的プログラミング)
- Procedural programming(手続き型プログラミング)
- Object-Oriented Programming(オブジェクト指向プログラミング)
このポスターを眺めてみると、プログラミングの世界は広大であり、 自分は視野が狭かった、ほんの片鱗しか見えていなかったと思った。
そして、この講座で紹介されなかったパラダイムもまだまだたくさんあることに驚いた。 もっともっと、いろんな言語やパラダイムに触れたいと、強く思った。
ちなみに、最後にオススメ言語が紹介される。 よい言語は、広く様々なパラダイムをカバーしてていること。 その意味で、ScalaとErlangがオススメ、 C++とJavaもややマルチパラダイムだけどちょっとレガシー、だそうだ。
Coursereで紹介されたプログラムパラダイムのメモ
メモをとりながら、動画を見ていたのでそのメモ。
今まで、あまりメモはとらなかった。満員電車で動画を見ることが多かったので。 今回はGWに集中して取り組めたので、メモをとることはよいことだと思った。
以下、引用がほとんどのメモだけれども、内容が間違っているかもしれないので注意。
これはEmacs org-modeで階層的にメモをとった。 これからも、今回触れられなかったパラダイムを追加していき、 パラダイムツリーを生涯にわたって進化させていきたい。
プログラミングパラダイムとは
プログラミングパラダイムとは、プログラミングの分類方法、スコープ、見方。
なにかを定義しているようでなにもいっていない・・・詳しくはwikipedia参照。
Base Concepts
Valiables
変数の構成要素は以下の2つ。
- 識別子(Identifier)
- 格納域実体(Store entity)
Identifires and Store Entity
x = 1 ということはどういうことかを説明する概念。
数学的な写像関係で x = 1 を説明しようとしている。{ X -> x1=1 }みたいな感じ。 x1がメモリ上の実際の(束縛された)値で、Xがそれを指し示す識別子。
environments
識別子と変数の写像関係を環境という。
State
State(状態）とは、必要とされる計算の途中結果を含む、値の時系列。 (sequence of values calculated progressively, which contains the intermediate results of a computation)
状態の導入によって、プログラムに時間の概念を与える。
Declarative Programming
宣言型プログラミング。
第1の意味は、 処理方法ではなく対象の性質などを宣言することでプログラミングするパラダイム。 第2の意味は、 純粋関数型プログラミング、論理プログラミング、制約プログラミングの総称。
- 宣言型プログラミング - Wikipedia
- Imperative Programingの対になる概念。 "Function without State"
- Imperative vs Declaretive is also Stateful vs Stateless
HTMLはStateless、Declarative Programming language. 状態はクッキーを導入してしばしば実現する。
Functional Programmming
Impliclite(declarative) State
暗黙的状態。宣言的状態ともいう。
- 関数の実行結果が値をもつ
- 同じ入力には必ず同じ出力を返す。
- Explicite Stateとの対概念。
- 参照透明性。
Higher-order programming
高階プログラミング。procedure valueをサポートしている言語でのプログラミング技術。 関数を引数としてわたす能力。
Rubyではlambda, procなど。C言語には関数ポインタがある。C言語は2階。
Recursion
再帰的プログラミング。
accumulater
C++の、numericライブラリ(accumuulateなど)で利用されている。
スタックのサイズが均一なことが特徴的。
tail-recursion
末尾再帰。
その中にただ1つの再帰呼び出しがあり、 かつその呼び出しが手続き本体の最後にあるもの。
invariant programming
不変式プログラミング。再帰的に呼ばれる度に、数学的に真になる式。
Imperative Programming
命令型プログラミング。 計算をプログラム状態を変化させる文の列で記述するパラダイム。
Imperative Programmingとは、Function paradigmにCellの概念を加えたもの。
- Declarative Programingの対になる概念。 Imperative vs Declaretive is also Stateful vs Stateless
Imperative programming = Function paradigm + Cell
- 実行するたびに、内部の状態によって結果がことなる。
- 手続き型と同義のこともある。(Procedural programming)
手順やチェックリストはプログラムではないが、 命令型プログラミングのスタイルに似たコンセプトである。 それらのステップが命令であり、実世界が状態を保持している。
- 械語は命令から構成される
低レベルから見た場合、 プログラムの状態はメモリの内容によって定義され、文としては機械語の命令が相当する。
Explicite State
明示的状態。
- 生存期間が2度以上の手続的呼び出しに渡るような一つの状態。
- 関数の実行の中に値をもつ。
- 手続きの引数に現れないもの。
同様なことを関数型パラダイムで実現するためには、仮引数に状態を持たないといけない。
Cell
Explicite State(明示的状態)を表す基本型。二つの構成要素からなる。
- 名前値(Vaiue)
- 単一代入格納域への参照(Identifier)
Function ParadigmsとImperative Paradigmの違いは、
- Function
- 状態変化しない(Immunity)
- 機能追加時にインタフェースの変更の影響度がおおきい。
- Inperative
- 機能追加時にインタフェースの変更の影響度がない。(モジュール性, モジュールプログラミング）
- 状態変化する。
Structured programming
構造化プログラミング。
構造化プログラミングではプログラミング言語が持つステートメントを 直接使ってプログラムを記述するのではなく、 それらを抽象化したステートメントを持つ仮想機械を想定し、 その仮想機械上でプログラムを記述する。 普通、抽象化は1段階ではなく階層的である。 各階層での実装の詳細は他の階層と隔離されており、 実装の変更の影響はその階層内のみに留まる(Abstract data structures)。 各階層はアプリケーションに近い抽象的な方から土台に向かって順序付けられている。 pこの順序は各階層を設計した時間的な順番とは必ずしも一致しない(Concluding remarks)
標準的な制御構造のみを使い、 プログラム全体を段階的に細かな単位に分割して処理を記述していく手法。
「制御の流れ」を構造化しただけであり、 「データ構造」には何の制限や規則も設けていない。
「芸術品」から脱却して「工業製品」へ遷移すること、 あるいは、「処理性能重視」から「保守性重視」へ向かったもの。 別の見方をすれば、処理効率を犠牲にして、作りやすさや理解容易性を求めたもの。
三つの構造化文
ダイクストラが提唱。
- 順次
順接、順構造とも言われる。 プログラムに記された順に、逐次処理を行なっていく。 プログラムの記述とコンピュータの動作経過が一致するプログラム構造である。
- 反復
一定の条件が満たされている間処理を繰り返す。
- 分岐
ある条件が成立するなら処理Aを、そうでなければ処理Bを行なう。
Object-Oriented Programming
Data abstraction
データ抽象。3つの構成要素がある。
- Input
- Output
- Interface
データ抽象は内部と外部からなるプログラムかつ、両者がインターフェースを通じてやりとりするもの。
A data abstraction is a part of a program that has an inside, an outside, and an interface in between The inside is hidden from the outside.
Input/Output
内部は外部からは隠蔽されている。-> カプセル化という。
The inside is hidden from the outside
Interface
The interface is a set of operations that an be used according to certain rules.
データ抽象には、主に二つの方法がある。
- Abstract Data Type(ADT) keeps values and operations separate.
- Object groups together value and operations in a single entity.
Encapsulation
プログラムと内部と内部をインタフェースで分けること。
カプセル化のメリットは大規模開発をシンプルにする。
- 正しさを保証する。
- 複雑さを解消する。
Abstract Data Type
抽象データ型。ADTと略されることも。
構造化プログラミングは仮想機械モデルに基づく段階的詳細化法（stepwise refinement）をもたらしたが、 データ構造の変更を行うと変更部分がソースコード中に散在してしまうという弱点があった。 データ抽象の概念はその欠点を補完するものであった
An ADT consists of a set of values and a set of operations.
- Integer型
- Value:1,2,3
- Operation:+
- Stack型
- Value: elemtent
- Operation: push, pop, .
ValueとOperationそれ自体はStateを持たない。
CTM, p433
Diference between ADT and Object。Stackをつかった実装の違い。
- ADT
local Wrap Unwrap in {NewWrapper Wrap Unwrap} fun {NewStack} {Wrap nil} end fun {Push W X} {Wrap X|{Unwrap W}} end fun {Pop W X} S={Unwrap W} in X=S.1 {Wrap S.2} end fun {IsEmpty W} {Unwrap W}==nil end end
この手法はStateful ADTという。
そして、C言語では、こうやってデータ抽象化を行うことがおおい。 もちろん関数ポインタ配列を使えばC言語でもObjectをつくることができるが、 実際にはそこまでやらない。(面倒)
- Object
オブジェクトでは、データに対する操作はプロシージャ変数として扱われることに注目。
fun {NewStack} C={NewCell nil} proc {Push X} C:=X|@C end proc {Pop X} S=@C in X=S.1 C:=S.2 end fun {IsEmpty} @C==nil end in stack(push:Push pop:Pop isEmpty:IsEmpty) end
オブジェクト指向言語は、 単にObjectをサポートする言語ではなくて、Abstruct Data Typeも強力にサポートしている。
ObjectとADTの意味がごっちゃにつかわれているのが現実の現状。
Object
値と操作をひとつのまとまりとしたもの。以下の構成要素をもつ。
- 値 ・・・Explicite State(明示的状態)
- 操作 ・・・Procedural Data Abstruction(手続的データ抽象)
以下の能力を備えている。
Data Abstruction
オブジェクトは内部と外部はインタフェースを通じてやりとりされる。
内部の明示的状態をAttributes,インタフェースをMethodsという。
Procedure Dispatch
オブジェクトは単一なエントリポイントをもつ。(エントリポイント = 呼び出し口) エントリポイントに渡される引数をメッセージという。
下の例だと、Counterがエントリポイント。エントリポイントにinc,getメッセージを送る。
{Counter inc}
{Counter get(X)}
エントリポイントから、メッセージに対応するプロシージャが呼びだされる。
メッセージとプロシシージャはあらかじめDispatch(バンドリング)されている。
Instantiation
オブジェクトは一つのメソッドで、 異なる属性をもつ複数のオブジェクトを生成できる。
この能力をInstantiation(インスタンス化）という。
Classes
メソッドと属性を定義する特別なシンタックスをClassという。
属性とメソッドはレコードデータ構造によって管理されているだけである！
Classという概念によって、オブジェクトの"宣言"と"生成(new)"を分離する。
Polymorphism
Inheritance
継承。あるオブジェクトが他のオブジェクトの特性を引き継ぐこと。
Exceptions
例外。プログラムがある処理を実行している途中で、 なんらかの異常が発生した場合に、 現在の処理を中断（中止）して、別の処理を行うこと。 その際に発生した異常のことを例外と呼ぶ
よくある2つの概念。
- try ・・・ 例外ハンドラをもつ例外補足コンテクストを生成。
- raise・・・ もっとも内部の例外補足コンテキストへjampし、そこにある例外ハンドラを起動。
各コンテキストはスタックで管理され、tryはスタックの１つにmarkerをつける。 raiseはmarkerにジャンプしてmarkerの場所に例外処理のコンテキストを挿入する。
CTM p93参照。
例外をつかわないと、コンテクストごとの結果を検証必要があり、 case文が乱立するうんこコードが出来る。
Concurrenct Programming
複数の相互作用を及ぼす計算タスクの（同時）並行的実行をおこなうパラダイム。
平行プログラミング。(並列プログラミングではない)。
Multiple progressing activities that exist at the same time Activities that can communicate and synchronize
- Communicate: information passes from one activity to another
- Synchronize: an activity waits for another to perform a specific action
平行プログラミングには3つの代表的なパラダイムがある。
- Detarministic Dataflow
- Message-passing concurrency(Erlang and Scala actor)
- Shared-State concurrency(Java monitors)
その他、並列実行の競合をさけるためには、以下ようなパラダイムもある。
- Lazy Deterministic Dataflow
- Constraint Programming
Detarministic Dataflow Programming
決定性データフロープログラミング。
関数型パラダイムをべースにしている。
スレッド処理、時間経過をともなうのにも関わらず、実行結果はつねに一定！ これが、Deterministicと名づけられた所以。
Deerministic is not Obsarbable.
アイデア自体は70年代に提示されたアイデアのに、今まで忘れ去れれていた。
- MultiCore, ManyCore Processing (マルチコア、メニーコア)
- Destributed Computing
- Concurrent Deployment
- BigData Computing
以上のようなキーワードとともに、 21世紀の今こそ注目をあびるべき、次世代プログラミングパラダイム！ （とピーターバンロイさんがいっていた）
CTMCP, Chapter 4
Detarministic Dataflow
Unbound Value
メモリ上に値が存在しないが、宣言された変数。
- C/C++では、ゴミ(不定データ)が格納されている。
- Javaは0初期化されている。
- Prologは実行時にエラー終了する。
- Ozは値がbindされるまでまちあわせる。
DataFlow Value
Unbound Valueがbindされるまでプログラムの実行を待ち合わせるような宣言的変数。
Bindされたときの実行を Dataflow Executionという。
このデータフロー変数によって、No Race Conditions(非強豪状態)を実現する！ (これがもっともこのパラダイムで大事)
Threads
プログラムの処理の単位(Thread of Program)
- Each thread is sequential.
- Each thread is independent of the others.
- Two threads can communicate if they share a variable
WikipediaではCPUのひとつの処理単位と定義されている。
Streams
リストの終端がUnbound Variableであるもの。
Streamsは2つのThread間の通信チャネルとして利用できる。
Streamの構成要素は以下。
- Producer ストリームのデータを生成。
- Consumer Producerから生成されたストリームのデータを受け取ってアクションを起こす。
- Transformer ProducerとConsumerとの間を仲介する。
- Pipeline ProducerとConsumerとTransformerの間を仲介する。
単一格納変数(single-assined value)の性質（一度しか代入できない) を同期のスレッド間通信のための手段にする。
平行スレッドのなかでStreamを読み書きするものをAgentsという。
Produce ----------> Transformer --------> Consuemer
NonDeterminism
非決定性。プログラムの実行結果を決定ことができるシステムの能力。
Nondeterminismはmanagedされることが必須！ しかし、制御がとても難しい。 だからこそ、Determinismが重要なのだと。
Scheduler
どのスレッドを実行するかを決める、システムの一部をスケジューラという。
Concurrency Transparency
concurrency for dummies
平行性のためのダミースレッド。
平行透過性のためには、いくらスレッドを動的に追加しようとも、削除しようとも、 最終的に得られる結果はかわらない(Deterministic!)
それは、スレッドの各処理をincrementalに動作させることで可能となる
Multi-agent dataflow programmming
マルチエジェーントデータフロープログラミング。
Concurrency を解決するためのいろいろなパラダイムのなかで、 最強のパラダイムがこれだとピーターバンロイさんはいう。
なぜなら、Deterministic Dataflow Programmingをベースに、 NonDeterminismの制御を機能追加したから。
(Deterministic Dataflow Programmingに、Portという明示的状態をくわえた)
Distributed Systemともいう。
CTMCP, Chapter 5
Port
ボート。Named Steram.名前のつけられたストリーム。
以下の操作をもつ、Abstruct Data Structure。
- Port Creation
- Message Sending
- Asyncronize
- Syncronize
Agents
通信モデルは大きく2つに分けられる。
- Client-Server Architectures
- Pear-to-Pear Architectures
Client,Server,PearをAgentという。
以下の構成要素をもつ。
- have identity . mail address
- recieve messages . mailbox
- process messeges . orderd mailbox
- reply to messeges . pre-addressed return letter
エージェントは独立実体で、自身の局所的な目的を目指して仕事をする。 相互作用が適切に設計されていればエージェントは大局的仕事も達成する。
CTMCP, Chapter 5より。
Agentをもちいるプログラミングを、 Object-Oriented Programmingと対比されて、 Agent-Oriented Programmingということもある。
ただし、Agentは必ずしもObjectでなくてもよい。2つのうちのどちらか。
- Object
- Transition state-functions
Coordinator
AgentのなかでほかのAgentをまとめるAgentをCoordinatorという。以下の性質をもつ。
- 代理性 ・・・他のAgentの代理をして処理をおこなう。処理の結果をAgentに通知。
- 知性 ・・・ 他のAgentから情報をあつめを代表して判断を下す。
- 移動性 ・・・他のAgentを代表して判断を下す。
Master(Coordinator)-Slave Archtecture.
Stateless Agent
あるメッセージを受信したときに、そのメッセージに応じてアクションをとるAgents. アクションは受信メッセージに依存する。
Agentはひとつのスレッドと複数のポートをもつ。ボートは明示的変数(Cell)と同義。
このPort以外はImmutableなデータ構造。Portのみがメモリ上に確保される。
State with Agent
ポートの他にState(明示的状態)をもつこともある。
処理の実行自体はStreamデータ構造に入ったfunctionのプロシージャごとに実施する (Immutable and incremental)が、StateによってReplyの方法を変える。
Protocol
BroadCast
他の複数のエージェント(Multi-Agent)に通信を送る。
Contract Net
Ozma
Multi-agent dataflow programmmingを実現するための言語。ScalaとOzを合体させた。
ピーターバンロイさん直々の説明動画は以下で見れる。
github repository.
Active Objects Programming(Object-Based Agent)
オブジェクト指向におけるオブジェクトを、 自ら判断し処理できる機能を持ったエージェントと呼ばれるモジュールに 置き換えたもの。
Object-Oriented Programming とMulti-Agent Programmingの2つのパラダイムを 合体させてできたパラダイム。
オブジェクトの属性ではなくて振る舞いが重要視される。
EnglishのWikipediaに OOPとAOPの対応比較表がある。