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…
…so I built a hash table implementation that you can use in your own KAREL programs. The source is available here: https://github.com/onerobotics/hash.
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.
INCLUDING files
The KAREL translator allows you to include other files into your source code line-for-line with the %INCLUDE directive.
I’ve found that it’s useful to separate shared library constants, types, routines and vars into their own *.c.kl, *.t.kl and *.h.kl files respectively.
Configuration
I wanted to allow other users the flexibility to customize the memory footprint of their hash tables while still simplying including hash.t.kl.
The hashNode struct defined in hash.t.kl uses the constants HASH_KEYSIZE and 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.
Obscure built-in
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 hashPut, hashGet and hashDel routines could be modified to dispatch to alternative routines based on the provided variable’s type.
Testing
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 command: 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!