プログラミング言語論・第 2 回レポート

問題

  1. （問 4.1.13） 例題 4.1.12の deleteの定義 
    (define (delete x xs)
  (if (or (null? xs) (< x (car xs)))
      xs
      (if (= x (car xs))
          (cdr xs)
          (cons (car xs) (delete x (cdr xs)))))))
    では、(delete 4 '(1 4 4 7))は (1 4 7)になってしまう。 (delete 4 '(1 4 4 7))が (1 7)になるように deleteを定義し直せ。 （4が何回続こうが、 (delete 4 '(1 4 ... 4 7))は (1 7)にならなければいけない。）

  2. （問 4.1.14） insert, deleteを拡張して、数ではなく、 数と文字列の組を扱えるようにせよ。例えば、 
    (define schedule '((1300 "Lunch") (1800 "Dinner")))
(set! schedule (insert '(1600 "Tea") schedule))
    とすると、scheduleが 
    ((1300 "Lunch") (1600 "Tea")(1800 "Dinner"))
    になる。

  3. （問 4.1.16） 1以上の整数 nに対して、リスト (n n-1 ... 1) を返す関数 list-fromを（再帰的に）定義せよ。

  4. （問 4.1.17） 2つの整数 m, n (m<=n)を受取り、リスト (m m+1 ... n)を返す関数 from-toを（再帰的に）定義せよ。 例えば (form-to 2 5)は (2 3 4 5)、 (form-to 7 8)は (7 8)となる。

  5. （第2回実習の問題より）
    次の add1, add1!（例題 4.3.1）, append（例題 4.1.10）, append!（例題 4.3.3） 
    (define (add1 xs)
  (if (null? xs)
      '()
      (cons (+ 1 (car xs)) (add1 (cdr xs)))))

(define (add1! xs)
  (if (null? xs)
      '()
      (begin (set-car! xs (+ (car xs) 1))
             (add1! (cdr xs)))))

(define (append xs ys)
   (if (null? xs)
       ys
       (cons (car xs) (append (cdr xs) ys))))

(define (append! xs ys)
   (if (null? (cdr xs))
       (set-cdr! xs ys)
       (append! (cdr xs) ys)))
    とそれぞれ同等の関数を C言語で定義せよ。

    ただし、

    テストとして次のような一連の文を実行するプログラムを作成して、 動作を確かめよ。 

      List list1, list2;

  printf("Please Input List 1: ");
  list1 = read_list();			/* リストその 1の入力 */
  printf("Please Input List 2: ");
  list2 = read_list();			/* リストその 2の入力 */

  printf("(add1 list1) => \t");
  print_list(add1(list1));		/* add1のテストの結果出力 */
  putchar('\n');
  add1EX(list1);
  printf("(append list1 list2) => \t");
  print_list(append(list1, list2)); 	/* add1!と appendのテストの結果出力 */
  putchar('\n');
  appendEX(list1, list2);		/* append!のテストの結果出力 */
  printf("list1 => \t");
  print_list(list1);
  putchar('\n');

  6. （問 5.1.3）任意の述語とリストを受取り、 リストの中で述語を満たす要素が存在するかどうか判定する関数 exist?を定義せよ。
以上の問題をすべて解いてください。 （一部、第 1 回レポートのボーナスポイント問題と重なりますが、 第 1 回のレポートでこれらの問題を解いた人も、 いちおう第 2 回レポートにもう一度解答を含めておいてください。 さらに以下のボーナス問題を解いてくれることを期待します。）

さらに余裕のある人は次のボーナス問題を（できるだけたくさん） 解いてください。

  1. （問 5.2.3） リスト (a0 a1 ... an)を受け取り、 多項式 a0 xn + a1 xn-1+ ... +an の値を計算する関数を返す関数 polynomial を定義せよ。（その方が簡単なら、係数が逆順の an xn + an-1 xn-1+ ... +a0でもよい。）
  2. （問 5.3.2）
  3. （問 5.4.1） iterateを改造して、終了条件の述語を与える代わりに、 生成されるリストの長さを指定できる関数 iterate2を定義せよ。 例えば、(iterate2 0 (lambda (x) (+ x 1)) 6)は、 (0 1 2 3 4 5)に、(iterate2 1 (lambda (x) (* 2 x)) 5)は (1 2 4 8 16)になる。
  4. （チャレンジ問題） 5.5節のエラトステネスのふるいのプログラムを Cで実装しなおせ。 （配列ではなくリストを用いて、不要になったセルはちゃんと freeすること。）
  5. （超チャレンジ問題） 5.3節のようなぺインタ（besideや rotate90のような演算を含めて）を Cあるいは C++で実現してみよ。

提出要領

（なお、経済学部の人は、オンライン提出は、 メール（kagawa@eng.?????）またはフロッピーでも結構です。 別途相談してください。）
Koji Kagawa (kagawa@eng.?????)