The SPiM Language

©Andrew Phillips 2007

Version 0.05

Table of Contents

1  Introduction

This document presents the SPiM Language Definition. The Language is defined in BNF notation, where optional elements are enclosed in braces as { Optional}.

2  Programs

Syntax
A Program consists of one or more Declarations, together with optional top-level Directives for sampling and plotting simulation results.
Program ::= { Directive1... DirectiveM}   Directives,M³1
    Declaration1... DeclarationN   Declarations,N³1
 
Directive ::= directive sample Float { Integer}   Sample Directive
  | directive graph    Graph Directive
  | directive plot Point1... PointN   Plot Directive
 
Point ::= ! Channel {as String}   Output Point
  | ? Channel {as String}   Input Point
  | Name ( Value1, ..., ValueN)  {as String}   Process Point,N³0
 
Sample Directive

directive sample Float { Integer}
Specifies the maximum duration of a simulation, together with the maximum number of plots.

The maximum duration of the simulation is specified by the given Float. The units of simulation time are not given explicitly, but are determined by the reaction rates in the program. For example, if the rates are given in seconds-1 then the simulation time is assumed to be in seconds. The simulation is halted when the simulation time exceeds the maximum duration.

The maximum number of plots is specified by the given Integer. This is used to compute the minimum interval of time between plots. For example, if the duration is 10.0 and the maximum number of plots is 1000 then there will be a minimum time of 0.01 between plots. This has the effect of sampling plots at regular time intervals. If no maximum number of plots is given then all of the plots are used.

If no sample directive is given then the simulation continues until the program terminates.

Graph Directive

directive graph 
Instructs the simulator to output a graphical representation of the program in .dot format. The resulting file can be viewed using the Graphviz DOT layout engine1, which can also be used to export a directed graph in .ps or .png format. The graphical representation corresponds to the program code, where top-level value, type and channel declarations are omitted. The graph directive is disabled for the GUI version of the simulator, which uses a menu command to export a graphical representation of the program that was last simulated.

Plot Directive

directive plot Point1... PointN
Specifies one or more points to be recorded at each time step. If no plot directive is given then the number of possible inputs and outputs on all channels is recorded at each time step.

The simulation results for a given SPiM program are stored in a corresponding .csv file as a sequence of comma-separated values. The first line of the file contains the headers for the remaining lines. The first header denotes the simulation time, and each subsequent header denotes the number of possible inputs ?x or outputs !x on a given channel x, or the number of running processes P(n) with parameters n. Each subsequent line contains the current simulation time, followed by the number of inputs, outputs or processes. A new line is written to the result file for each simulation step.

The result file can be viewed using a suitable spreadsheet in order to plot a graph of the results. For example, Microsoft Excel can be used to open the result file in order to plot a scatter diagram of selected inputs, outputs and processes over time. The result file can also be imported into Microsoft Excel as external data, which can be refreshed whenever the result file is updated during a simulation.

Points
A point can be an output or input on a Channel or the Name of a process, together with an optional String header.
! Channel {as String}
Records the number of possible outputs on the given Channel at each time step, using the given String header. If no string header is specified then the header "! Channel" is used by default. If more than one channel is declared with the same name then the sum of all the outputs on these channels is recorded.
? Channel {as String}
Records the number of possible inputs on the given Channel at each time step, using the given String header. If no string header is specified then the header "? Channel" is used by default. If more than one channel is declared with the same name then the sum of all the inputs on these channels is recorded.
Name ( Value1, ..., ValueN)  {as String}
Records the number of processes with the given Name and parameters ( Value1, ..., ValueN) , using the given String header. If no string header is specified then the header "Name( Value1, ..., ValueN) " is used by default. Only processes of a certain form can be recorded, i.e. those that are defined as a choice of actions preceded by zero or more channel, type or value declarations. If no parameters are specified then the sum of all the processes with the given Name is recorded.

Declarations

Declaration1... DeclarationN
Specifies one or more top-level declarations to be executed.

3  Declarations

Syntax
A Declaration can be a Channel, Type, Value or Process declaration, or one or more mutually recursive Definitions.
Declaration ::= new Name{@ Value}: Type   Channel Declaration
  | type Name =   Type   Type Declaration
  | val Pattern =   Value   Value Declaration
  | run Process   Process Declaration
  | let Definition1 and ... and DefinitionN   Process Definitions,N³1
 
