The first time I encountered an external Domain-specific language (DSL) was in the summer of 1988. It was over the school holidays while working on the conversion of 2 video games:

• Stryx a 2d scrolling platform game
• Blood Money a 2d scrolling shoot ‘em up

Both conversions were from the Commodore Amiga to PC, and involved porting 68000 assembly language to 8086.

Blood Money used an external DSL to specify the state machines of the aliens of the game. This made the conversion significantly easier as only the interpreter need be converted rather than all the game logic. The language employed a yield keyword to signify the end of state processing for a particular frame. Interestingly in 2005 C# 2.0 introduced a yield keyword to signal the end of an iteration in an iterator block.

The use of both Internal and External DSLs has always been popular in video games. Using low-level languages like assembler, C and C++ was time consuming. Internal DSLs could be created simply by using a combination of Macros and well-named functions, and made the code easier to read. External DSLs had 2 additional benefits:

• the game logic could be changed without recompiling the program
• byte code generated from a DSL took less space than machine code instructions

Back in 1994 on the development of the Addams Family Values action RPG title for the SNES and MegaDrive, we used 2 DSLs. The first was a tile based graphical DSL (a bit like Kodu) that was drawn onto the game maps and specified for example the key needed to open a specific door.  The second, another state machine language for the monsters.

The 80-20 rule or Pareto Principle stipulates that for many events, roughly 80% of the effects come from 20% of the causes. In a video game typically most of the CPU is spent rendering the scene. The CPU cost of processing basic game logic rarely warrants the cost of development in a low-level language. In the 1980s, and the 8-bit era, I used BASIC to prototype game logic, which allowed edit and continue debugging. Once the game play was set I could either compile or hand code to machine code as required. Nowadays games often employ scripting languages like Lua for their greater productivity over C and C++. The light syntax of Lua feels quite similar to that of F#, a multi-paradigm language used recently in the development of the XBox Live title Path of Go.

Miss Grant’s Controller

In 2010 Martin Fowler and Rebecca Parsons released a book dedicated to Domain-Specific Languages with examples in Java and Ruby. One of the examples running through the book is Miss Grant’s controller, a simple state machine. Below I’ve created internal and external DSL implementations which I hope show the ease of use of the F# language. You can compare with the implementations in Java and Ruby in the following article:

• Domain-Specific Languages: An Introductory Example

---

F# Internal DSL Snippet

 1: // Miss Grant's Controller as an Internal DSL in F#
 2: // See Domain-Specific Languages: An Introductory Example by Martin Fowler
 3: // http://www.informit.com/articles/article.aspx?p=1592379&seqNum=3
 4: 
 5: Semantic model type definitions
 6: 
 7: Internal DSL helper functions
 8: 
 9: let doorClosed =    event "D1CL"
10: let drawerOpened =  event "D2OP"
11: let lightOn =       event "L1ON"
12: let doorOpened =    event "D1OP"
13: let panelClosed =   event "PNCL"
14: 
15: let unlockPanel =   command "PNUL"
16: let lockPanel =     command "PNLK"
17: let lockDoor =      command "D1LK"
18: let unlockDoor =    command "D1UL"
19: 
20: let rec idle () = 
21:     state
22:         [unlockDoor; lockPanel]
23:         [doorClosed => active]
24: and active () =
25:     state 
26:         [] 
27:         [drawerOpened => waitingForLight
28:          lightOn => waitingForDrawer]       
29: and waitingForLight () =
30:     state [] [lightOn => unlockedPanel]
31: and waitingForDrawer () =
32:     state [] [drawerOpened => unlockedPanel]
33: and unlockedPanel () =
34:     state
35:         [unlockPanel; lockDoor]
36:         [panelClosed => idle]

---

