Sunday, April 06, 2014

Fun with destructuring pattern matching -- a well kept secret of F#

Despite having been using F# as my go-to language for any personal project for 5+ years now, there are still simple things about the language that -- not being pointed out in the texts -- had passed me by until now. Prompted by a number of questions on the MSDN F# forum about porting some category theory implementation in ML to F#, I tried the exercise myself over a few evenings.

To my surprise, almost everything just ported over with mechanical syntax changes -- with the notable exception that F# doesn't have an infix keyword to mark a function as behaving like an operator. This included repeated idioms involving pattern matching in function arguments

type Cat<'o,'m>  = Cat of ('m->'o)*('m->'o)*('o->'m)*('m*'m->'m)
  let source(Cat(s,_,_,_))   = s

even though you can't do multiple overloads of the same function name with different patterns, Erlang style (those would have to be different cases in a function expression); you can even have your destructuring and eat it too as in

let K (Cat(_,_,id',_) as A) (a) = ...

where you have names for a component of the first argument and the first argument as a whole brought into scope. This generalises to being able to provide names for components of a tuple argument

type Functor<'o,'m,'o1,'m1>  =   
       Ffunctor of Cat<'o, 'm> *('o->'o1)*('m->'m1)*Cat<'o1, 'm1>

  let apply_Fun_CoCone(Ffunctor(_,fo,fm,_) as F, c) = ...

you just have to parenthesise appropriately to distinguish taking the last element or the tuple as a whole.

There is one caveat -- if you want to do pure destructuring to assign names to components and write

let Cat(_,_,id,comp) = ...

this gets parsed as defining a function Cat on a tuple that returns a constant; unlike in SML you have to provide a dummy name for the whole expression

let Cat(_,_,id,comp) as cat' = ...

to get the destructuring assignment to id and comp that you wanted in the first place.



April foolery

Normally at this time of year, after the clocks have gone forwards, I think to myself that there's light in the evenings, but it's still too cold to do anything with it. This week it's been mild enough that I've sat out at the picnic table twice in the evening to eat my supper, as well as doing the necessary weeding.


Monday, March 31, 2014

9305.8

A busy month, but with dry enough weather for a lot of cycling; and after cleaning contacts and making a few infinitesimal adjustments to the sensor magnet, odo readings once again, to a total of 361.2 miles for the month, and 758 miles year to date, compared with last year's 604.



Wednesday, March 12, 2014

March Madness

March opened with our next-door neighbour getting a new fence around his front garden. Unfortunately, the old phone line ran just under the soil along the boundary, so was exactly where a hole got dug for one of the fence posts.

So farewell to the last of the GPO junction boxes in the close...








...and hello to a new BT one, plus a 25% increase in our download speed! (Though perhaps that was ADSL2 kicking in at the same time). It did take more than a week, though.


Tuesday, March 04, 2014

Wet weather

While there was hardly enough rain in March to disrupt my steady schedule of cycling, there was just enough to put the Cam into spate and flood the usual spots along the water meadows.


so I got to take some pictures on a bright morning on the way to work, but otherwise rejoiced thing the fact that we're in a semi-desert in the part of the world.

Friday, February 28, 2014

February cycling -- 8944.6 + 53

Well, between other commitments at the weekend, rain, wind and a cold, there was an 8-day gap in cycling spanning the second week of the month; then increasingly temperamental contacts on the odo dropped 53 miles -- stopped registering at the return from a supermarket run and one way to work, registered for the next couple of commutes, then failed entirely for two full round trips. So an unsurprisingly low increment in this shortest of months -- 184 total (131 + 53) and 397 for the year, which still keeps me ahead of last year.

It would have been more but the two good days this week I was at a corporate off-site, which I'm still recovering from; and now after a spring-like start to the week, it's wet and wintry again.

I shall have to get a new odo and give up the idea of running the current one around the clock.


Monday, February 17, 2014

A 1,001 software development nights

If you have ever read some of the translated Arabian Nights, you will be familiar with the way that a character will head off on a quest, find someone who knows how to help him complete the quest, if he will just run an errand for them... And so Scheherazade secured her position by greatly delaying unwinding the recursion thus engendered.

I'm finding some of my side-project coding is being like that at the moment. The failure of one apparently innocuous change to do what I wanted led me to think "I could use a tool to help here!" And then "But to do that, it would be useful in the long run to have a tool that helps build programs including that sort of tool."

And then I find that some of the libraries I was relying on as support don't quite do what I want, so "I could use a tool to help here! But to do that, ..."

So now I have a handful of new side projects just to help unblock me on but one of my already over-long list of same.


Sunday, February 09, 2014

Anime — 2013 in review

When something that used to have a regular slot in the day happens less often, there comes a tipping point where it almost never does. It was like that with TV before we gave that up; and it happened with anime last year.

The year opened with us picking up three series -- Chihayafuru 2, Vividred Operation (previously reviewed) and The Unlimited (good to see familiar faces, but the story was a bit meh) from the winter quarter in addition to carry-overs, including the previous summer's Uta Koi (generally harmless mix of humour and retellings of the lives of the poets), and going back to pick up the previous autumn's Girls and Panzer (a fun piece of sports fluff involving the lady-like art of sensha-dō).

But as spring arrived and none of the series appealed, it was time to eke out what we had (including barrelling through the entire run of Encouragement of Climb taken as one 40 minute session) -- and hence the crash.

Of summer's shows I tried the first episodes of about half a dozen series, but the few that didn't end with a feeling of "glad that's over" didn't leave me eager for the next episode, and the only one that went any further than that was Gatchaman Crowds, which is the other series we're carrying forward to this year along with Chihayafuru 2 (and House of Five Leaves, where the DVDs never got unpacked all year -- should have just charged through it when we started).

At some point I might get around to looking at some of the autumn titles (the ones that sound dire but got good word of mouth and the one that looked plausible and got no word of mouth) -- but I did watch a lot more anime in the closing weeks of last year than the whole rest of it, rewatching Akagi (having seen that was on the Crunchyroll repertoire), Saki (in readiness for the current season's continuation that I haven't started yet) and Sora no Woto.


A sad tale of digital decay (with a happy ending)

In the distant past, I used to use CVS for my home projects, before moving to SVN, and latterly to Mercurial (because it seemed that git would never play nice on Windows -- so, not long before Github for Windows came out, then). For various reasons, I thought I'd sweep the cobwebs off one of the old projects that still lived in the CVS repo backup.

I also had a copy of the WinCVS installer from way back when, so I expected just to run it up, check things out and be done.

It turned out that that was when the fun began. I started with looking for a CVS/Mercurial bridge, but they all seemed to be Unix based and included dire warnings about CVSNT being problematic. And it's not as if I really needed the old check-in history. So back to the long-hand way.

WinCVS installed OK, but the CVSNT sub-installer just hung. Try the latest (coming up to its 7th birthday) release. No joy there either, just the same hang. Discover that CVSNT itself is now being charged for -- there surely is indeed one born every minute! Try Tortoise CVS -- which completes its install of the included CVSNT, but (as I find after much googling for the error message

cvs server: Couldn't open default trigger library: No such file or directory

later) has failed to install the default_trigger.dll file.

Start looking for the CVS file format and how it handles binaries, because there are image files in the repo module as well as just code; and discover that it's the same as RCS format.

Inspiration finally dawns. The problems cited by cvs2svn with CVSNT in migrations is CVSNT in its role as a command line client, and not with the repo it talks to! Fire up cygwin and check everything out smoothly, after three hours beating around the bush.

The moral of the story : it's not enough to keep the back-ups -- you have to be able to usefully read them as well! Even if it's just some hobby code, rather than NASA downlink telemetry from the 1960s.



Garden rubbish

The weather has continued mild over the past 4 weeks, and now we have the crocuses and snowdrops out amongst the marigolds, and one slow-motion blooming rose in the more sheltered and sunny part of the garden.

We finished the last of the apple crop yesterday, and pulled half the leeks last weekend; and the crop of salad leaves that were mostly eaten by caterpillars last August have actually pulled themselves together enough in the winterised bed in the greenhouse that I've been able to get garnishes for Karen's lunch.

And with the garden next door no longer a wilderness, that's been a cue to start tidying up dead wood (and all too live ivy) in our own back hedge -- I've already got enough debris to fill the green bin until going on Easter. It looks like that'll be this year's garden project by the time it's done.

Saturday, February 01, 2014

8813.3

Despite the wettest January since whenever, the main reasons I had at any point not to cycle to work in the continuing mild weather were either meetings mid-afternoon with no suitable window to get home before dark, or when the bolt securing my saddle snapped for the second time in six weeks, which latter robbed me of about 30 miles. So, 213 miles in all, rather than the almost 250 it could have been -- still 35 miles ahead of last year.

Meanwhile the garden is merging late autumn -- marigolds, and a rose slowly opening -- with spring as the snowdrops are out and the other bulbs are poking through. And with both the mild weather and our neighbour having cleared the spinney which had grown up in his back garden over the last ~30 years, no deer has been coming to nibble on them.


Sunday, January 12, 2014

Garden Rubbish

While there was a fairly white frost on parts of the garden this morning, the half-hardy fuchsias and the marigolds seem to have shrugged it off again. Meanwhile, in the greenhouse, one of the last of the beef tomatoes was ripe enough to pick, along with some salad leaves growing in the raised bed, between the bubble-wrap covered overwintering pot-plants.

Meanwhile the apple crop is just about running out and getting to the stage when I'm racing decay in the early picked stored apples, the celeriac seem to have done nothing, and the leeks are just about ready enough to do for a couple of meals. At least with the milder weather and the next door garden no longer being a spinney, there's been no muntjac nibbling the sound windfalls that have been in "outdoor storage" where they lie.

With the weather in general staying benign, it's also meant I've been steadily mounting up the miles on the bike again, workshifting the last couple of hours of the working day.


Tuesday, December 31, 2013

8600.5

Standing water

While we have had the occasional day of heavy rain, with a little bit of waterlogging -- though nothing quite as bad as last year,

Bright Winter's Day

thanks to the continuing fair weather -- including a lovely few days at the start of the holidays -- I more than made all the mileage goals I'd set myself. On my bike that was 3008 miles, plus 433 on hired bikes for a total of 3441 miles; not quite the equivalent of commuting to work every other day.

Maybe I should try for the 10 miles a day average next year.



Monday, December 30, 2013

An introduction to Functional Programming in F# -- Part 6: Continuations and Monads

Hang onto your hats! This final part is where the ride gets wild.


Topics covered in the series

Alas, despite having trailed generative programming, I find I don't have any notes from the seminar series covering that topic explicitly (it was not one I was presenting). If I find something, I'll add it in as an extra post.


Continuations

This style of programming originally arose in handling data streams in a fashion using lazy evaluation, and uses closures to represent each step of the program. I/O is made available as a pair of lazy lists, a request list and a response list, and the program is a function which takes a response list to a request list:

type Request = Getq | Putq of char
type Response = Getp of char | Putp
type Dialog = Response list -> Request list

For example:

let readChar f p =
    Getq ::
    (match p with 
     | (Getp c) :: p1 -> f c p1
     | _ -> []);;

The hidden causality here is that putting the Getq at the head of the request queue causes the Getp c to exist at the head of the response queue (perhaps by reading the keyboard).


In general, the continuation style uses chained closures to construct a complex compound operation from a collection of small basic operations. We introduce the types

type continuation = K of (unit -> unit)
let execute (K f) = f()
let stop = K (fun () -> ());;

Our building blocks will mostly be producers and consumers, and others that are neither:

Producer: (X -> continuation) -> continuation
Consumer: X -> continuation -> continuation // strictly a continuation generator, as it produces a continuation from the output of the producer.
Operation: continuation -> continuation
  • Where possible, the continuations are built during the construction phase.
  • Each step is provided with the rest of the execution as a continuation building block(s).
  • A producer is provided with a consumer which constructs a continuation from the produced data at execution time.

Example -- Console I/O

First we define some primitives:

let putc (c: char) (k: continuation) =
    let write () = System.Console.Write(c);
                   execute k
    K write
let getc (g: char -> continuation) =
    let read () = execute (g <| System.Console.ReadKey(true).KeyChar)
    K read;;

where we introduce the standard convenience function

let (<|) f x = (f x);;

to avoid extra parentheses.

We can then define a compound operation, for example:

let rec echo k = 
    let echoChar c = if c = '\r'
                     then putc '\n' k
                     else putc c (echo k)
    getc echoChar;;

Example -- The Lexer revisited

The type constructor lexerResult describes the values that the lexer is going to produce. Note that the lexer is going to be a producer continuation.

// Define a result type of a lexeme list or error message:
type lexerResult<'lexeme> = 
    Success of 'lexeme list
  | Failure of string;;

The type constructor lexerSystem provides us with an I/O abstraction.

// Define a type with a character source, a 'lexeme sink and an error string sink:
type lexerSystem<'lexeme> = { 
  input: unit -> char option;
  output: 'lexeme -> unit;
  error: string -> unit;
  result: unit -> lexerResult<'lexeme> };;

Given that the lexer is going to be a producer, we will need a consumer to complete its construction.

// Read the output result and continue with (g result)
let lexComplete s g = 
    let complete () =
        g (s.result ())
    K complete;;

To allow for lexical analysis failures, we also have a building block for that.

// Set the output to the failure state and continue with k
let lexFail s e k =
    let storeError () =
        s.error e
        execute k
    K storeError;;

Note that although it looks like a consumer, in practice we always know the message to use at construction time.

Function lexGetChar builds our most primitive producer continuation.
The consumer (g) constructs a continuation from the character option read from the input.

// s is our lexerSystem
let lexGetChar s g =
       K (fun () -> execute (g (s.input())));;

Similarly, lexPutLexeme builds our most primitive consumer, which writes a lexeme to the output.

let lexPutLexeme s lexeme (k: continuation) =
    let storeLexeme () =
        s.output lexeme;
        execute k
    K storeLexeme;;

In order to make decisions based on our inputs we need to express a conditional branch.

// (^^) associates on the right, which means that we can chain instances without requiring nested brackets
let ( ^^ ) (test, g1) (g2: 'x -> continuation) x =
      (if test x then g1 else g2) x;;

and similarly we want to be able to express repetition.

let rec ( ^* ) (generator: ('x option -> continuation) -> continuation, test)
            (consumer: 'x list -> 'x option -> continuation) =
    generator (function Some x -> if test x
                                  then (generator, test) ^* (fun l -> consumer(x::l))
                                  else consumer [] (Some x)
                      | None -> consumer [] None);;

Thus equipped we can start to write the lexer.

type LispLex = Bra | Ket | Dot | Str of string | Num of int | Symbol of string
let alpha c = ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z'))
let digit c = (c >= '0') && (c <= '9')
let eqChar c c' = c = c'
let l2s l = String(List.toArray l)
let ( ^| ) p q = fun x -> (p x) || (q x)

// Read a symbol from the input
let readSymbol s char g =
     (lexGetChar s, alpha ^| digit ^| eqChar '_') ^*
     (fun l ->
             fun opt ->
                    lexPutLexeme s (Symbol (l2s ([char]@l))) (g opt));;

Exercise: Complete the lexer.


Summary

We have used closures as continuations to construct functions which compose using function application to create more complex functions. The end result is a complex closure, which is itself just a function which, when applied to the unit value “()”, is the program we want, with any side effects of the constituent closures. The main problem that we, as programmers, are likely to feel with this approach is that the process of construction is counter-intuitive, due to the back to front construction style, given that each step of the closure takes an argument representing the rest of the program, thus

type continuation = K of (unit -> unit)
step1: continuation -> continuation
end: continuation
program = step1 end : continuation

As Eric Lippert put it (in the context of writing asynchronous code in this style in C#):

Remember what I was saying about the pros and cons of CPS?

  • PRO: Arbitrarily complex and interesting control flows can be built out of simple parts – check.
  • CON: The reification of control flow via continuations is hard to read and hard to reason about – check.
  • CON: The code that represents the mechanisms of control flow completely overwhelms the meaning of the code – check.
  • CON: The transformation of ordinary code control flow into CPS is the kind of thing that compilers are good at, and almost no one else is – check.

It is important to note, however, that this is not the only use of continuations. We regularly use continuations as event handlers, and they can also be used to search a set of alternatives, by effectively constructing a set of programs to be tried one after another until one does not fail provides a result, or all of them fail.

Used appropriately, this is a powerful technique.



Monads

Despite the scary name, monads are constructs that arise quite naturally in functional programming; typically as a result of trying to express the OO notion of a separation of concerns, here between individual functions doing localized transformations, and the larger control flow of the program.

A monad is a type the values of which encapsulate a piece of a program in much the same way as a continuation does. There are, however, differences in the way the values work and the way they compose, which fits into the functional programming style more naturally. We will, for the moment, write a monad as a type M t where t is a type which values of the monad produce when “run”, except when the run fails (in which case no value is produced). As with continuation programming, a program is constructed by the composition of monads and functions which produce monads. The basic constructions used are:

Return: t -> M t
Fail: M t
Bind: (t1 -> M t2) -> M t1 -> M t2

Understanding “bind”

The “bind” combinator is often written as the infix operator >>=. This begins to make sense if we use a program layout thus:

m >>= fun value1 ->
E1[value1] >>= fun value2 ->
E2[value2]

We read this as binding value1 to the output(s) of m, using this to produce the monad E1[value1], and then binding value2 to the outputs of that, constructing the monad E2[value2], and so on. A language with monads built in can even provide syntactic sugar for this, such as:

value1 := m;
value2 := E1[value1]
E2[value2]

Unfortunately the F# type system is not expressive enough for us to write a general >>= along the lines of

let __binder__<'T, 'U, 'M when 'M : (static member bind : ('T -> 'U 'M ) -> 'T 'M -> 'U 'M)> (x: 'T 'M) (f : 'T -> 'U 'M) =
    x |> 'M.bind f;;
let (>>=) = __binder__;;

so for the moment we will write >>= but mean the comparable operator specialised to the monad of interest.

Derived combinator cases

A monad type M unit is special (think of it as pure side-effect). With such a type there little point in binding the result values – we know that we will only get ():

let (>>) m1 m2 = m1 >>= fun () -> m2;;

A monad which produces a function or functions is also interesting:

let Apply m1 m2
    = m1 >>= fun f ->
      m2 >>= fun x ->
      Return (f x);;

Given a function we can construct a function over monads:

let Lift f m =
    m >>= fun x ->
    Return (f x);;

Exercise: Prove that Lift f = Apply (Return f)

Given two functions that return monads, we can combine them:

let (>=>) f g
    = fun x -> (f x) >>= g;;

A monad which produces a monad or monads can be flattened (lose a level of monad):

let Join mm
    = mm >>= fun x -> x;;

The name join makes sense when the monad involved produces multiple values – the result monad produces all of the values produced by all of the monads produced by mm.

Given a list of monads we can construct a monad of lists:

let rec Sequence l
    = match l with
      | [] -> Return []
      | h::t -> h >>= fun h1 -> (Sequence t) >>= fun t1 -> Return (h1::t1);;

An example of a monad

We introduced the notion of a monad with the description that it handles things like separation of concerns. One very familiar language construct that we have been using from the very first session can be written in monadic form; a 'a list is just another monad 'a:

let ReturnList x = [x]
let FailList = []
let (>>=*) m f = List.concat (List.map f m);;

Another pure monad construction is Option.

let ReturnOption x = Some x
let FailOption = None
let (>>=?) m f = Option.bind f m;;

which allows us to chain together a series of operations that might fail, and bypass the calls made after any failure.

Exercise: Construct a pure monad based on trees.


An I/O Monad

These pure monads do not really have a notion of execution. We can use closures again to construct a monad which itself carries out some side-effecting computation and returns a value. As we did for continuations, we will wrap the closures up using a data type (as before this is to highlight the construction and can be elided):

type 'a io = IO of (unit -> 'a)
exception  IOFailure
let RunIO (IO f) = f();;

The principal functions for this are:

let ReturnIO x = IO (fun () -> x)
let FailIO = IO (fun () -> raise IOFailure)
let (>>=) m f = IO (fun () -> RunIO(f(RunIO m)));;

The construction for bind (>>=) deliberately constructs a wrapped closure. At first sight it looks the same as f(runIO m), which has the same type, but we need to make sure that the sub-term runIO m is evaluated when the result of the bind is run rather than when it is constructed. As all of the other combinators are defined in terms of these three, we won’t need to worry about evaluation order for them. The issue will arise, however, for most special primitives, as we will want side effects to occur at the right time.

To read and write characters we can use:

let GetC = IO (fun () -> System.Console.ReadKey(true).KeyChar)
let PutC  (c:char) = IO (fun () -> System.Console.Write c) ;;

We can, of course, string a lot of these together using the derived combinators >>= and >>. The result does nothing until run. For example:

let EchoC = GetC >>= PutC;;

We can also define read and write for strings:

let GetS length =
    let rec get chars count =
            if count > 0
            then GetC >>= fun c -> get (chars@[c]) (count – 1)
            else Return IO String(List.toArray chars)
    get [] length;;

Exercise: write PutS.


Computation expressions

F# does provide a form of syntactic sugar that allows us to write monadic code, and continuation passing, in a form that is actually comprehensible to the programmer.

Consider the Option monad. If we introduce a singleton type

type OptionBuilder() =
    member self.Bind(input, operation) = Option.bind operation input
    member self.Delay (operation:(unit -> 'a option)) = operation ()
    member self.Return input = Some input
    member self.ReturnFrom (input : 'a option) = input
let option = OptionBuilder();;

where Delay has the effect (as in the >>= operation for our I/O monad) of delaying the execution of the operation until the appropriate point in the sequence, we can write the monadic code using chains of >>=? combinators as a sequence of assignment-like let! expressions.

let result = option {
let! y = f x
let! z = g y
return! h z};;

where f, g, h are functions taking plain values to option values.

The actual compiled form of the let! binding

builder {let! pattern = expr
                        compound_expr }

is in the continuation form

builder.Bind(expr, (fun pattern -> compound_expr))

This not only allows us to write monadic code in something close to the syntactic sugar form as alluded to above, but also to express naturally continuation based code (e.g. asynchronous operations) in a sequential style (indeed the async computation builder is a standard part of the library for exactly this purpose).

We can also express the equivalence of the two notations by building a monadic form from a computation expression, such as the async computation builder:

let ReturnAsync x = async { return x }
let (>>=!) m f = async { return Async.RunSynchronously(f(Async.RunSynchronously m)) }
let (>>!) m1 m2 = m1 >>=! fun () -> m2
let (>=>!) f g = fun x -> ((f x) >>=! g)
let ApplyAsync m1 m2 =
      m1 >>=! fun f ->
      m2 >>=! fun x ->
      ReturnAsync (f x)
let LiftAsync f = ApplyAsync (ReturnAsync f)
let SequenceAsync (l : _ list) =
      Async.Parallel l >>=! fun a ->
      ReturnAsync(Array.toList a);;

Concluding Remarks

Now, like Wittgenstein's Ladder once you have grokked the content of this course, you should be able to discard the often inefficient implementations used for simplicity (such as avoiding cluttering the example code with reversing cons'd lists), and be confident in using a functional style where complex programs can be built from simple pure elements composed together.

As to the F# language itself, we have barely skimmed the surface -- material like active patterns, quotations (the missing last lecture), the standard collections modules, reactive events and more still remain untouched. But in my experience, once the initial hurdle of the programming style has been crossed, picking those up when you realise you need them is the easy part; whereas before the "Aha!" moment the motivation and need for such features will remain mostly obscure, hidden behind the dilemma of "how do you program when your variables don't?" .

Exercise: Test your understanding by reworking the course material for another language of your choice. Note that for some functional languages, parts will not be applicable as they stand (e.g. neither assignment nor the shared-state queue will be expressible in Erlang); and that for many languages pattern based dispatch and infix notation will not be available.



Sunday, December 29, 2013

An introduction to Functional Programming in F# -- Part 5: Objects and Exceptions

This session marks a pause for breath between the introductory parts where we concentrated on doing interesting work with mostly simple immutable lists and with algebraic datatypes, and the last part which will be all heavy lifting, to look at other ways of representing compound data, and how the functional world interacts with the more familiar parts of the .net framework. Also, this week, no exercises either.

I'm keeping this part in mainly for completeness' sake, as a transcription of the original seminar material from '08; rather than for any great insights it offers. In particular, unlike the previous sessions there won't be any of the two steps to comprehend -- first, how the program works, and then with increasing familiarity, why you wouldn't actually implement things in quite that way in a real program. It'll be more like a shopping list instead.


Topics covered in the series


Assignment

Actually we covered assignment and mutability last time.


Tuples

We used tuples -- collections of a fixed number of items, defined by the types of each item, way back in the first session. Recall

let Half_Adder x y = (XOR x y, AND x y);;

The value returned by this function is a 2-tuple of the Bits type -- written Bits * Bits; but in general the types in a tuple will be heterogeneous.

Tuples are usually best employed as ad hoc datastructures; while there are standard functions

let fst (a,b) = a;;
let snd (a,b) = b;;

for extracting members of a 2-tuple, getting at parts of longer tuples will involve destructuring pattern matching.


Records

A record is more like a class -- or, really, a 'C'-style struct -- in having a series of named fields. We have actually used records in their simplest form, in some of our previous examples

type SEXPR = SYMBOL of string | NUMBER of int | NIL | CONS of (SEXPR * SEXPR) | COMPUTATION of COMP
and COMP = { func : SEXPR -> SEXPR } ;;

because functions are just values, we can put them into a record just as well as other types. We can be more object like if we mix scalar and function values in a record:

type  Point = { x: int; y: int; move: Point -> Point }
let rec makePoint vx vy = 
    let doMove p = makePoint (vx + p.x) (vy + p.y)
    { x = vx; y = vy; move = doMove };;

which defines a 2D point type with a displacement-vector behaviour.

Records themselves are immutable, so we can only create new records based off old ones e.g.

let p = (makePoint 1 2).move(makePoint 2 3);; 

There is a copy but replace one or more fields syntax

{p with x = 6; y = 0 };;

but this of course violates the contract that the move function displaces its target by the x,y value of the point. However, types can have methods

type Point = { mutable x: int; mutable y: int }
              with member p.move q = p.x <- p.x + q.x;
                                     p.y <- p.y + q.y
let makePoint x y = { x = x; y = y }

and with the move member working on the current rather than creation time value of the coordinates, we have a class-like structure, albeit with public fields. And most of the time this is sufficient, if the type itself is not exposed.


Objects and interfaces

When interfacing with .net libraries, we need to define actual objects or interfaces. Our previous point behaviour can be expressed as an interface

type IPoint
     = interface
           abstract x: int;
           abstract y: int;
           abstract move: IPoint -> unit
       end 

which we can implement as

type Point
     = class
           val mutable vx: int;
           val mutable vy: int;
           new(x,y) = { vx = x; vy = y }
           interface IPoint
                with member p.move q = p.vx <- p.vx + q.x;
                                       p.vy <- p.vy + q.y
                     member p.x = p.vx
                     member p.y = p.vy
       end
let makePoint x y = new Point(x,y) :> IPoint;;

Note that F# syntax requires us to explicitly implement the interface; as a consequence, we also need to cast our concrete implementation explicitly to the interface type when we wish to refer to it as such.

There is an alternative syntax which removes the explicit new member as a constructor, and instead makes the class body act as a constructor function:

type Point(x,y)
     = class
           let mutable vx = x
           let mutable vy = y
           interface IPoint
                with member p.move q = vx <- vx + q.x;
                                       vy <- vy + q.y
                     member p.x = vx
                     member p.y = vy
       end

The two are similar, but not quite the same; for this second example vx and vy are not (as the result of pasting the code into the interactive prompt shows) instance variables, as they were before, but are in locals in the constructor function.

Alternatively, we can define an abstract base class, rather than an interface. This requires an attribute annotation, rather than a keyword:

[<AbstractClass>]
type AbstractPoint
     = class
           val mutable vx: int;
           val mutable vy: int;
           new(x,y) = { vx = x; vy = y }
           member p.x with get() = p.vx and set z = p.vx <- z
           member p.y with get() = p.vy and set z = p.vy <- z
           abstract move: AbstractPoint -> unit
       end
type Point'
     = class
           inherit AbstractPoint
           new(x,y) = { inherit AbstractPoint(x,y) }
           override p.move q = p.x <- p.x + q.x;
                               p.y <- p.y + q.y
       end

let p = Point'(2,3)
let q = Point'(1,2)
p.move(q)
p.x
p.y;;

Note that this time we don't have to cast anything to the base class in order to invoke the move method. A Point' is an AbstractPoint.


Exceptions

These have the sort of behaviour that we are familiar with

  • Exceptions do not affect the types of functions that throw them.
  • Exceptions “propagate up the call stack” until a handler is found (or to top level).

There are two built-in exception mechanisms

// Raise an ArgumentException:
invalid_arg "list must not be empty"
// Raise a FailureException:
failwith "internal error"

or we can just raise a standard exception type

raise (InvalidOperationException("help!"))

New exception types can be declared by subclassing, or by ML syntax

exception Special of int
raise (Special 99)

Exceptions are handled much like they are in C#/C++/Java...

exception EmptyList of string
let rec folds g x
    = match x
      with [] -> raise (EmptyList "folds")
         | [x] -> x
         | h::t -> g h (folds g t)
try folds (fun x y -> x + y) []
with EmptyList m -> stdout.WriteLine(m);
     0

where the with construct actually allows pattern matching over the exception (so can be the equivalent of multiple catch clauses)

There is a related construct; a finally clause can also be used with try as in C#, to add some code which is always executed:

let resource = getResource()
in try folds (useResource resource) []
   with EmptyList m -> stdout.WriteLine(m);
        rethrow()
   finally releaseResource resource 

though there is no portmanteau try ... catch ... finally as there is in C#.

Note that because we are in the .net framework here, exceptions are expensive operations, unlike in OCAML, where they are sufficiently cheap as to be a standard control flow construct.