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

Question

我正在努力真正理解LISP,以便有一个良好的基础向前发展,但它一直很慢,因为LISP(在我的情况下特别是Common Lisp)不遵循任何C族命名约定.

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

编辑:为了澄清,我使用"无效指针"这个词来表示关于cons-cell的CAR和CDR的本质的想法.我理解LISP中不存在'void指针',我试图在这里将概念从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未定义的行为,并且声明和代码不是出于说明目的.

使用这种类型的表示,一个很好的细节是使用Cp空指针作为Lisp符号nil.然后用C语言编写的任何内部例程都可以使用与Lisp相同的约定进行人体工程学编写:这nil既是假也是空列表.

C受Lisp的影响很大,因为它基于返回值的表达式,而空指针是假的.a?b:cC语言中的三元运算符有点像Lisp的淘汰(if a b c).

它需要很多C代码来引导一些类似于Lisp的语义,并且它有很多设计选择.因此,最好尝试将Lisp理解为抽象,而不是通过特定的详细数据结构和执行模型设计,更不用说用C表示的了.