Creating CONS cells in more primative languages.

[Pixel_Outlaw]

I've been toying with the idea of trying to make a mini lisp in C++.
We don't need another Lisp, I'm just trying to make something real time that can be parsed and fed back into C++ primitives at runtime.

What's in a CONS cell?
I mean we know there are two pointers, one to point to the next CONS or the value NULL.
Another to point to a value.

Are there implied parts of a CONS cell that are often abstracted away?
Should a CONS cell keep references to it's parents? (I suppose it could keep a count and every time a parent dies it could decrement the child's ref counter by 1 until it hits 0 and destroys the child CONS)

Perhaps the biggest problem is that CONS cells can keep any type of data inside.
One moment the cons can store an INT the next it's storing a string and the next, an entire list.

Should a CONS cell be immutable?
Should it be simply replaced when the value is changed?

It is one thing to just USE a Lisp varient.
It is quite another to implement one in languages that are not garbage collected and very type safe.

Any ideas here?
I'm sure at least one person has implemented a mini Lisp for amusement.
I know there are probably articles and code snippets all over but I'm curious to hear about people here.

[sylwester]

• I think it's cool. Everyone should implement LISP in LISP and a non LISP language.
  
• A cons cell is just a object with two pointers, car and cdr. Both car and cdr can be any data type, but if you chain cons cells and the last cdr is NIL we call it a proper list and display it differently.
  
• You usually need to store the type of the values in the cons cell somehow. Some implementations in the past has had references to it's parent, but I don't know how shared tail is handled nor why they did it. T is one of them. LISPs rely on garbage collection and some implementations are quite easy while the modern Lisps of today usually have incremental garbage collection that are very sophisticated. Don't know if they rely on link counting but it sounds difficult to maintain.
  
• That car/cdr can hold any object is not a problem. Car and cdr are just pointers (and perhaps native types embedded in the pointer itself. Think types that usually are eq)
  
• Werther or not cons cells are immutable for a program is up to you, but internally for your primitives and internals they are definitly mutable or else you could't make then to begni with.
  
• For mutable pairs (most LISPs have them) you allow the pointer to point to something else. The data in the other end is not mutated. Of course for the native types embedded in the pointer it's not actually a pointer so they are indeed "replaced", but for a cons pointing to another cons that is changed to a another value the other cons might be pointed to by a nother cons or a free variable from a binding.
  
• Since pointers are 32 bit and large data types are 32 bit align some LISPs store the type in the lower bits of teh pointer.. See picolisp documentation on how they do it ad perhaps this C implementation of a Scheme.

A slightly different challenge with LISP is of course the symbol table and how you handle bindings. Of course these are different dependent on if you are making an interpreter or a compiler (and what kind of compiler).

What to read first.. For a interpreter I recommend the wizard book and the SICP videos by the wizards themselves. If you are interested in compilation then you might be interested in the 90 minute talk about it with a working example of a small subset and Matt Mights page about something similar for his Compiler course .

Trying to solve your problems by yourself for a while before peeking too much at others implemementations. It might give you some ideas on how to do stuff differently. Zozotez Lisp doesn't store it's data type in the cons cell since I didn't know that was the way at the time and I'm planning a compiler that won't know what symbols are in it's runtime.

Good luck and be prepared to have lots of fun

[Pixel_Outlaw]

Thank you for the insight!