Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

.NET

Mondrian for .NET

Jason Smith, and

, February 01, 2002


Feb02: Mondrian for .NET

Nigel is a senior fellow and Jason a research assistant at the University of Canterbury, New Zealand. Erik is a program manager with Microsoft's Common Language Runtime team and adjunct professor of Computer Science at the Oregon Graduate Institute. Nigel and Erik can be contacted at [email protected] and [email protected], respectively.


Mondrian is a purely functional language specifically designed to leverage the possibilities of the .NET Framework. It brings powerful algorithm expression and scripting techniques to .NET programmers. For web programmers, Mondrian introduces multilanguage ASP.NET, where both C# and Mondrian code can be included on the same page. Mondrian runs under Visual Studio.NET and is freely available at http://www.mondrian-script.org/. (Versions work with .NET Beta 1, Beta 2, and RC1 as released at PDC 2001.)

Mondrian is designed to interwork with object-oriented languages; as such, it is a blend of the two paradigms. From its functional heritage (in particular, that of Haskell), it offers:

  • Higher order functions. Functions are first-class values and may be passed as function arguments and returned as results; new functions may be created dynamically.
  • Just-In-Time (JIT) evaluation. Work is not done until needed and is cached once it has been done the first time (usually termed "lazy" or "nonstrict" evaluation in the functional world).

  • Monadic I/O. Allows complex side-effecting computations to be constructed from simpler ones.

From the .NET Common Language Runtime (CLR) and C#, influenced by Massey Hope+C and Haskell, Mondrian offers:

  • Object-oriented friendly types. The ways of defining and using types are rather different in the functional and object-oriented paradigms. The Mondrian type system provides the flexibility of functional language type systems, while providing maximum compatibility with object-oriented languages. The syntax of type declarations leans toward the object-oriented style.

  • Multiple threads and thread synchronization primitives. Programs may consist of threads written in different languages.

  • Full support for exceptions, including cross-language throwing and catching.

The language syntax resembles a meld of C# and traditional functional languages to simplify use.

Mondrian code can call routines written in other .NET-hosted languages, and one of its design goals was to be useful as a scripting language. Mondrian also supports standalone programming and being called from other .NET-hosted languages. The latter lets you exploit the particular strengths of functional languages in projects primarily written in other languages.

Why Use Functional Languages?

Functional languages are so named because they are based entirely on functions, the term being used here in the mathematical sense. Functional languages contain no conventional assignment or flow-of-control statements; algorithms are expressed as mappings from input values to output values. This means that, in functional languages, you can concern yourself with the higher level details of what you want accomplished, and not with the lower level details of how it is accomplished. In turn, this reduces both development and maintenance costs.

Expressing an algorithm is often clearer and more concise than in traditional imperative languages. Furthermore JIT evaluation, where work is not done unless it is needed, opens up new ways of solving problems.

