Design Model F #

Question

Suppose I create a parser for a domain-specific language in F #.

I have defined a discriminatory 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 have created an AST of type Expression and want to generate code for it. I have one function that does type inference and type validation of an expression.

It is defined as

  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 for generating code that follows a similar pattern: Take an expression, write pattern matching statements for each element in the union.

My question is: is this an idiomatic way to do this in F #?

It seems to me that it would be cleaner if each member of the union defined their 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 redefine them in each subclass.

Is there any other way to do this?

Answer 1

It seems to me that this will happen if each member of the union defines its own InferType and GenerateCode locally with it.

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

Indeed, your ideal is that you implement the implementation of the code generator through 10 different classes?

There is definitely a fundamental tension between whether you want to group things “by type” or “by operation”. The usual OO method is “by type”, while the FP (functional programming) method “works”.

In the case of the compiler / interpreter (or most of the things that in OO are highly dependent on the Visitor template), I think that “by operation” is a more natural grouping. The code generator for If and And and Or may have several things in common; testers of various nodes will also have common features; if you create a nice printer, it is likely that formatting procedures common to all node -pretty-printing implementations will follow. In contrast, printing, type checking, and IfElse coding really don't really have much to do with each other, so why do you want to group them in an IfElse class?

(To answer your questions: yes, this is idiomatic. Is there any other way - yes, you can do it the same way as in C #. I think you will find that you are much less happy with C # and that the code will also 2-3 times more, without any advantages.)

Answer 2

As an OCaml programmer, I would say that this is completely idiomatic. By the way, this gives you a better separation of problems than if you wrote a class hierarchy using class methods. You will get similar modularity in OO with an InferType visitor, but that will be a lot more code.

Answer 3

Another thing you usually do in a functional language is to define a fold operation for a data type, and then define type checking and code generation functions in terms of folding. In this particular case, I'm not sure if it buys you a lot, because the fold function has so many arguments that it will not be particularly easy to understand:

 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 ...