search

rust-hosted-langs / book

Writing Interpreters in Rust: a Guide
https://rust-hosted-langs.github.io/book/
Creative Commons Attribution 4.0 International
479 stars 27 forks source link

Tagged Pointer: Nil == 0? #51

Closed andybest closed 2 years ago

andybest commented 2 years ago

First of all, great work on the book, I've been really enjoying reading through it!

I noticed that the implementation of TaggedPtr represents nil as a pointer with a tag of 0. I've also noticed that integers are represented with a tag of 0.

Would this not make a literal 0 be equal to nil, and mean that a zero integer would always be converted to a nil FatPtr (due to this code here )? Not sure if this is an intentional part of the design or not :)

pliniker commented 2 years ago

Well I've tried to mine my memory and notes for some clever reason I ordered the tags this way but I can't find anything 😄

Seems like a hole in the logic.

I'll fix this shortly, unless you are interested in submitting a PR?

andybest commented 2 years ago

I'm not sure what your preferred solution to this problem would be, but I've seen at least couple from things I've looked into:

  1. Statically allocate an arbitrary "nil" object (I've seen some Lisps that do this, and do pointer comparison with this object to determine if a value is "nil", or "the empty list")
  2. Use a tag value to represent a kind of "second order" tag. This way, you can have extra bits dedicated to another tag enum, and represent a whole bunch of things in the pointer, such as constants (like nil, true, false), and other types that would fit within a usize (like 8 and 16 bit integers). This has the obvious downside that you'd lose a tag that you could otherwise use for something else.
  3. Maybe use an object tag pointing to 0x0 (so it would be a constant pointer of 0x3)?

I'm sure that there are a multitude of other options

pliniker commented 2 years ago

The most obvious option to me is to reassign tags such that nil is a Symbol with a pointer value of 0x0. PR #52 should show what I mean.

I've considered option 1 to be a possible solution for keyword symbols in general. It would be a somewhat more involved solution, though there is already the SymbolMap which could be prepopulated with keyword symbols. I haven't thought this through all the way, yet.

andybest commented 2 years ago

Yup, looks like a good solution to me!