In his book 'Program Construction: Calculating Implementations from Specifications' published in 2003, Backhouse says
" to write a program that
would compare two strings for equality. One student's solution was to assign the
value true or false to a boolean equal as follows:
equal := (stringl.length = string2.length);
if equal
then for i := 1 to string1.length
do equal := (stringl.character[i] = string2.character[i])
The program is coded in Pascal. The characters of a string s are assumed to be stored in the
array s.character, indexed from 1 to s.length.
The problem with this code is that it returns the value true whenever the two
strings have equal length and their last characters are identical. For example, the
two strings 'cat' and 'mat' would be declared equal because they both have length
three and end in 't'. The student was quite taken aback when I demonstrated the error.
Indeed, upon further questioning, it emerged that the program had been tested quite systematically."
Obviously, the testing was not sufficient.
He adds "(Needless to say, I observed the error by reading the code, not by testing. The
student was blameless. The error was the responsibility of the student's teacher
for having failed to teach proper design principles and suggesting that testing
was adequate.)"
I wonder what sort of design principles are not taught and what sort of testing was taught to be adequate. Whenever assignment statement is used within a loop there is a possibility of getting the updating process wrong and logical reasoning from school math can help.
A typical declarative programmer would reason like this.
Two strings of length 1 are equal if they have the same character.
Two strings of length more than 1 are equal if they have the same first character and the rest of the strings are equal.
In Prolog,
eqs([X], [X]).//
eqs([F1| R1], [F2| R2]) :- eqs([F1],[F2]), eqs(R1, R2).
This is a very common idiom in declarative languages. With a little care, this can be translated into an imperative language like java that allows recursion.
public class StringEqualCheck {
public static void main(String[] args) {
System.out.println(check("aab","bba"));
System.out.println(check("abc","ddc"));
System.out.println(check("abc", "abc"));
}
public static boolean check(String s1, String s2) {
if (s1.length() == 1)
return (s1.charAt(0) == s2.charAt(0)) ? true:false;
return (s1.charAt(0) == s2.charAt(0))
&& check(s1.substring(1), s2.substring(1)) ;
}
}
It is possible to think iteratively as the student attempted to do.
What is the meaning of the boolean variable 'equal'?
It is the truth value of the comparison of the prefixes of the strings of length i - 1.
It is not the truth value of the comparison of characters at i. (the mistake made by the student).
Correct updating statement follows from this understanding. My second child, Saurya recognized this immediately. My translation into java.
public static boolean itercheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
if(!equal) return false;
equal = equal && (s1.charAt(i) == s2.charAt(i));
}
return equal;
}
Update on 2 May 2014.
From the above code the line
if(!equal) return false;
can be removed and it is still correct and may be more (less) efficient.
Another possibility pointed out by Sarada is to replace the conjunction by just comparison.
Instead of
equal = equal && (s1.charAt(i) == s2.charAt(i));
have
equal = (s1.charAt(i) == s2.charAt(i));
because the return statement above ensures that the boolean variable is always true just before the character comparison. We have two reasonable different programs.
Saurya's program:
public static boolean itercheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
equal = equal && (s1.charAt(i) == s2.charAt(i));
}
return equal;
}
Sarada's program:
public static boolean itercheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
if(!equal) return false;
equal = (s1.charAt(i) == s2.charAt(i));
}
return equal;
}
" to write a program that
would compare two strings for equality. One student's solution was to assign the
value true or false to a boolean equal as follows:
equal := (stringl.length = string2.length);
if equal
then for i := 1 to string1.length
do equal := (stringl.character[i] = string2.character[i])
The program is coded in Pascal. The characters of a string s are assumed to be stored in the
array s.character, indexed from 1 to s.length.
The problem with this code is that it returns the value true whenever the two
strings have equal length and their last characters are identical. For example, the
two strings 'cat' and 'mat' would be declared equal because they both have length
three and end in 't'. The student was quite taken aback when I demonstrated the error.
Indeed, upon further questioning, it emerged that the program had been tested quite systematically."
Obviously, the testing was not sufficient.
He adds "(Needless to say, I observed the error by reading the code, not by testing. The
student was blameless. The error was the responsibility of the student's teacher
for having failed to teach proper design principles and suggesting that testing
was adequate.)"
I wonder what sort of design principles are not taught and what sort of testing was taught to be adequate. Whenever assignment statement is used within a loop there is a possibility of getting the updating process wrong and logical reasoning from school math can help.
A typical declarative programmer would reason like this.
Two strings of length 1 are equal if they have the same character.
Two strings of length more than 1 are equal if they have the same first character and the rest of the strings are equal.
In Prolog,
eqs([X], [X]).//
eqs([F1| R1], [F2| R2]) :- eqs([F1],[F2]), eqs(R1, R2).
This is a very common idiom in declarative languages. With a little care, this can be translated into an imperative language like java that allows recursion.
public class StringEqualCheck {
public static void main(String[] args) {
System.out.println(check("aab","bba"));
System.out.println(check("abc","ddc"));
System.out.println(check("abc", "abc"));
}
public static boolean check(String s1, String s2) {
if (s1.length() == 1)
return (s1.charAt(0) == s2.charAt(0)) ? true:false;
return (s1.charAt(0) == s2.charAt(0))
&& check(s1.substring(1), s2.substring(1)) ;
}
}
It is possible to think iteratively as the student attempted to do.
What is the meaning of the boolean variable 'equal'?
It is the truth value of the comparison of the prefixes of the strings of length i - 1.
It is not the truth value of the comparison of characters at i. (the mistake made by the student).
Correct updating statement follows from this understanding. My second child, Saurya recognized this immediately. My translation into java.
public static boolean itercheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
if(!equal) return false;
equal = equal && (s1.charAt(i) == s2.charAt(i));
}
return equal;
}
Update on 2 May 2014.
From the above code the line
if(!equal) return false;
can be removed and it is still correct and may be more (less) efficient.
Another possibility pointed out by Sarada is to replace the conjunction by just comparison.
Instead of
equal = equal && (s1.charAt(i) == s2.charAt(i));
have
equal = (s1.charAt(i) == s2.charAt(i));
because the return statement above ensures that the boolean variable is always true just before the character comparison. We have two reasonable different programs.
Saurya's program:
public static boolean itercheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
equal = equal && (s1.charAt(i) == s2.charAt(i));
}
return equal;
}
Sarada's program:
public static boolean itercheck(String s1, String s2) {
boolean equal = true;
for (int i=0; i < s1.length(); i++){
if(!equal) return false;
equal = (s1.charAt(i) == s2.charAt(i));
}
return equal;
}
The student's program combines two reasonable ideas to produce a buggy program.
My guess is his thinking was close to Sarada's program and probably forgot to include the if statement but went ahead with testing and felt good about many tests passing and submitted the faulty code.
