スキーム、文字列の代わりにシンボルを使用するのはいつですか?
-
30-09-2019 - |
質問
原始的な英語について事前にお詫び申し上げます。文法的なエラーなどを避けるために最善を尽くします。
2週間前、私はスキーム(およびその啓発)の知識を、手の間に手に入れた数学の資料、特にオートマトン理論と登録されている計算に関するコースの通常の言語を実装することにしました。
これまでのところ、私はアルファベットを代表しています シンボルのリスト それ以外の
- Charsのリストは、可変サイズの文字が必要なためです。
- 文字列のリストは、それは幾分存在しないと感じているからです。
私は経験不足で、この特定の選択についてあなたの意見を知りたいと思います。シンボルは特定の種類のタスクのために予約されていますか?これにより、私はそれらを悪用していますか?これに関するコメントは、私がガイダンスを求めていることで非常に感謝しています。
さらに手を伸ばすと、アルファベットの上に可能なすべての単語のセットを実装する時間もあります。これは無限です。私は、許可されている単語の最大サイズでセットを制限することを考えていました。繰り返しますが、これは良い習慣ですか、それとも代わりにストリームに行くべきですか?ストリームはより良いアプローチになると感じていますが、まだ学んだことがないので、それらを使用するという意味が本当にわかりません。
とにかく、提案や解説は歓迎されます。あなたが私の疑問を読むのにかかった時間に本当に感謝しています。良い週末を!
解決
簡単な違いは、シンボルが比較するのが非常に安価であることです。使用できます 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")))
リストを返します (4 "match")
. 。ただし、文字列をキーとして使用する場合 assq
もはや十分ではなく、それを使用します eq?
むしろ、比較のための手順 assoc
使用する必要があります equal?
手順は、構造を再帰的に比較するため、はるかに費用がかかります。上記の実装は、実際には、通訳者の連想配列と環境をモデル化する方法としてしばしば使用するのに十分な安価ですが、確かにランダムアクセスではありません。
編集:あなたが尋ねたように、ストリームについて:
スキーム標準は素敵なペアをサポートし、1つは呼ばれる関数です force
, 、もう1つはaです 特別なフォーム 呼び出されました 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
)
約束が実際に一度だけ評価されることが明らかになり、再び強制されると、初めて評価されたときと同じ値が得られます。
これは、通常、ストリームまたは概念的な「無限のリスト」で使用されるものです。この場合のリストのCDRは、取得したときに強制される残りのリストの約束です。それ以外の場合は、非終了計算に変わるように、たとえば、一般的に定義します。
(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))))
スキームコンパイラまたはインタープリターは、すべての発生を翻訳します (stream-cons x y)
に (cons x (delay y))
任意の任意のxおよび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ゼロ)は、完全に満たされたストリームを生成します。 FIBSストリームは、それ自体が再帰的に定義されています。最初の2つの要素が与えられ、残りはたまたまFIBとFIBS自体のストリームCDRである2つのストリームから計算されます。