Functions in Mondrian

In object-oriented languages, functions are members of classes, whereas functional languages normally follow the traditional module and function model. This difference has a fundamental effect on the styles of programming in the two paradigms .

For example, in a functional language, as in many non “object-oriented imperative languages, a sorting function typically takes a comparison function as an argument. In Haskell, the declaration of such a function might be

 Sort :: (Integer -> Integer -> Boolean) -> IntList           -> IntList 

In the object-oriented model, the replacement for a function value is usually an object with a well-known method. This approach is refined in some languages by specifying an interface, rather than a class, type for the comparison argument. In this style, the sorting example in C# becomes

 interface CompareOperation  {  Boolean Compare(Integer a, Integer b); } static IntList Sort(CompareOperation op, IntList l); 

The need to create special classes, or implement interfaces, to produce function "values" obfuscates the code. As for parametric types, function values are key to the expressive power of functional languages, and such obfuscation is not acceptable. Mondrian, therefore, requires an approach that supports function values clearly, while also supporting easy interworking with other CLR-hosted languages.

Monomorphic Functions

As suggested by the sorting example given earlier, a function in a functional language could be compiled into an class with a well-known method. A function "value" would then become an object reference that can be treated like any other reference type. This includes passing functions as arguments, returning them as function results, and storing them in data structures.

From the functional language perspective, the programmer sees the usual functional model and the expressive power of the languages is not obscured. Other CLR-hosted language programmers see a CLR object with a standard method name . For example, the Mondrian function

 length :: IntList -> Integer 

could be compiled to

 class length  { Integer Eval(IntList l) { ... }    ... } 

This approach presents an appropriate model to CLR-hosted language programmers if the Mondrian function being called is indeed a function value returned by some computation. For example, in C#:

 length lenFun;  int len; IntList aList; lenFun = <some object>.<some method>(...); len = lenFun.Eval(aList); 

However, for statically defined Mondrian functions, the code wouldn't be as clear:

 int len;  IntList aList; len = (new length()).Eval(aList); 

For this reason, our approach in Mondrian is to provide two well-known methods ; an instance method for use when calling a dynamic function value, and a class method for use when calling a statically defined function: ^[2]

^[2] Some readers might be concerned over the efficiency of this technique. The static method does not simply encapsulate an object creation and instance method application. A Mondrian function is a method-only class and, as such, has no state. This means that only one instance is ever required; the Mondrian compiler takes advantage of this fact and allocates a single (hidden) instance. The Apply method simply calls the Eval method on this compiler-allocated instance.

 class length  {  Integer Eval(IntList l) { ... }    static Integer Apply(IntList l) { ... }    ... } 

NOTE

The CLR directly supports viewing object/method pairs as function values with its delegates. It may be thought that for other CLR-hosted languages using delegates would provide them with a simpler model for accessing Mondrian functions. Unfortunately, however, delegates appear to be close to, but are not quite at, what is required to support the general function values required by functional languages, which include those described in the following sections. Therefore, we do not intend to exploit them in Mondrian at present.

Polymorphic Functions

Polymorphic functions are provided by using a combination of the strategies for parametric types and monomorphic functions detailed earlier. This means that static type information is lost, just as for parametric types, and therefore runtime checks may be needed. For example, the Mondrian function declared as

 length : forall a . List<a> -> Integer; 

is compiled to

 class length  {  Integer Eval(List l) { ... }    static Integer Apply(List l) { ... }    ... } 

NOTE

Runtime checks are not always required. The length of a list is independent of the type of items in the list, so in the example function the loss of static type information on the kind of the list does not result in any redundant runtime checks.

Partial Applications

Many functional languages allow a function to be partially applied (or curried ); that is, a function may be applied to fewer arguments than it requires, and the result of such an application is itself a function, which expects the remaining arguments. This is another feature that adds to the unique expressive power of functional languages and needs to be provided cleanly by Mondrian. Indeed, because a partially applied function is just a function value, functional programmers never need to know when applying a given function whether it is the result of an earlier partial application. The ideal for a CLR-hosted functional language design is to allow other CLR-hosted language programmers to use partially applied functions just like standard ones, so they too need not be concerned over the difference.

To explain how Mondrian achieves this goal, we need to delve a little deeper beyond the programmer's view and look at the implementation. A typical implementation of partial applications on a standard machine uses closures or thunks. A closure is simply a structure containing the values of the already-supplied arguments ("the environment") and a reference to the original function. When a closure is applied, the compiler emits code that merges the arguments from the call site with those from the environment, and then calls the functions.

An obvious parallel to a closure in an object-oriented environment is an object with instance variables to store the environment. The code usually emitted by the compiler to apply the closure can be placed into a method of this same object. The technique is easiest explained by an example. The Mondrian code fragment

 times : Float -> Float -> Float;  ... addTax = times 1.125; withTax = addTax 54; 

