Microsoft PowerPoint L02-Introduction-students ( )

Transcription

1 プログラミング言語論 A (Concepts on Programming Languages) 趙建軍 ( チョウ ) (Jianjun Zhao) of Programming Languages.html 1 第 2 回 講義の紹介 (Introduction)

2 講義内容と目的 目的 プログラミング言語に関するアイデアを一通り習得すること 内容 プログラミング言語パラダイム プログラミング言語の諸要素 プログラム理論 プログラムの意味論 3 プログラミング言語の分類 (1) 記述と抽象度のレベル (Abstraction) 機械語 アセンブリ言語 高級言語 4 2

3 プログラミング言語の分類 5 プログラミング言語の分類 (2) 実行の形式 コンパイラ言語 インタプリタ言語 スクリプト言語 6 3

4 Phoenix + Tools : 10kft View Designer Modeler Browser Formatter Obfuscator Refactor Lint Visualizer Editor+ Xlator Profiler Security Checker Phx APIs Phx APIs C# C++ Core Program Representation [ AST+] Custom Extended Pgm Rep [AST++] I/O Sync Trans mgr Master Program DB + Profiles VB J# Readers: CIL, MSIL, HIR, x86 Phx Core Lib Core structures, Utils; AST, CodeGen Srvcs HL Opts HL Opts HL Opts Retarget LL Opts LL Opts LL Opts Code Gen EXE Native Image HIR LIR 7 プログラミング言語の分類 (3) 用途 科学技術計算用言語 ビジネス用 人工知能用言語 ネットワークプログラミング用 特殊用途用 ( シミュレーション用 データベース管理 ) 8 4

5 プログラミング言語の分類 (3) 9 プログラミング言語の分類 (4) 10 5

6 プログラミング言語の分類 (5) 命令型プログラミング言語 (Imperative) 手続き型 Procedural オブジェクト指向型 Object-oriented スクリプト型 Scripting C, Ada, Pascal, Algol, FORTRAN,... Scala, C#, Java, Smalltalk, SIMULA,... Perl, Python, PHP, プログラミング言語の分類 (5) 命令型プログラミング言語 (Imperative) 手続き型 Procedural オブジェクト指向型 Object-oriented スクリプト型 Scripting C, Ada, Pascal, Algol, FORTRAN,... Scala, C#, Java, Smalltalk, SIMULA,... Perl, Python, PHP,

7 プログラミング言語の分類 (5) 命令型プログラミング言語 (Imperative) 手続き型 Procedural オブジェクト指向型 Object-oriented スクリプト型 Scripting C, Ada, Pascal, Algol, FORTRAN,... Scala, C#, Java, Smalltalk, SIMULA,... Perl, Python, PHP, プログラミング言語の分類 (5) 宣言型プログラミング言語 (Declarative) 関数型 Functional 論理型 Logic データ流れ Data-flow Haskell, SML, Lisp, Scheme,... Prolog, KL1,... Id, Val,

8 プログラミング言語の分類 (5) 宣言型プログラミング言語 (Declarative) 関数型 Functional 論理型 Logic データ流れ Data-flow Haskell, SML, Lisp, Scheme,... Prolog, KL1,... Id, Val, プログラミング言語の分類 (5) 宣言型プログラミング言語 (Declarative) 関数型 Functional 論理型 Logic データ流れ Data-flow Haskell, SML, Lisp, Scheme,... Prolog, KL1,... Id, Val,

9 歴史 (History) 時期 プログラミング言語 Experimental use of expression compilers FORTRAN, COBOL, LISP, Algol APL notation, Algol 60 (revised), SNOBOL, CPL APL, SNOBOL 4, FORTRAN 66, BASIC, SIMULA, Algol 68, Algol-W, BCPL Pascal, PL/1 (Standard), C, Scheme, Prolog Smalltalk, Ada, FORTRAN 77, ML 17 歴史 (History) 時期 プログラミング言語 Smalltalk-80, Prolog, Ada C++, SML, Haskell Ada 95, TCL, Perl Java C#, Python, Ruby, Scala Go, R,

10

11

12 23 Quiz Time! 24 12

13 von Neumann ( ) Home Country: (1) Russia (2) Hungary (3) Germany von Neumann is (1) Mathematician (2) Computer Scientist (3) Economist 25 von Neumann ( ) Home Country: (1) Russia (2) Hungary (3) Germany von Neumann is (1) Mathematician (2) Computer Scientist (3) Economist 26 13

