Phil Trelford's Array
POKE 36879, 255

Domain-Specific Languages

May 30, 2011 14:53 by phil

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

Comments

June 3. 2011 14:39

Loschaos

Great article. I was always curious how those old games were converted to play on PCs.  Cheers!

Loschaos

June 10. 2011 11:21

Wii U forums

Great in-depth article Phil. The first game reminds me of the great Scramble.

Wii U forums

August 16. 2011 08:21

Game tester

I miss these overhead games so much! I really enjoyed reading through and seeing how this is all done.

Game tester

August 30. 2012 00:25

trackback

Blog 101

Blog 101

Phil Trelford's Array

January 4. 2014 06:52

trackback

Small Basic Interpreter

Small Basic Interpreter

Phil Trelford's Array

Add comment


(Will show your Gravatar icon)

  Country flag

biuquote
  • Comment
  • Preview
Loading