プログラミング言語論 第2回 情報工学科 篠埜 功.

Slides:



Advertisements
Similar presentations
プログラミング言語論 第3回 BNF 記法について(演習付き) 篠埜 功. 構文の記述 プログラミング言語の構文はどのように定式化できるか? 例1 : for ループの中に for ループが書ける。 for (i=0; i
Advertisements

1 情報基礎 A 第 9 週 プログラミング入門 VBA の基本文法 1 準備・変数・データの入出力 徳山 豪・全 眞嬉 東北大学情報科学研究科 システム情報科学専攻 情報システム評価学分野.
オブジェクト指向 言語 論 知能情報学部 新田直也. 講義概要  私の研究室: 13 号館 2 階 (13-206)  講義資料について :  参考図書 : 河西朝雄 : 「原理がわかる プログラムの法則」,
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
アルゴリズムとデータ構造 第2回 線形リスト(復習).
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
1.1 C/C++言語 Hello.ccを作りコンパイルしてa.outを作り出し実行する
プログラミングパラダイム さまざまな計算のモデルにもとづく、 プログラミングの方法論 手続き型 関数型 オブジェクト指向 代数 幾何.
データ構造とアルゴリズム 第10回 mallocとfree
プログラミング入門2 第10回 構造体 情報工学科 篠埜 功.
プログラミング入門2 第10回 構造体 情報工学科 篠埜 功.
オブジェクト指向言語論 知能情報学部 新田直也.
プログラミング言語論 第1回 情報工学科 篠埜 功.
プログラミング言語論 第1回 情報工学科 篠埜 功.
プログラミング言語論 第6回 型 情報工学科 篠埜 功.
プログラミング言語論 第4回 式の構文、式の評価
応用情報処理V 第1回 プログラミングとは何か 2004年9月27日.
プログラミング言語論 理工学部 情報システム工学科 新田直也.
プログラミング言語論 理工学部 情報システム工学科 新田直也.
プログラミング言語論 第4回 手続きの引数機構 変数の有効範囲
構造体.
条件式 (Conditional Expressions)
言語処理系(5) 金子敬一.
応用情報処理V 第1回 プログラミングとは何か 2003年9月29日.
オブジェクト指向 プログラミング 第一回 知能情報学部 新田直也.
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
プログラミング言語論 第12回 関数型プログラミング 情報工学科 篠埜 功.
プログラミング言語入門 手続き型言語としてのJava
プログラミング言語論 第3回 BNF記法について(演習付き)
暗黙的に型付けされる構造体の Java言語への導入
プログラミング言語論 第9回 Hoare論理の練習問題 手続きの引数機構 変数の有効範囲
コンピュータ系実験Ⅲ 「ワンチップマイコンの応用」 第1週目 アセンブリ言語講座
精密工学科プログラミング基礎 第10回資料 (12/18実施)
プログラミング言語入門.
第7回 授業計画の修正 中間テストの解説・復習 前回の補足(クロックアルゴリズム・PFF) 仮想記憶方式のまとめ 特別課題について
計算機構成 第3回 データパス:計算をするところ テキスト14‐19、29‐35
Fortranについて 高エネルギー加速器研究機構 平山 英夫.
情報処理Ⅱ 第2回:2003年10月14日(火).
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
情報とコンピュータ 静岡大学工学部 安藤和敏
先週の復習: CPU が働く仕組み コンピュータの構造 pp 制御装置+演算装置+レジスタ 制御装置がなければ電卓と同様
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
コンパイラ 2011年10月20日
精密工学科プログラミング基礎Ⅱ 第5回資料 今回の授業で習得してほしいこと: 構造体 (教科書 91 ページ)
C言語 はじめに 2016年 吉田研究室.
高度情報演習1A スクリーンセーバ作成 2016年4月13日 情報工学科 篠埜 功.
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
計算機プログラミングI 木曜日 1時限・5時限 担当: 増原英彦 第1回 2002年10月10日(木)
第14回 前半:ラムダ計算(演習付) 後半:小テスト
プログラミング言語論 第10回 情報工学科 篠埜 功.
プログラミング言語論 第2回 篠埜 功.
第6回放送授業.
~sumii/class/proenb2010/ml5/
情報処理Ⅱ 2007年12月3日(月) その1.
コンパイラ 2012年10月11日
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
PROGRAMMING IN HASKELL
オブジェクト指向言語論 第一回 知能情報学部 新田直也.
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
Javaとは Javaとはオブジェクト指向言語でJava VM(Java仮想マシン)と呼ばれるプログラム上で動作します。
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
C#プログラミング実習 第1回.
1.2 言語処理の諸観点 (1)言語処理の利用分野
岩村雅一 知能情報工学演習I 第7回(後半第1回) 岩村雅一
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
計算機プログラミングI 第10回 2002年12月19日(木) メソッドの再定義と動的結合 クイズ メソッドの再定義 (オーバーライド)
Presentation transcript:

プログラミング言語論 第2回 情報工学科 篠埜 功

機械語(machine language) フォンノイマンマシン(von Neumann machine) 1946年にプリンストン高等研究所で設計。 Turing machineをランダムアクセスマシンにし、入出力装置を追加したものに相当。 機械語(machine language)はもっとも低レベルの言語。コンピュータが直接解釈実行する。機械語は最初、コード(code)と呼ばれた。(今日では高級言語のプログラムのこともコードと言う。)

機械語(machine language) 数字の列であらわされる。 [1946年に設計されたvon Neumann machineの機械語の断片例] 00000010101111001010 00000010111111001000 00000011001110101000 (10番地と11番地の値を足し、その結果を12番地に 保存する) 現代のコンピュータも原理的にはvon Neumann machineと同じであり、”von Neumann architecture”のコンピュータと言われる。 アセンブリ言語(assembly language)は機械語の命令を記号で表す。

プログラミング言語 プログラミング言語は特定の機械に依存しないことが(通常は)望まれる(高水準言語)。 プログラミング言語が持つべき性質 高水準の記述能力 プログラムの論理構造を簡潔に記述 厳密な意味の定義 その言語で記述可能なすべてのプログラムの意味(動作)を完全に規定 効率的実装 その言語で記述可能なすべてのプログラムを、効率のよい機械語に変換

高水準言語の利点 機械語、アセンブリ言語はほとんどすべての領域において高水準言語にとってかわられた。 例: C言語 人間にとって読みやすい 特定の機械に依存しない (portable) ライブラリが使える 構文チェック、型チェックなどの検査機構がある 例: C言語 1973年に開発, UNIXのkernel(最初はアセンブリ言語で書かれていた)をCで書き換えた  アセンブリ言語で書かれていたころより修正や、新しいデバイスの追加に対する拡張などがはるかに容易になった 異なるハードウェア(PDP-11以外)に対するUNIX OSも、コードの大部分を変えることなく作れた。

プログラミング言語の分類 プログラミング言語は計算モデルにより以下のように分類される。 命令型言語(imperative language)あるいは手続き型言語(procedural language) 関数型言語(functional language) オブジェクト指向言語(object oriented language) 論理型言語(logic programming language)

言語が提供するもの(1) 計算モデル(前ページ参照) データ型(とその操作) (例) C言語では構造体、ポインタ、共用体等、データを組み合わせて大きな構造のデータを作る仕組みが提供される。int型, string型, double型などの基本型のデータをそれらで組み合わせることにより、複雑な構造のデータを組み立てることができる。また、構造体等に対し、その部分構造を得る操作関数(構造体のメンバ演算子など)が提供される。

言語が提供するもの(2) 抽象化機構 検査機構 (例1) C言語の関数 (例2) [参考] Standard MLなどにおける多相型 関数の定義は計算を抽象化している 関数適用は具体化(仮引数に実引数を当てはめる) (例2) [参考] Standard MLなどにおける多相型 型を抽象化、具体化。 検査機構 (例)構文チェック、型検査 コンパイル時に構文エラー、型エラーを発見できる。

プログラミング言語の構文 (例) BNF記法による数字列言語の構文定義 <d> ::= 0|1|2|3|4|5|6|7|8|9 <digit_seq> ::= <d> | <d><digit-seq> <real-number> ::= <digit-seq> . <digit-seq> 通常、プログラミング言語の文法は 文脈自由文法(context-free grammar)に属する。 文脈自由文法に属する文法はBNF記法で記述できる。

プログラミング言語の意味 (例) 日付を表す言語の構文 <date> ::= <d><d> / <d><d> / <d><d><d><d> 01/02/2001 アメリカでは2001年1月2日を表す。 2001年2月1日を表す国もある。 プログラミング言語は構文と意味を定義することにより定義される。

プログラミング言語の定義、説明 チュートリアル(Tutorial) レファレンスマニュアル(Reference Manual) 言語の概略を紹介。 レファレンスマニュアル(Reference Manual) 構文と意味を記述。BNFによる構文定義と英語などの自然言語による意味の説明。 形式的定義(formal definition) 英語などの自然言語ではなく、操作的意味など、形式的な議論に耐える意味の記述。

プログラミング言語の基礎(第2章) 簡単な言語の例---Little Quilt Quiltの例

Little Quilt言語 2つの基本図形(正方形)を組み合わせてquiltを作成する言語 a b

Little Quilt言語の式の定義 <exp> ::= a | b | turn (<exp>) | sew (<exp>, <exp>) turn (e) --- キルトeを90度右回転させたキルトを表す。 sew (e1, e2) --- 高さが同じキルトe1, e2を左右に並べ、縫い合わせる (左がe1、右がe2)

Little Quilt言語の式の例 式 quilt b turn (b) turn (turn (b)) a sew (turn (turn (b)), a)

turn (sew (turn (b), turn (b))) 演習問題1 以下の式が表わすQuiltを図示せよ。 turn (sew (turn (b), turn (b)))

関数宣言の導入 fun unturn (x) = turn (turn (turn (x))) 左回転操作 fun pile (x,y) = unturn (sew (turn (y), turn (x))) 幅の等しいキルト xとyを上下に並べて縫い合わせる(上がx, 下がy) このように、よく使う計算パターンに名前を付けることができると便利。 関数宣言の構文 fun <name> (<formals>) = <exp> <formals> ::= <name> | <name>, <formals> ただし、<exp>の定義に<name>と関数適用式を追加する。(後述)

局所宣言(let式)の導入 (例) let fun unturn (x) = turn (turn (turn (x))) fun pile (x,y) = unturn (sew (turn (y), turn (x))) in pile (unturn (b), turn (b)) end let式の構文 let <decls> in <exp> end <decls>の定義は後で行う。 <decls>で宣言された関数名の有効範囲は、<decls>内のその宣言以降およびinとendの間。ただし、その範囲内で同じ名前が導入された場合はその名前の有効範囲を除いた部分。

fun f (x) = turn (turn (x)) in f (f (b)) end 演習問題2 以下の式が表わすQuiltを図示せよ。 let fun f (x) = turn (turn (x)) in f (f (b)) end

値に名前を付ける構文の導入 (例) let val x = unturn (b) val y = turn (b) in sew (x,y) end 値に名前を付ける構文(value declaration) val <name> = <exp> この構文についても、名前の有効範囲は関数宣言の場合と同じ。

少し大きな例 let fun unturn (x) = turn (turn (turn (x))) fun pile (x,y) = unturn (sew (turn (y), turn (x))) val aa = pile (a, turn (turn (a))) val bb = pile (unturn (b), turn (b)) val p = sew (bb, aa) val q = sew (aa, bb) in pile (p,q) end

Little Quilt言語の構文定義 <exp> ::= a | b | <name> | <name> ( <actuals>) | turn (<exp>) | sew (<exp>, <exp>) | let <decls> in <exp> end <actuals> ::= <exp> | <exp> , <actuals> <decls> ::= <decl> | <decl> <decls> <decl> ::= fun <name> (<formals>) = <exp> | val <name> = <exp> <formals> ::= <name> | <name>, <formals> <name>は文字列など。通常、字句解析で処理する。 <name> ::= <c> | <c><name> <c> ::= a | b | c | d | e … などで定義できる。

補足1 Little Quilt言語の構文定義では、 sew (e1,e2)においてe1とe2の高さが同じにならないような式も許す。 未定義の名前を使用する式も許す。 関数適用式において引数の個数が合っていない式も許す。 このようなチェックは構文解析フェーズでは行わない。コンパイラーの構文解析より後のフェーズでチェックするか、あるいは実行時にチェックする。

補足2 Little Quilt言語の組み込み関数sewは前置だが、 1+2における + のように、間に書く記法(中置記法)もある。