6

コンピュータープログラミングの構造と解釈の質問 4.4 の最後の部分を解こうとしています。タスクは、または構文変換として実装することです。基本的な構文形式のみが定義されています。quote、if、begin、cond、define、apply、およびラムダ。

(または ab ... c) は最初の真の値と等しいか、真の値がない場合は偽です。

私がそれにアプローチしたい方法は、たとえば（またはabc）を次のように変換することです

(if a a (if b b (if c c false)))

これの問題は、a、b、および c が 2 回評価されることであり、それらのいずれかに副作用があると、誤った結果が生じる可能性があります。だから私はレットのようなものが欲しい

(let ((syma a)) 
     (if syma syma (let ((symb b)) 
                        (if symb symb (let ((symc c))
                                           (if (symc symc false)) )) )) )

これは、演習 4.6 のようにラムダを介して実装できます。ここでの問題は、シンボル syma、symb、および symc を決定することです。たとえば、式 b に変数 syma への参照が含まれている場合、let はバインディングを破棄します。したがって、syma は b にも c にもない記号である必要があります。

ここで問題が発生しました。この穴から抜け出す唯一の方法は、eval に渡されたどの式にも含まれていないシンボルを持つことです。(これには、他の構文変換によって渡された可能性のあるシンボルが含まれます)。

ただし、式で環境に直接アクセスできないため、そのようなシンボルを生成する合理的な方法があるかどうかはわかりません。Common Lisp には、この目的のための関数 gensym があると思います (これは、メタサーキュラー インタープリターで状態を保持し、同時使用を危険にさらすことを意味します)。

何か不足していますか？gensym を使用せずに実装する方法はありますか? 私は、Scheme が独自のハイジェニック マクロ システムを持っていることを知っていますが、それがどのように機能するかを理解していません。また、下に gensym があるかどうかもわかりません。

4

2 に答える 2

6

ここでやりたいことは、さまざまな形式の評価がネストされていない構文展開に変換することだと思います。たとえば、各フォームを関数としてラップすることでこれを行うことができ、lambda使用しているアプローチは問題ありません。たとえば、次のようなものを回すことができます

(or a b c)

の中へ

(let ((l1 (lambda () a))
      (l2 (lambda () b))
      (l3 (lambda () c)))
  (let ((v1 (l1)))
    (if v1 v1
      (let ((v2 (l2)))
        (if v2 v2
          (let ((v3 (l3)))
            (if v3 v3
              false)))))))

(実際には、lambda関数呼び出しifの評価はs とs でネストされていletますが、関数の定義は、ネストされた sとslambdaでそれらを呼び出しても、キャプチャされたバインディングで問題が発生しないような場所にあります。)変数–<code>l3 および–<code>v3 を取得する方法の問題には対処していませんが、それはそれほど重要ではありません。それらのいずれも関数の本体のスコープ内にないため、それらが体内に現れるかどうかを心配する必要はありません。実際、すべての結果に同じ変数を使用できます。ifletl1v1lambda

(let ((l1 (lambda () a))
      (l2 (lambda () b))
      (l3 (lambda () c)))
  (let ((v (l1)))
    (if v v
      (let ((v (l2)))
        (if v v
          (let ((v (l3)))
            (if v v
              false)))))))

この時点で、実際には次のようなより一般的な形式のループ展開を行っているだけです。

(define (functional-or . functions)
  (if (null? functions)
      false
      (let ((v ((first functions))))
        (if v v
            (functional-or (rest functions))))))

の展開(or a b c)は単純です

(functional-or (lambda () a) (lambda () b) (lambda () c))

このアプローチは、 Why (apply and '(1 2 3)) does not work while (and 1 2 3) works in R5RS?への回答でも使用されます。. そして、これはどれもingを必要としませんでした！GENSYM

于 2013-08-17T11:47:24.453 に答える
1

SICP では、or を実装する方法が 2 つあります。それらを自明な特殊な形式として扱うものと派生式として扱うもの。これを問題と見なすと彼らが実際に考えていたかどうかはわかりませんが、実装gensymまたは変更variable?し、次のような派生変数を作成する方法でそれを行うことができます。

;; a unique tag to identify special variables
(define id (vector 'id))

;; a way to make such variable
(define (make-var x)
  (list id x))

;; redefine variable? to handle macro-variables
(define (variable? exp) 
  (or (symbol? exp)
      (tagged-list? exp id)))


;; makes combinations so that you don't evaluate
;; every part twice in case of side effects (set!)
(define (or->combination terms)
  (if (null? terms)
      'false
      (let ((tmp (make-var 'tmp)))
        (list (make-lambda (list tmp)
                           (list (make-if tmp 
                                    tmp 
                                    (or->combination (cdr terms)))))
              (car terms)))))


;; My original version
;; This might not be good since it uses backquotes not introduced 
;; until chapter 5 and uses features from exercise 4.6
;; Though, might be easier to read for some so I'll leave it.
(define (or->combination terms)
  (if (null? terms)
      'false
      (let ((tmp (make-var 'tmp)))
        `(let ((,tmp ,(car terms)))
           (if ,tmp
               ,tmp
               ,(or->combination (cdr terms)))))))

どのように機能するかはmake-var、同じ引数を使用しても、呼び出されるたびに新しいリストを作成することです。id最初の要素がvariable?あるため、変数として識別されます。これはリストであるため、同じリストである場合にのみ変数ルックアップで一致しますeq?。そのため、いくつかのネストされた or-> 組み合わせ tmp-vars はすべて異なるものとして表示されlookup-variable-value、(eq? (list) (list)) => #f特別な変数はリストであるため、コード内のシンボルをシャドウすることはありません.

これは、同様の方法で構文規則を実装する Al Petrofsky によるeiodの影響を受けています。他の実装をネタバレと見なさない限り、読んでください。

于 2013-08-17T11:48:42.287 に答える