3.2k
views4
comments

[Taken from my post of the same name on F# mail list]

What would smooth the transition of a C# programmer to F#?

While some people here advocate "shock treatment" -- functional is a
different way of thinking so throw away your OO preconceptions and start
over without classes -- that approach (IMHO) is unlikely to appeal to anyone beyond
the highly motivated.

I want to discuss an alternate approach: "augment your bag of tricks with
some new ones".

This approach is designed to make the way as smooth as possible.

Begin by showing how to do in F# what you already know how to do in C#.

Take a number of simple C# fragments, and re-write them in F#, showing each
of the features that map 1:1. Start with C# 2.0 features only.

Early on, will have to discuss mutable vs. non-mutable values, since values
are mutable by default in C#. Show why non-mutable values are a good thing.

Then start introducing new features. Justify each feature by starting with a
design goal, solving it in C# as best as possible. Then show how using one
new feature of F# results in simpler code. NOTE: At the same time, can show
the migration from C# 2.0 to C# 3.0, where 3.0 adds a new
functionally-inspired feature similar to the F# one.

Start with features that are easy for an OO programmer to grasp:

* local functions.
* tuples.
* discriminated union & match.
* sequence comprehension & yield.
* functions as parameters.

Rather than insisting on a pure functional style, show how even a partial
rewrite using one of these features simplifies a given code snippet.

In particular, I have found the following "blended functional + OO" style to
be useful:

Define interfaces, and implement classes which implement those interfaces.
Use a DU whenever there is "choice between alternatives". Show how a DU is a
powerful way to work with several related classes, rather than deepening the
inheritance hierarchy. That is, encourage a "flat" OO style, where each
class directly implements interfaces, but does not inherit from other
classes. Have an interface hierarchy, but not a class hierarchy.

NOTE: My insistence on using even this limited amount of OO appears to be
controversial, based on reactions from experienced functional programmers.

Only after all this solid ground is established, would I demonstrate the
power of (advanced / higher-order / more abstract) constructs:

* currying
* list-folding
* replacing iteration with recursion
* functions that return functions
* workflow

~TMSteve

Continuing the approach of gradually introducing functional, there are two ways in which I have found it very convenient to combine ("blend") DUs (discriminated unions) with an interface, implemented in classes.

The result is easily comprehended by an OO programmer. So I would teach these. THEN show purely functional alternatives.

[Posts 2A-2D] The first "blend" is "A class with a DU member".

Motivation: A DU is a struct, and therefore has no general way to add a data field to the DU as a whole. (Though there are some alternatives in certain situations, to be covered a bit later). Nor is it clear what a constructor would look like, if a DU had alternatives -AND- initialization values that needed to be passed to the constructor.

Example: "Decorating abstract syntax trees with line numbers" [link:cs.hubfs.net]
Here, in the author's mind, the DU is the main focus, but then he wants, off to the side in some manner, some "extra" information, that most of the program won't access. Here is a similar DU from my PEG metacompiler:

1
2
3

  type Spacing1 =
    | Space of Space
    | Comment of Comment

This is a translation of grammar rule:
Spacing1 <- Space / Comment

The design has a number of different grammar rules, each with their corresponding DU.
So there is also:

1
2
3

  type Space =
    | Blank of Whitespace  // ' ' or '\t'
    | EOL of EndOfLine  // EndOfLine

...etc...

If instead of a DU, the author were using a class hierarchy, he would add "extra" members to the common base class, and they would then be available for use where needed. The downside of the class approach is that a class would have to be defined for each alternative; a DU with 4 alternatives would be replaced by 1 base class + 4 sub classes = 5 classes total.

The point here is that the class approach requires extra definition coding, but doesn't require client code to change in the face of this design change -- a key benefit. (NOTE: certain other design changes would be smoother in the functional implementation.) Anyway, here we DIDN'T use the class approach, we used a DU, so we need to deal with that.

An OO programmer, faced with this new requirement, might refactor by wrapping the DU in a class. A functional programmer might wrap in a record. Again, my approach is to first show what an OO person might think to do.

Define a record for the functionality to be added:

  type Position = {index: int; line: int; column: int}

Define an interface as the contract that a class can respond with Position:

1
2

  type HasPosition =
    abstract position: Position

Define a wrapper class per DU:

  type WSpacing1(du: Spacing1, position: Position) =
    member it.du = du
    with interface HasPosition with
      member it.position = position

...etc...

Each reference to a DU is now replaced with a reference to the corresponding wrapper:

1
2
3

  type Spacing1 =
    | Space of WSpace
    | Comment of WComment

What's interesting about the code, is that each wrapper has a "du" field, that returns its DU, and a "position" field.
So usage, that before was passing around Spacing1, would now pass around wrapper classes, and match against "ob.du" when needed:

  let test(wrapper:WSpacing1) =
    match wrapper.du with
      | Space sp -> "Spacing1.Space"
      | Comment com -> "Spacing1.Comment"

Here is the complete code listing:

#light

// ---------- Extended Information: Position ----------


/// The functionality to be added.
type Position = {index: int; line: int; column: int}

/// The contract that a class can respond with Position.
type HasPosition =
  abstract position: Position


// ---------- Basic Types, with Wrappers ----------

type AChar = char
type EndOfLine = char

/// ----- Space & WSpace -----
type Space =
  | Whitespace of AChar  // ' ' or tab
  | EOL of EndOfLine  // EndOfLine

type WSpace(du: Space, position: Position) =
  member it.du = du
  with interface HasPosition with
    member it.position = position

/// ----- Comment & WComment -----
/// This is a single alternative DU, for consistency with the multi-alternative grammar rules.
type Comment = Chars of AChar list

type WComment(du: Comment, position: Position) =
  member it.du = du
  with interface HasPosition with
    member it.position = position

/// ----- Spacing1 & WSpacing1 -----
/// This is a translation of grammar rule:
///  Spacing1 <- Space / Comment
type Spacing1 =
  | Space of WSpace
  | Comment of WComment

type WSpacing1(du: Spacing1, position: Position) =
  member it.du = du
  with interface HasPosition with
    member it.position = position


// ---------- Tests ----------
let ps msg = printfn "%s" msg
let pam msg a = printfn "%s = %A" msg a

let zero_position = {index= 0; line= 1; column= 1}

let test1(ws1:WSpacing1) =
  match ws1.du with
    | Space sp -> "Spacing1.Space" |> ps
    | Comment com -> "Spacing1.Comment" |> ps
  (ws1 :> HasPosition).position |> pam "wrapper.position"

let test() =
  let ws = new WSpace(' ' |> Whitespace, zero_position)
  let ws1 = new WSpacing1(ws |> Space, zero_position)
  test1(ws1)

test()
printf "----- Done: Press any key. -----"
System.Console.ReadKey(false) |> ignore

By ToolmakerSteve on 4/20/2008 6:08 PM (permalink)

Now lets see a pure functional version. Here, instead of defining an interface, and a set of wrapper classes, we simply define a set of wrapper records. For example:

  type WSpace = {du: Space; position: Position}

Can't get more succinct than that!

One complication arises when we use these records. It is easiest to construct records when no two record types use the same field names. We want all the "position" fields to have the same name, since they are the same type. So we will have to tell F# which record we are working with. E.g., instead of saying:

  let ws = {du=' ' |> Whitespace; position=zero_position}

we have to say:

  let ws = {WSpace.du=' ' |> Whitespace; WSpace.position=zero_position}

Comparing the previous "class" version to this "record" version, here the type definitions are significantly more concise, but each construction ended up slightly wordier. Here is repeated the "class" construction for comparison:

  let ws = new WSpace(' ' |> Whitespace, zero_position)  // This is from previous example.

While I like having the "du=" and the "position=" to show which field is which; I'm not fond of prepending "WSpace." multiple places.
WISH: a syntax requiring the record type in only one place, e.g.:

    WSpace{du=' ' |> Whitespace; position=zero_position}

Actual field access is just what we want:

    ws1.position

Vs. the class version:

    (ws1 :> HasPosition).position  // This is from previous example.

NOTE: In C#, the class version's access would have been as concise as the F# record version.

Here is the complete listing:

#light
// Code Sample: DUs in records
// ---------- Extended Information: Position ----------

/// The functionality to be added.
type Position = {index: int; line: int; column: int}


// ---------- Basic Types, with Wrappers ----------

type AChar = char
type EndOfLine = char

/// ----- Space & WSpace -----
type Space =
  | Whitespace of AChar  // ' ' or tab
  | EOL of EndOfLine  // EndOfLine

type WSpace = {du: Space; position: Position}

/// ----- Comment & WComment -----
/// This is a single alternative DU, for consistency with the multi-alternative grammar rules.
type Comment = Chars of AChar list

type WComment ={du: Comment; position: Position}

/// ----- Spacing1 & WSpacing1 -----
/// This is a translation of grammar rule:
///  Spacing1 <- Space / Comment
type Spacing1 =
  | Space of WSpace
  | Comment of WComment

type WSpacing1 = {du: Spacing1; position: Position}


// ---------- Tests ----------
let ps msg = printfn "%s" msg
let pam msg a = printfn "%s = %A" msg a

let zero_position = {index= 0; line= 1; column= 1}

let test1(ws1:WSpacing1) =
  match ws1.du with
    | Space sp -> "Spacing1.Space" |> ps
    | Comment com -> "Spacing1.Comment" |> ps
  ws1.position |> pam "wrapper.position"

let test() =
  let ws = {WSpace.du=' ' |> Whitespace; WSpace.position=zero_position}
  let ws1 = {WSpacing1.du=ws |> Space; WSpacing1.position=zero_position}
  test1(ws1)

test()
printf "----- Done: Press any key. -----"
System.Console.ReadKey(false) |> ignore

By ToolmakerSteve on 4/20/2008 10:33 PM (permalink)

Creating these extra wrapper entities, whether classes or records, was a bit of extra coding; are there other approaches?

One simple approach would have been to add the position field directly to each alternative in each DU; e.g.:

 
type Spacing1 =
  | Space of Space * Position
  | Comment of Comment * Position

I find it unappealing to have to repeat the same information on every branch. It also violates my sense of factoring: something that is logically shared, should only be defined in one place. However, it does avoid the need to define another type.

Lets see how it affects the code. All of our matches extracting the du information get changed on every branch, to mark the extra parameter (I'm not thrilled by such widespread change; but at least the changes are small, and the compiler will tell you where needed):

 
  match ws1 with
    | Space (sp,_) -> ...
    | Comment (com,_) -> ...

Worse, position is no longer a simple "." access, but requires a full match:

 
  match ws1 with
    | Space (_,position)
    | Comment (_,position) -> ...

The construction is tight, so that is one plus:

1
2

 
  let ws = (' ', zero_position) |> Whitespace

Here is the complete code:

 
#light
// Code Sample: DUs with extra field on every choice
// ---------- Extended Information: Position ----------

/// The functionality to be added.
type Position = {index: int; line: int; column: int}


// ---------- Basic Types, with Extra field on every choice ----------

type AChar = char
type EndOfLine = char

/// ----- Space -----
type Space =
  | Whitespace of AChar * Position  // ' ' or tab
  | EOL of EndOfLine * Position  // EndOfLine

/// ----- Comment -----
/// This is a single alternative DU, for consistency with the multi-alternative grammar rules.
type Comment = Chars of AChar list * Position

/// ----- Spacing1 -----
/// This is a translation of grammar rule:
///  Spacing1 <- Space / Comment
type Spacing1 =
  | Space of Space * Position
  | Comment of Comment * Position


// ---------- Tests ----------
let ps msg = printfn "%s" msg
let pam msg a = printfn "%s = %A" msg a

let zero_position = {index= 0; line= 1; column= 1}

let test1(ws1:Spacing1) =
  match ws1 with
    | Space (sp,_) -> "Spacing1.Space" |> ps
    | Comment (com,_) -> "Spacing1.Comment" |> ps
  match ws1 with
    | Space (_,position)
    | Comment (_,position) ->
      position |> pam "wrapper.position"

let test() =
  let ws = (' ', zero_position) |> Whitespace
  let ws1 = (ws, zero_position) |> Space
  test1(ws1)

test()
printf "----- Done: Press any key. -----"
System.Console.ReadKey(false) |> ignore

By ToolmakerSteve on 4/20/2008 10:53 PM (permalink)

Other approaches? Thanks to Jon Harrop for pointing out that recursive structures have a natural place to hook in other information. That doesn't apply readily to the design I've been showing; here is a design where it would apply, and Jon's brief notes on it. NOTE: I have slightly edited the example he supplied to fit in with my previous examples.

I won't go into detail about this; if you feel comfortable reading what is below: congratulations, you are now a functional programmer!

I do believe this is the kind of technique one needs to eventually grasp, to be a "master" at functional programming. I am aiming at an easier target: "functional enough" to start an OO programmer on the road.

 
#light
// Code Sample: recursive DU, using generic type.

// ---------- Extended Information: Position ----------

/// The functionality to be added.
type position = {index: int; line: int; column: int}

(*Jon Harrop says: Just untie the recursive knot so that you can inject
any extra data you need at a later time.
This is very easy and widely done in other functional languages: *)

(*// ---------- Original recursive DU, without position info ----------

type expr = 
  | Int of int 
  | Add of expr * expr 
  | Mul of expr * expr *)

// ---------- Recursive DU, now generic ----------

// becomes a pair of types that are parameterized over their "children": 
type 'a expr = 
  | Int of int 
  | Add of 'a * 'a 
  | Mul of 'a * 'a

type 'a expr_pos = { expr: 'a expr_pos expr; pos: position }

// Then you mimic the layout of the types in the functions that act upon them: 

let rec eval_expr eval = function 
  | Int n -> n 
  | Add(f, g) -> eval f + eval g 
  | Mul(f, g) -> eval f * eval g

let rec eval_pos eval (ep:'a expr_pos) = eval_expr (eval_pos eval) ep.expr


// Once you're finished extending you just tie the recursive knot: 

let rec eval (ep:'a expr_pos) = eval_pos (eval_expr eval) ep;;

// ---------- Tests ----------
let zero_position = {index= 0; line= 1; column= 1}

// NOTE: Not bothering to set meaningful positions in this example.
eval { expr= Add( {expr=Int 3; pos= zero_position},
                  {expr=Int 4; pos= zero_position} );
       pos= zero_position
     }

By ToolmakerSteve on 4/21/2008 12:27 AM (permalink)

Topic tags

Built with WebSharper

Home

Answers

Events

Courses

Groups and Conferences

Blogs

Jobs

Developers

Topic tags