The Power of .NET: A Multilanguage Example

We conclude this appendix by working through a complete, though small, example of how the .NET Framework enables different languages to be combined to solve a problem.

Many programming courses cover the generation of prime numbers using an algorithm known as "the Sieve of Eratosthenes." Primes are useful in many applications, including hashing algorithms and cryptography, so being able to generate them easily is useful on a practical level.

The Sieve of Eratosthenes in C#

The method in Listing G.3 ^[6] is an implementation of the Sieve of Eratosthenes in C#.

^[6] We use the common idiom of using division to check for multiples . A "true" sieve uses index incrementing and involves no division, but the method shown here is more widely known.

Listing G.3

 static void PrintPrimes(int limit) {  int[] sieve = new int[limit];    // initialize array    for(int i = 2; i < limit; i++) sieve[i] = i;    // find primes    for(int cursor = 2; cursor < limit; cursor++)    {  if(sieve[cursor] != 0)       {  System.Console.WriteLine(cursor);          // "sieve" the array          for(int j = cursor + 1; j < limit; j++)             if(sieve[j]%cursor == 0)                sieve[j] = 0;       }    } } 

This method will generate and display all the primes up to a certain value ”call it N . However, what if you need to generate N primes? To do so using the formulation in Listing G.3, you need to start with an array large enough to hold the N th prime, and to determine that size you need to know the N th prime, which you will not until the program has been run.

Constructing a C# program that can produce N primes, rather than all primes _N , is a lot more involved. It is possible, however, and concurrent programming and threads can help [14].

The Sieve: Combining Mondrian and C#

The problem with the formulation of Eratosthenes's algorithm in Listing G.3 is that an array is a fixed-size structure. What we really need is a dynamic structure that is as large as needed. Furthermore, we can't easily quantify how large in advance; this size is a dynamic function of the algorithm.

This is one of the many areas where just-in-time evaluation provides benefits. In Mondrian, we can define the list of all the integers _N as follows :

 from : Integer -> List<Integer>;  from = n -> n :: from (n + 1); 

A call such as " from 2 " returns all the integers _2 . That is a very long list (2,147,483,647 items, followed by an overflow exception!). Attempt to write from in C#, and you will probably run out of memory rather quickly, and certainly before the call ever returns. However, Mondrian uses just-in-time evaluation, so from returns rather quickly. No items in the list are actually generated until you need them; once you've used an item and moved on, the CLR's garbage collection can reclaim the storage and reuse it for subsequent items. In short, you have an (almost) infinite list in a finite amount of space. The from function is so useful it is provided as standard in Mondrian.

Another useful function is filter :

 filter :: forall a. (a -> Boolean) -> List<a> -> List<a>;  filter = pred -> elems ->             switch(elems)             {  case Nil:                   Nil;                case Cons{h = head; t = tail}:                   if (pred h)                   then h :: (filter pred t)                   else filter pred t             }; 

This function removes all elements from a list for which the function pred returns false . Again, due to just-in-time evaluation, this function does only as much work as is needed. The filter function is also provided as standard by Mondrian.

Using from and filter , we can implement the Sieve algorithm rather easily (see Listing G.4).

Listing G.4

 // remove all multiples from a list sieve : List -> List; sieve = xs ->    switch (xs)    {  case (y::ys):          y :: sieve (filter (notMultiple y) ys);    }; notMultiple : Integer -> Integer -> Boolean; notMultiple = x -> y -> not (y % x == 0); // the "infinite" list of primes primes : List Integer; primes = sieve (from 2); 

The code in Listing G.4 handles the generation of primes, but we also need to be able display them. C# is good for generating user interfaces, so we'll use it rather than Mondrian. The C# method in Listing G.5, PrintPrimes , calls the Mondrian function primes , defined in Listing G.4, and the standard Mondrian list accessor functions, hd and tl , to display count primes starting from the N th one.

Listing G.5

 void PrintPrimes(int N, int count) {  // list of all the primes...    Object longList = primes.Apply();   // skip to first desired prime   while(N > 0)    {  longList = tl.Apply(longList);    }    // display primes   while(count > 0)    {  System.Console.WriteLine(hd.Apply(longList));       longList = hd.Apply(longList);    } } 

A Glimpse into the Future: Improving the Interface

Although the preceding example is easy to follow, it lacks the "feel" with which object-oriented programmers are familiar. This stems from the mismatch between the object-oriented object/method view and the functional data/function model. An object-oriented prime generator would probably be written in "iterator" style ”that is, as a class with one method to obtain the current prime and another method to advance to the next prime. The iterator style can be provided by wrapping the accesses to Mondrian functions within another class (see Listing G.6). PrintPrimes could then be written as shown in Listing G.7.

Listing G.6

 class Primes {  Object longList;    public Primes()    {  longList = primes.Apply();    }    public Integer Current()    {  return (Integer)hd.Apply(longList);    }    public void Next()    {  longList = tl.Apply(longList);    } } 

Listing G.7

 void PrintPrimes(int N, int count) {  // allocate a prime generator    Primes primeGen = new Primes();   // skip to first desired prime   while(N > 0)    {  primeGen.Next();    }    // display primes   while(count > 0)    {  System.Console.WriteLine(primeGen.Current());       primeGen.Next();    } } 

Future work will examine the automatic generation of wrapper classes such as these from code written in Mondrian.