/var/log/messages

Nov 4, 2013 - 2 minute read - Comments - Scheme EoPL

EoPL の exercise 2.11

そもそもな考え方が違う、という事にようやく気付くなど。 例示されてるものを使って確認してみるに

(lambda (p) (+ p x))

の x を (* p 3) で置換する場合、以下になってはマズい、というのが前提。

(lambda (p) (+ (p (* p 3))))

ただ、置換自体はその通りでその外側にある p な束縛を p0 とかに変更しなきゃ、なのか。これ、自分で定義する解釈系 (?) の文法はけっこう単純になっているので無理矢理な方法で何とかなるのかどうなのか。

てことは、

  • 変数の置換は例示されている通り
  • lambda な分岐で色々しなきゃいけない
  • lambda-exp の id が subst-id と同じかどうかで操作が変わる

ということで以下なカンジになるのかどうか。

    (cases expression exp
       (var-exp (id)
            (if (eqv? id subst-id) subst-exp exp))
       (lambda-exp (id body)
                           (if (eqv? id subst-id)
                               (let ((newid (fresh-id body id)))
                                 (lambda-exp newid
                                             (subst (lambda-calculus-subst body newid id))))
                               (lambda-exp id (subst body))))

かなりぐぬぬぬ的なナニですがどうなるのか。

違う

fresh-id.scm で定義されてる all-ids を使って戻されるリストの検査を、なのか。手続き作るか。

(define shouldBeReplaced?
  (lambda (id list)
    (cond ((null? list) #f)
          ((eqv? id (car list)) #t)
          (else
            (shouldBeReplaced? id (cdr list))))))

で、以下な条件分岐なのかどうか。

(if (shouldBeReplaced? id (all-ids body))

で良いのかどうか。 て、以下なエラーが出てて困ってたのですが、fresh-id がアレだった模様。

got #<<error> "string required, but got p\n">

ぐぬ

違う。こうじゃん。

        (if (shouldBeReplaced? id (all-ids subst-exp))

そして置き換え対象な id も parse していないことが判明orz そして試験パス。いやはや。最終的に以下なカンジになってます。なんかキタナい。

(define shouldBeReplaced?
  (lambda (id list)
    (cond ((null? list) #f)
          ((eqv? id (car list)) #t)
          (else
            (shouldBeReplaced? id (cdr list))))))

(define lambda-calculus-subst
  (lambda (exp subst-exp subst-id)
    (letrec
      (subst
        (lambda (exp)
          (cases expression exp
                 (var-exp (id)
                   (if (eqv? id subst-id) subst-exp exp))
                 (lambda-exp (id body)
                   (if (shouldBeReplaced? id (all-ids subst-exp))
                       (let ((newid (fresh-id body (symbol->string id))))
                         (lambda-exp newid
                                     (subst 
                                       (lambda-calculus-subst 
                                          body 
                                          (parse-expression newid) 
                                          id))))
                       (lambda-exp id (subst body))))
                 (app-exp (rator rand)
                   (app-exp (subst rator) subst rand))
                 (lit-exp (datum)
                   (lit-exp datum))
                 (if-exp (test-exp true-exp false-exp)
                   (if-exp (subst test-exp)
                           (subst true-exp)
                           (subst false-exp)))
                 (primapp-exp (prim rand1 rand2)
                   (primapp-exp prim (subst rand1) (subst rand2)))))))
    (subst exp))))

commit 作って push しとこ。