Language-Oriented Programming: Inventing your own languages 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.

Ebook Download
View all
Learn
View all