Hatena::ブログ(Diary)

西尾泰和のはてなダイアリー

2010-07-26

レバレッジメモ: プログラミング言語の概念と構造

プログラミング言語の概念と構造。例の原稿を書く前にid:yuguiさんから借りたのに結局読みもせずに自分の記憶と勢いで原稿を書いてしまったのだが、今更読んでみた。っていうかこれはかなりいい本だ。というわけで返す前にレバレッジメモ作成。

参考文献のリストの引き写しは今日はもう遅くて眠いのでまた今度。


マリナーI無人金星探査機は1962年7月22日発射から290秒後に爆破された。損失は1800から2000万ドルと見積もられる。notの欠落が原因である。

1950年代には効率のよいプログラムは人がマシン語を書くことでのみ作られると信じられていた。この信念にFortranが挑戦した。

最初はアセンブリ言語で書かれていたUNIXカーネルは1973年にプログラミング言語Cによって書き換えられた。利点は「新しいユーザとプログラム」「移植性」「可読性」 Ritchie[1978] *1

BNFのNaurはAlgol60の報告書にBNF(当時はBackus Normal Form)を使った

初期のFortranではIからNで始まる変数はint型、それ以外はreal型であり、異なる型の加減乗除は出来なかった。後にrealとintの計算の際にはintがrealへと強制型変換されるようになった。

60年代の言語設計はAlgol60をどう改善するかに終始した。構文を指定するのにBNFを使うのもAlgolからの伝統。しかしAlgolにはデータ構造として配列しかなかった。

「Algol60のコードをPascalに変換することは単純な転記と考えて差し支えない」 Wirth[1971] *2

Modula-2は「Pascalのすべての側面を含んだ上で、重要なモジュール概念を持つように拡張した。」「あらゆる構造がキーワードで始まりキーワードで終わるようにした」

「Cが提供する機能に加えて、C++は新しい型を定義する柔軟で効率的な機能を提供する」Stroustrp[1986] *3 新しい型はSimula67から借用したクラスを用いて定義される。

今日のCと1972年のCの主な相違点は型検査に対する今日の厳格な態度である。現在ではある型へのポインターが整数や他の型へのポインターを装うことができなくなった。

代入演算子: Cでは式の中に代入を書くことが出来る(Pascalではダメ)

Knuth[1974]*4はgotoの有害性を最初に発表したのがNaur[1963a]で、Dijkstra[1968a]が流行らせたとしている。

Lispではダイナミックスコープが伝統的に使用された。最近のLispではレキシカルスコープを採用する傾向がある。 --- 太古の極初期のLisp(とEmacsLisp)くらいかとおもったら「伝統的」だったのか。ダイナミックスコープが終わって僕らは生まれた、ダイナミックスコープを知らない子供たちさ〜♪

値呼び出し: 右辺値を渡す、参照呼び出し: 左辺値を渡す、名前呼び出し: 名前の衝突を避けつつテキストそのものを渡す --- この簡潔なまとめは目からウロコ

初期のFortranでは実参照パラメータが代入可能かどうかを検査しなかった。その結果、swap(1, 2)は定数の1と2を交換してしまうことがあった。言語によっては左辺値を持たない式が実引数に指定された場合には値呼び出しを用いることでこの問題を避ける。

Cのマクロプリプロセッサは「名前の衝突」を無視した名前呼び出し。Algol60の名前呼び出しは衝突する際に局所名を変更するので大丈夫。

モジュールはプログラムを適度なサイズに分割したものであり、公開されている部分と、公開されていない内部状態とがある。

真の抽象仕様は実現が困難。実装隠蔽、カプセル化、表現独立によって、非公開部は外部に影響を与えることなく変更できる。

Modula-2のモジュール=可視性+初期化 明示的なimport/exportなしにモジュールの境界を超えてアクセス出来ない。

不透明な輸出(opaque export)とは型の名前だけのexport(構成要素を見せないの意)。代入と等価性のチェック、および明示的にexportされた他の操作だけしか使用できない。 --- HaskellのIOモナドの内部にアクセス出来ないのもこれだよね。

C++の基本型/派生型は上位型/部分型(サブタイプ)より一般化されている。private継承をすれば導出クラスが部分型となることを防ぐことが出来る。

List ProcessorであるLispはFortranのFLPL(Fortran List Processing Language)という拡張に萌芽がある。FLPLには再帰がなく、式の中に条件を書く事もできなかった。

プログラミング言語に置ける並行性とハードウェアにおける並列性は互いに独立した概念である。ハードウェアの演算はそれが時間的に重なりあって行われるときに並列(parallel)であるという。ソーステキスト上の操作は、並列に実行されることが可能であれば並行(concurrent)であると言われるが、必ずしも並列に実行される必要はない。 --- 今まで聞いた中で一番わかり易いparallelとconcurrentの違いの説明だ!

BNFに類似の表記法がサンスクリット語の複雑な文法を記述するために紀元前400年〜200年頃、古代インドの言語学者Paniniによって使用されていた Ingerman[1967]

*1:Dennis M. Ritchie The Evolution of the Unix Time-sharing System http://cm.bell-labs.com/cm/cs/who/dmr/hist.html

*2:The Programming Language Pascal. Acta Informatica, 1, (Jun 1971) 35-63. also in Programming Language Design, A.I.Wasserman, Ed., IEEE Computer Society Press, 1980.

*3:The C++ Programming Language Addison-Wesley, ISBN 0-201-88954-4 and 0-201-70073-5.

*4:Structured programming with go to statements (1974) http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf