I’ve made some progress on Orbit – well, I’ve setup the project directory and
started playing around with tagged unions for the
VMValue type system. I’ve
also made the repository public, even though it’s still pretty rough.
I’m now getting to the point where I can write a simple interpreter loop, and start thinking about function dispatch. I really like full dynamic dispatch like Objective-C does – that is, message-based dispatch: each function call is done by name, followed by a dispatch table lookup before invocation.
So I’ve built a hash map. It’s a pretty simple implementation, without any support for deletion so far, and with linear probing. Strings in orbit are immutable, which means the hash is only computed once at creation - for function calls, that means when the constant pool is built, before the code starts running. So far, so good. Looking for an entry looks a bit like this:
The loop is required in case different hashes modulo-ed to the same index at
insertion. That part doesn’t worry me too much, at least right now. What worries
me is the potential for hash collisions: what happens if two strings, both used
as keys into the same table, have the same
hash member. I could compare both
strings, but that would destroy performance, and I can’t allow that.
In the end, I think I’m going to accept that hash collisions might happen very rarely, but that still feels unsatisfactory, and the failure mode will be bad: the wrong function will be invoked, followed most certainly by a crash or corruption since the arguments are unlikely to be the right ones. Not sure I’m okay with such a fundamental bit of the language not being certain.