課題S16で定義した「if-fun」を用いて、「if」、「cond」、「or」などの条件分岐可能な構文を使わずに、階乗を計算する関数「fact4」を定義せよ。
締切: 1/31 23:59
次のように定義される「fix」を用いて、階乗を計算する関数「fact5」を再帰を使わずに定義せよ。
(define (fix f)
(lambda (x) ((f (fix f)) x)))
締切: 1/31 23:59
課題S26と同様の方法で階乗を計算する関数を定義するとして、「fix」の代わりとして利用可能な「fix2」を明示的な再帰を使わずに定義せよ。(「fact5」の定義内で、「fix」は1引数汎関数を受け取ってその不動点を求めている。不動点コンビネータなどを調べて見ると良い。)
締切: 1/31 23:59
以下のようにSchemeの処理系を作成することにする。 (第５回の資料の第三節以降を参照せよ。)
(define (scheme)
(let ((top-env (make-top-env)))
(define (rep-loop env)
(display "my-scheme> ")
(let* ((res (base-eval env (read)))
(env (car res))
(val (cdr res)))
(print-data val)
(newline)
(if (equal? val '*exit*)
#t
(rep-loop env))))
(rep-loop top-env)))
環境と式を受け取って環境と値のペアを返す関数「base-eval」を、「make-top-env」、「print-data」と共に定義して、処理系を完成させよ。環境やλ閉包のデータ構造はメタ処理系のものを使わずに自分で定義すること。全ての構文や組込み関数をサポートする必要はないが、最低限下記の例が動く程度には実装すること。(let式の本体やlambda式の中など、複数の式を書いてよい部分に1つの式しか書いてはいけないという制約を設けても下記の例は動く。) 当然ながら、「base-eval」の定義に、組込みの「eval」やそれに類する関数を用いてはならない。
実行例（#<unspecified>の部分に何が表示されるかは実装による）:
guile> (scheme)
> 10
10
> (+ (- (* (* 1 2) 3) (* 4 5)) (+ (* 6 7) (* 8 9)))
100
> (define a 100)
#<unspecified>
> a
100
> (define b (+ 10 1))
#<unspecified>
> b
11
> (if (< a b) 10 20)
20
> (quote (+ 1 2))
(+ 1 2)
> (define f (lambda (x) (+ x 1)))
#<unspecified>
> (f 10)
11
> (define g (lambda (x y) (+ x y)))
#<unspecified>
> (g 3 5)
8
> (define h (lambda (x) (lambda (y) (+ x (* a y)))))
#<unspecified>
> ((h 9) 9)
909
> (define i (lambda (x) (if (< x a) a x)))
#<unspecified>
> (i (f 100))
101
> (let ((a 1)) (i 10))
100
> (let ((a 10) (b (f a)) (c (- b 1))) (let ((a 10) (b (f a)) (c (- b 1))) (+ (+ a b) c)))
121
> a
100
> (define l (cons 1 (cons 2 (cons 3 (list)))))
#<unspecified>
> l
(1 2 3)
> (car (cdr l))
2
> (define fact (lambda (n) (if (< n 1) 1 (* n (fact (- n 1))))))
#<unspecified>
> (fact 10)
3628800
ヒント: Scheme処理系の資料を熟読せよ。本質的に難しい内容が含まれているため、初心者にとってはきちんと読んだとしても一読で内容を理解することは難しいかもしれない。(ましてや斜め読みにおいては理解は不可能であろう。)
資料にも書いてあるが、資料通りに実装を進めた場合「base-evalは環境と式を受け取って評価を実行する関数ですが、組み込みのevalと違って、環境と値のペアを返します」なので、実装の際には関数の返り値に注意せよ。
またclosure-body関数の定義は、資料での定義は本体部分に式のリストが来る事を想定した上での定義になっている。もし処理系の実装において、1つの式しか書いてはいけないという制約を設ける場合には、定義を適切に変更せよ。
締切: 1/31 23:59
自分自身を読み込むことが可能なSchemeの処理系を作成し、処理系を多段に実行した場合の処理速度について、簡単にコメントせよ。レポートは、処理系のコードとコメントをまとめたテキストファイルとして作成すること。
締切: 1/31 23:59