Composing Financial Contracts. Recent work in evaluating financial contracts has been reported by Simon Peyton Jones of Microsoft Research, Jean-Marc Ebar of LexiFi Technologies, and Julian Seward of the University of Glasgow, in the paper "Composing Contracts: An Adventure in Financial Engineering" (http://research.microsoft.com/Users/simonpj/Papers/contracts-icfp.htm).

Financial contracts can become quite complex, but are usually composed from a set of basic operations. Higher order programming, which allows larger functions to be composed from smaller ones, let Peyton Jones et al. flexibly construct more complex contracts from basic operations, paralleling the real-world process.

To evaluate a contract over a period of time, "value trees" are used, which represent a discrete approximation of the continuous process; for example, the interest-rate evolution. Computing a value tree can be intensive because its size is quadratic in the number of time steps it covers. Furthermore, complex contracts result in combining many value trees, so evaluating financial contracts is traditionally computationally intensive. However, Peyton Jones et al. significantly reduced the computation required by using a functional language. This occurs because only a path through the value tree is needed, and JIT evaluation performs just enough work to compute that path. In a traditional imperative or object-oriented language, the whole value tree is produced, doing much unneeded computation in the process.

Designing Chips. Traditional implementations of the Fast Fourier Transform (FFT) algorithm involve repeated iterations over arrays. In recent years, researchers have been working on new formulations of traditional algorithms. This work has produced purely functional implementations of a number of algorithms, including FFT. By "purely functional," we mean that the algorithm is defined as the composition of a number of functions. In a simple linear composition, data is fed into the first function: Its result becomes the input to the second function, and so on. Composition doesn't need to be linear — networks of functions can be created and the data flows around it. Function composition is a basic feature of functional programming languages and can be expressed clearly and concisely.

Digital circuits are made up of a number of functional units (gates and the like) connected by wires (connections on the chip). Functional composition is a direct model of this. This connection between functional programs and digital circuitry has caught the interest of fabricators, and functional languages are now being used to design and model real chips. (Work in this area, for example, is underway at Sweden's Chalmers University in association with various commercial companies, including Xilinx.)

Enter .NET. Real-world applications of functional programming range from programming telephone exchanges to graphical animation packages (for more information, see http://www.haskell.org/practice.html). However, it would be wrong to suggest that functional languages are the best tools for all programming tasks. Indeed, it would be wrong to claim that for any language or paradigm. As the history of PL/1 shows, no single programming language can be completely general purpose.

This is where .NET enters the picture. It lets you choose the most appropriate language for different parts of your applications. Mondrian for .NET lets you program your whole solution in a functional language if you wish. However, just as important, it lets you mix-and-match languages to exploit their particular powers and improve solutions whenever the use of the functional programming paradigm is most appropriate.

Algorithm Specification: Keep It Readable

To demonstrate the clarity of functional programming, we will compare QuickSort coded in C# and Mondrian.

The QuickSort algorithm can be described as follows (where "collection" means any collection type — list, array, and so on):

  1. If the collection has only one element, it is sorted.

  2. Select an element from the collection, call this the pivot. Any element will do; the first or last is often chosen.

  3. Partition the remaining elements in the collection into two. The first partition should contain all those elements less than the pivot, the second all those greater or equal to the pivot.

  4. Recursively perform the algorithm on the two partitions.

  5. Join the (now sorted) first partition, the pivot, and the second partition together to form the final sorted collection.

Listing One is the core of QuickSort written in C#. (A complete program demonstrating its use is available electronically; see "Resource Center," page 5.) This algorithm is not particularly complex, yet the correctness of it, in particular the partition function, is hard to determine. How much time has been lost over the years correcting invalid array index computations in algorithms such as this?

In contrast, Listing Two is the core of QuickSort written in Mondrian (again, a complete implementation is available electronically). This implementation is more concise and clearer than the C# version. Its correctness is simple to determine, no danger of catching "indexitis" here.

Our implementation uses Mondrian's standard filter function to split the data into the two partitions required by the algorithm. The filter function takes a predicate function and a list, and returns all items in the list for which the predicate is True (a complete definition for filter is available electronically). The code x -> compare x pivot denotes an inline anonymous function that uses the supplied comparison argument, compare, to define a predicate that selects all items less than the pivot value. The second application of filter selects all items greater than or equal to the pivot by negating (not) the result of the comparison function. The operator "++" is list concatenation.

In case you think we are cheating in this comparison by using the defined function filter, Listing Three is partition in Mondrian. The type Pair is standard in Mondrian and enables functions to easily return two values. Its definition is trivial and it is equivalent to a two-field structure in C#. (An implementation of QuickSort using partition is available electronically.)

JIT Evaluation: Don't Do Unnecessary Work!

JIT evaluation is a key concept in functional programming. JIT evaluation simply means that a computation is not actually performed until its result is needed; and once the computation has been performed, its value is cached. In particular, this means that unlike most programming languages, arguments to functions are not evaluated unless the function actually needs the value. JIT evaluation also allows the definition of potentially "infinite" data structures, but only the part traversed by the application is actually built in memory, and already traversed portions are garbage collected. For example, this Mondrian code defines the infinite list of all integers n (where "::" is Mondrian's list construction operator):

// from : Integer -> List<Integer>;

from = n -> n :: from(n + 1);

A call such as from 2 returns immediately, as the recursive call is not actually performed until the tail of the list is required. In contrast, if from would be defined in a strict language such as C#, then the call from(2) would either produce a stack overflow or, if you have a huge amount of memory, an overflow exception would result as C# tried to create a list of all integers 2.

The Sieve of Eratosthenes. Primes are useful in many algorithms; for example, in cryptography algorithms and random-number generators. The Sieve of Eratosthenes is a well-known and simple algorithm for generating primes:

  1. Initialize some collection (array, list, set, and the like) to contain integers starting from 2 and going up to some limit.

  2. Remove the least number from this collection; it is a prime.

  3. If another prime is required, then remove from the collection all multiples of the prime found in step 2.

  4. Go to step 2.

To code the Sieve in a procedural language, an array of some fixed size, n, is used, which is then sieved to produce all the primes n. Listing Four is a C# version of the Sieve, where ArrayList (from the .NET Framework) provides an extensible array. The algorithm cannot use an extensible array for the collection from which primes are generated; this must be a fixed-sized array, or the sieve would not work.

The Sieve algorithm in Mondrian (Listing Five) uses the built-in from function to generate a list of all the natural numbers, then sieves this list to calculate a list of all the primes on demand. In contrast to the procedural version, this implementation can determine the first n primes for all n.

As with QuickSort, we use the standard filter function. In this case, the predicate is the inline function x -> x % y != 0 that returns True if x is not a multiple of y.

The Best of Both Worlds. The Mondrian realization of the Sieve of Eratosthenes is both simpler and more flexible than the C# version being able to provide all the primes n or the first n primes. However, calculating primes is probably only a small part of a particular solution and other parts of that solution might be better written, for various reasons, in another language such as C#. Can you combine the benefits of using Mondrian for algorithms such as these with the benefits provided by other languages in other areas; for example, in producing GUIs? With .NET, the answer is "yes." One of .NET's strengths is its support for multilanguage programming. Whether you wish to use a whole library written in another language or just a single routine, .NET (through its CLR) provides a simple way to achieve this. Well, for some languages anyway.

Mondrian, with its JIT evaluation, is not compiled in quite the same way as typical object-oriented and procedural languages. This doesn't mean JIT evaluation cannot be compiled well onto .NET — it just means that calling a Mondrian function from, say, C# is a little different than calling, say, a Visual Basic function.

Listing Six is a C# class that provides an object-oriented iterator-style interface to the Mondrian prime generator in Listing Five. A Mondrian function, such as primes, is accessible from other .NET languages as a class with a method Apply. The Apply method handles the interface between Mondrian's JIT evaluation model and the strict model of .NET, similar to the way the standard class System.Delegate provides an invoke method. The functions/classes mondrian.prelude.hd and mondrian.prelude.tl are the standard Mondrian functions for returning the head and tail of a list, respectively.

The class PrimeIterator provides a more flexible prime generator than C# in Listing Four. This demonstrates some of the power of .NET — users of the PrimeIterator class never need to know what language it was written in, they never need to even have heard of JIT evaluation. All they see is a clever class, which they've no idea how to write themselves in C#, C++, or Visual Basic.

Scripting: Control Using Mondrian

Mondrian's function-plus-data model is rather different than .NET's object-plus-method model. This causes a slight impedance match when calling Mondrian from typical object-oriented languages. However, the object-plus-method model fits well into Mondrian's command expressions (known as "monads" by functional programmers). Command expressions enable Mondrian to be used very effectively to script code written in other .NET-hosted languages. As with functions, individual command expressions can be combined to produce more complex operations. Normal functions and JIT evaluation may also be exploited to produce scripts not easily written in other languages.

Listing Seven demonstrates the use of Mondrian to call and connect functions written in another CLR-hosted language. In this case, the functions are from the .NET Framework, whatever language(s) that is written in; as this is .NET, it does not matter. The classes HttpWebRequest and WebResponse are from the .NET Framework, the first three lines of the readLinesFromURL function open a URL and return a stream from which the contents of the item referred to by the URL may be read. The command function readLines, provided by Mondrian, takes a stream and returns a list of all the lines read from the URL. This function relies on JIT evaluation. The complete stream is not read in at one go — it could be gigabytes in length, so it is read in only as needed. JIT evaluation lets the URL stream be processed as though it was all in memory at once, avoiding the need to coordinate processing the current line, reading the next line, and so on.

The try/catch command construct mirrors that of .NET and languages such as C#. Mondrian can handle general exceptions (including those thrown by other .NET hosted languages it calls) and throw its own, which is unusual for a functional language.

ASP.NET: Multilanguage Web Scripting

Any language hosted on .NET can be used for coding ASP.NET pages if the language provider chooses to implement CodeDom support. The ease of supporting CodeDom ranges from trivial (for languages such as C# and Visual Basic) to very involved (for languages that are far removed from C# or Visual Basic). Mondrian falls into the latter category. However, by devising a new approach to CodeDom support, not only does Mondrian support ASP.NET, but in the true spirit of .NET, it also provides multilanguage ASP.NET pages. Currently, a mixture of Mondrian and C# is allowed; other languages may be added in the future.

Why would you want to use multiple languages on ASP.NET pages? To exploit the best tools for solving the problem. On the form in Figure 1, for instance, text can be typed into the left field, or one of the two Sample buttons used to enter sample text. Pressing the Sort button sorts the lines in the left field and places the result into the right field.

To produce this, you first need to define an ASP.NET form (see Listing Eight). In this form, every button has a handler method defined for the OnClick event. Defining the two initialization methods in C# is trivial, as in Listing Nine. The handler for the Sort button, however, is a little more involved. The contents of an asp:TextBox control is a single string. To sort the lines, this string must be broken up into the individual lines, these lines sorted, and then the reordered lines joined back together into a single string. Such data manipulation is one of Mondrian's strong points; Listing Ten is a function that does this.

Lists are the natural data type in Mondrian, so the input string is first converted to a list using stringToList, and the final result is converted to a string using listToString. The qsort function is defined in Listing Two, while lines and unlines are standard Mondrian functions. To attach SortLines to the ASP.NET button, another small C# routine is used, as in Listing Eleven. Finally, the code and HTML fragments need to be combined into a single ASP.NET page. To do this requires Mondrian's multilanguage support, the page outline is shown in Listing Twelve (the complete page is available electronically).

In a Mondrian ASP.NET page, the default language of a script is Mondrian. To include C# code, a language marker [C#] is added after the opening <script> tag. Mondrian and C# routines can call each other and both can access elements on the page.

Visual Studio Integration

Of course, your experience wouldn't be complete unless you could program in your favorite functional language (Mondrian, in this case) in your equally favorite RAD environment (say, Visual Studio .NET). To that end, we have integrated Mondrian into the Visual Studio .NET environment.

Acknowledgment

Mondrian started life at the Universiteit Utrecht in the Netherlands in a project led by Erik Meijer. Nigel Perry was a visiting researcher, from New Zealand, on the project and Arjan van IJzendoorn wrote much of the first system. The Mondrian project is now based in New Zealand. Questions regarding Mondrian can be directed to Nigel at [email protected].

DDJ

Listing One

delegate bool SortComp(Object lxpr, Object rxpr);
static void QSort(Object[] Data, SortComp Cmp)
{  QSortPart(Data, 0, Data.Length-1, Cmp);
}
static void QSortPart(Object[] Data, int Left, int Right, SortComp Cmp)
{  if(Right <= Left) return;
   int NewPivot = Partition(Data, Left, Right, Cmp);
   QSortPart(Data,       Left,   --NewPivot, Cmp);
   QSortPart(Data, ++NewPivot,        Right, Cmp);
}
static int Partition(Object[] Data, int Left, int Right, SortComp Cmp)
{  int iLeft  = Left - 1;
   int iRight = Right;
   int iPivot = Right; // Pick right element as the pivot
   Object PivotValue = Data[iPivot]; 
   while(true)
   {  while(Cmp(Data[++iLeft], PivotValue)); 
      while(Cmp(PivotValue, Data[--iRight]))
         if(iRight == iLeft) break;
      if(iLeft >= iRight) break;
      Swap(Data, iLeft, iRight);
   }
   Swap(Data, iLeft, iPivot);
   return iLeft;
}
static void Swap(Object[] Data, int i, int j) 
{  Object x = Data [i];
   Data[i] = Data[j];
   Data[j] = x;
}

Back to Article

Listing Two

// qsort : forall a. (a -> a -> Boolean) -> List<a> -> List<a>
qsort = compare -> l ->
   switch(l)
   {  case []: [];
      case (pivot::t):
         let
            before = filter (x -> compare x pivot)       t;
            after  = filter (x -> not (compare x pivot)) t;
         in
            (qsort compare before)
            ++ (pivot :: (qsort compare after));
   };

Back to Article

Listing Three

partition = pred -> data -> before -> after ->
   switch(data)
   {  case []:
         Pair{ a = before;
               b = after;
             };
      case (first::tail):
         if(pred first)
            partition pred tail (first::before) after
         else
            partition pred tail before (first::after);
   };

Back to Article

Listing Four

static ArrayList primes(int limit)
{  int [] sieve = new int[limit];
   ArrayList found = new ArrayList();

   // initialise array
   for (int i = 2; i < limit; i++) sieve[i] = i;
   // find primes
   for (int cursor = 2; cursor < limit; cursor++)
   {  if (sieve[cursor] != 0)
      {  // found a prime
         found.Add(cursor);
         // Sieve the array
         for (int j = cursor + 1; j < limit; j++)
            if (sieve[j]%cursor == 0)
               sieve[j] = 0;
      }
   }
   return found;
}

Back to Article

Listing Five

// sieve : List<Integer> -> List<Integer>;
sieve = xs -> 
   switch (xs)
   {  case (y::ys):
         // keep head, remove all multiples of head from tail,
         // then recursively sieve tail
         y :: sieve (filter (x -> x % y != 0) ys);
   };
primes = sieve (from 2);

Back to Article

Listing Six

class PrimeIterator
{  private Object list = primeGenerator.primes.Apply();
   public int Current()
   {  return (int)mondrian.prelude.hd.Apply(list);
   }
   public void Next()
   {  list = mondrian.prelude.tl.Apply(list);
   }
}

Back to Article

Listing Seven

// readLinesFromURL :: String -> IO<List<String>>;
readLinesFromURL = url ->
{  try
   {  req <- HttpWebRequest.Create(url);
      rsp <- req # HttpWebRequest.GetResponse();
      str <- rsp # WebResponse.GetResponseStream();
      readLines str;
   }
   catch (e : Exception)
   {   result Nil;
   };
};

Back to Article

Listing Eight

<form method="POST" action="SortMondrian.aspx" runat=server>
<table border=0 cellspace=4>
  <tr>
    <td valign=center>
      <asp:Button id="I1" text="Sample 1" OnClick="Init1"
       runat="server" />
      <br> <br>
      <asp:Button id="I2" text="Sample 2" OnClick="Init2"
       runat="server" /><br>
    </td>
    <td valign=center>
      <asp:TextBox id="T" rows="6" textmode="multiline" text=""
       runat="server" />
    </td>
    <td valign=center align=center>
      <asp:Button id="B" text="-> Sort ->" OnClick="DoSort"
       runat="server" />
    </td>
    <td valign=center>
      <asp:TextBox id="T2" rows="6" textmode="multiline" text=""
       runat="server" />
    </td>
  </tr>
</table>
</form>

Back to Article

Listing Nine

void Init1(object sender, EventArgs e)
{ T.Text = "turtle\nkakapo\naardwolf\neagle\ntuatara\nvole\nbadger";
}
void Init2(object sender, EventArgs e)
{ T.Text = "reversed\ninput\ndata";
}

Back to Article

Listing Ten

SortLines = cs ->
   let
      l = lines (stringToList cs);
      r = qsort stringLT l;
   in
      listToString (unlines r);

Back to Article

Listing Eleven

void Clicked(object sender, EventArgs e)
{  T2.Text = (string)SortLines.Apply(T.Text);
}

Back to Article

Listing Twelve

<%@ Page Language="Mondrian" %>
<script runat="server">
// qsort - Listing Two
// SortLines - Listing Ten
</script>
<script runat="server">[C#]
// C# handlers - Listings Nine and Eleven
</script>
<html>
<body>
// the form - Listing Eight
</body>
</html>






Back to Article


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.