0

我试图了解静态定义的数据结构和动态定义的数据结构之间的方案有什么不同。

我知道静态定义的数据结构是在编译时创建的，而动态定义的数据结构是在运行时创建的，但这在实践中意味着什么？

谢谢！

4

1 回答 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 个字的内存块的方法：一个机器字用于每个xand y，第三个机器字用于保存指向另一个坐标的指针（我们假设我们'重新将这些记录链接到一个列表中）。该声明还表明x和y表示有符号整数（在字长允许的范围内），而next表示指向坐标的指针。

（指针，即内存地址，与任意整数完全不同，尽管在某些语言的语法和实现中双关语在某些上下文中将指针和整数混为一谈。）

另一个重要的细节是，每个标识符都明显受限于它允许保存的值的类型。对于结构字段（x、y和next以上）以及参数和局部变量都是如此，如下面的函数定义sum_coords所示。

将每个坐标解释为二维平面中的向量，可以将所有坐标添加到坐标列表中，如下所示：

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显然仅限于持有coord_t*并且c显然仅限于持有coord_taka struct 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 实现中，每对只占用两个单词，而向量和字符串每个都有一个单独的大小，在分配它们的时候提供。（过程对象实例所需的内存高度依赖于 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 风格，因为即使方案编译器/解释器不需要这样的注释，阅读您的代码的其他人几乎肯定会需要它们。（有关此主题的更多信息，请参阅文本如何设计程序。）

  • 不需要明确声明表示 a 的列表的元素Coordinate是数字；Scheme 运行时将在必要时携带该信息（以便您可以使用谓词number?来查看携带的值是否为数字）。

Scheme 的类型安全实现将在必要时检查操作，例如+提供的参数是数字（而不是对对的引用，或对向量的引用等）；但是，R5RS 报告本身说：“向操作提供未指定处理的参数是错误的”；根据报告的约定，不一定会检测到此类错误，并且未指定后续行为。

  • 同样，变量c并没有明显地被限制为只能保存两个元素列表。也就是说，此过程并不固有地规定由 表示的值c必须始终看起来像与我们的数据定义匹配的坐标。只有通过编程约定，我们才会尝试确保这样的约束成立；编程语言与它无关。

  • 在 R5RS 方案中，不将类型与一对或向量的子组件相关联；任何值都可以被一对或向量的任何元素car引用。cdr将此与 C 代码进行比较，在 C 代码中，我们只能将intptr_t值放入 的x和y字段中struct coordinate，并且只能将struct coordinate*（即指向坐标的指针）放入next字段中。

最后一点是区分动态与静态的一个关键区别：在像上面这样的 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.

这个 bug 有点难找（尽管如果按照设计秘诀，就永远不会写出上面的代码）。但是有人可能会声称，在 Scheme 中这个错误很容易犯，因为该语言鼓励使用列表和对来表示所有内容，因此并不总是有保护措施阻止您将 Coordinate（一种列表）传递给一个点需要一个 CoordinateList （另一种列表）。（Scheme 的一些方言，例如Typed Racket ，为用户提供了静态定义数据类型的方法，以便编译器可以再次提供此类帮助。）

当然，在像 C 这样的语言中，类型系统主要是为了告诉编译器如何在内存中布局对象。在 C 中使用 typecast 来传递一个期望的struct coordinate*地方是非常简单的intptr_t，而且你不太可能得到一个很好的消息

 > (sum-coords '((1 4) (2 3) (3 2) (4 1)))
 Error: +: (4 1) is not a number.

所以你应该对两者之间的这种所谓的“区别”持保留态度。“类型安全”和“静态类型”之间存在很大差异。（简而言之，R5RS Scheme 和 C 都不是类型安全的，尽管 R5RS Scheme 的几个实现是类型安全的，或者试图是类型安全的。）

  • 另一个可以区分动态和静态的地方：我可能选择这样编写数据定义：

    ;; 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并没有明显地限制为仅包含两个数字元素列表。

（当然，在像 C++ 这样的语言中，可以通过子类化实现大致相同的目标，在 C 中也可以通过在其前三个单词中定义具有相同布局的另一个结构来实现 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 代码中的每个坐标由三个机器字组成；坐标结构中的第三个单词携带下一个元素的链接字段。在 Scheme 中更直接地编写它的一种方法是数据定义，例如

;; A Coordset is one of '(), or (vector Number Number Coordset)

这将导致对上面编写的 C 代码进行更忠实的逐字音译，但不太忠实于 Scheme 的精神，其中将坐标结构和链接结构解耦更为惯用。

通过语法扩展和其他方案方言的结构定义

尽管 R5RS Scheme 没有用于声明结构的特殊形式，但 R5RS 确实定义了一个宏系统，可以在其中定义此类记录语法。

此外， Racket和Chez等几种 Scheme 方言提供了语言扩展，用于定义称为记录的结构化数据。即使在后两种情况下，记录仍然是一个潜在的动态实体：可以动态创建新的记录类型，而不必在编译时预先提供所有所需的记录类型。但仅仅因为某些事情可以动态完成并不意味着它应该是，正如 Chez 手册中所解释的：

过程接口比句法接口更灵活，但这种灵活性会导致程序的可读性降低，并损害编译器生成高效代码的能力。只要够用，程序员就应该使用语法接口。

结论

用 C 和 Scheme 等语言定义数据结构的方式有很多不同。在 C 语言中，您需要预先说明数据结构中出现了多少条目，以及它们的类型是什么；对于参数和局部变量也是如此。在 Scheme 中，您可以在评论中说多少就说多少，然后相应地编写代码。

于 2013-02-12T01:06:29.717 回答