静的に定義されたデータ構造と動的に定義されたデータ構造のスキームの違いを理解しようとしています。
静的に定義されたデータ構造はコンパイル時に作成され、動的に定義されたデータ構造は実行時に作成されることは知っていますが、これは実際にはどういう意味ですか?
ありがとう！
質問する
379 次
1 に答える
4
あなたの質問は少し曖昧で不正確です。
あなたの質問に答えるには、「静的に定義されたデータ構造」と「動的に定義されたデータ構造」の意味を明確に理解する必要があります。結局、実際には、ほとんどのデータ構造インスタンスは実行時に作成されます (静的構造型が割り当てられているか、動的に定義されたレコードの寄せ集めであるかに関係なく)。したがって、少なくとも質問の最後のステートメントによると、これは、そのような構造がいつ作成されるかについてのあなたの理解と矛盾しているように見えます。
あなたが何を意味するのかを推測しようとした後、Scheme と他の有名な言語との比較を提供することにしました。それは、「静的に定義された」とは何を意味するのかについて共通の理解が得られる可能性が最も高い領域のように思われるからです。 .
静的に定義されたデータ構造 (C の例を含む)
Scheme ( R5RSのように) は、少なくとも Pascal、C、および C++ などの他の言語と比較すると、データ構造の静的定義では特に有名ではありません。(レキシカル スコープと静的な名前解決に厳密に準拠しているため、多くの点でPerl や Python などの他の言語よりも静的です。)
Pascal や C などの言語では、通常、明示的な構造体またはクラス定義を独立した宣言に書き出します。このような明示的な定義は、静的に(つまり、コンパイル時に) 以下を定義します。
構造体の各インスタンスを表すために割り当てられるメモリのバイト数
インスタンスから抽出されたときに、構造体の各インスタンスのメンバー/フィールドがどのように解釈されることを意図しているか。
したがって、C では、次のような宣言を行います。
typedef struct coordinate coord_t;
struct coordinate {
intptr_t x;
intptr_t y;
coord_t *next;
};
struct coordinateは、型が 3 ワードを占有するメモリ ブロックを表すxようにすることをコンパイラに伝える方法ですy。これらのレコードをリストにリンクします)。この宣言は、 および が符号付き整数 (ワード サイズで許可されている範囲内) であることxもy示し、一方next、座標へのポインターを示します。
(ポインタ、つまりメモリアドレスは、任意の整数とはまったく異なりますが、一部のコンテキストではポインタと整数を混同する一部の言語の構文および実装の駄洒落があります。)
もう 1 つの重要な詳細は、各識別子が保持できる値の型に明示的に制限されていることです。xこれは、以下の関数定義に示されているように、構造体フィールド ( 、y、およびnext上記) とパラメーターおよびローカル変数の両方に当てはまりsum_coordsます。
各座標を 2 次元平面のベクトルとして解釈すると、次のようにすべての座標を座標のリストに追加できます。
coord_t sum_coords(coord_t *coords)
{
coord_t c;
c.x = 0;
c.y = 0;
c.next = NULL;
while (coords != NULL) {
c.x += coords->x;
c.y += coords->y;
coords = coords->next;
}
return c;
}
coordsのみを保持するように明示的に制約され、akaのみcoord_t*を保持するように明示的に制約されていることに注意してください。型キャストを明示的に使用せずにその制約に違反しようとすると、コンパイラは次のようにプログラムのコンパイルを拒否する可能性があります。ccoord_tstruct coordinate
coord_t sum_coords(coord_t *coords)
{
coord_t c;
c = coords; // <-- compiler error: incompatible types in assignment
...
}
ここまでは順調ですね。しかしもちろん、あなたの質問はSchemeに関するものでした。
動的に定義されたデータ構造 (Scheme の例を使用)
典型的な R5RS スキーム コードは、上記のようには機能しません。R5RS スキームでは、データ型の各インスタンスに関連付けるメモリの量や、インスタンスのメモリ ブロック内のバイトをどのように解釈するかを記述する、スキーム コンパイラ/インタプリタによって解釈される個別の宣言を書き出すことはありません。
上記のような構造定義を使用する代わりに、R5RS スキームでは、複合データを作成するために、ペア、ベクトル、文字列、またはプロシージャ オブジェクトを割り当てます。(Scheme のリストはペアで構成されます。)多くの Scheme 実装では、各ペアは正確に 2 つの単語を占有しますが、ベクトルと文字列はそれぞれ、割り当てられた時点で提供される個別のサイズを持ちます。(プロシージャ オブジェクトのインスタンスに必要なメモリは、Scheme ランタイムと、それがクロージャとレキシカル環境をどのように表すかによって大きく異なります。)ポイントは、通常、データによって使用される機械語の数について考えさえしないということです。構造インスタンス; 代わりに、まず目の前の問題を解決することに集中し、そのような努力が必要であると判断するまで、バイト数について心配することを延期します。
とにかく、ポイントは、R5RS スキームでは、座標構造がどのように表現されるかをコンパイラ/インタプリタに伝える必要がないということです。少なくとも、その目的のためだけに追加された分離されたランタイム解析宣言ではありません。
代わりに、次のように書くことができます。
;; A Coordinate is a (list Number Number)
;; A CoordinateList is one of:
;; - '()
;; - (cons c cl), where c is a Coordinate and cl is a CoordinateList
;; sum-coords: CoordinateList -> Coordinate
(define (sum-coords l)
(cond ((null? l) (list 0 0))
(else (let ((c (car l))
(sum-of-rest (sum-coords (cdr l))))
(list (+ (list-ref c 0) (list-ref sum-of-rest 0))
(+ (list-ref c 1) (list-ref sum-of-rest 1)))))))
;; Below is in the REPL:
> (sum-coords '((1 4) (2 3) (3 2) (4 1)))
(10 10)
いくつかの違い:
ここで、データがどのようにレイアウトされるかの説明は、コードではなく、Schemeコメントにあります。このようなコメントは優れた Scheme スタイルです。Scheme コンパイラ/インタプリタはそのようなコメントを必要としませんが、あなたのコードを読む他の人間はほぼ確実にそれらを必要とするからです。(このトピックの詳細については、テキストHow to Design Programs を参照してください。)
Coordinatea を表すリストの要素が数値であることを明示的に宣言する必要はありません。代わりに、Scheme ランタイムはその情報を必要に応じて持ち運ぶ (述語を使用number?して、運ばれる値が数値であるかどうかを確認できるようにするため)。
Scheme のタイプ セーフな実装は、必要に応じて、+提供された引数が数値であるような操作をチェックインします (ペアへの参照やベクトルへの参照などではありません)。ただし、R5RSレポート自体には、「処理するように指定されていない引数が操作に提示されるのはエラーです」と記載されています。レポートの慣例によると、このようなエラーは必ずしも検出されるとは限らず、その後の動作は特定されていません。
同様に、変数
cは2 つの要素リストのみを保持するように明示的に制限されているわけではありません。つまり、この手順は、によって示される値cが常にデータ定義に一致する Coordinate のように見える必要があることを本質的に指示するものではありません。このような制約が保持されることを保証しようとするのは、プログラミングの慣例によるだけです。プログラミング言語はそれとは何の関係もありません。R5RS スキームでは、タイプをペアまたはベクトルのサブコンポーネントに関連付けません。任意の値は、ペアの または によって、またはベクトルの任意の要素によって参照でき
carますcdr。これを C コードと比較してください。ここでは、 のおよびフィールドにintptr_t値を入れることしかできず、フィールド(つまり、座標へのポインター) に入れることしかできませんでした。xystruct coordinatestruct coordinate*next
最後の点は、動的と静的を区別する重要な違いの 1 つです。上記のような Scheme プログラムでは、リスト (ペア) とベクトルを扱う際に、あらゆる種類の値を入れることができるため、大きな自由が得られます。この自由は、多くのパワーと柔軟性を提供します。しかし、何かをあきらめることもあります。間違った種類の値をペアまたはベクトルに入れると、コンパイラが教えてくれる助けを失い、依存している他のコードの仮定を壊します。
たとえば、次のバリアントを考えてみましょうsum-coords:
(define (sum-coords l)
(cond ((null? l) (list 0 0))
(else (let* ((c (car l))
(s (sum-coords (cdr c))))
(list (+ (car (car l)) (car c))
(+ (car (cdr c)) (car (cdr s))))))))
このバージョンは意図的に難読化しています。バグがあります。実行すると、エラーが発生します。
> (sum-coords '((1 4) (2 3) (3 2) (4 1)))
Error: cdr: 4 is not a pair.
バグを見つけるのは少し難しいです (ただし、設計レシピに従っていれば、上記のコードを書くことはなかったでしょう)。しかし、Scheme ではこの間違いを犯しやすいと主張する人もいるかもしれません。Scheme では、すべてを表すためにリストとペアの使用が推奨されているためです。そのため、Coordinate (リストの一種) をスポットに渡すことを妨げる保護手段が常にあるとは限りません。 CoordinateList (別の種類のリスト) が必要です。( Typed Racketなど、Scheme の一部の方言は、ユーザーがデータ型を静的に定義する方法を提供し、コンパイラが再びそのような支援を提供できるようにします。)
もちろん、C などの言語では、型システムは主に、メモリ内でオブジェクトをレイアウトする方法をコンパイラに伝えるために用意されています。C では、型キャストを使用して、期待されるstruct coordinate*場所にa を渡すことができるようにするのは非常に簡単です。intptr_t
> (sum-coords '((1 4) (2 3) (3 2) (4 1)))
Error: +: (4 1) is not a number.
したがって、この 2 つのいわゆる「区別」は、大まかに理解する必要があります。「型安全」と「静的型付け」には大きな違いがあります。(要するに、R5RS スキームも C もタイプ セーフではありませんが、R5RS スキームのいくつかの実装はタイプセーフであるか、そうしようと試みています。)
動的と静的を区別する可能性のある別の場所: データ定義を次のように記述することを選択した可能性があります。
;; A Coordinate is a (list Number Number Any ...);; interpretation: A Coordinate (list x y payload ...) is a point at location <x,y> on a 2D plane, with a metadata payload also associated with the point.
現在、 sum-coords の元の実装は、この定義で「機能」しています。ユーザーは追加情報 (色や点のラベルなど) をリストの追加要素として自由に投げることができ、X 要素と Y 要素を合計することもできます。cこれは、数値の 2 つの要素リストのみを保持するように明示的に制限されていない上記の点に関連しています。
(もちろん、C++ のような言語では、サブクラス化によってほぼ同じ目標を達成できます。また、C でも、最初の 3 ワードで layout と同じレイアウトを持つ別の構造を定義struct coordinateし、リンクされたリストを構築するときにキャストを型付けすることで達成できます。その時点で、これらの言語のいずれにおいても、事実上、データ構造定義のより動的なスタイルに戻りつつあります。それは、両極端の間のスペクトルをどこまで進むかという問題です。)
Scheme コードと構造的抽象化に関する注意事項
個別の構造体宣言を行う必要はありませんが、データ型を操作するための小さな一連のプロシージャを定義し、それらを他のすべての操作で使用することを意図した抽象インターフェイスとして使用するのは良いスタイルです。この場合、次のようにしようとします。
;; coord : Number Number -> Coordinate
(define (coord x y) (list x y))
;; coord-x : Coordinate -> Number
(define (coord-x c) (list-ref c 0))
;; coord-y : Coordinate -> Number
(define (coord-y c) (list-ref c 1))
これは完璧ではありません (漏れやすい抽象化です) が、これは出発点です。sum-coordsもちろん、のリスト表現に直接アクセスする代わりに、これらの手続きを使用するように修正することも期待されCoordinateます。
CからSchemeへの音訳（またはその欠如）に関する注意
Scheme コードは、C コードの完全な類似物であるとは意図されて いないことに注意してください。
たとえば、C コードの各座標は 3 つの機械語で構成されていました。座標構造体の 3 番目の単語は、次の要素のリンク フィールドを保持していました。それをSchemeでより直接的に記述する1つの方法は、次のようなデータ定義です。
;; A Coordset is one of '(), or (vector Number Number Coordset)
これは、上記の C コードのより忠実な単語ごとの音訳につながりますが、Scheme の精神にはあまり忠実ではなく、座標構造とリンクされた構造を分離することがより慣用的です。
構文拡張による構造定義、および他のスキーム方言での構造定義
R5RS スキームには構造を宣言するための特別な形式はありませんが、R5RS はそのようなレコード構文を定義できるマクロ システムを定義します。
また、 RacketやChezなどのいくつかの Scheme 方言は、レコードと呼ばれる構造化データを定義するための言語拡張を提供します。後者の 2 つのケースでも、レコードは潜在的に動的なエンティティのままです。コンパイル時にすべての必要なレコード タイプを事前に提供する必要はなく、その場で新しいレコード タイプを作成できます。しかし、Chez のマニュアルで説明されているように、何かを動的に実行できるからといって、そうすべきであるとは限りません。
手続き型インターフェイスは構文インターフェイスよりも柔軟性がありますが、この柔軟性により、プログラムが読みにくくなり、効率的なコードを生成するコンパイラの機能が損なわれる可能性があります。プログラマは、それで十分な場合はいつでも構文インターフェイスを使用する必要があります。
結論
C のような言語と、Scheme のような言語でデータ構造を定義する方法には、多くの違いがあります。C では、データ構造に出現するエントリの数とその型を前もって指定する必要があります。パラメータとローカル変数についても同様です。Scheme では、コメントで好きなだけ発言し、それに応じてコードを記述します。
于 2013-02-12T01:06:29.717 に答える