Definition ::= Name ( Pattern1, ..., PatternN)  =   Process   Process Definition,N³0
 
Channel Declaration

new Name{@ Value}: Type
Creates a new channel with rate Value and with the given Type, and assigns this channel to the given Name. The Rate is a floating point number that corresponds to the rate of an interaction on the channel. If no rate is specified then the channel is assumed to have an infinite rate.

Type Declaration

type Name =   Type
Assigns the given Type to the given Name. If the Name occurs in the Type then a recursive type is declared.

Value Declaration

val Pattern =   Value
Assigns the given Value to the given Pattern. If the Pattern is a Name then a single value is declared. If the Pattern is a tuple of N patterns Pattern1, ..., PatternN then N values are declared.

Process Declaration

run Process
Executes the given Process.

Process Definitions

let Definition1 and ... and DefinitionN
Declares one or more mutually recursive processes.

Process Definition

Name ( Pattern1, ..., PatternN)  =   Process
Assigns the given Process to the given Name, parameterised by zero or more Pattern arguments. An instance of the given Process can be executed by invoking the given Name with corresponding Value arguments.

4  Processes

Syntax
A Process can be Null, a Parallel Composition of processes, an Action, a Choice of actions, an Instance of a definition, a Replicated action, a Conditional process, a Pattern Matching process, a Repeated process or a collection of nested Declarations.
Process ::= () Null Process
  | ( Process1 | ... | ProcessM) Parallel,M³2
  | Action{; Process} Action Process
  | do Action1{; Process1} or ...or   ActionM{; ProcessM} Choice,M³2
  | Name ( Value1, ..., ValueN) {; Process} Instantiation,N³0
  | replicate Action{; Process} Replicated Action
  | if Value then Process {else Process} Conditional Process
  | match Value case Case1...case CaseN Matching,N³1
  | Integer of Process Repetition
  | ( Declaration1... DeclarationN  Process) Nested Declarations,N³0
 
Case ::= Value ->   Process Match Case
 
Null

()
Terminates the execution of a process.

Parallel Composition

( Process1 | ... | ProcessM)
Executes two or more processes in parallel.

Action Process

Action{; Process}
Tries to perform the given Action and then execute the given Process. If no Process is specified then nothing is executed after the action is performed.

Choice

do Action1{; Process1} or ...or   ActionM{; ProcessM}
Tries to perform two or more competing actions simultaneously. Once a chosen Actioni has been performed, any competing actions are discarded and Processi is executed. If no Processi is specified then nothing is executed after the action is performed.

Instantiation

Name ( Value1, ..., ValueN) {; Process}
Spawns a copy of the process defined by the given Name, instantiated with the given Value arguments, in parallel with the given Process. If no Process is specified then nothing is executed in parallel with the instantiated process. From version 0.042, the use of the optional {; Process} is deprecated.

A number of predefined processes are available: print(s) prints the given string s on the console, println(s) prints the given string s on the console followed by a new line character and break() halts the simulation until the user presses Enter.

Replicated Action

replicate Action{; Process}
Tries to perform the given Action and then spawn a copy of the given Process. This has the effect of repeatedly executing the given Action followed by the given Process.

Conditional

if Value then Process {else Process}
Executes the first Process if the given Value is true. Otherwise, the optional second process is executed.

Matching

match Value case Case1...case CaseN
Tries to match the given Value with one or more Cases, where each Casei is of the form:
Valuei ->   Processi
The cases are matched in order, from first to last. For each Casei, if the given Value matches Valuei then Processi is executed. Otherwise, the next case is examined. Note that any variables in Valuei are bound during matching. If none of the cases match the given Value then nothing is executed.

Repetition

Integer of Process
Executes zero or more copies of the given Process, as specified by the given Integer.

Nested Declarations

( Declaration1... DeclarationN  Process)
Executes zero or more nested declarations, followed by the given Process. The syntax is further constrained so that nested declarations cannot contain process definitions.

5  Actions

Syntax
An Action can be a stochastic Delay or an Output or Input on a Channel.
Action ::= delay@ Value   Delay
  | ! Channel {( Value1, ..., ValueN) } {* Value}   Output,N³0
  | ? Channel {( Pattern1, ..., PatternN) } {* Value}   Input,N³0
 
