In my last post, I wrote about using FParsec to build a user input validator with parser combinators.

For parsing simple conditional expressions like "say X if the user's age equals 16", this works well.

But sometimes you want more expressivity in your grammar.

Say you wanted to parse an expression that says "ask the current age of the user and their mother, then say X if the mother was older than Y when the user was born."

Parser combinators could be used to construct a grammar to represent this dialog condition.

But the more expressivity you want to encapsulate in your grammar, the closer you come to reimplementing a Turing complete language from scratch.

Sooner or later, you'll ask yourself "Why am I using one language to create parser combinators for another language? Why not just use the host language?"

At this point, you may be better off implementing a domain-specific language for your given task.

If you'd like, you can also skip straight to the code on GitHub. Otherwise, read on!

Mimicking dialog

Let's revisit the dialog system concept for a second. In simple terms, our program needs to know:

• what it should say to the user, and
• what the user can say to it.

This means the agent needs some way of validating the user's interaction, and some way of choosing the next response. In pseudocode:

say "Hello, what is your name?"

expect "My name is <[Alice|Bob] yourName>"

if yourName == "Alice" say "Hi Alice!"

if yourName == "Bob" say "I think we met before."

else say "I didn't understand"

We want to write these rules as cleanly as possible. Ideally, we want something very close to this pseudocode.

There are two reasons for this.

First, separation-of-concerns is always a good idea generally. Keeping "program execution code" separate from "dialog script" makes testing, maintenance and extension much easier.

Second, we may want non-programmers to write these dialog scripts. Teaching them a limited meta-language would be considerably faster than a full Turing-complete language.

I'm going to achieve this by creating a domain specific language (DSL) in F#.

A DSL will allow us to collapse considerable functionality into a minimal, clean language - helping us meet the two objectives we just laid out.

The DSL

Ultimately, we want our script writer to be able to write something like the following F# code:

{{< highlight fsharp >}} expect { let! yourName = ["Bob";"Jane"] yield "Hi %s", [ <@ yourName @> ] } {{< / highlight >}}

A developer could then extend this with the full expressivity of F#:

{{< highlight fsharp >}} expect { let! yourName = ["Bob";"Jane"] let temp = getCurrentTemp() match temp > 30 with | true -> yield "Hi %s, it's really hot today!", [ <@ yourName @> ] | false -> yield "Hi %s, it's really cold today!", [ <@ yourName @> ] } {{< / highlight >}}

Implementing this via parser combinators would be much more difficult.

The above code block might look a bit foreign, so let's dive in to see what's going on here.

First, we have some code wrapped inside an expect {...} block.

This is called a computation expression. These are given a detailed treatment in Scott Wlaschin's F# for Fun and Profit, which I suggest you read before continuing if you're not familiar with the concept.

At a high level, computation expressions let you specify some work to perform "behind-the-scenes" when your wrapped block of code is executed.

Computation expressions expose hooks for variable bindings, return statements, and so on, letting you trigger your own custom logic at certain points in the wrapped code.

Now where did this expect {...} block come from?

This is actually an instantiation of a specific builder type:

{{< highlight fsharp >}} type ExpectBuilder() = member x.Bind(comp:obj list, func) = func(comp) member x.Yield (formatString, expressions:Expr list) = let formats = formatString |> getExpectedFormats if Seq.length formats <> Seq.length expressions then failwith "Incorrect number of parameters provided" formatString, expressions |> List.map (fun x -> x.Evaluate()), createCallback formatString expressions member x.Combine (a,b) = [a :> obj;b :>obj] member x.Delay(f) = f()
let expect = new ExpectBuilder() let fmt, candidates, callback = expect { let! yourName = ["Bob";"Jane"] yield "Hi %s", [ <@ yourName @> ] } {{< / highlight >}}

The Bind, Yield, Combine and Delay methods are the hooks I mentioned above - specifically, for the let! and yield statements.

With a builder that implements these methods, we can say "run this code whenever a variable is bound via let! inside the code block".

So what is our expect {..} computation expression doing?

First, let's revisit our overall objective for this dialog system.

We want someone to be able to write a short script that generates:

• a string that the user should read out to us aloud (i.e. "Hi %s!")
• if applicable, any choices the user has within that string (e.g. "Hi [Bob|Jane]!")
• a validator function to check whether the user's response was valid (i.e. "Hi Dennis!" would return false).

The computation expression needs to return these three values, while hiding as much of the heavy lifting as possible from the script writer.

On the first line of our expect {..} expression, we first bind a variable called "name" with the optional values the user can insert into their response.

The let! statement corresponds to the Bind method of the ExpectBuilder: {{< highlight fsharp >}} expect { let! yourName = ["Bob";"Jane"] ... }