can be compiled into the following pseudocode:464 ^[3]

^[3] We have simply omitted some implementation "noise" to make the approach clear.

 class partialTimes  {  Float a1;    partialTimes(Float a1) { this.a1 = a1; }    Float Eval(Float a2) { return times.Eval(a1, a2); } } ... addTax = new partialTimes(1.125); withTax = addTax.Eval(54); 

This is the model we have adopted for Mondrian. The nonfunctional CLR-hosted language interface to a partial application, addTax in the preceding example, is identical to other function values produced by Mondrian code, so our goal is achieved.

The ability to create a partially applied method is not a standard object-oriented language feature. If an object-oriented programmer wishes to achieve the same effect, he or she must create a utility class, just like the partialTimes class produced automatically by the Mondrian compiler in the preceding example. Other CLR-hosted language programmers can utilize this technique to create partially applied Mondrian functions if they so choose. However, in typical use, we would expect only Mondrian code to actually produce partial applications.

Just-in-Time Evaluation

Just-in-time (JIT) evaluation, usually termed nonstrict evaluation by the functional language community, ^[4] involves delaying the evaluation of an expression until its value is actually required. JIT evaluation is another key attribute that contributes to the expressive power of functional languages, and as such it is supported by Mondrian.

^[4] The buzz-speak "just-in-time evaluation" is credited to Erik Meijer. We use it here as the term "JIT" is well understood in the object-oriented community whereas "nonstrict evaluation" is not.

For functional programmers, JIT evaluation is transparent, in the sense that they never need be concerned whether a given value is actually a "real" value or whether it is a "JIT expression" that will be automatically evaluated if the value is needed.

A trivial example (a more realistic one is included later in this appendix) to demonstrate the impact of JIT evaluation is the definition of a function to implement the same functionality as the following C# expression:

 ans = (x != 0) ? y/x : 0; 

This expression avoids a divide-by-zero exception if x has the value . However, if we define a C# method to replace the conditional expression,

 Integer fif(Boolean pred, Integer thenVal, Integer elseVal)  {  return pred ? thenVal : elseVal; } ans = fif(x != 0, y/x, 0); 

then a divide-by-zero exception is thrown if x has the value , as the division is always performed before the call to fif . However, if this same code is expressed in Mondrian,

 fif :: Boolean -> Integer -> Integer -> Integer;  fif = pred -> thenVal -> elseVal ->          if pred then thenVal else elseVal; ... ans = fif (x != 0) (y/x) 0 ... 

then no exception is thrown. Instead, the function argument (y/x) is evaluated just in time, which in this example is never if x has the value .

The Implementation of JIT Evaluation

If the following information appears confusing (JIT evaluation is easier to implement than to describe, and this appendix isn't really about implementation), just skip to the next section.

To understand how other CLR-hosted languages can handle JIT values produced by functional languages, such as Mondrian, we need to again peek below the normal programmer's view and look at the implementation. JIT evaluation is not new; indeed, it was provided by Algol 60 under the title call-by-name, and its implementation strategy has not changed: Use a closure. Recall that closures were used to represent partial applications earlier in this appendix. An expression can be viewed as a function whose arguments are the values of the variables in the expression. A JIT expression can then be viewed as a function call that hasn't been made yet or, alternatively, as a "partial" application where all the arguments have in fact been supplied, but the actual call has not been made. To obtain the value of a JIT expression, the "partial" application is evaluated.

Accessing JIT Values from Other CLR-Hosted Languages

The provision of JIT evaluation, as described above, raises an apparent problem for other CLR-hosted languages. What exactly is the value of a field of an object created by a functional language? Returning to our coordinate example,

 class Coord { Float x; Float y; } 

what is the value of x ? It could be a Float value, or it could be a reference to a JIT function object that will return a Float value when its Eval method is called. Accessing such a field is going to be rather involved and will require both testing and casts; the type of the field cannot even be Float .

Fortunately, good object-oriented programming style comes to the rescue. It is bad practice to allow direct access to instance variables of classes; rather, access methods should be used as mentioned in the section "Type Products." As access methods are written in Mondrian, the Mondrian compiler handles automatically any JIT values that are present. When a programmer using another CLR-hosted language calls a Mondrian access function, a real value will be returned. ^[5]

^[5] For functional programmers, the return value is technically a reference to a value in WHNF, which for primitive types is the same thing. For structured types (objects), further access functions will need to be called to access their fields, so JIT values will again be handled automatically.

However, should a programmer using another CLR-hosted language attempt to bypass the access methods and refer to the fields directly (which may be public so other Mondrian modules can access them), then the programmer may not get the expected result