A Data Structure–Based Language Implementation

Creating any DSL should start with defining what problem you need to solve; in this case, let’s imagine that you need to define a DSL library (sometimes called a combinators library) for drawing 2D images . This is something of an obvious choice. This example demonstrates how you can build up complicated structures out a number of simple primitives. An image on a computer screen is essentially just a collection of lines and polygons, although the image displayed might be extremely intricate. You begin by walking through the main points of the design process and conclude by looking at the full listings.

You start by designing a set of types that that will describe your picture; these types form the primitives of your image:

// represents the basic shapes that will make up the scene
type Shape =
    | Line of Position * Position
    | Polygon of List<Position>
    | CompositeShape of List<Shape>

This type is recursive, and the CompositeShape union case contains a list of shapes that it will use to form a tree-like structure. In compiler development, this tree-like structure is referred to as the abstract syntax tree (AST) . You’ll see another example of using an AST to represent a program at the end of the chapter.

So far, you have created your picture using three basic elements: lines, polygons, and shapes. The fact that your type is made up of just three simple elements is an important design decision; making your primitives simple makes implementing the engine that will render the image much simpler. The fact that your primitives are so simple means you don’t expect your user to spend time interacting with them directly; instead you’ll provide a set of higher-level wrapper functions that return values of type shape. These are your combinators. The CompositeShapecase in your union is an important example of this; it allows you to build up more complicated shapes out of simpler elements. You expose this through the compose function:

// allows us to compose a list of elements into a
// single shape
let compose shapes = CompositeShape shapes

You use this function to implement a number of higher-level functions. For example, the lines function , which takes a list of positions and returns a shape that is a path through those positions, takes advantage of the compose function to combine a number of individual lines into a single line:

// a line composed of two or more points
let lines posList =
    // grab first value in the list
    let initVal =
        match posList with
        | first :: _ -> first
        | _ -> failwith "must give more than one point"
    // creates a new link in the line
    let createList (prevVal, acc) item =
        let newVal = Line(prevVal, item)
        item, newVal :: acc
    // folds over the list accumlating all points into a
    // list of line shapes
    let _, lines = List.fold createList (initVal, []) posList
    // compose the list of lines into a single shape
    compose lines

Next, you use this lines function in the implementation of several high-level shapes, such as the square function:

let square filled (top, right) size =
    let pos1, pos2 = (top, right), (top, right + size)
    let pos3, pos4 = (top + size, right + size), (top + size, right)
    if filled then
        polygon [ pos1; pos2; pos3; pos4; pos1 ]
    else
        lines [ pos1; pos2; pos3; pos4; pos1 ]

The square function uses the lines function to plot the outline of a square with the calculated points. You can see the full module in Listing 11-4, although a more realistic implementation would probably contain more basic shapes for the users of the library to choose from.

To get this code working, start by creating a new F# Console Application . Add references to System.Drawing and System.Windows.Forms. Add new source files called Combinators.fs and Form.fs, and ensure that the three source files appear in the project in the order Combinators.fs, Form.fs, and then Program.fs. (In Visual Studio, you can reorder in Solution Explorer by right-clicking a source file and choosing “Move Up” or “Move Down.” In Xamarin Studio and MonoDevelop, it’s even easier: just drag source files into the required order in Solution Explorer.) Listing 11-4 goes in Combinators.fs, Listing 11-5 goes in Form.fs, and Listing 11-6 goes in Program.fs.

Listing 11-4. A Combinator Library for Creating Images

namespace Strangelights.GraphicDSL
open System.Drawing

// represents a point within the scene
type Position = int * int

// represents the basic shapes that will make up the scene
type Shape =
    | Line of Position * Position
    | Polygon of List<Position>
    | CompositeShape of List<Shape>

// allows us to give a color to a shape
type Element = Shape * Color

