Software Engineering Lecture 4/20

先週の復習

プログラムが満たしてほしい性質 ... 論理的意味、代数的意味
論理論理型プログラミング
プログラムを動かす仕組み ... 操作的意味
写像、関数関数型プログラミング
プログラムの動いた履歴 ... 実行結果
集合 Specification Z

Perlを実行して見る

Perl Version 5 と、そのGUI処理系であるPerl/Tkを使う。Version 4 が perl で Version 5 が perl5 である。多少違いがあるので、perl5 を使うことにする。

% perl5 -de 0
Loading DB routines from perl5db.pl version 1
Emacs support available.
Enter h or `h h' for help.
main::(-e:1):   0
  DB<1> print "Hellow"
Hellow
  DB<2>

というように対話的に動かすことができる。

集合

対象とするものの集まりを集合という。集合には二通りの表し方がある。

集合の要素を全部示す
{ 島袋哲,上原麻乃,金城尚治,比嘉陽一,前原崇章,三野敦史,宮城尚平 }
集合が満たす性質を示す
{X | X は情報工学3年}

有限集合を考える限りはまったく簡単だ。が、無限集合は難しい。集合に対して簡単な演算を考えることができる。

集合演算 ... ∧ (AND), ∨ (OR), ¬ (NOT)

Perlの配列

  DB<2> @a = (a,b,c,d,e)

  DB<3> p $a[1]
b
  DB<4> @b = (1,2,3,4)

  DB<5> @c = (@a,@b)

  DB<6> p "@c"
a b c d e 1 2 3 4
  DB<7>

for文で配列を処理するのが一般的。

for $i ( @a ) {
    print "$i\n";
}

要素を削除するには? splice というのがあるけど、今のところはcopyが簡単。

写像、関数

何かの入力に対して決まった値を返すものが関数である。

可能な入力の集合を定義域、定義域に対する出力の集合を値域という。

例g 学籍番号を入力として、アカウントを出力する関数
例f アカウントを入力として、名前を出力する関数
例fg 学籍番号を入力として、名前を出力する関数

関数を集合と集合の対応と考える時には特に写像という言葉を用いることが多い。(その方がCの関数と混同しなくてすむし...)

二つの関数を持って来て、片方の値域と他方の定義域が適合していれば、関数の合成を作ることができる。入力と出力の組み合わせの集合として関数を定義することもできる。

Perlの連想配列

  DB<7> $a{'kono'} = kono

  DB<8> $a{'key'} = value

  DB<9> p "%a"
%a
  DB<10> p %a
keyvaluekonokono
  DB<11> p join(" ",%a)
key value kono kono
  DB<12>

のように定義する。削除する時には delete を使う。

  DB<13> delete $a{'kono'}

  DB<14> p join(" ",%a)
key value
  DB<15>

問題

Perlの連想配列を使って、fg を使って定義してみよ。

論理

論理は以下の要素から構成される

命題 (Q,P,R) ... T / F, 正しい / 間違っている, 真 / 偽
変数 (x,y,z) ... いろいろな値が割り当てられる名前
述語 p,q(x) ... 変数を含む命題
論理演算 ... /\ (AND), \/ (OR), ~ (NOT)

空集合をF、空でない集合をT、と見ることによって、集合演算と論理演算は同じものとみなすことができる。

集合を定義するのには、論理式を使うことが多い。

{X | p(X)}

具体的なプログラムに関して集合を使って意味を考える

もし入力が有限で、出力が一つだけなら、とても簡単になる。

入力が無限だったりすると難しい。特にReal-timeプログラミング、並列プログラミングの意味は難しい。

仕様は論理式で表すのが容易である
実装は関数で表すのが容易である
実行結果は集合で表すのが容易である

しかし、この三つの道具は、実際には同等な力を持った道具であり、望むならば、論理だけ、関数だけ、集合だけ、ですべてを表現することもできる。しかし、適材適所を考えて使おう。

Perl 問題宿題

集合Dを配列に格納するPerlのプログラムを配列を使って作成せよ。
集合Eを生成するPerlのプログラムを配列を使って作成せよ。
集合Hを生成するPerlのプログラムを配列を使って作成せよ。
f'およびf'g を表す集合を連想配列を使って作成してみよ。

Perl の宿題は、メールでSubjectを
Subject: Report on Software Engineering Lecture 4/20
として提出すること。この講義の問題を提出する時には、 Subject: Exercise on Software Engineering Lecture 4/20
とすること。