C# Help Home » Articles » C# Language » C#, F# and SMLNET

C#, F# and SMLNET

24. Mar, 2007 by admin 0 Comments

While we are waiting for new C# which willhave generics, anonymous functions and many other interestingimprovements, maybe we should check on F# and SMLNET, which alreadyhave most of those features, and see how we can perform interoperationbetween them and C#. We will also take a look at tail call instructionwhich is usually not generated by C# compiler.

Languages for scientists

Both mentioned languages belong to the groupof functional languages. That means that in such languages functionscan be passed as arguments to other functions and received as a result.On the other hand probably the most popular languages between today'sprogrammers – C#, VB.NET, C++ and Java belong to the group of so-calledimperative languages. F# is subset of OCaml and SMLNET is subset ofStandard ML. Both OCaml and SMLNET have roots in ML which was inventedby Robin Milner with the intention to be a vehicle for theoremproffers. Mathematical foundation of ML is lambda-calculus which Iwon't attend to in this article. As we know science is not dogmatic andin OCaml and Standard ML we will also find many features fromimperative programming languages. That is very obvious in the case ofOCaml where we have for loops and typical OO features. Anothercharacteristic of those two languages is that they come as interactivecompilers. The most popular implementations of Standard ML are StandardML 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 canbe downloaded from http://caml.inria.fr/. At their respective web siteswe will also find more information about the authors and history ofprojects. All three are free downloads and open source. I find OCamlespecially interesting because of object layer but I'm recommendingdownloading all of them. Unfortunately we won't find object layer inF#. Tutorials, examples, lecture scripts and free books are alsoavailable, so crank up your favorite search engine and get them. SMLimplementations are coming as command line compilers and you may findMLEdit (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 fromhttp://research.microsoft.com/projects/fsharp. That is a part of widerwork on generics for .NET which Don Syme performs for Microsoft. Wewill see that F# uses extended IL and some other stuff in its work. Wewon'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 workas interactive compiler so I recommend using real OCaml to get familiarwith language and F# for compilation and ultimately .NETinteroperation. Let's do some simple examples where we can see how F#functions work. Example which we are going to find about everywhere iscalculation of Fibonacci numbers. Here is naove implementation togetherwith 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 = <fun>
# fib_naive 15;;
- : int = 987
</fun>

There are few things which we should payattention to. Function name mustn't start with capital letter or wewill see error message: Unbound constructor Fib_naove. The second ishow we use parentheses when we are passing parameters to function.Parentheses have precedence over parameter list and parameter list overarithmetic operator. We will see that in the example of non trivialtail-recursion implementation. This is port from SML to OCaml of theexample 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 wewill set the required environment variable. AddD:\compiler_folder\fsharp\bin (or where is your F# directory) to PATHand from command line execute :

set FSHARPLIB=D:\compiler_folder\fsharp\lib
fcs -a -g fib.ml

The result of that action is a debug versionof library as we were asking with switches g and a. We will check usingILDASM what fib.dll holds. The interesting part is :

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 fromcommand line using csc /r:fib.dll test.cs. We can execute test.exe andsee the first fourteen Fibonacci numbers. F# supports generics andrelies on extended IL libraries. The simplest example of it would bereversing a pair of anything (or tuple, as that structure is called inML). Here is what that looks in OCaml IDE :

# let tryrev (a, b) = (b, a);;
val tryrev : 'a * 'b -> 'b * 'a = <fun>
# tryrev("abc", 1.25);;
- : float * string = (1.25, "abc")
</fun>

We will save function : let tryrev (a, b) =(b, a) as gentry.ml and compile. Again using ILDASM we will check whatis in assembly :

We again have static method, genericparameters are of object type and tuple is FS.pair from fslib.dll. Wecan 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 usefslib.dll and ilxlib.dll from bin directory of F# installation. So whenML features need to be exposed to .NET languages there is a way to doso.I hope that these two small examples will convince you to visit F# website and get your copy of it.

SMLNET

SMLNET is the result of work of the samedevelopment team which created mlj, Andrew Kennedy, Claudio Russo andNick Benton. Its home page is athttp://www.cl.cam.ac.uk/Research/TSG/SMLNET/ and there you can get yourcopy of it. Similarities with F# are many, but there is also a numberof small and big differences. From .NET point of view the biggestdifference is that SMLNET doesn't expose ML types to .NET languages andno additional libraries are required. SMLNET compiler emits IL code andcalls ILASM to compile it and cre
ate assembly. From ML point of view F#and SML are different dialects with a number of differences. Forexample 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 MoscowML. Number of examples which is included in distribution of SMLNET ismuch higher than number of examples in F# distribution. Because of itwe will skip tail calls and ordinary recursion and go straight tomutual recursion. Again I will base my example on ML for the WorkingProgrammer by Lawrence C. Paulson. The original example is included indistribution 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 thanfew significant digits we need to execute number of recursions whichsignificantly exceeds that what we hope to see in our bank account inour wildest dreams. If we don't want to see stack overflow then theintroduction of accumulator variable, which holds partial sum, and tailcalls is a necessity. We will save code as TailLeibniz.sml and createlibrary 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 furtherwe specify what we want from it. Now we can open emitted TailLeibniz.iland see what we got. Similarly to F# we will have our functions asstatic 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 toTailLeibniz.dll. We will execute test program and there won't be stackoverflow which means that everything was according to the plan. Again Ihope that this is sufficient to make you go and get your own SMLNET.Knowing more languages can help us become better programmers and alsowe 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 recursionwith 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 butin 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 ILDASMwe will see :

.method private hidebysig static float64
pos(float64 d,
float64 acc) cil managed
{
// Code size 30 (0×1e)
.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. Ifwe compare it with SMLNET created library we will see that it uses tailcall. 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 shouldbe discarded during the call which is specified as the followinginstruction. So we need to adjust pos and neg code a little bit to looklike 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 bestack overflow to worry about. So we won't get tail call from C# but ifwe do a bit of reverse engineering and customization we can easily haveit.

About

I'm writing code and articles for www.CodeNotes.com and preparing toshow up on International Web Services Conference & Exposition inToronto, Canada on October 14-16, 2003 (http://www.WowGao.com). If youwant to contact me my new e-mail is filip_bulovic@yahoo.com.