LISP generalized lists in C

[Jean-Guillaume Pyraksos]

I want to work with "generalized lists" as in Lisp, say :

((23 () . 2) () ((10))) ; only pointers and integers

So the basic element is a node, a struct with two fields car and cdr.
Each of these fields can contain either a pointer (NULL or a pointer to
another node), or an int.

I want to define the functions cons, car and cdr of Lisp.

I tried this but gcc rejects it :

#include <stdio.h>
#include <stdlib.h>

typedef struct {
object car;
object cdr;
} node;

typedef struct {
int tag; // 0==int, 1==node*
union {
int value;
node *ptr;
} val;
} object;

node* cons(object a, object b) { ...}

Can you help ? Thanks...

JG

 

[Eric Sosman]

Jean-Guillaume Pyraksos wrote On 04/11/06 10:00,:

I want to work with "generalized lists" as in Lisp, say :

((23 () . 2) () ((10))) ; only pointers and integers

So the basic element is a node, a struct with two fields car and cdr.
Each of these fields can contain either a pointer (NULL or a pointer to
another node), or an int.
[...]

This is Question 1.15 in the comp.lang.c Frequently
Asked Questions (FAQ) list

http://www.c-faq.com/

 

[tmp123]

I want to work with "generalized lists" as in Lisp, say :

[...]

See some inserted comments:

typedef struct {
object car;
object cdr;
} node;

In Lisp, the cdr of a list is a list, not an object. Thus:

object cdr => node *cdr;

that can be written in C like:

typedef struct node {
object car;
struct node *cdr;
} node;

typedef struct {
int tag; // 0==int, 1==node*
union {
int value;
node *ptr;
} val;
} object;

"object" must be declared before "node", because "node" uses it

node* cons(object a, object b) { ...}

"cons" in Lisp takes a list and an object, not two objects. And in C
better not to pass structures, but pointers to structures:

node *cons (object *a, node *b) { ... }


Kind regards.

 

[Duncan Muirhead]

I want to work with "generalized lists" as in Lisp, say :

((23 () . 2) () ((10))) ; only pointers and integers

So the basic element is a node, a struct with two fields car and cdr.
Each of these fields can contain either a pointer (NULL or a pointer to
another node), or an int.

I want to define the functions cons, car and cdr of Lisp.

I tried this but gcc rejects it :

#include <stdio.h>
#include <stdlib.h>

typedef struct {
object car;
object cdr;
} node;

typedef struct {
int tag; // 0==int, 1==node*
union {
int value;
node *ptr;
} val;
} object;

node* cons(object a, object b) { ...}

Can you help ? Thanks...

JG

This compiles (gcc 3.4)
typedef struct
{
int tag; /* 0==int, 1==node* */
union {
int value;
struct node_tag *ptr;
} val;
} object;

typedef struct node_tag
{
object car;
object cdr;
} node;
Duncan

 

[Michael Wojcik]

In Lisp, the cdr of a list is a list, not an object.

[OT] The cdr of a cons cell in a list is, by definition, a list
(possibly nil), but in general the cdr of a cons cell is not
necessarily a list. See "dotted pair". To implement general
LISP-style cons cells in C, you'd have to allow for cdrs that are
not pointers to other cons cells.

Thus:

[1]> (cons 'a 'b)
(A . B)
[2]> (cdr (cons 'a 'b))
B

--
Michael Wojcik (e-mail address removed)

Auden often writes like Disney. Like Disney, he knows the shape of beasts --
(& incidently he, too, might have a company of artists producing his lines) --
unlike Lawrence, he does not know what shapes or motivates these beasts.
-- Dylan Thomas

 

[tmp123]

In Lisp, the cdr of a list is a list, not an object.

[OT] The cdr of a cons cell in a list is, by definition, a list
(possibly nil), but in general the cdr of a cons cell is not
necessarily a list. See "dotted pair". To implement general
LISP-style cons cells in C, you'd have to allow for cdrs that are
not pointers to other cons cells.

Thus:

[1]> (cons 'a 'b)
(A . B)
[2]> (cdr (cons 'a 'b))
B

Thanks for the clarification. I didn't known it.