simple lisp interpreter help needed

Discussion in 'C Programming' started by Thomas, Aug 24, 2007.

  1. Thomas

    Thomas Guest

    Hello,


    I am a CS student and I want to write simple lisp interpreter. The code
    should be entierly in C. I don't want to use any compiler generators like
    Bison or Yak, since wrinting this in raw C will give me more experience. I
    wrote a simple lexer ( changes leksems into the streams of tokens). The Lisp
    dialect I have to implement is not defined in any formal way, but I have a
    description of how it should behave (say its a >>writen halformal
    description which leads me to confusion <<). I ask for some tips, materials
    or guidence. Oh and it should use some garbage collector, but I think this
    should be implemented in the end. I suppose I need to define data
    structures in a clear way. I don't give a description of that machine lisp
    abstraction, since all are similar. The fragment of the descripion is this :


    (...)Program in Ansi C an interpreter of Lisp dialect described above. It
    should contain efective implementation of the associate list, agregeting
    atoms linked with values by the pseudofunction define and using some simple
    garbage collector algorithm (the cell is alive, if it is possilble to reach
    it starting from the atom belonging to the association list. The symbolic
    data constructed during interpreter run should be put in array dyn_mem
    define for example like this:

    ======================================================================

    #define MEMSIZE 1024
    struct cell {
    union data *left, *right;
    };
    union data {
    int atom; /* when MSB == 1 */
    struct cell *next; /* when MSB == 0 */
    };
    struct cell dyn_mem[MEMSIZE];

    ======================================================================

    Notice that this structure doesn't have MSB, to add in the orginal MacArthy
    lisp it was the redundant part of data register ( 36 -th bit or something),
    suppose this trick wouldn't go by on a 386 .....
     
    Thomas, Aug 24, 2007
    #1
    1. Advertising

  2. Thomas

    Jack Klein Guest

    On Fri, 24 Aug 2007 16:16:51 +0200, "Thomas" <> wrote in
    comp.lang.c:

    > Hello,
    >
    >
    > I am a CS student and I want to write simple lisp interpreter. The code
    > should be entierly in C. I don't want to use any compiler generators like
    > Bison or Yak, since wrinting this in raw C will give me more experience. I
    > wrote a simple lexer ( changes leksems into the streams of tokens). The Lisp
    > dialect I have to implement is not defined in any formal way, but I have a
    > description of how it should behave (say its a >>writen halformal
    > description which leads me to confusion <<). I ask for some tips, materials
    > or guidence. Oh and it should use some garbage collector, but I think this
    > should be implemented in the end. I suppose I need to define data
    > structures in a clear way. I don't give a description of that machine lisp
    > abstraction, since all are similar. The fragment of the descripion is this :
    >
    >
    > (...)Program in Ansi C an interpreter of Lisp dialect described above. It
    > should contain efective implementation of the associate list, agregeting
    > atoms linked with values by the pseudofunction define and using some simple
    > garbage collector algorithm (the cell is alive, if it is possilble to reach
    > it starting from the atom belonging to the association list. The symbolic
    > data constructed during interpreter run should be put in array dyn_mem
    > define for example like this:
    >
    > ======================================================================
    >
    > #define MEMSIZE 1024
    > struct cell {
    > union data *left, *right;
    > };
    > union data {
    > int atom; /* when MSB == 1 */
    > struct cell *next; /* when MSB == 0 */
    > };
    > struct cell dyn_mem[MEMSIZE];
    >
    > ======================================================================
    >
    > Notice that this structure doesn't have MSB, to add in the orginal MacArthy
    > lisp it was the redundant part of data register ( 36 -th bit or something),
    > suppose this trick wouldn't go by on a 386 .....


    I don't understand what your C question is, if indeed you have one.

    The common method to implement a union which might hold two different
    types at different times, the type to be determined at run-time when
    it is accessed, is usually something like this:

    enum { is_ptr, is_atom } cell_type;

    union cell_data { int atom; struct cell *next; };

    struct cell { enum cell_type type; union cell_data data; };

    Then when accessing a cell, the code first reads the type member to
    determine which member of the data union is present.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://c-faq.com/
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Aug 24, 2007
    #2
    1. Advertising

  3. Jack Klein <> writes:
    [...]
    > enum { is_ptr, is_atom } cell_type;


    This declares a single object of an anonymous enum type. You want:

    enum cell_type { is_ptr, is_atom };

    > union cell_data { int atom; struct cell *next; };
    >
    > struct cell { enum cell_type type; union cell_data data; };

    [...]

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Aug 24, 2007
    #3
  4. Thomas

    Thomas Guest

    Uzytkownik "Jack Klein" <> napisal w wiadomosci
    news:...
    > On Fri, 24 Aug 2007 16:16:51 +0200, "Thomas" <> wrote in
    > comp.lang.c:
    >
    > > Hello,
    > >
    > >
    > > I am a CS student and I want to write simple lisp interpreter. The

    code
    > > should be entierly in C. I don't want to use any compiler generators

    like
    > > Bison or Yak, since wrinting this in raw C will give me more experience.

    I
    > > wrote a simple lexer ( changes leksems into the streams of tokens). The

    Lisp
    > > dialect I have to implement is not defined in any formal way, but I have

    a
    > > description of how it should behave (say its a >>writen halformal
    > > description which leads me to confusion <<). I ask for some tips,

    materials
    > > or guidence. Oh and it should use some garbage collector, but I think

    this
    > > should be implemented in the end. I suppose I need to define data
    > > structures in a clear way. I don't give a description of that machine

    lisp
    > > abstraction, since all are similar. The fragment of the descripion is

    this :
    > >
    > >
    > > (...)Program in Ansi C an interpreter of Lisp dialect described above.

    It
    > > should contain efective implementation of the associate list, agregeting
    > > atoms linked with values by the pseudofunction define and using some

    simple
    > > garbage collector algorithm (the cell is alive, if it is possilble to

    reach
    > > it starting from the atom belonging to the association list. The

    symbolic
    > > data constructed during interpreter run should be put in array dyn_mem
    > > define for example like this:
    > >
    > > ======================================================================
    > >
    > > #define MEMSIZE 1024
    > > struct cell {
    > > union data *left, *right;
    > > };
    > > union data {
    > > int atom; /* when MSB == 1 */
    > > struct cell *next; /* when MSB == 0 */
    > > };
    > > struct cell dyn_mem[MEMSIZE];
    > >
    > > ======================================================================
    > >
    > > Notice that this structure doesn't have MSB, to add in the orginal

    MacArthy
    > > lisp it was the redundant part of data register ( 36 -th bit or

    something),
    > > suppose this trick wouldn't go by on a 386 .....

    >
    > I don't understand what your C question is, if indeed you have one.
    >
    > The common method to implement a union which might hold two different
    > types at different times, the type to be determined at run-time when
    > it is accessed, is usually something like this:
    >
    > enum { is_ptr, is_atom } cell_type;
    >
    > union cell_data { int atom; struct cell *next; };
    >
    > struct cell { enum cell_type type; union cell_data data; };
    >
    > Then when accessing a cell, the code first reads the type member to
    > determine which member of the data union is present.
    >
    > --
    > Jack Klein
    > Home: http://JK-Technology.Com
    > FAQs for
    > comp.lang.c http://c-faq.com/
    > comp.lang.c++ http://www.parashift.com/c -faq-lite/
    > alt.comp.lang.learn.c-c++
    > http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html


    Ok, thanks that makes sense. Well, maybe my C question is not well defined,
    but I have not found any better places for this post.
     
    Thomas, Aug 25, 2007
    #4
  5. Thomas

    Jack Klein Guest

    On Fri, 24 Aug 2007 12:06:37 -0700, Keith Thompson <>
    wrote in comp.lang.c:

    > Jack Klein <> writes:
    > [...]
    > > enum { is_ptr, is_atom } cell_type;

    >
    > This declares a single object of an anonymous enum type. You want:
    >
    > enum cell_type { is_ptr, is_atom };
    >
    > > union cell_data { int atom; struct cell *next; };
    > >
    > > struct cell { enum cell_type type; union cell_data data; };

    > [...]


    Yes of course, thanks.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://c-faq.com/
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Aug 25, 2007
    #5
    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. ekzept
    Replies:
    0
    Views:
    386
    ekzept
    Aug 10, 2007
  2. bolega

    C interpreter in Lisp/scheme/python

    bolega, Jun 14, 2010, in forum: C Programming
    Replies:
    26
    Views:
    2,362
    francogrex
    Jul 24, 2010
  3. bolega
    Replies:
    30
    Views:
    880
    francogrex
    Jul 24, 2010
  4. nanothermite911fbibustards
    Replies:
    0
    Views:
    388
    nanothermite911fbibustards
    Jun 16, 2010
  5. nanothermite911fbibustards
    Replies:
    0
    Views:
    329
    nanothermite911fbibustards
    Jun 16, 2010
Loading...

Share This Page