C 通过对除记录之外的所有类型使用结构等价来避免类型图中的循环

Question

以下为红龙书节选

Consider a linked list of cells, each containing some integer information and a pointer to the next cell in the list. Pascal declarations of type names corresponding to links and cells are:
type link = ↑ cell; 
    cell = record 
               info : integer;
               next : link
           end; 
Note that the type name link is defined in terms of cell and that cell is defined in terms of link, so their definitions are recursive.

Recursively defined type names can be substituted out if we are willing to introduce cycles into the type graph. If pointer (cell) is substituted for link, the type expression shown in Fig. 6.8(a) is obtained for cell. Using cycles as in Fig. 6.8(b), we can eliminate mention of cell from the part of the type graph below the node labeled record.

Example: C avoids cycles in type graphs by using structural equivalence for all types except records.

In C, the declaration of cell would look like
struct cell { 
      int info; 
      struct cell *next; 
 }; 
C uses the keyword struct rather than record, and the name cell becomes part of the type of the record. In effect, C uses the acyclic representation in Fig. 6.8(a).

C requires type names to be declared before they are used, with the exception of allowing pointers to undeclared record types. All potential cycles, therefore, are due to pointers to records. Since the name of a record is part of its type, testing for structural equivalence stops when a record constructor is reached - either the types being compared are equivalent because they are the same named record type or they are inequivalent. □

我的疑惑如下：

对应写的Pascal代码我们可以写一个C代码来模仿它：

   typedef struct cell* link;
   struct cell{
         int info;
         link next;
   };

现在是不是要将上面使用 typedef 的声明转换为上面摘录中给出的代码（typedef 被展开）？

名称单元格成为记录类型的一部分。现在，如果我们将结构声明为：

   typedef struct {
         int info;
   }cell;

虽然上面的定义不等同于Pascal的定义，但是名字cell现在还是记录类型的一部分吗？

Answer 1

在 C 中，typedef 名称是别名；这是标准中使用的实际词。别名是宏的一小步；别名是有范围的，它们代表实际事物（在本例中为类型），而不是将在上下文中重新解释的输入流。

所以它们比宏更规范一些，足以使用。但它们仍然完全是一个标签，原则上可以在编译之前用它们代表的实际对象替换整个代码。（在 AST 中，就是这样。显然没有办法在程序文本中进行替换。）

因此，在 C 中，同一类型 的两个不同别名是 同一类型。别名消失了；这只是程序员的方便。

struct 标签并非如此。具有不同标签的两个 struct 类型是不同的类型，即使它们的定义在其他方面是相同的。标记是类型标识的一部分。

C 中一个有趣的例子是没有标签的复合类型。这是合法的，但它的作用就好像每个文本定义都为缺失的标签插入了一个唯一的名称。这样的struct不能被引用两次，所以下面虽然合法，但是函数调用不了：

int f(struct {int a;} x) { return x.a; }

（实际上，这是一个谎言。您可以从不同的文件调用该函数，因为允许跨文件调用使用 compatible 类型。但这是不同的讨论。）

但是如果你给一个未标记的结构一个别名，你可以随意使用别名。这就是替换所表示的事物（复合类型）与宏样式文本替换之间的区别。因此，这两者之间有很大的区别

typedef struct { int a; } T;
#define T struct { int a; } // NEVER DO THIS

C 通过对除记录之外的所有类型使用结构等价来避免类型图中的循环

C avoids cycles in type graphs by using structural equivalence for all types except records

c

compiler-construction

record

pascal

typechecking