Exercise 2.10

fresh-id という手続きについて云々。定義が以下らしい。

(define fresh-id
  (lambda (exp s)
    (let ((syms (all-ids exp)))
      (letrec ((loop (lambda (n)
		       (let ((sym (string->symbol
				   (string-append s
						  (number->string n)))))
			 (if (memv sym syms) (loop (+ n 1) sym))))))
	(loop 0)))))

ふむ。実行例も出てますが略。all-ids を定義しなさい、という事らしい。
実行例から見るに例えば以下なリストを出力するんかな。

(w2 w1 w0 w3)

if-exp は無い、って前提で考えて良いのかな。何故か Ex.2.8 で enum-vars という手続きを定義させて頂いてるのですがざっくり以下なカンジで良いのかどうか。

(define all-ids
  (lambda (exp)
    (cases expression exp
      (var-exp (id) id)
      (lambda-exp (id body)
        (cons id (all-ids body)))
      (app-exp (rator rand)
        (cons (all-ids rator) (all-ids rand))))))

これを flatten して delete-duplicates すれば良いのかな。とりあえず例示されてるナニを試験にしてみました。

(use gauche.test)
(add-load-path ".")
(load "fresh-id")

(test-start "fresh-id")
(test-section "fresh-id")
(test* "example"
       'w4
       (fresh-id '(app-exp (lambda-exp 'w2
				       (app-exp (var-exp 'w1) (var-exp 'w0)))
			   (var-exp 'w3))
		 "w"))

(test-end)

なんか quote あたりが微妙だったので試験を以下に修正。数えあげも試験に追加。

(use gauche.test)
(add-load-path ".")
(load "fresh-id")

(test-start "fresh-id")
(test-section "all-ids")
(test* "example"
       '(w2 w1 w0 w3)
       (all-ids '(app-exp (lambda-exp w2
				      (app-exp (var-exp w1) (var-exp w0)))
			  (var-exp w3))))

(test-section "fresh-id")
(test* "example"
       'w4
       (fresh-id '(app-exp (lambda-exp 'w2
				       (app-exp (var-exp 'w1) (var-exp 'w0)))
			   (var-exp 'w3))
		 "w"))

(test-end)

以下の実装で両方パスしてます。

(add-load-path ".")
(load "expression")

(use srfi-1)

(define enum-filter-vars
  (lambda (exp)
    (delete-duplicates (flatten (enum-vars exp)))))

(define (flatten xs)
  (cond ((null? xs) '())
	((pair? xs) (append-map flatten xs))
	(else
	 (list xs))))

(define all-ids
  (lambda (exp)
    (delete-duplicates (flatten (enum-ids exp)))))

(define enum-ids
  (lambda  (exp)
    (cases expression exp
      (var-exp (id) id)
      (lambda-exp (id body)
        (cons id (all-ids body)))
      (app-exp (rator rand)
        (cons (all-ids rator) (all-ids rand))))))

(define fresh-id
  (lambda (exp s)
    (let ((syms (all-ids exp)))
      (letrec ((loop (lambda (n)
		       (let ((sym (string->symbol
				   (string-append s
						  (number->string n)))))
			 (if (memv sym syms) (loop (+ n 1)) sym)))))
	(loop 0)))))

エントリ投入と同時に GitHub にも反映させて Ex.2.11 を確認の方向。