module Combinators =
    // allows us to compose a list of elements into a
    // single shape
    let compose shapes = CompositeShape shapes

    // a simple line made from two points
    let line pos1 pos2 = Line (pos1, pos2)

    // a line composed of two or more points
    let lines posList =
        // grab first value in the list
        let initVal =
            match posList with
            | first :: _ -> first
            | _ -> failwith "must give more than one point"
        // creates a new link in the line
        let createList (prevVal, acc) item =
            let newVal = Line(prevVal, item)
            item, newVal :: acc
        // folds over the list accumlating all points into a
        // list of line shapes
        let _, lines = List.fold createList (initVal, []) posList
        // compose the list of lines into a single shape
        compose lines

    // a polygon defined by a set of points
    let polygon posList = Polygon posList    

    // a triangle that can be either hollow or filled
    let triangle filled pos1 pos2 pos3 =
        if filled then
            polygon [ pos1; pos2; pos3; pos1 ]
        else
            lines [ pos1; pos2; pos3; pos1 ]

    // a square that can either be hollow or filled
    let square filled (top, right) size =
        let pos1, pos2 = (top, right), (top, right + size)
        let pos3, pos4 = (top + size, right + size), (top + size, right)
        if filled then
            polygon [ pos1; pos2; pos3; pos4; pos1 ]
        else
            lines [ pos1; pos2; pos3; pos4; pos1 ]

You now have the basic elements of your language; next you need to implement an interpreter to display the image. The interpreter described in this chapter is a WinForm . The advantage to this approach is that you might also implement an interpreter in WPF or some other graphics environment, which means that it is quite portable between GUI libraries and platforms. Implementing the interpreter is straightforward. You just need to implement each of your union cases. In the case of Line and Polygon, you draw these shapes using the GDI+ objects that WinForms are based on. Fortunately, GDI+ makes it straightforward to draw a line or polygon. The third CompositeShapecase is also straightforward; you simply call your drawing function recursively. You can see the full source code for this in Listing 11-5.

Listing 11-5. An Interpreter to Render Images from Your Combinator Library

namespace Strangelights.GraphicDSL

open System.Drawing
open System.Windows.Forms

// a form that can be used to display the scene
type EvalForm(items: List<Element>) as x =
    inherit Form()
    // handle the paint event to draw the scene
    do x.Paint.Add(fun ea ->
        let rec drawShape (shape, (color: Color)) =
            match shape with
            | Line ((x1, y1), (x2, y2)) ->
                // draw a line
                let pen = new Pen(color)
                ea.Graphics.DrawLine(pen, x1, y1, x2, y2)
            | Polygon points ->
                // draw a polygon
                let points =
                    points
                    |> List.map (fun (x,y) -> new Point(x, y))
                    |> Array.ofList
                let brush = new SolidBrush(color)
                ea.Graphics.FillPolygon(brush, points)
            | CompositeShape shapes ->
                // recursively draw the other contained elements
                List.iter (fun shape -> drawShape(shape, color)) shapes
        // draw all the items we have been passed
        items |> List.iter drawShape)

Putting together a simple image composed of two squares and a triangle now becomes straightforward. You simply call the appropriate functions from your combinator library and then combine them with a color to make a full description of the scene. Listing 11-6 shows how to do this; you can see the resulting image in Figure 11-1.

Figure 11-1. A scene rendered by your combinator library

Listing 11-6. Calling Your Combinator Library

open System.Drawing
open System.Windows.Forms
open Strangelights.GraphicDSL

// two test squares
let square1 = Combinators.square true (100, 50) 50
let square2 = Combinators.square false (50, 100) 50

// a test triangle
let triangle1 =
    Combinators.triangle false
        (150, 200) (150, 150) (250, 200)

// compose the basic elements into a picture
let scence = Combinators.compose [square1; square2; triangle1]

// create the display form
let form = new EvalForm([scence, Color.Red])

[<EntryPoint>]
let main argv =
    // show the form
    Application.Run form
    0

