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:
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:
The semantic model is implemented with F# discriminated unions. A custom operator (=>) specifies state transitions from events. Finally mutually recursive functions define the state machine. 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]
type code = string
type event = Event of code
type command = Command of code
type transition = Transition of event * (unit -> state)
and state = State of command seq * transition seq
let event = Event
let command = Command
let state actions transitions = State(actions,transitions)
let (=>) event state = Transition(event,state)
val doorClosed : event
Full name: Snippet.doorClosed
type: event
implements: System.IEquatable<event>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<event>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
Multiple items
val event : code -> event
Full name: Snippet.event
--------------------
type event = | Event of code
Full name: Snippet.event
type: event
implements: System.IEquatable<event>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<event>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val drawerOpened : event
Full name: Snippet.drawerOpened
type: event
implements: System.IEquatable<event>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<event>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val lightOn : event
Full name: Snippet.lightOn
type: event
implements: System.IEquatable<event>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<event>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val doorOpened : event
Full name: Snippet.doorOpened
type: event
implements: System.IEquatable<event>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<event>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val panelClosed : event
Full name: Snippet.panelClosed
type: event
implements: System.IEquatable<event>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<event>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val unlockPanel : command
Full name: Snippet.unlockPanel
type: command
implements: System.IEquatable<command>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<command>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
Multiple items
val command : code -> command
Full name: Snippet.command
--------------------
type command = | Command of code
Full name: Snippet.command
type: command
implements: System.IEquatable<command>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<command>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val lockPanel : command
Full name: Snippet.lockPanel
type: command
implements: System.IEquatable<command>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<command>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val lockDoor : command
Full name: Snippet.lockDoor
type: command
implements: System.IEquatable<command>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<command>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val unlockDoor : command
Full name: Snippet.unlockDoor
type: command
implements: System.IEquatable<command>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<command>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val idle : unit -> state
Full name: Snippet.idle
Multiple items
val state : seq<command> -> seq<transition> -> state
Full name: Snippet.state
--------------------
type state = | State of seq<command> * seq<transition>
Full name: Snippet.state
type: state
implements: System.IEquatable<state>
implements: System.Collections.IStructuralEquatable
val active : unit -> state
Full name: Snippet.active
val waitingForLight : unit -> state
Full name: Snippet.waitingForLight
val waitingForDrawer : unit -> state
Full name: Snippet.waitingForDrawer
val unlockedPanel : unit -> state
Full name: Snippet.unlockedPanel
A set of mutually recursive functions are used to parse the string tokens and build the State Machine as an F# record type.
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
Multiple items
val string : 'T -> string
Full name: Microsoft.FSharp.Core.Operators.string
--------------------
type string = System.String
Full name: Microsoft.FSharp.Core.string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
type code = string
Full name: Snippet.code
type: code
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
Code type abbreviation
type Machine =
{events: (name * code) list;
resetEvents: name list;
commands: (name * code) list;
states: (name * State) list;}
with
static member empty : Machine
end
Full name: Snippet.Machine
type: Machine
implements: System.IEquatable<Machine>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<Machine>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
State Machine record type
Machine.events: (name * code) list
type name = string
Full name: Snippet.name
type: name
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
Name type abbreviation
type 'T list = List<'T>
Full name: Microsoft.FSharp.Collections.list<_>
type: 'T list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'T>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'T>
implements: System.Collections.IEnumerable
Machine.resetEvents: name list
Machine.commands: (name * code) list
Machine.states: (name * State) list
type State =
{actions: name list;
transitions: (name * name) list;}
with
static member empty : State
end
Full name: Snippet.State
type: State
implements: System.IEquatable<State>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<State>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
static member Machine.empty : Machine
Full name: Snippet.Machine.empty
State.actions: name list
State.transitions: (name * name) list
static member State.empty : State
Full name: Snippet.State.empty
val whitespace : char []
Full name: Snippet.whitespace
type: char []
implements: System.ICloneable
implements: System.Collections.IList
implements: System.Collections.ICollection
implements: System.Collections.IStructuralComparable
implements: System.Collections.IStructuralEquatable
implements: System.Collections.Generic.IList<char>
implements: System.Collections.Generic.ICollection<char>
implements: seq<char>
implements: System.Collections.IEnumerable
inherits: System.Array
val parseError : string -> 'a
Full name: Snippet.parseError
val s : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
val invalidOp : string -> 'T
Full name: Microsoft.FSharp.Core.Operators.invalidOp
val parse : Machine -> string list -> Machine
Full name: Snippet.parse
Returns new machine with values parsed from specified text
val machine : Machine
type: Machine
implements: System.IEquatable<Machine>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<Machine>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val xs : string list
type: string list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string>
implements: System.Collections.IEnumerable
val events : Machine -> string list -> Machine
Full name: Snippet.events
Parses event declarations until end token is reached
val resetEvents : Machine -> string list -> Machine
Full name: Snippet.resetEvents
Parses reset event declarations until end token is reached
val commands : Machine -> string list -> Machine
Full name: Snippet.commands
Parses command declarations until end token is reached
Multiple items
val name : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
--------------------
type name = string
Full name: Snippet.name
type: name
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
Name type abbreviation
val state' : State
type: State
implements: System.IEquatable<State>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<State>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val parseState : State -> string list -> State * string list
Full name: Snippet.parseState
Parses state declaration until end token is reached
property State.empty: State
val machine' : Machine
type: Machine
implements: System.IEquatable<Machine>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<Machine>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val x : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
Multiple items
val code : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
--------------------
type code = string
Full name: Snippet.code
type: code
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
Code type abbreviation
val event : string * string
val command : string * string
val state : State
type: State
implements: System.IEquatable<State>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<State>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
val actions' : name list
type: name list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<name>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<name>
implements: System.Collections.IEnumerable
val actions : string list -> name list * string list
Full name: Snippet.actions
Parses action names in curly braces
val event : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
val action : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
val transition : string * string
val scope : (string list -> string list -> string * string list)
Returns text inside curly braces scope
val acc : string list
type: string list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string>
implements: System.Collections.IEnumerable
module String
from Microsoft.FSharp.Core
val concat : string -> seq<string> -> string
Full name: Microsoft.FSharp.Core.String.concat
Multiple overloads
System.String.Split(separator: char []) : string []
System.String.Split(separator: string [], options: System.StringSplitOptions) : string []
System.String.Split(separator: char [], options: System.StringSplitOptions) : string []
System.String.Split(separator: char [], count: int) : string []
System.String.Split(separator: string [], count: int, options: System.StringSplitOptions) : string []
System.String.Split(separator: char [], count: int, options: System.StringSplitOptions) : string []
module Array
from Microsoft.FSharp.Collections
val toList : 'T [] -> 'T list
Full name: Microsoft.FSharp.Collections.Array.toList
val text : string
Full name: Snippet.text
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
DSL specification
val machine : Machine
Full name: Snippet.machine
type: Machine
implements: System.IEquatable<Machine>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<Machine>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
Machine built from DSL text
namespace System
type StringSplitOptions =
| None = 0
| RemoveEmptyEntries = 1
Full name: System.StringSplitOptions
type: System.StringSplitOptions
inherits: System.Enum
inherits: System.ValueType
field System.StringSplitOptions.RemoveEmptyEntries = 1
property Machine.empty: Machine