By Filip Bulovic
While we are waiting for new C# which will have generics, anonymous functions and many other interesting improvements, maybe we should check on F# and SMLNET, which already have most of those features, and see how we can perform interoperation between them and C#. We will also take a look at tail call instruction which is usually not generated by C# compiler.
Languages for scientists
Both mentioned languages belong to the group of functional languages. That means that in such languages functions can be passed as arguments to other functions and received as a result. On the other hand probably the most popular languages between today's programmers - C#, VB.NET, C++ and Java belong to the group of so-called imperative languages. F# is subset of OCaml and SMLNET is subset of Standard ML. Both OCaml and SMLNET have roots in ML which was invented by Robin Milner with the intention to be a vehicle for theorem proffers. Mathematical foundation of ML is lambda-calculus which I won't attend to in this article. As we know science is not dogmatic and in OCaml and Standard ML we will also find many features from imperative programming languages. That is very obvious in the case of OCaml where we have for loops and typical OO features. Another characteristic of those two languages is that they come as interactive compilers. The most popular implementations of Standard ML are Standard ML of New-Jersey (http://cm.bell-labs.com/cm/cs/what/smlnj/index.html) and Moscow ML (http://www.dina.kvl.dk/~sestoft/mosml.html). OCaml can be downloaded from http://caml.inria.fr/. At their respective web sites we will also find more information about the authors and history of projects. All three are free downloads and open source. I find OCaml especially interesting because of object layer but I'm recommending downloading all of them. Unfortunately we won't find object layer in F#. Tutorials, examples, lecture scripts and free books are also available, so crank up your favorite search engine and get them. SML implementations are coming as command line compilers and you may find MLEdit (http://www5a.biglobe.ne.jp/~sasagawa/MLEdit/english/home.html) free tool written by Kenichi Sasagava very useful.
F# with a look at C# interop
We will start with F# which is port of OCaml. It was written by Don Syme and can be downloaded from http://research.microsoft.com/projects/fsharp. That is a part of wider work on generics for .NET which Don Syme performs for Microsoft. We will see that F# uses extended IL and some other stuff in its work. We won't find some very interesting features of OCaml, like object layer, in F# but there is enough to keep us busy for a while. F# doesn't work as interactive compiler so I recommend using real OCaml to get familiar with language and F# for compilation and ultimately .NET interoperation. Let's do some simple examples where we can see how F# functions work. Example which we are going to find about everywhere is calculation of Fibonacci numbers. Here is naove implementation together with test :
# let rec fib_naive n=if n>1 then fib_naive(n-1) + fib_naive(n-2) else 1;;
val fib_naive : int -> int =
# fib_naive 15;;
- : int = 987
There are few things which we should pay attention to. Function name mustn't start with capital letter or we will see error message: Unbound constructor Fib_naove. The second is how we use parentheses when we are passing parameters to function. Parentheses have precedence over parameter list and parameter list over arithmetic operator. We will see that in the example of non trivial tail-recursion implementation. This is port from SML to OCaml of the example from ML for the Working Programmer by Lawrence C. Paulson :
(*
let rec itfib n prev curr =
if n=1 then curr (*does not take n=0*)
else itfib (n-1) curr (prev+curr)
let fib n = itfib n 0 1
*)
let fib n =
let rec itfib n prev curr =
if n=1 then curr else itfib (n-1) curr (prev+curr)
in itfib n 0 1
Commented version is closer to the original. We will save it as fib.ml and compile it using F# compiler. First we will set the required environment variable. Add D:\compiler_folder\fsharp\bin (or where is your F# directory) to PATH and from command line execute :
set FSHARPLIB=D:\compiler_folder\fsharp\lib
fcs -a -g fib.ml
The result of that action is a debug version of library as we were asking with switches g and a. We will check using ILDASM what fib.dll holds. The interesting part is :
|___[CLS] Fib
| | .class public auto ansi beforefieldinit
| |___[STM] .cctor : void()
| |___[STM] fib : int32(int32)
We have static method to deal with. From C# we will use it as any other assembly :
class MLClient{
static void Main(){
for (int i = 1; i < 15; i++)
System.Console.WriteLine("Fibonacci({0}) = {1}", i, Fib.fib(i));
}
}
We will save it as test.cs and compile from command line using csc /r:fib.dll test.cs. We can execute test.exe and see the first fourteen Fibonacci numbers. F# supports generics and relies on extended IL libraries. The simplest example of it would be reversing a pair of anything (or tuple, as that structure is called in ML). Here is what that looks in OCaml IDE :
# let tryrev (a, b) = (b, a);;
val tryrev : 'a * 'b -> 'b * 'a =
# tryrev("abc", 1.25);;
- : float * string = (1.25, "abc")
We will save function : let tryrev (a, b) = (b, a) as gentry.ml and compile. Again using ILDASM we will check what is in assembly :
|___[CLS] Gentry
| | .class public auto ansi beforefieldinit
| |___[STM] .cctor : void()
| |___[STM] tryrev : class [fslib]FS/pair(object,object)
We again have static method, generic parameters are of object type and tuple is FS.pair from fslib.dll. We can use this method from C# like this :
class GenClient{
static void Main(){
FS.pair np = new FS.pair("letter", 3.14);
System.Console.WriteLine("First is {0} and second {1}.",np.f1, np.f2);
np = Gentry.tryrev(np.f1, np.f2);
System.Console.WriteLine("First is {0} and second {1}.",np.f1, np.f2);
}
}
To compile and execute it you will need to use fslib.dll and ilxlib.dll from bin directory of F# installation. So when ML features need to be exposed to .NET languages there is a way to do so.
I hope that these two small examples will convince you to visit F# web site and get your copy of it.
SMLNET
SMLNET is the result of work of the same development team which created mlj, Andrew Kennedy, Claudio Russo and Nick Benton. Its home page is at http://www.cl.cam.ac.uk/Research/TSG/SMLNET/ and there you can get your copy of it. Similarities with F# are many, but there is also a number of small and big differences. From .NET point of view the biggest difference is that SMLNET doesn't expose ML types to .NET languages and no additional libraries are required. SMLNET compiler emits IL code and calls ILASM to compile it and create assembly. From ML point of view F# and SML are different dialects with a number of differences. For example our fib_naove in SML looks like this :
- fun Fibonacci n = if n>1 then Fibonacci (n-1) + Fibonacci (n-2) else 1;
> val Fibonacci = fn : int -> int
- Fibonacci 14;
> val it = 610 : int
That is done using interactive compiler Moscow ML. Number of examples which is included in distribution of SMLNET is much higher than number of examples in F# distribution. Because of it we will skip tail calls and ordinary recursion and go straight to mutual recursion. Again I will base my example on ML for the Working Programmer by Lawrence C. Paulson. The original example is included in distribution of Moscow ML. It uses Leibniz's algorithm: PI/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11... to calculate approximately value of PI.
structure TailLeibniz =
struct
fun pos (d, acc) = neg(d - 2.0, acc + 1.0/d)
and neg (d, acc) = if d>0.0 then pos(d - 2.0, acc - 1.0/d) else acc;
fun piapprox n = 4.0 * pos (real (4*n+1), 0.0);
end
To get the value of PI correct on more than few significant digits we need to execute number of recursions which significantly exceeds that what we hope to see in our bank account in our wildest dreams. If we don't want to see stack overflow then the introduction of accumulator variable, which holds partial sum, and tail calls is a necessity. We will save code as TailLeibniz.sml and create library like this :
smlnet
SML.NET 1.1 build 521 of Friday, 06 June 2003
\ export TailLeibniz
\ target library
\ make
Analysing dependencies...done.
Compilation succeeded: output in TailLeibniz.dll
With smlnet we start the compiler and further we specify what we want from it. Now we can open emitted TailLeibniz.il and see what we got. Similarly to F# we will have our functions as static methods. This is a C# client :
using System;
class MainClass{
static void Main(){
Console.WriteLine("PI is approximately {0}",
TailLeibniz.piapprox(1024000));
}
}
To compile it we will add reference to TailLeibniz.dll. We will execute test program and there won't be stack overflow which means that everything was according to the plan. Again I hope that this is sufficient to make you go and get your own SMLNET. Knowing more languages can help us become better programmers and also we may use the ideas from other languages in C#.
Tail call in C#
Maybe we can try to do what ML programmers do in C#. Mutual recursion with tail calls looks as a good starting point.
using System;
class mutual_recursion{
static double pos(double d, double acc){
return neg(d-2,acc+1/d);
}
static double neg(double d, double acc){
if(d>0)
return pos(d-2,acc-1/d);
return acc;
}
public static double calcPI(int n){
return 4*pos(4*n+1, 0.0);
}
}
class driver{
static void Main(){
Console.WriteLine(mutual_recursion.calcPI(256000));
}
}
We wrote the same code as in last example but in C#. When we compile it and execute there would be stack overflow. Why, if we did everything the same way? If we open assembly with ILDASM we will see :
.method private hidebysig static float64
pos(float64 d,
float64 acc) cil managed
{
// Code size 30 (0x1e)
.maxstack 4
IL_0000: ldarg.0
IL_0001: ldc.r8 2.
IL_000a: sub
IL_000b: ldarg.1
IL_000c: ldc.r8 1.
IL_0015: ldarg.0
IL_0016: div
IL_0017: add
IL_0018: call float64 mutual_recursion::'neg'(float64,
float64)
IL_001d: ret
} // end of method mutual_recursion::pos
We got normal call with stack transition. If we compare it with SMLNET created library we will see that it uses tail call. Real implementation of pos is here :
.method static assembly float64 'b'(float64,float64) cil {
.maxstack 3
.zeroinit
.locals (float64)
ldc.r8 1.0
ldarg.0
div
stloc.0
ldarg.0
ldc.r8 2.0
sub
ldarg.1
ldloc.0
add
tail.
call float64 '$'.'Globals'::'c'(float64,float64)
ret
}
Instruction tail. means that the stack should be discarded during the call which is specified as the following instruction. So we need to adjust pos and neg code a little bit to look like this :
.method private hidebysig static float64
pos(float64 d,
float64 acc) cil managed
{
.maxstack 4
ldarg.0
ldc.r8 2.
sub
ldarg.1
ldc.r8 1.
ldarg.0
div
add
tail.
call float64 mutual_recursion::'neg'(float64,
float64)
ret
} // end of method mutual_recursion::pos
.method private hidebysig static float64
'neg'(float64 d,
float64 acc) cil managed
{
.maxstack 4
ldarg.0
ldc.r8 0.0
ble.un.s done
ldarg.0
ldc.r8 2.
sub
ldarg.1
ldc.r8 1.
ldarg.0
div
sub
tail.
call float64 mutual_recursion::pos(float64,
float64)
ret
done:
ldarg.1
ret
} // end of method mutual_recursion::'neg'
Compile it using ILASM and there won't be stack overflow to worry about. So we won't get tail call from C# but if we do a bit of reverse engineering and customization we can easily have it.
About
I'm writing code and articles for www.CodeNotes.com and preparing to show up on International Web Services Conference & Exposition in Toronto, Canada on October 14-16, 2003 (http://www.WowGao.com). If you want to contact me my new e-mail is filip_bulovic@yahoo.com.