The simple example given in Listing 11-6 probably doesn’t represent how you would create images using the combinator library. You’ll take look at a more realistic scenario in Listing 11-7. The best approach to using the combinator library would probably be to carry on programming in the style you wrote the original combinator library in; that is, you would build up simple elements that you can reuse in your image. Next, you’ll look at how to create a scene composed of seven stars. The obvious place to start is with the creation of the star; you can see how to create the star function defined in Listing 11-7. This function creates triangles that are mirror images and combines them with a slight offset to form a six-sided star. This example might give you some idea of how to build up more complex shapes out of simpler ones. Once you have the definition of your star, you simply need a list of positions that tell where to print the stars. You can see this list of points in Listing 11-7. Once you have these two elements, you can combine them using the List.map function and the compose function to create your scene. Next, you can display your scene the same way you did in the previous listing.

Listing 11-7. Creating a More Complex Image Using Your Combinator Library

open System.Drawing
open System.Windows.Forms
open Strangelights.GraphicDSL

// define a function that can draw a 6 sided star
let star (x, y) size =
    let offset = size / 2
    // calculate the first triangle
    let t1 =
        Combinators.triangle false
            (x, y - size - offset)
            (x - size, y + size - offset)
            (x + size, y + size - offset)
    // calculate another inverted triangle
    let t2 =
        Combinators.triangle false
            (x, y + size + offset)
            (x + size, y - size + offset)
            (x - size, y - size + offset)
    // compose the triangles
    Combinators.compose [ t1; t2 ]    

// the points where stars should be plotted
let points = [ (10, 20); (200, 10);
               (30, 160); (100, 150); (190, 150);
               (20, 300); (200, 300);  ]

// compose the stars into a single scene
let scence =
    Combinators.compose
        (List.map (fun pos -> star pos 5) points)

// show the scene in red on the EvalForm
let form = new EvalForm([scence, Color.Red],
                        Width = 260, Height = 350)

[<EntryPoint>]
let main argv =
    // show the form
    Application.Run form
    0

Replace the contents of Program.fs with Listing 11-7 and run your project. Figure 11-2 shows the resulting image.

Figure 11-2. Another scene rendered by your combinator library

You’ve now seen two approaches for creating combinator libraries (libraries that create little languages though data structures). At this point, you’re probably beginning to see how you can break a problem down into an abstract description of the problem based on a small set of primitives, possibly with aid of other libraries that you build on these primitives.

The Abstract Syntax Tree

An AST is a representation of the construct that makes up the program; it’s intended to be easy for the programmer to use. One reason that F# is good for this kind of development is its union type. This type is great for representing languages because you can use it to represent items that are related yet do not share the same structure. The following example shows how to use an AST:

type Ast =
  | Ident of string
  | Val of System.Double
  | Multi of Ast * Ast
  | Div of Ast * Ast
  | Plus of Ast * Ast
  | Minus of Ast * Ast

The tree consists of only one type because it is quite simple. A complicated tree would contain many more types , but it would still follow this basic pattern. Here you can see that the tree, which is of the type Ast, will consist of either identifiers (the Ident type); the names of the identifiers represented by a string; or values (the Val type), which will be values represented by a System.Double. The type also includes four more types (Multi, Div, Plus, and Minus) that represent the arithmetic operations. They use recursion, allowing them to be composed of other expressions.

Interpreting the AST

Once you create your AST, you have two choices: you can either interpret it or compile it. Interpreting it simply means walking the tree and performing actions as you go. Compiling it means changing it into some other form that is easier, or more typically, faster, for the machine to execute. This section will examine how to interpret the results ; the next section will look at the options for compiling them; and finally, you will look at when you should use interpretation and when you should use compilation.

The following example shows a short interpreter for your program. The main work of interpreting the AST is done by the function interpret, which walks the tree, performing the necessary actions as it goes. The logic is quite simple. If you find a literal value or an identifier, you return the appropriate value :

| Ident (s) -> variableDict.[s]
| Val (v) -> v

If you find an operand, you recursively evaluate the expressions it contains to obtain its values and then perform the operation:

| Multi (e1, e2) -> (interpretInner e1) * (interpretInner e2)

You can see the complete interpreter in Listing 11-9.

Listing 11-9. Interpreting an AST Generated from Command-Line Input

open System

type Ast =
   | Ident of string
   | Val of System.Double
   | Multi of Ast * Ast
   | Div of Ast * Ast
   | Plus of Ast * Ast
   | Minus of Ast * Ast

