Computing primes, in Python and C0

This page shows a simple program in Python is rewritten in C0. The original Python source, sieve2.py is due to David Kosbie.

We begin with the fourth function defined: what is a prime number?

def isPrime(n):
    if (n < 2): return False
    # deal with evens first (to cut time in half)
    if (n == 2): return True
    if (n % 2 == 0): return False
    # then only check odds up to the square root
    for factor in range(3, 1+int(round(n**0.5)), 2):
        if (n % factor == 0):
            return False
    return True

The first difference we have to account for is that functions are typed, which means we have to specify that isPrime takes an integer argument and returns a boolean (either true or false)

bool isPrime(int n)
{
  ...
}

Rather than relying on indendation, the body of the function is enclosed in curly braces {...}. You will see many of these when writing code in C0.

Prime numbers are integers greater or equal to 2, so just as in the Python code we first check whether it is a valid candidate and return false if it isn't. The constant false is all in lowercase, and this matters; False would be flagged as an undeclared identifier.

bool isPrime(int n)
{
  if (n < 2) return false;
  ...
}

In C0, there is no colon (:) after the condition, and the return statement is followed by semicolon (;). All simple statements in C0 are followed by semicolons, but not compound statements like conditionals. Therefore we know that the semicolon "belongs to" the return statement, rather than the condition.

The next two lines in the Python code are an optimization, which we can faithfully reproduce. The constant true is also in lowercase. The modulus and comparison operators are like in Python, except that C0 enforces that the two sides are expressions of the same type.

bool isPrime(int n)
{
  if (n < 2) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  ..
}

Let's look again at the remainder of the Python function.

  for factor in range(3, 1+int(round(n**0.5)), 2):
      if (n % factor == 0):
          return False
  return True

We translate the iteration using the for statement into a so-called for-loop. A for-loop is much more restrictive than Pythons iteration: we say how to initialize a variable, how to test whether to exit the loop, and how to step from one iteration to the next. This is written as for(init; test; step). In this program, init is int factor = 3, declaring the new integer variable factor and giving it the initial value of 3. The exit test avoid the square root (since C0 has neither a built-in square root nor floating point numbers of exponentiation) and we just check if the potential factor is greater or equal to the square root by squaring it and comparing it to n. Finally, the range expression indicates a step size of 2, which we model in C0 by incrementing the factor by 2 on each iteration.

  for (int factor = 3; factor * factor < n, factor += 2) {
    if (n % factor == 0)
      return false;
  }

Indentation here has no semantic meaning, but it is excellent practice for indentation to reflect the program structure, just as you would in Python. If this loop uncovers no true factor, we return true: the number is indeed prime.

bool isPrime(int n)
{
  if (n < 2) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  for (int factor = 3; factor * factor < n; factor += 2) {
    if (n % factor == 0)
      return false;
  }
  return true;
}

For reference, here is our initial Python program.

def isPrime(n):
    if (n < 2): return False
    # deal with evens first (to cut time in half)
    if (n == 2): return True
    if (n % 2 == 0): return False
    # then only check odds up to the square root
    for factor in range(3, 1+int(round(n**0.5)), 2):
        if (n % factor == 0):
            return False
    return True

## Types

The two functions, in C0 and Python, are quite similar. One difference is that in C0 we have specified that the argument to the function is supposed to be an integer, while there is no corresponding declaration in Python. Let's do some testing in Python.

% python -i sieve2.py
>>> isPrime(10)
False
>>> isPrime(17)
True
>>> 

This is as expected, fortunately. Now let's try some other numbers as arguments to the function.

>>> isPrime(1.5)
False
>>> isPrime(2.5)
True
>>> isPrime("abc")
isPrime("abc")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in isPrime
TypeError: not all arguments converted during string formatting

All of these are quite meaningless. 1.5 is rejected because it is less than 2, but 2.5 is accepted as a "prime number" because it passes all the tests. The string "abc" finally yields a type error because the modulus operation is not defined on strings. We have uncovered here a hidden assumption, namely that the argument to isPrime is an integer.

In C0, using the coin interpreter, the behavior is quite different.

% coin sieve2.c0
Coin 0.2.10 'Penny'(r76M, Sun May 27 17:34:40 EDT 2012)
Type `#help' for help or `#quit' to exit.
--> isPrime(10);
false (bool)
--> isPrime(17);
true (bool)
--> isPrime(2.5);
<stdio>:1.11-1.12:error:expected identifier, found '5'
--> isPrime("abc");
<stdio>:1.1-1.15:error:type mismatch
expected: int
   found: string
--> 

C0 has only integers, so 2.5 is rejects as illegal. It does have strings, but before ever running the function is realizes that we cannot pass a string to a function that requires an integer.

## Testing

We have seen above that we can test the code in coin in the same way as we can test it with a Python interpreter. We might put some testing code into a file, using Python's assert statement.

print "Testing isPrime for correctness...",
assert(isPrime(10) == False)
assert(isPrime(17) == True)
assert(isPrime(-1) == False)
print "Passed!"

But we cannot embed the testing commands directly into the file as we can in Python. A general convention is to create a second file sieve2-test.c0 which contains a function main of no arguments that runs some testing functions and returns an integer. In most testing functions we just return 0. The line #include <conio> (for console input/output) allows is to call a printing function.

/* file sieve2-test.c0 */
#use <conio>

int main () {
  print("Testing isPrime for correctness...\n");
  assert(isPrime(10) == false);
  assert(isPrime(17) == true);
  assert(isPrime(-1) == false);
  print("Passed!\n");

  return 0;
}

We can see that print is just a library function, and therefore takes its argument in parentheses. Also, we add a newline character \n to the end of each print statement. In C0, output is buffered which means that a line may not be actually printed on the console until an end-of-line character is encountered. So if we want to see that it has started testing, we need to add that character at the end of the string. Now we can test it.

% coin sieve2.c0 sieve2-test.c0
Coin 0.2.10 'Penny'(r76M, Sun May 27 17:34:40 EDT 2012)
Type `#help' for help or `#quit' to exit.
--> main();
Testing isPrime for correctness...
Passed!
--> 

If we encounter an error (here created intentionally), the assert statement in C0 will abort the program and issue an appropriate error message.

% coin sieve2.c0 sieve2-error.c0
Coin 0.2.10 'Penny'(r76M, Sun May 27 17:34:40 EDT 2012)
Type `#help' for help or `#quit' to exit.
--> main();
Testing isPrime for correctness...
sieve2-error.c0:8.3-8.31: assert failed
Last position: sieve2-error.c0:4.1-12.2
               main from <stdio>:1.1-1.7
--> 

The error message is given with a region, which is line.column-line.column, here from line 8, column 3 to line 8, column 31. We can now go to line 8 of the file sieve2-error.c0 and examine it

  assert(isPrime(-1) == true);

and we see the incorrect test.