Thursday Quote: Yaron Minksy
“A complete commitment to immutability is a commitment to never building anything real.”
– Yaron Minksy
OCaml for the Masses
Thursday Quote: Dwight D. Eisenhower
“Every gun that is made, sale every warship launched, online every rocket fired signifies, discount in the final sense, a theft from those who hunger and are not fed, those who are cold and are not clothed.”
– Dwight D. Eisenhower
The Chance for Peace
Thinking Functionally In PHP
I’ve noticed a trend in PHP code to shy away from function application and closures. I understand to some extent. Useful, inline anonymous functions were not available until 5.3.0, which is relatively new. And create_function is an abomination.
Still, I think that PHP programmers just don’t think in this mindset, but it can be very useful.
Here is a rather contrived example, but one I’ve honestly seen an analogue of before.
|
1 2 3 4 5 |
$accumulator = array(); foreach( $this->tags->all() as $tags ) { $accumulator[] = htmlspecialchars( $tag->name ); } return implode( ', ', $accumulator ); |
Easy to understand, simple, does the job, but it is far more verbose than it needs to be.
Here is a version using array_map.
|
1 2 |
$tags = array_map( 'htmlspecialchars', $this->tags->all() ); return implode( ', ', $tags ); |
The array_map function is doing all the work of the loop, but you don’t have to write it and you don’t have to manage the accumulator.
Doesn’t that feel better?
Next time you mangle an array, first think if array_map or it’s friends array_filter or array_reduce could do it better.
Fundamentals: Hashing
What the hash?
This post is about a fundamental programming concept, hashing.
“A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys.”
Hash function
Wikipedia – 2011/11/15
So, a hashing function can turn this:
Hello, my name is John Hobbs. I like hashes.
into this:
8ced81aa42cd91930024054f26ed92ea
Doesn’t seem super useful, does it? The content looses its semantic value. 8ced81aa42cd91930024054f26ed92ea is not the same as a personal introduction.
That’s okay though, we can find a use for a hash that won’t be seen by a human.
But first, let’s try our hand at writing a hash function.
Mapping to keys
So, the principal function of a hashing algorithm is to reduce a large block of data into a smaller block of data.
Let’s set up some arbitrary limits for developing our function.
For simplicity, let’s work at hashing values into a one byte integer, so eight bits.
Let’s also focus on only hashing ASCII strings, since ASCII characters are conveniently one byte long.
Now that that is established, let me propose a hashing function in pseudo-code:
|
1 2 3 |
let hash = 0 for each character in string: let hash = hash XOR character |
For those of you not familiar with XOR, I mean exclusive or. This means comparing the bytes bit by bit. If the bits are the same, the result is zero. If they are different, the result is one. The common notation for XOR is ^. Here’s an example of 5 ^ 117:
|
1 2 3 4 |
00000101 = 5 ^ 01110101 = 117 ---------------- 01110000 = 112 |
Working at a byte by byte level like this ensures that our hash will not exceed 8 bits in length, or an integer value of 128.
Buckets
With our shiny little hash function in mind, let’s use find a use.
One great use is lookup tables. These are sometimes called dictionaries, associated arrays, hash tables, etc.
Basically, they map a key to a value. So you tell a table that “my name” is “john”, and then later, if you ask it for “my name” is tells you “john”. Great tool for amnesiacs.
Hashing is perfect here for faster lookups, and for giving bound memory performance.
Think of it as a finite line of buckets. When you want to store something you hand it to the walrus, and say “Please keep this fish in a bucket called ‘Salmon’.”
Now, the walrus only has so many buckets, and none of them are labeled “Salmon”.
So, he uses a special walrus method (a hashing function) that deterministically says “Salmon == 5”, and puts the fish in the fifth bucket.
Later, when you come back and ask for the fish from the “Salmon” bucket, he knows to get the fish out of the fifth bucket because he can derive that “Salmon == 5” using the same method as before.
Unfortunately, he ate the fish already, so there is nothing to give you
Walrus are selfish that way.
Implementation
Now that we have a use case, let’s implement our hashing function.
I chose JavaScript here.
|
1 2 3 4 5 6 7 |
function hash ( string ) { var c = 0; for( var i = 0; i < string.length; i++ ) { c = c ^ string[i].charCodeAt(); } return c; }; |
Let’s give it a try:
|
1 2 3 4 |
console.log( hash( "hello" ) ); // prints "98" console.log( hash( "goodbye" ) ); // prints "125" |
Cool! Now there is just a little more glue to make this complete. We have to have a get and a set for values, and an array to store them in.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
var SimpleHashTable = function () { // these are the buckets this.table = new Array(128); // hand it to the walrus this.set = function ( key, value ) { this.table[this.hash( key )] = value; }; // get it from the walrus this.get = function ( key ) { return this.table[this.hash( key )]; }; // walrus math this.hash = function ( string ) { var c = 0; for( var i = 0; i < string.length; i++ ) { c = c ^ string[i].charCodeAt(); } return c; }; }; |
The get and set functions are pretty similar. You hash the key, and use that integer as the index to either set, or retrieve a value in the table array.
Let’s give it a try!
|
1 2 3 4 |
var ht = new SimpleHashTable(); ht.set( "salutations", "Hello, good sir." ); console.log( ht.get( "salutations" ) ); // prints "Hello, good sir." |
Perfect!
Collision course
Now let’s use our SimpleHashTable to store some stuff!
|
1 2 3 4 5 6 |
ht.set( "salutations", "Hello, good sir." ); console.log( ht.get( "salutations" ) ); // prints "Hello, good sir." ht.set( "q", "BARF!" ) console.log( ht.get( "salutations" ) ); // prints "BARF!" |
Wait, what the heck just happened?!
It shouldn’t have printed the value for q, we asked for salutations!
This is known as a collision, and it happens.
What happened is that the hash value we compute for q is the same value as the hash for salutations. It’s bound to happen, we only have 128 possible buckets and an infinite amount of possible keys.
So we have several ways to improve this situation.
One option is more buckets.
We can also improve the hashing function, but this only buys us fewer, more predictable collision rates.
Another common fix is a second level to each bucket keeping the exact key, value tuple, and doing a scan on collisions.
That would be like the walrus putting a sticky note that says “Salmon” on the fish before tossing it into the bucket. Then, when you ask for the “Salmon”, he rifles through the bucket, checking each fish until he finds one labeled “Salmon”.
I’ll leave these as an exercise for the reader, because it’s time we got moving on.
Real hashes
Okay, so now you have an example of a simple hash you could use for table lookups. That’s cool and everything, but in general we should leave details like that to the neckbeards. It’s good to know roughly how it works, but we don’t need to do it ourselves.
What else are hashes good for? Well, there is a specie of hash called a cryptographic hash. These hashes are cryptographic primitives, with strong promises of distribution and collision avoidance.
Examples you may have come across are MD5, or the SHA family of algorithms.
Implementation
These algorithms are considerably more complex than the hash function we created earlier, so I would urge you not to write your own except as an exercise.
Implementations are available in a variety of languages, so Google wisely.
Uses
This class of hash has several every day uses that apply to developer-types.
Data Integrity
Since hashes are deterministic functions, the output can be used as a fingerprint for the input. Passing data and the hash of that data allows for others to quickly check and make sure that the data has not become corrupted or tampered with in transit.
This assumes a secure channel for the hash, so use it wisely.
If you are on a Linux machine, you can quickly get the fingerprint for a file. In this example I’ll use the sha1 algorithm to verify the Redis 2.4.2 source code.
|
1 2 3 |
jmhobbs@Cordelia:~/Downloads$ sha1sum redis-2.4.2.tar.gz d2c9288dcfe16b4718e39a0f8ad7b21f4ffc6de0 redis-2.4.2.tar.gz jmhobbs@Cordelia:~/Downloads$ |
Comparing that hash to the Redis website, it looks like my download completed without errors. Huzzah!
Secret Verification
Another common use of hashing is to verify secrets, without storing the secret in the clear.
Say I was writing a system login, and I needed to use usernames and passwords.
I know it’s bad to store passwords in plaintext on my server. What if my server gets hacked and the user table is stolen?
I can’t store my passwords in the clear, but I need to reliably verify them.
Hashes make for a great solution to this problem.
You hash the password and store it in your database. Then, when a user wants to login, you hash the password they provide and compare it to the one in the database.
If they match, you log them in.
Doing this properly is a bit more complicated than that, so if you need to work with passwords like this, I recommend you read up.
Data Authenticity
We can also use hashes to confirm the authenticity of a message.
Say we both know a secret phrase, and no one else does.
If you want to send a message to me, and want it to be provably from you, you can send me the message along with a hash of the message concatenated to the secret.
Then, when I get the message, I also take the hash of the message plus the secret and compare it to your provided hash.
If they match, then I know it’s from you.
This is encapsulated in something called a Hashed Message Authentication Code, or HMAC.
File De-duplication
One final case that I regularly use is file de-duplication.
If you host uploads for a website, it’s a nice trick to store upload meta data (user, original name, upload time, etc.) separate from the file itself.
By de-coupling these you can hash files on upload, and if you already have a copy of that content, discard it and point the meta data at the existing file.
Here is an example in pseudo-code:
|
1 2 3 4 5 6 |
let hash = sha1_file( uploaded_file.tmp_path ) file = uploads.find_by_hash( hash ) if not file.loaded(): file.hash = hash file.save() return file.id |
Conclusion
Hashes are useful tools for programmers, so learn the concepts and the applications.
I hope you learned something from this post! How do you use hashes?
Skunk: A stinky PHP microframework
Six months ago I wrote a little PHP framework as an exercise. I’d been down this path before with the now abandoned Xoket – but this time I decided to go small, and throw away.
Hence Skunk was born.
Skunk is a single file, very lightweight API. Really, it’s just a borrowed router with some sugar wrapped around it.
I was after a Sinatra or Bottle feel, and I think I got something rather nice out of it.
Skunk uses anonymous functions extensively, so use PHP 5.3+ to save yourself the pain of create_function.
Example
Here is a super simple Skunk application:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Initialize $s = new Skunk(); // Add a route $s->get( '/hi(/<name>)', function ( &$s, $name = null ) { $s->body = 'Hello' . ( ( is_null( $name ) ) ? '' : " $name" ) . '!'; } ); // Run it! $s->run(); |
Let’s tear that apart.
|
1 |
$s = new Skunk(); |
Everything in Skunk revolves around the Skunk object, so we need to set one up.
While it is possible to have multiple Skunk objects, there really isn’t a good use case I can think of. But we won’t restrict your cleverness with a singleton.
|
1 |
$s->get( |
The two most important functions for Skunk are get and post.
These functions take a route and a function to apply when that route is matched, in a GET request and a POST request respectively.
|
1 |
'/hi(/<name>)', |
In this chunk we are setting up a GET request, with the route /hi(/<name>), so that will match /hi, /hi/John, etc.
Note the identifier <name> in the route. This named match will be captured and sent as an argument to the function.
|
1 2 3 4 |
function ( &$s, $name = null ) { $s->body = 'Hello' . ( ( is_null( $name ) ) ? '' : " $name" ) . '!'; } ); |
Skunk route functions always need to take a reference to the Skunk object as their first argument. Following that are any other arguments that might be pulled from the route itself.
In this case we are just setting the body of the Skunk response.
|
1 |
$s->run(); |
This kicks off the request process and also renders the response.
Other Tricks
Skunk has some other features too.
You can raise a variety of errors inside of a request:
|
1 2 3 4 5 6 |
$s->get( '/error/500', function ( &$s ) { return $s->HTTP_500(); } ); |
You can set headers:
|
1 2 3 4 5 6 7 |
$s->get( '/example.json', function ( &$s ) { $s->header( 'Content-Type', 'application/json' ); $s->body = json_encode( array( "Example" => TRUE ) ); } ); |
There is even a little hook system, so you can do middleware-ish stuff:
|
1 2 3 4 5 6 |
$s->hook( 'send_head', function ( &$s ) { $s->header( 'X-Stinky-By', 'Skunk' ); } ); |
Summary
So that is Skunk.
It could use some love, but it’s workable. We’ve run Number Laundry on it with no problems for four months with no problems yet.
For an example of Skunk in action, check out Number Laundry’s source at github.