// requesting a value for variable from the user
let getVariableValues e =
    let rec getVariableValuesInner input (variables : Map<string, float>) =
        match input with
        | Ident (s) ->
            match variables.TryFind(s) with
            | Some _ -> variables
            | None ->
                printfn "%s: " s
                let v = float(Console.ReadLine())
                variables.Add(s,v)
        | Multi (e1, e2) ->
            variables
            |> getVariableValuesInner e1
            |> getVariableValuesInner e2
        | Div (e1, e2) ->
            variables
            |> getVariableValuesInner e1
            |> getVariableValuesInner e2
        | Plus (e1, e2) ->
            variables
            |> getVariableValuesInner e1
            |> getVariableValuesInner e2
        | Minus (e1, e2) ->
            variables
            |> getVariableValuesInner e1
            |> getVariableValuesInner e2
        | _ -> variables
    getVariableValuesInner e (Map.empty)

// function to handle the interpretation
let interpret input (variableDict : Map<string,float>) =
    let rec interpretInner input =
        match input with
        | Ident (s) -> variableDict.[s]
        | Val (v) -> v
        | Multi (e1, e2) -> (interpretInner e1) * (interpretInner e2)
        | Div (e1, e2) -> (interpretInner e1) / (interpretInner e2)
        | Plus (e1, e2) -> (interpretInner e1) + (interpretInner e2)
        | Minus (e1, e2) -> (interpretInner e1) - (interpretInner e2)
    interpretInner input

// the expression to be interpreted
let e = Multi(Val 2., Plus(Val 2., Ident "a"))

// collect the arguments from the user
let args = getVariableValues e

// interpret the expression
let v = interpret e args

// print the results
printf "result: %f" v

Executing this code in F# Interactive produces the following results:

[a]: 12
result: 28.000000

Compiling the AST

To many developers, compilation means generating native code , so it has a reputation for being difficult. But it doesn’t have to mean generating native code. For a DSL, you typically generate another, more general-purpose programming language. The .NET Framework provides several features for compiling an AST into a program.

Your choice of technology depends on several factors. For example, if you want to target your language at developers, it might be enough to generate a text file containing F#, some other language, or a compiled assembly that can then used within an application. However, if you want to target end users, you will almost certainly have to compile and then execute it on the fly. Table 11-1 summarizes the various options available.

You use the System.Reflection.Emit.DynamicMethod class, not because you need the flexibility of IL, but because IL includes built-in instructions for floating-point arithmetic, which makes it well-suited for implementing a little language. The DynamicMethodclass also provides a fast and easy way to let you call into the resulting program.

The method createDynamicMethod compiles the AST by walking the AST and generating code. It begins by creating an instance of the DynamicMethod class to hold the IL you define to represent the method:

let temp = new DynamicMethod("", (type float), paramsTypes, meth.Module)

Next, createDynamicMethod starts walking the tree. When you encounter an identifier, you emit some code to load an argument of your dynamic method:

| Ident name ->
    il.Emit(OpCodes.Ldarg, paramNames.IndexOf(name))

When you encounter a literal, you emit the IL code to load the literal value:

| Val x -> il.Emit(OpCodes.Ldc_R8, x)

When you encounter an operation, you must recursively evaluate both expressions and then emit the instruction that represents the required operation:

| Multi (e1 , e2) ->
    generateIlInner e1
    generateIlInner e2
    il.Emit(OpCodes.Mul)

Note how the operation is emitted last, after both expressions have been recursively evaluated. You do it this way because IL is stack-based, so data from the other operations must be pushed onto the stack before you evaluate the operator.

You can see the complete compiler in Listing 11-10.

Listing 11-10. Compiling an AST Generated from Command Line Input

open System
open System.Reflection
open System.Reflection.Emit

type Ast =
   | Ident of string
   | Val of System.Double
   | Multi of Ast * Ast
   | Div of Ast * Ast
   | Plus of Ast * Ast
   | Minus of Ast * Ast

