LISP generalized lists in C

Discussion in 'C Programming' started by Jean-Guillaume Pyraksos, Apr 11, 2006.

  1. 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
     
    Jean-Guillaume Pyraksos, Apr 11, 2006
    #1
    1. Advertising

  2. Jean-Guillaume Pyraksos

    Eric Sosman Guest

    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/

    --
     
    Eric Sosman, Apr 11, 2006
    #2
    1. Advertising

  3. Jean-Guillaume Pyraksos

    tmp123 Guest

    Jean-Guillaume Pyraksos wrote:
    > 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.
     
    tmp123, Apr 11, 2006
    #3
  4. On Tue, 11 Apr 2006 16:00:32 +0200, Jean-Guillaume Pyraksos wrote:

    > 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
     
    Duncan Muirhead, Apr 11, 2006
    #4
  5. In article <>, "tmp123" <> writes:
    > Jean-Guillaume Pyraksos wrote:
    > > I want to work with "generalized lists" as in Lisp, say :

    >
    > 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

    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
     
    Michael Wojcik, Apr 12, 2006
    #5
  6. Jean-Guillaume Pyraksos

    tmp123 Guest

    Michael Wojcik wrote:
    > In article <>, "tmp123" <> writes:
    > > Jean-Guillaume Pyraksos wrote:
    > > > I want to work with "generalized lists" as in Lisp, say :

    > >
    > > 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.
     
    tmp123, Apr 13, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. venkat
    Replies:
    3
    Views:
    1,560
    Robert Kern
    Jun 1, 2005
  2. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    409
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  3. ekzept
    Replies:
    0
    Views:
    372
    ekzept
    Aug 10, 2007
  4. nanothermite911fbibustards
    Replies:
    0
    Views:
    378
    nanothermite911fbibustards
    Jun 16, 2010
  5. nanothermite911fbibustards
    Replies:
    0
    Views:
    318
    nanothermite911fbibustards
    Jun 16, 2010
Loading...

Share This Page