#include <iostream>
using namespace std;
int main() {
int data[100] = {3, 5, 7, 12, 42, 19, 8, 73, 45, 73};
int size = 10;
int value;
cout << "value to search for? ";
cin >> value;
int index = 0;
while (index < size && data[index] != value) {
index++;
}
if (index == size) {
cout << "index = -1" << endl;
} else {
cout << "index = " << index << endl;
}
return 0;
}
It assigns 10 values in an array that has a capacity of 100 and then prompts
for a value to search for. It has the classic double test to see if we've
found a value and whether we've run out of values to examine. I asked whether
we could eliminate the loop test for size:
while (data[index] != value) {
index++;
}
This will still work properly when the value is found, but not when the value
is not in the list. We saw very odd behavior when we had it search for values
not in the list. But we can fix that by putting the value we are searching for
after the sequence of values we are examining:
data[size] = value;
while (data[index] != value) {
index++;
}
That way it is guaranteed to find the value. Of course, this requires having
an extra array element in which to store this value, but that generally is easy
to arrange. This loop does half the testing of the other loop. I showed a
section of Knuth's Art of Computer Programming Volume 3 (Sorting and
Searching) that describes this as "Algorithm Q" and Knuth indicates that it is
important to figure out ways to reduce tests in this way.I pointed this out more for historical reasons to indicate that we cared about small efficiency improvements. In modern programming, we're more concerned with security issues. The Biden White House issued a report discouraging the use of C and C++ because they are less secure than languages like Rust, Java, C#, and OCaml.
The issue here is involves the concept of type safety. The concept of type safety has generally replaced the older terminology about a language being strongly typed.
Type safety is a concept that is usually described in terms of its opposite. We talk about the concept of type errors and say that a language is type safe if it doesn't allow any type errors to occur. The poster child for type errors is C and its close relative C++, so it's easiest to beat up on C and C++ in talking about how not to achieve type safety.
One way to think of type safety is that any given sequence of bits stored on the computer should not be interpreted in two different ways. In C and C++, for example, you can use casting to make variables of one type refer to variables of another type. We first looked at this short program:
#include <iostream>
using namespace std;
int main() {
cout << "hello world" << endl;
char text[4];
text[0] = 'f';
text[1] = 'u';
text[2] = 'n';
text[3] = '\0';
int * p = (int *) &text;
cout << text << endl;
cout << *p << endl;
*p *= 2;
cout << text << endl;
cout << *p << endl;
return 0;
}
This program declares a variable that stores an array of four characters. Each
character takes up one byte of memory in the computer (8 bits). So the overall
array takes up 4 bytes in memory. That also happens to be the amount of space
that an int takes up and in most implementations of C and C++. In the program
above, I use casting to have an int pointer point to the same address as the
array. Then when I ask it to print the value of *p, it reinterprets those 4
bytes as an int rather than as an array of 4 characters.This code works in C++. It reports that *p is 7239014. What's happening underneath is that we store four characters as bits using their ASCII codes:
'f' has code 01100110
'u' has code 01110101
'n' has code 01101110
'\n' has code 00000000
When we reinterpret this as an int, we simply look at all 32 bits as:
00000000011011100111010101100110
When viewed this way, it looks like the int value 7239014. So even though we
used characters to construct these bits, we are now interpreting them in a
completely different way.Things got worse when we doubled the int value by adding this line of code:
*p *= 2;
When we did that, the string no longer contained printing characters.In a type-safe language like Java, casting is limited to casts that make sense. You can cast an int to a double or a double to an int, but in that case an actual conversion takes place (the bits in one form are converted to appropriate bits of the other form). You aren't allowed to cast a String to an int or to otherwise reinterpret bits without conversion.
Probably the more egregious error occurs in C and C++ when you access unitialized variables. For example, if you construct an array using C's malloc operator or using C++'s new operator, you are just assigned a chunk of memory. The memory isn't initialized in any way. But the memory you are allocated may have been used previously for some other data, so you have a set of "dirty" bits that are going to be potentially reinterpreted as being of another type. Java avoids this by initializing all arrays and objects when they are constructed and by insisting that local variables be intialized before they are used.
Another place that this comes up is with local variables. When you make two different method calls in a row:
f1();
f2();
The computer has to allocate the local variables for f1 while it executes and
then deallocate them when it's done and then do the same for f2. This is
generally done with a stack. You allocate space on the stack for f1's local
variables while it executes, then pop the stack. Then do the same for f2. But
that can have a curious side effect. If you fail to initialize your local
variables in f2, then they have whatever value is left over from f1. In
general, this will be a garbage value because the types won't match. In a
type-safe language like Java, it is illegal to examine the value of a local
variable without first initializing it.I showed the following program to demonstrate that we can get the same reinterpretation of bits through the use of local variables:
#include <iostream>
using namespace std;
void foo() {
char text[4];
text[0] = 'f';
text[1] = 'u';
text[2] = 'n';
text[3] = '\0';
cout << text << endl;
}
void bar() {
int n;
cout << n << endl;
}
int main() {
foo();
bar();
return 0;
}
The output was the same as in the previous program. The character array is a
local variable in f1 and when f2 is called, those same bits are reused as a
local variable of type int.Then I showed the following C++ program that manages to pass values from one function to another through the use of local variables:
#include <iostream>
using namespace std;
void f1() {
int x;
double y;
x = 15;
y = 38.9;
cout << x << endl;
cout << y << endl;
}
void f2() {
int a;
double b;
cout << a << endl;
cout << b << endl;
}
int main() {
f1();
f2();
return 0;
}
This program printed the values 15 and 38.9 twice even though they were
initialized in f1 but not in f2. If you switch the order of the
printing statements, then you get something very different, so clearly
this is dependent on the order in which local variables are accessed.We looked at one final example of a program that declares an array and allows the user to request the value at a particular index:
#include <iostream>
using namespace std;
int main() {
int data[100];
int n;
cout << "n? ";
cin >> n;
cout << data[n] << endl;
data[n] = 3;
cout << "have a nice day" << endl;
return 0;
}
When we ran this program, we were able to request values using all
sorts of illegal index values like -10 and 500. In some cases it
showed us a value and in others it caused a segmentation fault.
Because C++ is not doing any bounds checking, we are able to examine
values in random parts of memory that may or may not be int values.I concluded this discussion by asking people for a list of features that Java has to avoid these kind of type errors. We came up with this list:
The function filter is very helpful here. We just need a function to determine if a value is equal to 0. This is a good place to use an anonymous function:
fun x -> x = 0
We can use that to filter a list:
filter((fun x -> x = 0), lst)
We then return the length of this list as the answer:
let num_zeros(lst) = List.length(filter((fun x -> x = 0), lst))
Then we explored how to use currying to replace the anonymous function with an
equivalent expression. What is the underlying function that we're applying?
The operator equals. Rember that we can ask OCaml about operators by
putting them inside parentheses:
# (=);;
- : 'a -> 'a -> bool = <fun>
Now we need to partially instantiate the function. The problem is that our
test begins with x:
x = 0
But it doesn't have to begin with 0, because this is equivalent:
0 = x
This is now fairly easy to partially instantiate:
(=) 0
When we typed the expression above into the OCaml interpreter, it responded
with this:
- : int -> bool = <fun>
Just as we would hope, the expression evaluates to a function that takes an int
as an argument and that returns a boolean value (whether or not the int is
equal to 0). I mentioned that in writing OCaml code, it is useful to type
these little code snippets into the interpreter to check your solution. If you
rely on always typing in the full version of a function, you might have trouble
locating syntax errors or bugs. It's better to test it in pieces.Using this expression, we were able to define a new version of the function:
let num_zeros(lst) = List.length(filter((=) 0, lst))
Then I asked how we could use currying to eliminate the function definition and
replace it with a let binding. The problem is that we have two different
functions that we want to apply: List.length and filter. Whenever you have two or
more functions to apply, you know you're going to need the composition
operator. So the basic form of our answer is going to be:
let num_zeros = List.length % (call on filter)
In other words, at the highest level what we're doing is to compose a call on
List.length with a call on filter. But how do we rewrite the call on filter?
In the code above, we are using the noncurried version of filter. We can
instead use List.filter which is the built-in curried version of the function.
The general form of a call on List.filter would be:
List.filter (predicate function) (list)
In our case, we are trying to eliminate the list parameter so that we can write
this using a let binding rather than a standard function declaration. In
other words, we want a partially instantiated call on this function where we
supply the predicate but not the list. We have to use List.filter instead of
filter and we have to be careful to use parentheses to indicate the grouping of
the expression that returns our predicate function:
List.filter ((=) 0)
Without the parentheses, OCaml tries to think of this as:
(List.filter (=)) 0
And that generates an error because the equals operator is not a predicate.
Putting the List.filter expression into our original expression, we get our
third version of the function definition:
let num_zeros = List.length % (List.filter ((=) 0))
In this case we actually don't need parentheses around the call on List.filter,
but it's generally easier to include some extra parentheses than to have to
learn all of the subtleties of OCaml precedence rules.Then we revisted Pascal's triangle. Someone had suggested that there is a more efficient way to compute a given row. For example, to compute row 5:
1
* 5 / 1 -> 5
* 4 / 2 -> 10
* 3 / 3 -> 10
* 2 / 4 -> 5
* 1 / 5 -> 1
I said that we can think of this row as being computed using a value I referred
to as m that varies from 1 to 5. We start with 1. Then we multiply by 5 and
divide by 1. Then we multiply by 4 and divide by 2. We keep going while m is
less than or equal to n.
We needed a helper function to keep track of the result we are building up, the
previous value we computed, and m and we needed to provide initial values for
these three parameters:
let row(n) =
let rec helper(result, prev, m) =
if m > n then result
else let next = prev * (n + 1 - m) / m
in helper(next::result, next, m + 1)
in helper([1], 1, 1)
Given this function, we can easily redefine the triangle function using a call
on map:
let triangle(n) = map(row, 0--n)