// get a list of all the parameter names
let rec getParamList e =
    let rec getParamListInner e names =
        match e with
        | Ident name ->
            if not (List.exists (fun s -> s = name) names) then
                name :: names
            else
                names
        | Multi (e1 , e2) ->
            names
            |> getParamListInner e1
            |> getParamListInner e2
        | Div (e1 , e2) ->
            names
            |> getParamListInner e1
            |> getParamListInner e2
        | Plus (e1 , e2) ->
            names
            |> getParamListInner e1
            |> getParamListInner e2
        | Minus (e1 , e2) ->
            names
            |> getParamListInner e1
            |> getParamListInner e2
        | _ -> names
    getParamListInner e []

// create the dynamic method
let createDynamicMethod e (paramNames: string list) =
    let generateIl e (il : ILGenerator) =
        let rec generateIlInner e  =
            match e with
            | Ident name ->
                let index = List.findIndex (fun s -> s = name) paramNames
                il.Emit(OpCodes.Ldarg, index)
            | Val x -> il.Emit(OpCodes.Ldc_R8, x)
            | Multi (e1 , e2) ->
                generateIlInner e1
                generateIlInner e2
                il.Emit(OpCodes.Mul)
            | Div (e1 , e2) ->
                generateIlInner e1
                generateIlInner e2
                il.Emit(OpCodes.Div)
            | Plus (e1 , e2) ->
                generateIlInner e1
                generateIlInner e2
                il.Emit(OpCodes.Add)
            | Minus (e1 , e2) ->
                generateIlInner e1
                generateIlInner e2
                il.Emit(OpCodes.Sub)
        generateIlInner e
        il.Emit(OpCodes.Ret)

    let paramsTypes = Array.create paramNames.Length (typeof<float>)
    let meth = MethodInfo.GetCurrentMethod()
    let temp = new DynamicMethod("", (typeof<float>), paramsTypes, meth.Module)
    let il = temp.GetILGenerator()
    generateIl e il
    temp

// function to read the arguments from the command line
let collectArgs (paramNames : string list) =
    paramNames
    |> Seq.map
        (fun n ->
            printf "%s: " n
            box (float(Console.ReadLine())))
    |> Array.ofSeq

// the expression to be interpreted
let e = Multi(Val 2., Plus(Val 2., Ident "a"))

// get a list of all the parameters from the expression
let paramNames = getParamList e

// compile the tree to a dynamic method
let dm = createDynamicMethod e paramNames

// print collect arguments from the user
let args = collectArgs paramNames

// execute and print out the final result
printfn "result: %O" (dm.Invoke(null, args))

Running the code in Listing 11-10 produces the following results:

a: 14
result: 32

Compilation vs. Interpretation

So when should you use compilation and when should you use interpretation? The final result is basically the same, so the answer generally comes down to the raw speed of the final generated code, though memory usage and start-up times can also play a role in the decision. If you need your code to execute more quickly, then compilation will generally give you better results.

The test harness in Listing 11-11 enables you to execute the interpret function results of createDynamicMethod repeatedly and time how long this takes. It also tests an important variation on dynamic methods; that is where you also generate a new .NET delegate value to act as the handle by which you invoke the generated code. As you can see, it turns out that this is by far the fastest technique. Remember, you’re timing how long it takes to evaluate the AST either directly or in a compiled form; you’re not measuring the parse time or compilation time.

Listing 11-11. A Test Harness for Comparing Performance

open System
open System.Diagnostics
open Strangelights.Expression

// expression to process
let e = Multi(Val 2., Plus(Val 2., Val 2.))

// collect the inputs
printf "Interpret/Compile/Compile Through Delegate [i/c/cd]: "
let interpertFlag = Console.ReadLine()
printf "reps: "
let reps = int(Console.ReadLine())

type Df0 = delegate of unit -> float
type Df1 = delegate of float -> float
type Df2 = delegate of float * float -> float
type Df3 = delegate of float * float * float -> float
type Df4 = delegate of float * float * float * float -> float

// run the tests
match interpertFlag with
| "i" ->
    let args = Interpret.getVariableValues e
    let clock = new Stopwatch()
    clock.Start()
    for i = 1 to reps do
        Interpret.interpret e args |> ignore
    clock.Stop()
    printf "%i" clock.ElapsedTicks
