I was working on a KAREL project the other day where I really wanted to use an associative array to store some
key => value pairs. While a
STRUCT would be appropriate if my keys were known ahead of time, there’s no data type for mapping unknown keys to values…
Usage is documented in the README, but I thought it might be interesting/useful to talk a bit about what’s going on behind the scenes.
The KAREL translator allows you to include other files into your source code line-for-line with the
I’ve found that it’s useful to separate shared library constants, types, routines and vars into their own
*.h.kl files respectively.
I wanted to allow other users the flexibility to customize the memory footprint of their hash tables while still simplying including
hashNode struct defined in hash.t.kl uses the constants
HASH_VALSIZE for the string-lengths of those fields. When translated, your KAREL program will use the current value of those constants, and the translator will throw an error if they are undefined.
The hash function makes use of the
ORD built-in which returns the ASCII code for a given character. I haven’t needed this one many times, but I do make use of its cousin
CHR from time to time.
Short-circuit RETURN statements
Hash tables work by computing an index for a given key with a hash function. Ideally the index would be unique for all keys, but given limited memory available, it is possible that keys will collide. It’s also possible that the table will fill up completely. (You can see these conditions tested in the KUnit test suite).
To prevent my index function from looping forever on a potentially full table, I used a
FOR loop that can only go around
ARRAY_LEN(tbl) times, incrementing the
index attempt on each go (this is called linear probing in hash-table speak). If the index was available in the table, I
RETURN the value immediately, stopping the
FOR loop before it finishes.
The BYNAME built-in
This is about the closest thing KAREL has a pointer. Essentially it allows you to pass any variable from any program to a routine without having to previously declare it.
Why did I use it here?
Well, the current implementation only supports mapping string keys to string values, but I might want to have a hash table that stored something else like numbers or positions someday.
If that were the case, the
hashDel routines could be modified to dispatch to alternative routines based on the provided variable’s type.
Well it wouldn’t be a post about KAREL unless I talked a little bit about testing. Though I haven’t used this library extensively, I am pretty confident that it works as intended because it’s unit test suite passes.
It’s strangely satisfying to think of edge-cases and devise tests for them.
Side-note: KUnit has been updated to provide plaintext responses by default, so I can run all the tests with a simple
curl -s http://localhost/karel/kunit?filenames=test_hash.
I hope you learned something new about KAREL by reading this post or reading through the library’s source code. Let me know if you make use of the hash table in a project!