なにこれ

プログラム言語論2012年度の問題を解いてみた。
ツッコミは@alstamber迄。

問題1

1

   1 maklist……(10 9 8 7 6 5 4 3 2 1)
   2 maklist-r……(1 2 3 4 5 6 7 8 9 10)

2

maklistは末端再帰ではなく、再帰の巻き戻し時にリストの構成が行われている。
maklist-rは末端再帰であり、再帰の巻き取り時にリストの構成が行われている。
; LISP特にSchemeでは末端再帰をタダのループに変換する操作が実行時に行われている。そのため再帰のスタックが積み上がらずstack overflowにならないのである。

3

   1 (define (myapp a b)
   2 (cond ((null? a) b)
   3 (else (cons (car a) (myapp (cdr a) b)))))

4

   1 (define (myapp-r a b) (myapp-r2 (myrev-r a) b))
   2 (define (myapp-r2 a b)
   3 (cond ((null? a) b)
   4 (else (myapp-r2 (cdr a) (cons (car a) b)))))

問題2

1

(a・((b・(c・()))・((d・())・()))))

2

   1 ?- [H|T] = [a,b,c,d].
   2 
   3 H = a
   4 T = [b,c,d]

3

   1 append([], S2, S2).
   2 append([H|S1], S2, [H|S3]) :- append(S1, S2, S3).

4

   1 ?- append(S1, S2, [x,y,z]).
   2 S1 = []
   3 S2 = [x,y,z] ? ;
   4 
   5 S1 = [x]
   6 S2 = [y,z] ? ;
   7 
   8 S1 = [x,y]
   9 S2 = [z] ? ;
  10 
  11 S1 = [x,y,z]
  12 S2 = [] ? ;

問題3

1

i

このプログラムのmain関数ではnextという変数にsというオブジェクトのoutという関数からの戻り値を取り出すという操作を繰り返している。このような実装をすることで、実装の際にsというオブジェクトの中でデータがどのような構造で格納されているのかという具体的な表現の詳細を隠すことができる。このように予め公開された関数を使ってしか内部のデータ構造にアクセスできないようにし、内部のデータ構造に関する情報を遮蔽することをカプセル化と呼ぶ。

ii

プログラム中にはおなじoutという名前の関数が複数定義されており、それぞれ違う手続きが定義されている。outという名前の関数は複数存在するがプログラムを見るとoutという名前の関数が定義されているクラスがそれぞれ違っており、そこから関数の実体を含むオブジェクトがそれぞれ異なることがわかる。このように同じ名前の関数が、実体のオブジェクトによって異なる動きをすることを多様性とよんでいる。

2

A

virtualは仮想関数であることを示すを示す修飾子である。仮想関数とは派生クラスで再定義されることを前提とした関数で、このプログラムではitemクラスの派生クラスであるcounter, sieve, filterクラスでそれぞれ違ったout関数がオーバーライドされている。

B

ここでのpublicはクラスを継承する際に基底クラスから継承されるメンバの可視性を規定している。publicと書いた場合には、基底クラスでの可視性がそのまま継承される。つまり基底クラスでpublicなメンバは派生クラスでもpublicで、privateなメンバはprivateになる。

C

item(src)は基底クラスのコンストラクタであり、ここではそれを呼び出している。(C)の行ではsieveクラスのコンストラクタの引数であるsrcをそのままitemクラスのコンストラクタに渡している。

D

staticがついているメンバはそのメンバが静的メンバであることを表している。静的メンバとはインスタンスごとではなくクラスにただ一つのメンバがあり、それがそのクラスから生成されたすべてのインスタンスの間で共有されているようなメンバを指している。

3

   1 counter* c = new counter(2);
   2 sieve* s = new sieve(c);
   3 next = s->out();

4

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, number of primes: 10