2 LISP

2.1

次のS式はどのようなセル構造で表されるか。

1. ((a) (b) (c))
2. ((a) (b a))
3. ((a b (c . d)) ((e f) . g))

2.2

Schemeで階乗を求めるプログラムを、再帰呼び出しを用いない ものと用いるものを両方記述せよ。200の階乗を実際に求めてみよ。

2.3

Schemeのcontinuationとはなにか。

2.4

continuationを用いてコ・ルーチンのプログラムを書き、解説せよ。

2.5

次のS式はどのようなセル構造で表されるか。

1. ((a b c) (d e f) . g)
2. (defun (app x y) (if ((= x ())) y (cons (car x) (app (cdr x) y))))

2.6

2つのリストをアペンドする関数を書く。

1. 再帰呼び出しを用いて実現する。
2. 再帰呼び出しを用いずに実現する。

2.7

上の問題の回答のconsを行なう数を計算せよ。

2.8

リストの並びを逆にする関数を考える。

1. 再帰呼び出しを用い、引数一つの関数を定義することによって 実現する。
2. 再帰呼び出しを用いずに実現する。

2.9

上の問題の回答のconsを行なう数を計算せよ。

2.10

リストの並びを逆にする関数を書く。 ただし、consを行なう数が、入力リストの長さに比例すること。

2.11(2問分)

λ計算のβリダクションを1ステップ行なうプログラムを記述し、 それを用いてλ式の標準形を求めるプログラムを書け。実際にいくつかのλ式の 標準形を求めること。

2.12(2問分)

命題論理の論理式の真理値表を求めるプログラムを書け。

2.13(2問分)

命題論理の論理式がトートロジーであることを確認するプログラムを 書け。

2.14(2問分)

関数記号と述語記号(アリティつき)のリストを与えられて、 それらからHerbrand BaseとHerbrand Universeを生成するプログラムを記述せよ。 無限に存在する場合は、自然数を引数とし、その数の元を生成するようにせよ。 ただし、nを増やしていくと、すべての元を生成する必要がある。

2.15

次のS式の結果のセル構造とそれらのS式を求めよ． S式は，まったく省略してないものとできるだけ省略したもの両方を求めること． あらかじめ，
(define x (cons (cons 'a (cons 'b '())) (cons 'c 'd)))
としてあるとする．

1. x
2. (cons x (cons x x))

2.16

あらかじめ，
(define x (cons (cons 'a (cons 'b '())) (cons 'c 'd)))
(define y (cons (cons '(1 2 3) (cons 'a '())) (cons 'c '(d))))
(set-car! (car y) (cdr x))
(set-cdr! x (car x)) (define t (cons x '()))
(set-cdr! t t)
としてあるとする． このとき，次の3つの大域変数の値のセル構造とそれらのS式を求めよ． S式は，まったく省略してないものとできるだけ省略したもの両方を求めること． ただし，無限のS式となってしまう場合には求めなくてもよい．

1. y
2. x
3. t