Delay

delay@ Value; Process
Waits for a period of time stochastically determined by the given Value, and then executes the given Process.

Output

! Channel {( Value1, ..., ValueN) } {* Value}; Process
Tries to send zero or more values on the given Channel and then execute the given Process. If there is a parallel input on the same channel then the values are sent over the Channel and the Process is executed. The rate of the reaction is multiplied by the given Value.

Input

? Channel {( Pattern1, ..., PatternN) } {* Value}; Process
Tries to receive zero or more values on the given Channel, assign them to the given patterns and then execute the given Process. If there is a parallel output on the same channel then values are received over the Channel and assigned to the patterns, and the Process is executed. The rate of the reaction is multiplied by the given Value.

6  Patterns

Syntax
A Pattern can be a Wildcard, a Name with an optional type annotation, or a sequence of zero or more patterns enclosed in parentheses:
Pattern ::= _   Wildcard Pattern
  | Name{: Type}   Name Pattern
  | ( Pattern1, ..., PatternN)   Patterns,N³0
 
Assignment
A Value can be assigned to a given Pattern inside a given Process, written
Process{Pattern:=Value}

7  Values

Syntax
A Value can be a Constant, a Constructed value or an Expression:
Value ::= String   String Value
  | Integer   Integer Value
  | Float   Float Value
  | Character   Character Value
  | true   Boolean True
  | false   Boolean False
  | int_ of_ float   Float to Integer
  | float_ of_ int   Integer to Float
  | sqrt   Square Root
  | Name   Variable
  | show Value   String Representation
  | - Value   Negation
  | Value+ Value   Addition
  | Value- Value   Subtraction
  | Value* Value   Multiplication
  | Value/ Value   Division
  | Value= Value   Equal
  | Value<> Value   Different
  | Value< Value   Less Than
  | Value> Value   Greater Than
  | Value<= Value   Less Than or Equal
  | Value>= Value   Greater Than or Equal
  | Name ( Value1, ..., ValueN)   Constructor Value,N³0
  | []   Empty List
  | Value:: Value   List Value
  | ( Value1, ..., ValueN)   Values,N³0
 
Constant Values
A String, Integer, Float or Character constant, boolean true, or boolean false.

Constructed Values
A sequence of zero or more values, enclosed in parentheses:
( Value1, ..., ValueN)
A data constructor consisting of a Name and a sequence of zero or more Value arguments:
Name ( Value1, ..., ValueN)
A list, which can be either empty [] or of the form Value1:: Value2, where Value1 is the first element of the list and Value2 is the remainder of the list. Note that all values in a list must be of the same type:
Value:: Value

Expressions
A value expression can be a variable Name representing a predefined value, a prefix operator followed by a Value argument, or an infix operator between two Value arguments.

The prefix operator show Value1 converts Value1 to a string value. By definition, every value has a corresponding string representation. The prefix operators int_ of_ float and float_ of_ int perform float and integer conversions, respectively. The prefix operator - Value is defined in Table 1.

Infix operators take two arguments of any type, provided both types are the same. The comparison operators (= ,,,=,=) return a result of boolean type and rely on an ordering to compare both arguments. The arithmetic operators (+,-,*,/) return a result of the same type as their arguments. Table 1 describes the behaviour of the operators for each corresponding type of arguments. The _ symbol means that the behaviour of the operator is unspecified, although the result will always be of the correct type.
Type + - * / - (prefix) = ,,,=,=
String Concatenate _ _ _ _ Lexicographic Order
Integer Add Subtract Multiply Divide Minus Integer Order
Float Add Subtract Multiply Divide Minus Float Order
Character _ _ _ _ _ ASCII Code Order
Boolean Or _ And _ Not Lexicographic Order
List Append _ _ _ _ Order of Elements
Data _ _ _ _ _ Lexicographic Order
Other _ _ _ _ _ _

Table 1: Operator Definitions

8  Types

Syntax
A Type can be a Constant type, a Constructed type or a type Expression:
Type ::= string   String Type
  | int   Integer Type
  | float   Float Type
  | char   Character Type
  | bool   Boolean Type
  | Name   Type Variable
  | ' Name   Polymorphic Type
  | chan{ ( Type1, ..., TypeN) }   Channel Type,N³0
  | proc ( Type1, ..., TypeN)   Process Type,N³0
  | Name ( Type1, ..., TypeN)   Constructor Type,N³0
  | Type1 | ... | TypeM   Data Type,M³2
  | list( Type)   List Type
  | ( Type1, ..., TypeN)   Types,N³0
 
Constant Types
A string, int, float, char or bool type.

Constructed Types
A channel that can carry zero or more values of given types:
chan{ ( Type1, ..., TypeN) }
A process that can be instantiated with zero or more values of given types:
proc ( Type1, ..., TypeN)
A sequence of zero or more types, enclosed in parentheses:
( Type1, ..., TypeN)
A data constructor consisting of a Name and a sequence of zero or more arguments of given types:
Name ( Type1, ..., TypeN)
A data type consisting of a choice between two or more types:
Type1 | ... | TypeM
A list that can contain values of a given type:
list( Type)

Type Expressions
A type expression can be a Name representing a predefined type, or a polymorphic type variable that can be instantiated with an arbitrary type.

Type-checking
Before executing a given program, the simulator checks if the program is well-typed and reports any type errors. The type system for the SPiM Language is based on the type system for the Pict Language, available from http://www.cis.upenn.edu/~bcpierce/papers/pict/

9  Lexical Syntax

Regular Expressions
Regular Expressions (Regexp) are used to describe the syntax of Constants and Variables in the SPiM Language:
Regexp ::= c   Character
  | c···c   Character Range
  | ¬c   Character Complement
  | Regexp Regexp   Concatenation of Expressions
  | Regexp |  Regexp   Alternative Expressions
  | Regexp?   Optional Expression
  | Regexp*   Repetition of Expression
  | Regexp+   Strict Repetition of Expression
  | ( Regexp)   Nested Expression
 
Constants
An Integer constant consists of an optional negative sign followed by one or more digits:
Integer::= (-)?(0···9)+
A String constant consists of a sequence of zero or more characters enclosed in double quotes. The sequence can only contain a double quote if it is preceded by a backslash:
String::= "((¬") | (\"))*"
A Float constant consists of an Integer, followed by a decimal point and one or more digits, followed by an optional exponent. The exponent consists of e or E, followed by + or -, followed by one or more digits:
Float::= Integer.(0···9)+((e | E)(+ | -)(0···9)+)?
A Character constant consists of any character enclosed in single quotes, apart from the single quote character. It can also consist of a backslash, followed by a special escaped character or a three-digit decimal number, enclosed in single quotes:
Character::= '(¬')'   Regular Character
| '\''   Single Quote
| '\\'   Backslash
| '\n'   Linefeed
| '\r'   Carriage Return
| '\t'   Horizontal Tabulation
| '\b'   Backspace
| '\(0···9)(0···9)(0···9)'   ASCII Character Code
 