... member x.Bind(comp:obj list, func) = func(comp) ... {{< / highlight >}}

Invoking func simply binds the variable, so we don't actually perform any custom logic here.

But say we wanted to add "Smith" to each of the names, we could have implemented that as follows:

{{< highlight fsharp >}} ... member x.Bind(comp:obj list, func) = comp |> List.map (fun x -> x + " Smith ") |> func ... expect { let! yourName = ["Bob";"Jane"] // name is now bound to ["Bob Smith";"Jane Smith"] ... }

{{< / highlight >}}

Our Yield method, on the other hand, does actually do something:

{{< highlight fsharp >}} expect { ... yield "Hi %s", [ <@ yourName @> ] }

... member x.Yield (formatString, expressions:Expr list) = let formats = formatString |> getExpectedFormats if Seq.length formats <> Seq.length expressions then failwith "Incorrect number of parameters provided" formatString, expressions |> List.map (fun x -> x.Evaluate()), createCallback formatString expressions ... {{< / highlight >}}

The method accepts a format string ("Hi %s"), some expressions (which I'll explain shortly), extracts the formats from the string ("%s") and fails if the number of formats doesn't match the number of expressions.

Otherwise, the method converts the expressions into a callback, returning the format string, the evaluated expressions, and the callback.

Now what does that actually mean?

F# code quotations

If you don't know what a code expression is, none of that is going to make any sense.

Before I explain, I should first mention that code expressions are different from computation expressions are different. The former are indicated by <@ @> or <@@ @@> tags, the latter by a {..} block.

So what are code quotations then?

Let's take another look at the argument passed to the Yield method inside the expect {..} computation expression:

{{< highlight fsharp >}} expect { let! yourName = ["Bob";"Jane"] yield "Hi %s", [ <@ yourName @> ] } {{< / highlight >}}

We're passing in a list of variables, each wrapped inside <@ @> tags.

Remember in my parser combinator post, I mentioned that parsers turn tokens into an abstract representation of a data structure?

Let's think about that in the context of a programming language compiler. Roughly speaking, code is transformed from plain text into machine-level instructions via:

• a lexer, which transforms the text of the source code into its constituent tokens
• a parser, which transforms those tokens into an abstract representation of the program
• a compiler, which transforms that representation into some lower-level code (machine code, .NET IL, LLVM, etc).

At stage 2, many parsers produce a data structure to represent the program prior to compilation, known as an Abstract Syntax Tree:

In F#, you can actually compile code into one of these abstract representations. So rather than compiling "(1 + 1) * 5" into code that evaluates to 10 at runtime, the expression can be compiled into an object that represents the expression.

The <@ @> symbols in our expect {..} expression above are these markers, meaning "compile and return the following code as its abstract representation".

So when we write: {{< highlight fsharp >}} let! yourName = ["Bob";"Jane"] yield "Hi %s", [ <@ yourName @> ] {{< / highlight >}}

The second parameter to yield is not a list of string lists.

In fact, it is a list of expressions, each of which represents the binding of a variable to a string list.

Now why would I want to do this? What's the point of working with these abstract expressions?

The reason is very simple, and admittedly it's more for illustration's sake than practicality.

Recall from my previous post that we capture user-provided placeholder values ("Bob" or "Jane") in a global context under a key that we specify ("yourName").

Working with the code quotation gives us compile-time access to the name of a bound variable.

This lets us use the programmatic variable name ("yourName") as the key to store the eventual value:

{{< highlight fsharp >}} member x.Yield (formatString, expressions:Expr list) = ... for x in expressions do
match x with | PropertyGet(_, propOrValInfo, _) -> printfn "%s" propOrValInfo.Name ... yield "Hi %s", [ <@ yourName @> ] // prints "yourName" {{< / highlight >}}

This means:

• we don't need to manually track/update variable names
• we don't need to use reflection
• we get compile-time checks that dialog scripts don't accidentally overwrite context variables.

All good things, in my opinion.

Summary

Admittedly, this example is slightly contrived. The above is just a demonstration that hasn't (and won't) make it to production.

However, that's not because the computation expression/code quotation design was flawed. I do think it's a good illustration of what these concepts look like in the wild.

You might see from the repository that I experimented with passing these blocks to an embedded FSI session. This was fine on Android, but I encountered a lot of difficulty AOT-compiling FSI on iOS.

Though computation expressions and code quotations are definitely an advanced feature, but they open up designs and functionality that would otherwise be inaccessible. Fable is the best example of code quotation in the wild - a transpiler that generates Javascript from an F# AST.

Either way, I strongly encourage reading Scott Wlaschin's book for a more in-depth treatment.

In the meantime, feel free to leave any questions or comments you may have.