| "c" ->
    let paramNames = Compile.getParamList e
    let dm = Compile.createDynamicMethod e paramNames
    let args = Compile.collectArgs paramNames
    let clock = new Stopwatch()
    clock.Start()
    for i = 1 to reps do
        dm.Invoke(null, args) |> ignore
    clock.Stop()
    printf "%i" clock.ElapsedTicks
| "cd" ->
    let paramNames = Compile.getParamList e
    let dm = Compile.createDynamicMethod e paramNames
    let args = Compile.collectArgs paramNames
    let args = args |> Array.map (fun f -> f :?> float)
    let d =
        match args.Length with
        | 0 -> dm.CreateDelegate(typeof<Df0>)
        | 1 -> dm.CreateDelegate(typeof<Df1>)
        | 2 -> dm.CreateDelegate(typeof<Df2>)
        | 3 -> dm.CreateDelegate(typeof<Df3>)
        | 4 -> dm.CreateDelegate(typeof<Df4>)
        | _ -> failwith "too many parameters"
    let clock = new Stopwatch()
    clock.Start()
    for i = 1 to reps do
        match d with
        | :? Df0 as d -> d.Invoke() |> ignore
        | :? Df1 as d -> d.Invoke(args.[0]) |> ignore
        | :? Df2 as d -> d.Invoke(args.[0], args.[1]) |> ignore
        | :? Df3 as d -> d.Invoke(args.[0], args.[1], args.[2]) |> ignore
        | :? Df4 as d -> d.Invoke(args.[0], args.[1], args.[2], args.[4]) |> ignore
        | _ -> failwith "too many parameters"
    clock.Stop()
    printf "%i" clock.ElapsedTicks
| _ -> failwith "not an option"

Table 11-2 summarizes the results of executing this program against this expression: Multi(Val 2., Plus(Val 2., Val 2.)).

Table 11-2 and Figure 11-3 indicate that Compiled and Compiled via delegate are much faster over a small number of repetitions. But notice that over 1, 10, and 100 repetitions, the amount of time required grows negligibly. This is because over these small numbers of repetitions, the time taken for each repetition is insignificant. It is only the time that the JIT compiler takes to compile the IL code into native code that is significant. This is why the Compiled and Compiled via delegatetimes are so close. They both have a similar amount of code to JIT compile. The Interpreted time takes longer because you must JIT compile more code, specifically the interpreter. But JIT is a one-off cost because you need to JIT each method only once; therefore, as the number of repetitions goes up, this one-off cost is paid for, and you begin to see a truer picture of the relative performance cost.

Figure 11-3. The evaluation time in machine ticks of the expression 1 + 1 against the number of evaluations of the express

You can see clearly from Figure 11-3 that, as the number of repetitions goes up, the cost of Compiled goes up steeply. This is because accessing the compiled DynamicMethodthrough its Invoke method is expensive, and you incur this cost on every repetition. This means that the time taken for a Compiled method increases at the same rate as the number of repetitions. However, the problem lies not with compilation, but with how you invoke the compiled code. It turns out that calling a DynamicMethod through a delegate rather than the Invoke member on the dynamic delegate allows you to pay only once for the cost of binding to the method, so executing a DynamicMethod this way is much more efficient if you intend to evaluate the expression multiple times. Based on these results, compilation with invocation via a delegate provides the best option in terms of speed.

This analysis shows the importance of measurement : don’t assume that compilation has given you the expected performance gains until you actually see the benefits on realistic data sets and have used all the available techniques to ensure no unnecessary overhead is lurking in your code. However, many other factors can affect your performance in the real world. For example, if your expressions change often, your interpreter will need to be JIT compiled only once, but each compiled expression will need to be JIT compiled, which means you’ll need to run your compiled code many times if you want to see any performance gains. Given that interpreted code is usually easier to implement, and that compiled code provides significant performance gains only in certain situations, interpreted code is often your best choice.

When dealing with situations that require code to perform as quickly as possible, it’s generally best to try a few different approaches and then profile your application to see which approach gives the best results.