Language-Oriented Programming: Inventing your own languages in F#

Using cool features like discriminating unions, you can pretty much invent your own language structures in F#.

F# has some powerful language features that let you define expressions as a conglomerate of expressions and types.  You can build expressions using discriminating unions using simple expressions and primitive types.

Below is a simple example of how I might do this.  Say I wanted to explicitly list my operator names in a boolean expression.  Instead of using &&  and ||,  I want to define Xor, And, Or, and Not as operators on my boolean values. You can define a discriminating union structure as shown below:

 

#light type logicExpr = | And of logicExpr * logicExpr | Or of logicExpr * logicExpr | Xor of logicExpr * logicExpr | Not of logicExpr | Constant of bool;;

 

This structure is recursive, so you can define logic expressions within expressions. Each line of the expression logicExpr defines a type.  The And type consists of a tuple of two logic expressions. So does the Or, and Xor types.  The Not type is just of type logicExpr.  The Constant type is of type bool. We need the constant type to allow us to return from each recursive logicExpr structure.

Now we need to implement our union operators using pattern matching as a sort of state engine.  The Eval function matches a logic expression against one of our 5 operators.  It then returns the result by performing the F# operation on the passed in value.  The recursive matching builds are recursive logic structure:

 

let rec Eval x = match x with | And (x, y) -> let (lv, rv) = (Eval x, Eval y) lv && rv | Or (x, y) -> let (lv, rv) = (Eval x, Eval y) lv || rv | Xor (x, y) -> let (lv, rv) = (Eval x, Eval y) (lv <> rv) | Not (x) -> let lv = (Eval x) lv <> true | Constant (x) ->x;;

 

Finally we can implement our new language components.  Below are two sample logic structures we built using our discriminating union.  Also shown, is the Eval function called on these logic structures.

 

let logic1 = And (Or(Constant(true), Xor (Constant(true), Constant(false))), Constant(true)) let xx = true let yy = false let zz = true;; let logic2 = Xor ( Not(Constant(yy)), Constant (zz <> yy));;   print_any logic1;; printf ("\n"); let result1 = Eval logic1;; print_any result1;; printf ("\n"); print_any logic2;; printf ("\n");   let result2 = Eval logic2;; print_any result2;; Console.ReadLine()

 

The console shows the resulting structures of logic1 and logic2.  It also shows the result of calling Eval on each of the logic expressions, returning a single boolean value.