4

初歩的な英語で申し訳ありません。文法上の誤りなどを避けるために最善を尽くします。

2 週間前、私は手で手に入れた数学の教材、特に私が登録しているオートマトン理論と計算のコースの通常言語を実装しながら、Scheme (およびその啓蒙) の知識を新たにすることにしました。

これまでのところ、私はアルファベットを記号のリストとして表現してきました。

  1. 可変サイズの文字が必要なため、文字のリスト。
  2. 文字列のリストは、エレガントではないと感じるからです。

私は経験が浅いので、この特定の選択についてあなたの意見を知りたいです. シンボルは特定の種類のタスク用に予約されていますか?これにより、シンボルを誤用していますか? これに関するコメントは、ガイダンスを求めているため、非常に高く評価されます。

さらに進むと、無限にあるアルファベットで可能なすべての単語のセットを実装する時が来るでしょう。許可される単語の最大サイズによってセットを制限することを考えていました。繰り返しますが、これは良い習慣ですか、それとも代わりにストリームに行くべきですか? ストリームの方がより良いアプローチだと思いますが、まだ学んでいないので、ストリームを使用することの意味がよくわかりません。

とにかく、提案やコメントは大歓迎です。私の疑問を読むのに時間を割いていただき、本当に感謝しています。良い週末を！

4

1 に答える 1

7

単純な違いは、シンボルは比較するのが非常に安いということです。eq?2 つのシンボルを同一として比較するために使用できます。これは、コンパイル時に、コンパイラが基本的にすべてのシンボルを数値で列挙するためです。そのため、整数を比較しているだけで、非常に安価なマシン操作です。

これは、2 つの記号が同じ文字から構成されている場合にのみ同一であることを意味します。コード内で同じ文字を持つ 2 つのシンボルを識別する方法はありません。それらは定数であり、 と のように同じオブジェクト3です3。

ただし、2 つの文字列は、メモリの異なる場所に存在する異なるオブジェクトである可能性が非常に高く、それらを比較するには、すべての文字を個別に比較して一致させる必要があります。

したがって、シンボルは、たとえば次のことを考慮して、このために使用する必要があり、よく使用されます。

(assq 'symb  '((foo 1 2 3) (bar symb) (symb "match")))

(symb "match")これは、比較するのと同じくらい安価なリストを返します。

(assq 4  '((0 1 2 3) (1 symb) (4 "match")))

list を返します(4 "match")。ただし、文字列をキーとして使用する場合は、比較にプロシージャassqを使用するだけでは十分ではなく、構造を再帰的に比較するため、はるかにコストがかかるプロシージャを使用する必要があります。上記の実装は、確かにランダムアクセスではありませんが、インタープリターで連想配列と環境をモデル化する方法としてよく使用されるほど、実際には十分に安価です。eq?assocequal?

編集：あなたが尋ねたように、ストリームで：

Scheme 標準はナイス ペアをサポートしています。1 つは と呼ばれる関数forceで、もう 1 つは と呼ばれる特別な形式delayです。効果的に何

(delay (+ 1 2 3))

または、戻り値の代わりにあるその他のコード(+ 1 2 3)は、いわゆる「プロミス」です。そのプロミスの答えの計算を遅らせますが、6そこに到達したと評価されたときに結果が同じになることを約束します。これはまったく役に立たないように思えるかもしれませんが、結果が変更可能な変数に依存しているとします。

(define x 4) ; x is bound to 4.
(let ((promise (delay (+ 2 x)))) ; evaluating the expression now would result into 6, but we delay it.
  (set! x 5) ; we change the value of x.
  (display (force promise)) ; displays 7
  (set! x 6) ; change it again
  (force promise) ; ALSO displays 7, not 8
)

promise が実際に 1 回だけ評価されることが明らかになり、再度強制されると、最初に評価されたときと同じ値が生成されます。

これは通常、ストリーム、または概念的な「無限リスト」で使用されるものです。この場合のリストの cdr は、リストの残りの部分に対する promise であり、取得時に強制されます。それ以外の場合は、終了しない計算になります。たとえば、通常、次のように定義します。

(define (stream-cdr x) (force (cdr x))) ; it forces that promise to evaluate it.
; and optionally
(define stream-car car) ; same

これは引数を評価できないため、特別な形式である必要があります。

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons x y)
     (cons x (delay y))))

これで、Scheme コンパイラまたはインタプリタは、任意の x および y に対してすべての(stream-cons x y)toを変換します。(cons x (delay y))

簡単な例として、必要になるまで評価を遅らせたので、ゼロの無限リストを作成できます。

(define zero-stream (stream-cons 0 zero-streams))

ストリームを使用していない場合、リストは決して終了しないはずです。無駄ですが、アイデアを示しています。stream-cdr空のリストに到達することなく、これを何度も何度も使用できます。同じ「0の無限リスト」が再び返されます。

より実用的な例は、すべてのフィボナッチ数のリストです。これはやや複雑です。

(define fibs 
  (stream-cons 0 (stream-cons 1
    (stream-map + fibs (stream-cdr fibs))))

ストリーム マップは法線マップの類似物です。その定義は非常に複雑ですが、調べればわかると思います。それ自体がストリームを生成します。したがって、`(stream-map (lambda (xy) (+ 1 xy)) zeroes zeroes) は、完全に 1 で満たされたストリームを生成します。fibs ストリームは、それ自体で再帰的に定義されます。最初の 2 つの要素が与えられ、残りはたまたま fibs である 2 つのストリームと fibs 自体のストリーム cdr から計算されます。

于 2010-06-27T17:57:21.710 に答える