14 パラダイム (paradigm) In science and philosophy, a paradigm is a distinct set of concepts or thought patterns, including theories, research methods, postulates, and standards for what constitutes legitimate contributions to a field. 27 パラダイム (paradigm) パラダイム (paradigm) とは 科学史家 科学哲学者のトーマス クーンによって提唱された 科学史及び科学哲学上の概念 一般には 模範 範 を意味する語である トーマス クーン : 科学革命の構造 (The structure of scientific revolutions) ( パラダイム転換 ) 28 14

15 Programming Paradigm Programming paradigms are a way to classify programming languages based on the features of various programming languages. Languages can be classified into multiple paradigm 29 プログラミング言語パラダイム (1) プログラマにプログラムの見方を与えるものと言える 例えば : オブジェクト指向プログラミングにおいて プログラムとはオブジェクトをつくりそれを管理するものである 関数型プログラミングにおいては 状態を持たない関数の評価の連続である 30 15

16 プログラミング言語パラダイム (2) 命令型言語パラダイム 関数型言語パラダイム 論理型言語パラダイム オブジェクト指向型言語パラダイム 31 プログラミング言語パラダイム (3) 32 16

17 プログラミング言語パラダイム (3) 33 計算モデルの必要性 世の中の情報システム ( コンピュータや生物 ) は非常に複雑 この情報システムがどのような原理に基づくかを知るには数学的基盤を持つ抽象的な枠組みを導入する必要がある 34 17

18 計算モデルの必要性 計算機のハードウェア 複雑すぎて扱えない C や Pascal などで書かれたプログラム 数学的な厳密さを持つとは限らない プログラムを入力から出力を得るものとする 例 : 数学的な関数 ただし 実際に入力を与えても その答え ( 出力 ) が導けるとは限らない 35 計算モデルとは コンピュータによる計算機構を抽象的に捉 ( とら ) えた数学的な枠組みであり, これにより計算に関する様々な議論が可能になる 計算するとはどういうことであるかの説明 計算モデルが変わるとプログラミング言語の設計も変わる プログラミング言語パラダイムの最重要かつ主要な構成要素 36 18

19 計算モデル 情報システムの抽象的な枠組み = 計算モデル 37 代表的な計算モデル ( 逐次 ) 計算モデル 抽象機械計算モデル 関数型計算モデル 論理型計算モデル 項書き換え型計算モデル ( 並列分散 ) 計算モデル プロセス代数 ( プロセスカルキュラス ) イベント機械モデル ( ペトリネット ) 38 19

20 プログラミング言語の諸要素 文法 BNF 制御構造 構造化プログラミング 変数 値 データ型 型代数 オブジェクト指向 抽象データ型 サブルーチンと呼出しクラス 継承 カプセル化 実行 部分計算 ネットワーク対応 検証 アサーション 入出力 イベント駆動 39 プログラム理論 プログラムの正しさ (correctness) 正当性と停止性 (Termination) 2 つのプログラムが等しいということ 入力と出力の関係が等しいこと プログラムの計算の仕方も含めて等しいこと プログラムによって計算できること できないこと 数学的に定義できる関数 プログラミング言語によって表現できる関数 40 20

21 プログラムの意味論 プログラミング言語は言語である 言語は何かを表現するためのもの 表現しているものがその文の意味 プログラムは何を表現しているのか プログラムは 計算機に何を要請しているのか プログラムが正しいということは 何を期待しているのか 41 プログラミング言語の意味論 操作的意味論 (Operational Semantics) プログラムの状態をどのように変化させていくのか 公理的意味論 (Axiomatic Semantics) プログラムの実行によってどんな性質が満たされるのか 表示的意味論 (Denotational Semantics) プログラムが意味するものを 具体的に対応付ける 42 21

22 プログラミングの基本的な理解 Fundamental Understanding of Programming Tony Hoare (ACM Turing Award) プログラミングの基本的な理解 (1) Q1: What is this program for? ( このプログラムは何ですか?) A: Its specification tells you its function ( その仕様はあなたにその機能を伝える ) Q2: How does it work? ( このプログラムはどのように機能するか?) A: Annotation at interfaces explains how ( インタフェースでのアノテーションは説明できる ) 22

23 プログラミングの基本的な理解 (2) Q3: Why does it work? ( なぜこのプログラムは機能するか?) A: The theory of programming explains why ( プログラミングの理論から説明できる ) Q4: Are the answers accurate? ( 答えは正確ですか?) A: A verifying compiler provides a reliable check ( 検証コンパイラは信頼できるチェックを提供する ) 23