F# design pattern

Question

Lets say I'm building a parser for a domain-specific language in F#.

I've defined a discriminated union to represent expressions:

    type Expression = 
        | Equality of Expression*Expression
        | NonEquality of Expression*Expression
        | Or of Expression*Expression
        | And of Expression*Expression
        | If of Expression*Expression
        | IfElse of Expression*Expression*Expression
        | Bool of bool
        | Variable of string
        | StringLiteral of string

Now, I've built up an AST of type Expression and want to generate code for it. I have one function which does type inference and type checking on an expression.

It's defined like

    let rec InferType expr = 
        match expr with
        | Equality(e1,e2) -> CheckTypes (InferType e1) (InferType e2)
        | Or(e1,e2) -> CheckTypes (InferType e1) (InferType e2)
        | And(e1,e2) -> CheckTypes (InferType e1) (InferType e2)
        ...

And I have another function to generate code which follows a similar pattern: Take an expression, write pattern-matching statements for each item in the union.

My question is: Is this the idiomatic way to do it in F#?

It seems to me that it would be cleaner if each member of the union defined its own InferType and GenerateCode locally with it.

If I were using C#, I would define some abstract base class called Expression with virtual methods for InferType and GenerateCode and then override them in each subclass.

Is there any other way to do this?

Answer 1

It seems to me that it would be cleaner if each member of the union defined its own InferType and GenerateCode locally with it.

I believe you mean "more familiar", not "cleaner".

Really, is your ideal to have you code generator implementation spread out across 10 different classes?

There is definitely a fundamental tension between whether you want to group things "by type" or "by operation". The usual OO way is "by type" whereas the FP (functional programming) way is "by operation".

In the case of a compiler/interpreter (or most things that in OO rely heavily on the Visitor pattern), I think "by operation" is the more natural grouping. The code generator for If and And and Or may have a bit in common; the typecheckers of the various nodes will similarly have commonalities; if you make a pretty-printer, there will likely be formatting routines common to all the node-pretty-printing implementations. In contrast, printing, typechecking, and codegenning an IfElse really don't have much to do with one another at all, so why would you want to group those in an IfElse class?

(To answer your questions: yes, this is idiomatic. Is there another way - yes, you can do it just like you would in C#. I think you'll find you're much less happy with the C# way, and that the code will also be 2-3x larger that way, with no benefit.)

Answer 2

As an OCaml programmer, I'd say this is entirely idiomatic. Incidentally, this gives you better separation of concerns than if you had written a class hierarchy with class methods. You'd get similar modularity in an OO language with an InferType visitor, but it would be a lot more code.

Answer 3

The other thing that you might typically do in a functional language is to define a fold operation on the datatype and then define the typechecking and code generating functions in terms of the fold. In this particular case I'm not sure that it buys you much because the fold function would have so many arguments that it won't be particularly easy to comprehend:

let rec fold eqE nonE andE orE ... = function
| Equality(e1,e2) -> eqE (e1 |> fold eqE nonE ...) (e2 |> fold eqE nonE ...)
| NonEquality(e1,e2) -> nonE ...
...

let inferTypes = fold checkTypes checkTypes checkTypes ...