Check my Program is Correct

JEREMY: In today’s video, we’re going to find out about a powerful, automated testing tool called QuickCheck. This allows us to run randomly generated tests on our code to ensure the code meets certain correctness properties that we specify. QuickCheck comes as part of the Haskell platform, so you should already have access to it on your own machine. It’s widely used in the software industry. For instance, many modern telecom software products are tested using QuickCheck. OK, suppose we want to implement a substitution cipher. Let’s do Caesar’s cipher, where we encode letters by shifting them a certain number of places along in the alphabet. In this example here, we shift letters one place.

So add– A-D-D in the plaintext– will become bee– B-E-E– in the ciphertext. We might ask what plaintext Z, the final letter of the alphabet, should be in code. The answer is a. The alphabet wraps round. Properly, this is a rotation rather than a shift.

First, we import the Data.Char module, which allows us to use utility functions for manipulating characters.

We select candidate characters to cipher or encode using the shouldcipher function here. Look at the type signature. It’s going to take a character, a single character, and return a Boolean that tells us whether or not this particular character is going to be enciphered. And we’re only going to want to cipher characters c that are letters and are ASCII character codes. Haskell actually uses the Unicode character set. So this means we’re only going to encipher letters, alphabetic letters, and not numbers or punctuation characters. To encipher letters, then come down to the next function here, cipherchar. We want to move letters along in places in the alphabet, where the number of places we move them is the first argument shift.

That’s an integer. And the second argument is the original character, the character in the plaintext. And we’re going to return the character that’s the ciphered version of our plaintext character. So let’s think about how we’re going to do this. What we really want to do is to add a certain number of character positions, the shift, to the original character. But c is a character, and shift is an integer. So actually, we have to use the ord function to turn the character into an integer code. And then add in the shift and then use the chr function to turn the resulting integer back into a character. Type safety is important here. We can’t add integers and characters directly.

Ord and chr might be familiar to Python programmers, for instance. Now we only want to do this in the situation where the character– that is, the input c– is going to be a character that’s a letter that we ought to cipher. So let’s say shouldcipher c means that we do this calculation. And otherwise, we’re going to say, just return the value c itself. It might be a punctuation character, or a space, or another non-letter character.

Great, now what we want to do is to– let’s get rid of this comment– map this cipherchar function over the whole of the string. And that’s what the next function does. Cipher, do you see here? It takes an integer shift amount, a character list, i.e. a string. That’s the plaintext. And returns another character list, which is the ciphertext. So here’s the definition here. We’re going to use the map function. And what we’re mapping is the cipherchar function for a certain shift amount mapped onto every character in the plaintext. Let’s try out this code. I’m going to save it.

So let’s try this inside GHCi. First, we’ll load cipher.hs. That’s in the code directory. And then we’re going to say cipher hello. That’s my string. And we want to move things along one space. Sorry, one space. There we are. And we get the enciphered message. And then we’ll do an original Caesar message. He’d normally move things three places long. Veni, vidi, vici. And we get back a rather unpronounceable string there, which is its encoding. Now for the decipher, we want to shift letters back in the opposite direction to the encipher. Look– so decipher is going to have the same type as decipher. It’s going to take an integer shift amount.

The second parameter is going to be the character amount shift. And then it’s going to return to the decoded, deciphered message.

So decipher shift ciphertext is going to be– well, it’s really just the ciphering function, but shifting in the opposite direction. But hopefully, this ought to give us the deciphered or decrypted message. So let’s say reload. And now we should be able to use the decipher function. If I say, decipher 3, and then I’m going to copy and paste this encoded string here. I should get back the original message. And I do. Now we want to check that our code works properly. Of course we know it shouldn’t because we haven’t done the wrapping around the alphabet for Z.

Rather than devise a number of test cases, we will use the QuickCheck tool to generate random input data and see whether a correctness property holds for our code. The property we want to check is, if we cipher a message and then decipher it, we should get back the original message. First, let’s import the QuickCheck module. Test.QuickCheck.

Make sure you get the capital letters right. Notice how the interactive prompt now has been modified to include Test.QuickCheck to show that it’s loaded into our environment. Now let’s ask QuickCheck to check our property. We need to encode the property in Haskell. So suppose we cipher a string by shifting it n places. The string is called s. And then we decipher this string using the same shift amount. Then the answer we ought to get back should be equal to the original string itself.

This is the property we want to check. We need to wrap this up as a lambda abstraction. So we’re going to take n, which is an integer, and then s, which is a string.

And given these two parameters, we can then check that when we decipher the enciphered message, we get back the original message. Let’s put some types here. So we take an int, n, the string, s. And we’re going to return a Boolean, which is the result of the equality check. OK.

And we’re going to provide this lambda abstraction as an argument to the QuickCheck function. And look, it runs, and then it says it failed. And it’s failed after six tests. And here’s where it’s failed. Look. The shift amount is one, and the string we’re trying to cipher is z. If we shift z along one place– well, let’s do that and see what happens. cipher 1 z. And then we end up with the next character in the character encoding, which is open curly brace. And now, if we try and decipher this– decipher 1 open curly brace, it doesn’t go back to z, because look– this is not a letter. And we’re only ciphering letters.

And the definition of decipher 1 curly brace is of course cipher minus 1 curly brace. And ciphering doesn’t work for non-letter characters. So this is the problem. Our code fails because it doesn’t wrap around the alphabet. Our cipherchar doesn’t do the adjustment for wrapping. So QuickCheck showed us that our program is wrong. Let’s go back and write a correct Caesar cipher code. And in fact, I should have one a little bit further down here. So we need to check to see whether our character, when it’s shifted, is going to wrap around the alphabet. So it’s a lower character. And it’s character code is greater than z when we’ve done the shift. Then yes, we need to wrap around.

If it’s an upper case character, and its character code, when we add the shift in, is greater than an upper case Z, Then yes, we need to wrap. Otherwise, we don’t. So that’s the wrap around. And then this other function here I’ve called bettercipherchar takes an integer shift amount, a character to encode, and then the encoded character. And this does some adjustments to make sure that we wrap around the alphabet if we need to. You can download this code and check it for yourself later on. It’s linked at the bottom of this page in the course. But what I’m going to do is change the definition of cipher to use bettercipherchar, rather than the original cipherchar.

And now, hopefully when I go back to shell and say reload, and then try and test my property again with this bettercipherchar, it ought to work now. So I want to QuickCheck this expression. Lambda n, that’s my shift amount. Lambda s, that’s my string. And I want to check that when I decipher the ciphered message, then the thing I get back is the original message.

I’m going to put in the types again. The types are helpful for QuickCheck to generate the right kind of random input data. Let’s run this now, and hopefully, it ought to pass. Look, it says it passed 100 tests, which gives us some confidence that it might be correct. We can actually trace the QuickCheck tests to see what the randomly generated input data looks like. Instead of using the QuickCheck function– I’m just going to borrow that code there. Instead, we use the verboseCheck function instead. VerboseCheck. Let’s run that, and we’ll see it generates the input data. There it is scrolling up there. It says for each test whether it passes.

So in this last example here, the shift amount is minus 42. And here’s the string, very random string here that was generated. Some of the characters aren’t even printable. But it passes all the tests. Great, we’ve passed the tests. A word of warning– even though the property is correct for all tests, this doesn’t guarantee our code is correct. Edsger Dijkstra, a famous computer scientist once said, testing can only show the presence of bugs, not their absence. However, QuickCheck provides a nice way to generate automated random tests to help us have more confidence that our code is doing what we want it to do.