Alfrothul: So, String.get.
Anton: Yes, String.get?
Alfrothul: Given a string and an index, it yields a character at that index in the string.
Vigful (helpfully): Starting at 0. The index, I mean. Look:
# String.get "0123" 0;;
- : char = '0'
# String.get "0123" 1;;
- : char = '1'
# String.get "0123" 2;;
- : char = '2'
# String.get "0123" 3;;
- : char = '3'
#
Alfrothul: Thanks, Pablito.
Anton: And your point was?
Alfrothul: Well, what happens if the index is too big?
Loki: Or the string is too short. It’s a matter of perspective.
Pablito: An error occurs, that’s what happens. Look:
# String.get "0123" 4;;
Exception: Invalid_argument "index out of bounds".
#
Anton: The index could be negative too. Then an error should occur too.
Pablito (diligently): Let me try:
# String.get "0123" -1;;
Characters 0-17:
String.get "0123" -1;;
^^^^^^^^^^^^^^^^^
Error: This expression has type int -> char
but an expression was expected of type int
#
Pablito: See? An error.
Anton: Wait a second. That’s a weird error.
Pablito (with dignity): Well, an error is an error.
Anton: But it’s not the same error. It’s an entirely different kind of error.
Alfrothul: Guys, guys—OCaml is reading the minus sign not to mean “minus 1”, but to mean subtraction as an infix operator.
Anton: And that explains the error message. Since String.get has type string -> int -> char, String.get "0123" has type int -> char.
Pablito: But there is no space between the minus sign and 1.
Alfrothul: There need be no space around infix operators. Look:
# (fun x -> x+1) 10;;
- : int = 11
#
Loki: Unless this infix operator is * and it is between parentheses, you mean.
Alfrothul: Yes, I mean. And talking about parentheses, all we need to do here is to wrap -1 between parentheses to disambiguate:
# String.get "0123" (-1);;
Exception: Invalid_argument "index out of bounds".
#
Dana: Or to prefix the minus sign with a tilde, to tell the parser that this sign is not an infix sign:
# String.get "0123" ~-1;;
Exception: Invalid_argument "index out of bounds".
#
Loki: Are you so sure about that, Dana? I mean look:
# (~-);;
- : int -> int = <fun>
#
Dana: Right. That’s Int.neg, the negation function – look at its type – and (-) is syntactic sugar for Int.sub – again, look at its type.
Anton: Can we get back on track? If the index is out of bounds, we get an error:
# String.get "0123" 4;;
Exception: Invalid_argument "index out of bounds".
# String.get "0123" (-1);;
Exception: Invalid_argument "index out of bounds".
#
Alfrothul: What about not getting an error?
Anton (O_o): Not getting an error.
Alfrothul: Yes. Instead, we could get a default character.
Anton (o_O): A default character.
Alfrothul: Yes. Given a string, an index, and a default character, the function could yield a character at that index in the string if the index is within bounds, or the default character if the index is out of bounds. See? No error.
Anton: I won’t get all epistemological on you about the nature of errors, but OK, why not.
Alfrothul: Let me see:
let test_string_get' candidate =
(candidate "012" 0 ' ' = '0') && (candidate "012" 1 ' ' = '1') && (candidate "012" 2 ' ' = '2')
&&
(candidate "012" 3 ' ' = ' ') && (candidate "012" (-1) ' ' = ' ');;
Anton: OK, the three first tests verify that when the index is within bounds, the result is the correct character, and the two last tests verify that when the index is out of bounds, the result is the default character.
Alfrothul: And now we can implement string_get':
let string_get' s i c =
if 0 <= i && i < String.length s
then String.get s i
else c;;
Anton: Right, that should do it:
# test_string_get' string_get';;
- : bool = true
#
Anton: Yes, it does do it.
Alfrothul: Right...
Dana: So String.get implements a partial function, and string_get' implements a total function.
Alfrothul: Yes, precisely.
Halcyon: And what about test coverage?
Anton: Test coverage.
Halcyon: Well, as per the title of this chapter. We are supposed to talk about test coverage, are we not?
Dana: Breaking the fourth wall, are we?
Halcyon (virtuously): I read the lecture notes beforehand.
Dana: So what happens now?
Halcyon: You tell me.
Alfrothul (emerging from his thoughts): Tell you what.
Halcyon: Thank you.
Alfrothul: Test coverage is about the boolean expressions in the program that is being unit-tested.
Halcyon: Yes.
Alfrothul: Here, the expressions are 0 <= i and i < String.length s.
Pablito: And 0 <= i && i < String.length s.
Alfrothul (conciliating): Yes, that one too.
Anton (jumping in): There are 5 tests. For the 4 first ones, 0 <= i evaluates to true, and for the 5th one, 0 <= i evaluates to false.
Alfrothul: And for the first 3 tests and the 5th test, i < String.length s evaluates to true, and for the 4th one, 0 <= i evaluates to false.
Anton: So for the first 3 ones, 0 <= i && i < String.length s evaluates to true and for the last 2 ones, 0 <= i && i < String.length s evaluates to false.
Pablito: OK, it looks like when the unit-test function is applied, all the tests in the function being tested evaluate to true and to false.
Anton: Right. And so all the consequents and all the alternatives in the function being tested are being evaluated in the course of the unit test.
Pablito: OK...
Alfrothul: That’s a small OK, Pablito.
Pablito: I am still a bit confused.
Dana: Let me guess. It’s the boolean conjunction, right?
Pablito (with a small voice): Kind of, yes?
Dana: Look—here is another implementation of string_get':
let string_get'' s i c =
if 0 <= i
then if i < String.length s
then String.get s i
else c
else c;;
Dana (continuing): And to be on the safe side:
# test_string_get' string_get'';;
- : bool = true
#
Dana (ending): Do you find this implementation clearer?
Pablito: Actually I do—there is only one boolean expression in each test.
Dana: Yup. If the outer test fails, then the result is the default character, and if it succeeds...
Pablito: ...then if the inner test fails, then the result is the default character, and if it succeeds, then the index is within bounds.
Anton: Right, that’s clearer. In the 4 first tests of the unit-test function, the outer test succeeds, and in the 5th test of the unit-test function, the outer test fails.
Alfrothul: And if the outer test has succeeded, in the first 3 tests of the unit-test function, the inner test succeeds, and in the 4th test of the unit-test function, the inner test fails.
Pablito: Yes, clearer.
Halcyon (happily): And we do have test coverage.
Pablito: So the two implementations are equivalent?
Mimer: Actually yes they are, and we can prove this equivalence using algebraic reasoning, as in mathematics. Stay tuned.
Anton: You mean equivalence as in the 3 expressions if b then true else false, b = true, and b being equivalent?
Mimer: I do mean. This notion of equivalence is similar to the extensional equivalence of functions and of programs and is due to Jim Morris. Two expressions are observationally equivalent if evaluating one is undistinguishable from evaluating the other: either both of their evaluations do not terminate, or they yield the same error, or they yield the same result, and if any side effects occur in the course of their evaluation, these side effects are the same and they occur in the same order.
Loki: Side effects?
Mimer: For example, next week, we will see how to print values in passing, to trace a computation. Such a trace is a computational effect, a.k.a. a side effect: something that can be observed independently of the result of the evaluation. Two expressions that emit the same trace and yield the same result are observationally equivalent. Stay tuned.
Dana: Ah, then we can print something in the unit tests. That will be more useful than just returning false when they fail.
Mimer: Again, yes. Stay tuned.
Alfrothul: But still.
Anton: Still?
Alfrothul: If we look at the test a <= b && b < c, we can enumerate all the possibilities for it to succeed or to fail.
Anton: You mean to yield true or to yield false.
Alfrothul: Yes. For 3 integers n1, n2, and n3 such that n1 <= n2 < n3, the test should succeed.
Anton: Right. And for 3 integers n1, n2, and n3 such that n1 > n2 < n3 or such that n1 <= n2 >= n3, the test should fail.
Alfrothul: It should also fail if n1 > n2 > n3.
Anton: So, 4 possibilities.
Alfrothul: And we should enumerate these 4 possibilities in a unit test.
Loki: Well, here, a is 0, so maybe not so many.
Anton: Harrumph.
Getting back to the definition of string_get', enumerate all the possibilities for the test 0 <= i && i < String.length s to succeed or to fail, and implement a new unit-test function based on this enumeration. How does your unit-test function compare to test_string_get'?
Implement a unit-test function for boolean conjunction:
let test_conjunction candidate =
...
Verify that OCaml’s implementation passes your unit test. In other words, test_conjunction (fun b1 b2 -> b1 && b2) should evaluate to true.
Implement boolean conjunction using OCaml’s conditional expression:
let conjunction b1 b2 =
...if...
Your implementation should only use if to test b1 and b2, i.e., it should not use &&, ||, =, etc. (Possibly it could use not for brevity.)
Analyze the code coverage of your unit-test function (in a.) with respect to your implementation (in c.). Is your implementation exhaustively tested?
Is your implementation correct? Why?
Implement a unit-test function for boolean disjunction:
let test_disjunction candidate =
...
Verify that OCaml’s implementation passes your unit test. In other words, test_disjunction (fun b1 b2 -> b1 || b2) should evaluate to true.
Implement boolean disjunction using OCaml’s conditional expression:
let disjunction b1 b2 =
...if...
Your implementation should only use if to test b1 and b2, i.e., it should not use &&, ||, =, etc. (Possibly it could use not for brevity.)
Analyze the code coverage of your unit-test function (in a.) with respect to your implementation (in c.). Is your implementation exhaustively tested?
Is your implementation correct? Why?
Implement a unit-test function for the Sheffer stroke:
let test_nand candidate =
...
Verify that the quick and dirty implementation fun b1 b2 -> not (b1 && b2) passes your unit test. In other words, test_nand (fun b1 b2 -> not (b1 && b2)) should evaluate to true.
Implement the Sheffer stroke using OCaml’s if construct:
let nand b1 b2 =
...if...
Your implementation should not use &&, ||, =, <>, etc., i.e., it should just use if to test b1 and b2. (Possibly it could use not for brevity.)
Analyze the code coverage of your unit-test function (in a.) with respect to your implementation (in c.). Is your implementation exhaustively tested?
Is your implementation correct? Why?
Implement a unit-test function for Peirce’s arrow:
let test_nor candidate =
...
Verify that the quick and dirty implementation fun b1 b2 -> not (b1 || b2) passes your unit test. In other words, test_nor (fun b1 b2 -> not (b1 || b2)) should evaluate to true.
Implement Peirce’s arrow using OCaml’s if construct:
let nor b1 b2 =
...if...
Your implementation should not use &&, ||, =, <>, etc., i.e., it should just use if to test b1 and b2. (Possibly it could use not for brevity.)
Analyze the code coverage of your unit-test function (in a.) with respect to your implementation (in c.). Is your implementation exhaustively tested?
Is your implementation correct? Why?
Implement a unit-test function for exclusive disjunction:
let test_xor candidate =
...
Verify that the quick and dirty implementation fun b1 b2 -> b1 <> b2 passes your unit test. In other words, test_xor (fun b1 b2 -> b1 <> b2) should evaluate to true.
Implement xor using OCaml’s if construct:
let xor b1 b2 =
...if...
Your implementation should not use <>, nor should it use =, &&, ||, etc., i.e., it should just use if to test b1 and b2. (Possibly it could use not for brevity.)
Analyze the code coverage of your unit-test function (in a.) with respect to your implementation (in c.). Is your implementation exhaustively tested?
Is your implementation correct? Why?
Replaced the occurrences of != with <> since we are considering structural equality [10 Mar 2023]
Created [10 Jan 2023]