Variables
A Name variable consists of a letter followed by zero or more letters, digits, underscores or single quotes:
Name::= (A···Z | a···z)(A···Z | a···z | 0···9 | _ | ')*
A Channel variable is a Name representing a Channel value:
Channel::= Name
The following variable names are reserved keywords of the language:
and   as   bool   chan   char   delay   directive
do   else   float   float_to_int   if   in   int
int_to_float   false   let   list   new   out   or
of   plot   proc   replicate   run   sample   show
sqrt   string   then   true   type   val    

Comments
A comment starts with the sequence of characters (* and ends with the sequence of characters *). Comments can be nested, but they cannot occur inside single or double quotes.

10  Language Summary

This section presents a summary of the SPiM language definition, where optional elements are enclosed in braces as { Optional}. The syntax is further constrained so that nested declarations cannot contain process definitions.
Program ::= { Directive1... DirectiveM}   Directives,M³1
    Declaration1... DeclarationN   Declarations,N³1
 
Directive ::= directive sample Float { Integer}   Sample Directive
  | directive graph    Graph Directive
  | directive plot Point1... PointN   Plot Directive
 
Point ::= ! Channel {as String}   Output Point
  | ? Channel {as String}   Input Point
  | Name ( Value1, ..., ValueN)  {as String}   Process Point,N³0
 
Declaration ::= new Name{@ Value}: Type   Channel Declaration
  | type Name =   Type   Type Declaration
  | val Pattern =   Value   Value Declaration
  | run Process   Process Declaration
  | let Definition1 and ... and DefinitionN   Definitions,N³1
 
Definition ::= Name ( Pattern1, ..., PatternN)  =   Process   Definition,N³0
 
Process ::= ()   Null Process
  | ( Process1 | ... | ProcessM)   Parallel,M³2
  | Name ( Value1, ..., ValueN) {; Process}   Instantiation,N³0
  | ActionProcess   Action Process
  | do ActionProcess1 or  ... or   ActionProcessM   Choice,M³2
  | replicate ActionProcess   Replicated Action
  | if Value then Process {else Process}   Conditional Process
  | match Value case Case1...case CaseN   Matching,N³1
  | Integer of Process   Repetition
  | ( Declaration1... DeclarationN  Process)   Nested Declarations,N³0
 
Case ::= Value ->   Process   Match Case
 
ActionProcess ::= Action{; Process}   Action Process
 
Action ::= delay@ Value   Delay
  | ! Channel {( Value1, ..., ValueN) } {* Value}   Output,N³0
  | ? Channel {( Pattern1, ..., PatternN) } {* Value}   Input,N³0
 
Pattern ::= _   Wildcard Pattern
  | Name{: Type}   Name Pattern
  | ( Pattern1, ..., PatternN)   Patterns,N³0
 
Value ::= String   String Value
  | Integer   Integer Value
  | Float   Float Value
  | Character   Character Value
  | true   Boolean True
  | false   Boolean False
  | int_ of_ float   Float to Integer
  | float_ of_ int   Integer to Float
  | sqrt   Square Root
  | Name   Variable
  | show Value   String Representation
  | - Value   Negation
  | Value+ Value   Addition
  | Value- Value   Subtraction
  | Value* Value   Multiplication
  | Value/ Value   Division
  | Value= Value   Equal
  | Value<> Value   Different
  | Value< Value   Less Than
  | Value> Value   Greater Than
  | Value<= Value   Less Than or Equal
  | Value>= Value   Greater Than or Equal
  | Name ( Value1, ..., ValueN)   Constructor Value,N³0
  | []   Empty List
  | Value:: Value   List Value
  | ( Value1, ..., ValueN)   Values,N³0
 
Type ::= string   String Type
  | int   Integer Type
  | float   Float Type
  | char   Character Type
  | bool   Boolean Type
  | Name   Type Variable
  | ' Name   Polymorphic Type
  | chan{ ( Type1, ..., TypeN) }   Channel Type,N³0
  | proc ( Type1, ..., TypeN)   Process Type,N³0
  | Name ( Type1, ..., TypeN)   Constructor Type,N³0
  | Type1 | ... | TypeM   Data Type,M³2
  | list( Type)   List Type
  | ( Type1, ..., TypeN)   Types,N³0
 
Regexp ::= c   Character
  | c···c   Character Range
  | ¬c   Character Complement
  | Regexp Regexp   Concatenation of Expressions
  | Regexp |  Regexp   Alternative Expressions
  | Regexp?   Optional Expression
  | Regexp*   Repetition of Expression
  | Regexp+   Strict Repetition of Expression
  | ( Regexp)   Nested Expression
 
Character ::= '(¬')'   Regular Character
  | '\''   Single Quote
  | '\\'   Backslash
  | '\n'   Linefeed
  | '\r'   Carriage Return
  | '\t'   Horizontal Tabulation
  | '\b'   Backspace
  | '\(0···9)(0···9)(0···9)'       ASCII Character Code
 
Channel ::= Name
Integer ::= (-)?(0···9)+
String ::= "((¬") | (\"))*"
Float ::= Integer.(0···9)+((e | E)(+ | -)(0···9)+)?
Name ::= (A···Z | a···z)(A···Z | a···z | 0···9 | _ | ')*
Keywords ::=
 
and   as   bool   chan   char   delay   directive
do   else   float   float_to_int   if   in   int
int_to_float   false   let   list   new   out   or
of   plot   proc   replicate   run   sample   show
sqrt   string   then   true   type   val    

A comment starts with the sequence of characters (* and ends with the sequence of characters *). Comments can be nested, but they cannot occur inside single or double quotes.
1
Available from http://www.graphviz.org/ compatible with version 2.8
This document was translated from LATEX by HEVEA.