Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > simple lisp interpreter help needed

Reply
Thread Tools

simple lisp interpreter help needed

 
 
Thomas
Guest
Posts: n/a
 
      08-24-2007
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 .....


 
Reply With Quote
 
 
 
 
Jack Klein
Guest
Posts: n/a
 
      08-24-2007
On Fri, 24 Aug 2007 16:16:51 +0200, "Thomas" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      08-24-2007
Jack Klein <(E-Mail Removed)> 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.velocityreviews.com/forums/(E-Mail Removed) <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"
 
Reply With Quote
 
Thomas
Guest
Posts: n/a
 
      08-24-2007

Uzytkownik "Jack Klein" <(E-Mail Removed)> napisal w wiadomosci
news:(E-Mail Removed)...
> On Fri, 24 Aug 2007 16:16:51 +0200, "Thomas" <(E-Mail Removed)> 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.


 
Reply With Quote
 
Jack Klein
Guest
Posts: n/a
 
      08-25-2007
On Fri, 24 Aug 2007 12:06:37 -0700, Keith Thompson <(E-Mail Removed)>
wrote in comp.lang.c:

> Jack Klein <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C interpreter in Lisp/scheme/python bolega C Programming 26 07-24-2010 08:56 AM
C interpreter in Lisp/scheme/python bolega Python 30 07-24-2010 08:56 AM
Nice historical Musical - VERY RELAXING - about LISP history -fundamental ideas of LISP nanothermite911fbibustards C++ 0 06-16-2010 09:47 PM
Nice historical Musical - VERY RELAXING - about LISP history -fundamental ideas of LISP nanothermite911fbibustards Python 0 06-16-2010 09:47 PM
pat-match.lisp or extend-match.lisp in Python? ekzept Python 0 08-10-2007 06:08 PM



Advertisments