Expressing a domain specific language of propositions in F#

One aspect of many functional languages that’s always fascinated me is the ease with which you can express a recursive structure, such as a language, and have it evaluated. Suppose you want to define the grammar of a DSL of propositions, in F# you could do so using the discriminated union type:

type Proposition =
    | True
    | And of Proposition * Proposition
    | Or of Proposition * Proposition
    | Not of Proposition

In an object-oriented language like C#, this definition would be analogous to a hierarchy of classes. Proposition would be the base class of True, And, Or, and Not. Each would then have a constructor that accepts some number of arguments, e.g., the And constructor would accept a two-tuple, two propositions, making the Proposition type recursive. In C# you might even model the recursive relationship using the Composite pattern.

In F#, an instance of the Proposition type may be created using a constructor syntax that resembles that of a function call:

let p = And(Or(True, Not(True)), Not(Not(True)))

Now, because of the recursive nature of the Proposition type, instances of it form a parse tree-like structure:

                        And
                        /\
                       /  \
                      Or  Not 
                      /\    \
                     /  \    \
                  True  Not  Not
                          \    \
                           \    \ 
                          True  True

Having a parse tree is not useful in itself. What you need is some way to execute or evaluate it. Given the recursive nature of the grammar, it makes sense for the evaluator to be recursively defined as well. The evaluator would do pattern matching on the node type, deconstructing it into the parts needed to evaluate it. Since our language of propositions maps directly to the boolean operations of F#, it’s simple to evaluate the parse tree:

let rec eval (p: Proposition) =
    match p with
    | True -> true
    | And(p1, p2) -> eval p1 && eval p2
    | Or (p1, p2) -> eval p1 || eval p2
    | Not(p1) -> not (eval p1)

let e = eval p // e : bool = true

The features of F# used here allow for more complicated languages to be expressed and evaluated directly without the need for any Backus-Naur form and parser generator.

PS: I’ve encountered this gist implementing a nice progression of the same idea with expressions and variables.