lisp - 我对 LISP cons-cell 列表的定义是否正确？

Question

我试图真正理解 LISP，以便为向前发展打下良好的基础，但进展缓慢，因为 LISP(在我的例子中特别是 Common Lisp)不遵循任何 C 系列命名约定。

这是我个人对 LISP 列表的定义，它基本上正确吗？: LISP 中的所有列表都是使用 void 指针作为节点和下一个指针的单链表构造的。

编辑:为澄清起见，我使用“空指针”一词来表示关于 cons-cell 的 CAR 和 CDR 的性质的想法。我知道 LISP 中不存在“空指针”，我正在尝试将 C 中的概念应用到 LISP 中

Answer 1

用 C 语言术语表示的基本 Lisp 数据结构可能如下所示:

/* A value is a "discriminated union". */
typedef struct value {
  /* It has a type field. */
  enum type { t_cons, t_symbol, t_fixnum, t_character /* , ... */ } type;

  /* And then one of several payloads, overlaid in the same space,
     which one being there depending on the type field. */
  union {
    struct symbol *sym;
    struct cons *cons;
    int fixnum;   /* unboxed integer: no heap allocation */
    /* ... */
  } u;
} value;

/* This is the heap-allocated part of a cons cell;
   not the complete cons cell value, which is actually
   of "struct value" type. See cons()
   function below which makes a cons value. */
struct cons {
  struct value car, cdr;
};

static  value nil = { t_symbol };

value cons(value a, value d)
{
   value retv;
   struct cons *c = allocate_cons(); /* from special cons heap */
   c->car = a;
   c->cdr = c;
   retv.type = t_cons;
   retv.u.cons = c;
   return retv;
}

int is_nil(value v)
{
  return (v.type == t_symbol && v.sym == NULL);
}

value cons(value a, value d)
{
   struct value retv;
   struct cons *c = allocate_cons(); /* from special cons heap */
   c->car = a;
   c->cdr = c;
   retv.type = t_cons;
   retv.u.cons = c;
   return retv;
}

value car(value arg)
{
  switch (arg.type) {
  case t_cons:
    return arg.u.cons->car;
  case t_symbol:
    if (is_nil(arg))   /* (car nil) -> nil */
      return nil;
    /* fallthrough */
  default:
    /* This function generates a Lisp exception somehow */
    throw_error("car: not applicable to ~s", arg);
  }
}

Lisp 概念并没有详细说明数据结构。

实际的 Lisp 实现通常会做一些更聪明的事情来更紧凑地表示 value。一种常见的技术是使用机器字(现在通常是指针大小)作为 Lisp 值，并在该字中使用几个标记位来指示它是否是指向堆上某物的指针，或者整数的直接表示。 (这意味着 Lisp fixnum 整数不使用所有可用的 32 或 64 位，但可能只使用 30 或 62。更大的整数是不同类型的 bignum ，并且是堆分配的。)

但是，为值而不是指针使用结构为浮点值的按值语义创造了机会，这对数字代码来说是一个胜利。这意味着浮点对象不必在堆中分配，而是存储在一个值中。

用 C 编写的 Lisp 实现可以做这种诡计，但它会导致 ISO C 未定义的行为，并且声明和代码不适合说明目的。

对于这种类型的表示，一个很好的细节是为 Lisp 符号 nil 使用 C 空指针。然后任何用 C 编写的内部例程都可以使用与 Lisp 相同的约定以符合人体工程学的方式编写:nil 既是假又是空列表。

C 深受 Lisp 的影响，因为它基于返回值的表达式，并且空指针为假。 C 中的 a?b:c 三元运算符有点像 Lisp 的 (if a b c) 的仿制品。

引导一些看起来像 Lisp 语义的东西需要相当多的 C 代码行，并且它的许多方面都有多种设计选择。因此，最好将Lisp理解为一种抽象，而不是通过特定的详细数据结构和执行模型设计，更不用说用C表达了。