F# External DSL Snippet

  1: // Miss Grant's Controller External DSL with F# parser
  2: // See Domain-Specific Languages: An Introductory Example by Martin Fowler
  3: // http://www.informit.com/articles/article.aspx?p=1592379&seqNum=3
  4: 
  5: /// Name type abbreviation
  6: type name = string
  7: /// Code type abbreviation
  8: type code = string
  9: 
 10: /// State Machine record type
 11: type Machine = { 
 12:     events : (name * code) list
 13:     resetEvents: name list
 14:     commands : (name * code) list
 15:     states : (name * State) list
 16:     } with 
 17:     static member empty =
 18:         { events = []; resetEvents = []; commands = []; states = [] }
 19: and State = { actions: name list; transitions: (name * name) list }
 20:     with static member empty = { actions=[]; transitions=[] }
 21:      
 22: let whitespace = " \t\r\n".ToCharArray()
 23: let parseError s = invalidOp s
 24: 
 25: /// Returns new machine with values parsed from specified text
 26: let rec parse (machine:Machine) = function
 27:     | "events"::xs -> events machine xs
 28:     | "resetEvents"::xs -> resetEvents machine xs
 29:     | "commands"::xs -> commands machine xs
 30:     | "state"::name::xs -> 
 31:         let state',xs = parseState (State.empty) xs
 32:         let machine' = { machine with states = (name,state')::machine.states }
 33:         parse machine' xs
 34:     | [] -> machine
 35:     | x::_ -> "unknown token " + x |> parseError
 36: /// Parses event declarations until end token is reached
 37: and events machine = function
 38:     | "end"::xs -> parse machine xs
 39:     | name::code::xs -> 
 40:         let event = (name,code)
 41:         let machine' = { machine with events = event::machine.events }
 42:         events machine' xs
 43:     | _ -> parseError "events"
 44: /// Parses reset event declarations until end token is reached
 45: and resetEvents machine = function
 46:     | "end"::xs -> parse machine xs
 47:     | name::xs -> 
 48:         let machine' = { machine with resetEvents = name::machine.resetEvents }
 49:         resetEvents machine' xs
 50:     | _ -> parseError "resetEvents"
 51: /// Parses command declarations until end token is reached
 52: and commands machine = function
 53:     | "end"::xs -> parse machine xs
 54:     | name::code::xs ->
 55:         let command = (name,code)
 56:         let machine' = { machine with commands = command::machine.commands }
 57:         commands machine' xs
 58:     | _ -> parseError "commands"
 59: /// Parses state declaration until end token is reached
 60: and parseState state = function
 61:     | "end"::xs -> state,xs
 62:     | "actions"::xs ->
 63:         let actions', xs = actions xs  
 64:         let state' = { state with actions = actions'@state.actions }
 65:         parseState state' xs
 66:     | event::"=>"::action::xs ->        
 67:         let transition = (event,action)
 68:         let state' = { state with transitions = transition::state.transitions }
 69:         parseState state xs 
 70:     | _ -> parseError "state"
 71: /// Parses action names in curly braces
 72: and actions (xs:string list) = 
 73:     /// Returns text inside curly braces scope
 74:     let rec scope acc = function
 75:         | (x:string)::xs when x.Contains("}") -> 
 76:             (String.concat "" acc).Trim([|'{';'}'|]), xs
 77:         | x::xs -> scope (x::acc) xs
 78:         | [] -> invalidOp "scope"
 79:     let s, xs = scope [] xs
 80:     s.Split(whitespace) |> Array.toList, xs
 81: 
 82: /// DSL specification
 83: let text = "
 84: events
 85:  doorClosed D1CL
 86:  drawerOpened D2OP
 87:  lightOn L1ON
 88:  doorOpened D1OP
 89:  panelClosed PNCL end
 90:  
 91: resetEvents
 92:  doorOpened 
 93: end
 94: 
 95: commands
 96:  unlockPanel PNUL
 97:  lockPanel PNLK
 98:  lockDoor D1LK
 99:  unlockDoor D1UL
100: end 	
101: 
102: state idle	
103:  actions {unlockDoor lockPanel}
104:  doorClosed => active 
105: end 
106: 
107: state active
108:  drawerOpened => waitingForLight
109:  lightOn => waitingForDrawer 
110: end 
111: 
112: state waitingForLight
113:  lightOn => unlockedPanel 
114: end 
115: 
116: state waitingForDrawer
117:  drawerOpened => unlockedPanel 
118: end 
119: 
120: state unlockedPanel
121:  actions {unlockPanel lockDoor}
122:  panelClosed => idle 
123: end"
124: 
125: /// Machine built from DSL text
126: let machine =
127:     text.Split(whitespace, System.StringSplitOptions.RemoveEmptyEntries)
128:     |> Array.toList
129:     |> parse Machine.empty

Since I first posted an F# solution to Left-Truncatable Primes, C# and Haskell have entered the frame, and although this is not a good problem for a serious comparison of languages, I think it is still interesting.

So lets start at the beginning, Dominic Penfold initially posed the problem and gave an efficient algorithm implemented in C++ (39 lines):

bool IsPrime(int num)
{
    int sqrt = 1 + sqrtf(num);
    for (int i=2; i<sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
 
int NthLeftTruncatablePrime(int target)
{
    std::vector<int> PrimeRoots;
    PrimeRoots.push_back(2);
    PrimeRoots.push_back(3);
    PrimeRoots.push_back(5);
    PrimeRoots.push_back(7);
    int start = 0;
    int tens = 10;    
    while(true)
    {
        int end = PrimeRoots.size();
        for (int i=1; i<10; i++)
        {
            for (int pos = start; pos< end; pos++)
            {
                int newprime = tens * i + PrimeRoots[pos];
                if (IsPrime(newprime))
                {
                    PrimeRoots.push_back(newprime);
                    if (PrimeRoots.size()==target)                                      
                        return newprime;                    
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

Performance was considerably faster when 32-bit integers were switched for 64-bit integers.

The C++ code is very easily converted into C# (35 lines):

static bool IsPrime(int num)
{
    int sqrt = 1 + (int ) System.Math.Sqrt(num);
    blue">for (int i = 2; i < sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

static int NthLeftTruncatedPrime(int target)
{
    var primeRoots = new List<int>() { 2, 3, 5, 7};               
    int start = 0;
    int tens = 10;
    while (true)
    {
        int end = primeRoots.Count;
        for (int i = 1; i < 10; i++)
        {
            for (int pos = start; pos < end; pos++)
            {
                int newprime = tens * i + primeRoots[pos];
                if (IsPrime(newprime))
                {
                    primeRoots.Add(newprime);
                    if (primeRoots.Count == target)
                        return newprime;
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

Conversion to F# is only slightly trickier as there is no equivalent return statement, but similar behavior can be accomplished using yield (30 lines):

let IsPrime n =
    if n = 1 then false
    else    
        let max = n |> float |> sqrt |> int
        let rec Test = function
            | x when x > max -> true
            | x -> if (n % x) = 0 then false else Test (x+1)
        Test 2

let NthLeftTruncatablePrime n =
    let oneDigitPrimes = [2;3;5;7]          
    seq {            
        let primes = ref oneDigitPrimes        
        for tens = 1 to 8 do
            let acc = ref []
            for i=1 to 9 do 
                let newPrime = i * pown 10 tens                
                let primes' = ref !primes
                while (!primes').Length > 0 do                            
                    let x = newPrime+(!primes').Head
                    if IsPrime x then 
                        acc := x :: !acc
                        yield x
                    primes' := (!primes').Tail                    
                done                                     
            done         
            primes := !acc |> List.rev    
        done            
    }
    |> Seq.append oneDigitPrimes
    |> Seq.nth (n-1)

The extra overhead of generating a sequence can be avoided using instead recursion (25 lines including IsPrime function):

let NthLeftTruncatablePrime index =
    let rec Find digit factor primes primes' count acc =
        match digit, primes' with
        | 10, _ -> 
            let primes = List.rev acc
            Find 1 (10*factor) primes primes count []
        | _, [] ->
            Find (digit+1) factor primes primes count acc
        | _, prime::tail -> 
            let k = (digit * factor) + prime
            let count, acc =
                if IsPrime k then count+1, k::acc else count, acc 
            if count = index then k
            else Find digit factor primes tail count acc
    let primes = [2;3;5;7]
    if index <= 4 then List.nth primes (index-1)
    else Find 1 10 primes primes 4 []

Later Matt Curran (coincidentally another ex-games developer) got in on the act with a Haskell version (17 lines including a comment – although the lines are a little dense):

isPrime :: Int -> Bool
isPrime 1 = False
isPrime x = null $ take 1 [n | n <- [2..upperBound x], 0 == mod x n]
    where
        upperBound = floor . sqrt . fromIntegral

-- list of all left truncatable primes
ltps :: [Int]
ltps = ps 1 [0]
    where
        ps _ []      = []
        ps m prevMag = thisMag ++ (ps (m*10) thisMag)
            where
                thisMag = primes [x*m | x <- [1..9]] prevMag
                    where
                        primes [] _ = []
                        primes (m:mgs) bases = 
                            (filter isPrime [m+x | x <- bases]) ++ (primes mgs bases)

Results Breakdown by language

Note: the time is to generate the 1000th prime, and the same computer was used for all tests, as was release mode. Haskell time coming soon.

LeftTruncatablePrime.cpp (1.45 kb)

LeftTruncatablePrime.cs (1.58 kb)

LeftTruncatablePrime_seq.fs (1.53 kb)

LeftTruncatablePrime_rec.fs (1.36 kb)