Lope is a general-purpose programming language, with a particular emphasis on mobile and distributed systems. It is loosely based on the Bigraphs formalism, and owes an ideological debt to the Bigraphical Programming Languages project.
The fundamental unit of computation within Lope is the reaction. A reaction is expressed as a rule of the form r --> r', where r is the redex and r' the reactum. This corresponds to the rule if any part of the system matches the pattern defined by r, replace it with r'. This is suitably powerful to express many kinds of computation.
A "program" in Lope consists of three parts:
In understanding Lope, it is important to remember that while bigraphs are primarily a modeling formalism, Lope attempts to permit modeling while remaining, in essence, a programming language. For this reason, pragmatics are given precedence over theoretical concerns where any conflict should arise between the two.
A bigraph is essentially two graphs that share a set of nodes. The place graph defines a tree that is the nesting of nodes. A node may contain other nodes and so on to any arbitrary depth, for example:
This corresponds to a tree, as shown below:
Lope extends the bigraphical notion of a place-graph with a concept of an implied "World" node that is the super-node of all nodes in the system. The purpose of this World node will be described later.
The second graph within a bigraph is the link graph. This defines connectivity between nodes. Links are bidirectional and may cross node boundaries. More unusually, the link graph is a hypergraph, so a link may connect more than two nodes:
Combining the two graphs, we get a visual representation of a bigraph:
At this point we begin to diverge from the theory of bigraphs. Whereas bigraphs have a much refined notion of inner names and outer names, we use language-based features to control composition of bigraphs in a much cruder way, and as such we do not require this distinction.
Another bigraphical concept of significance for Lope is the existence of sites. A site is a kind of meta-node that permits another bigraph to be substituted in its place. The crossed white areas in the following example are the two sites in this bigraph:
The final concept of some importance is sortings. Because Lope is fundamentally a programming language, we will revert to the more familiar (though possibly less-accurate) term types. A node can have a type, which we indicate using a syntax like: name : type.
While we are using entirely graphical representations here, a textual syntax for Lope will be introduced in a later section.
A reaction rule has a left hand side (a redex) and a right hand side (a reactum), which indicates that in the presence of a match with the "pattern" defined by the left hand side, the matching part of the system should be replaced with the right hand side. We also extend this basic notion of a reaction with the ability to define arbitrary behaviours associated with input and output with a reaction.
Given that I spend a lot of time on it, the first example of a bigraph with reaction rules will be a simulation of a small part of the London Underground. Our simulation will only include three stations, each with an east- and west-bound platform (each of which can accomodate exactly one train at a time). Keep in mind that this is simulation, not modeling. Our goal is to be able to output something like:
... West train has left KingsCross station East train has entered RussellSquare station West train has entered RussellSquare station East train has left RussellSquare station ...
Each station will have a pre-determined "wait time", and fixed travel times between stations. This will require a 'timer' mechanism, which I will explain prior to describing the rest of the system.
A timer is a pre-existing component, built using language internals. It takes two parameters; the interval (in seconds) between events, and the node that should be introduced into the environment when the event fires:
Instantiation of a timer silently introduces some reaction rules into the system. One of these reaction rules will increment the 't' value once per second. The other reaction rule is shown below:
The effect of the timer firing is to introduce a new node ('Go') inside the node where the timer has been instantiated. This result of this is that we can then write a reaction rule using 'Go' to hook into the timer firing:
The "IO" type is another special built-in type. The environment provides reaction rules for IO nodes, taking their contents, printing them and then removing the IO node once it is processed. Taking all of this together, the result is that this program will print "Hello" every 15 seconds.
Having described the function of timers, I now present the first part of our example program - the initial state of the system:
This is an idealised London Underground (largely because it only has three stations, which would make for absurdly short travel times), with one east-bound and one west-bound train only. The "E" blocks at each end are some sort of mysterious zones into which trains disappear and never come back (otherwise known as 'the rest of the London Underground'). Now we need some reaction rules to give it behaviour!
This rule allows a train that is in a station to move into an empty tunnel, going west:
Some explanation might be required. The first thing to notice is that our reaction rule is expressed as a bigraph. This will come in handy later when we start to dynamically generate new reaction rules and modify our existing rules. Second, notice that we leave out a lot of information from the original model. We only need to include enough information to obtain a match, and only enough to allow us to access (and manipulate) the nodes that are of interest to us. Anything that is matched in the redex will be replaced with the reactum, leaving anything that was not mentioned in the redex untouched. The effect of matching something in the redex and not mentioning it in the reactum (as we do with our timer signal, GW) is to delete it.
This rule relies on the timer behaviour described earlier. It will not fire until the timer reaction rules place a "GW" node inside the current node, at which point the train is allowed to leave the station. If the GW node is absent, or if the tunnel is not empty, the train will not be allowed to leave the tstation.
This rule allows a train to move from a tunnel into an empty station once the tunnel timer fires.
The $X : Station and $t : Train syntax is a way of matching on types in reaction rules. $X : Station will match any node of type Station, and $X any subsequent occurences of $X in the reactum will be replaced by the matched node.
Note: The way in which the "IO" node is used in these examples is something of an over-simplification so as to keep the graphical notation readable and simple. The exact graphical representation of IO elements will be explained after the textual representation of Lope programs is introduced.
We need one final rule, which dictates that a train that reaches the end of the line disappears into nothingness, and then reappears back at the other end of the line in the same instant (i.e. trains wrap around).
Obviously we have only encoded rules for traveling in one direction (west). We would need to construct rules for east-bound trains in much the same way. The introduction of a textual description will allow us to produce a fully parameterised version of this same program, where a single rule can suffice to describe the behaviour of both east- and west-bound trains. For argument's sake, assume we have manually constructed the corresponding set of rules for east-bound trains.
Hopefully the graphical representations and examples have given you you some sense of the "flavour" of Lope programming. There are a few reasonably interesting observations we can make at this point:
Because almost everything in Lope is a bigraph, the textual representation is primarily geared towards representation and construction of bigraphs.
A bigraph is a first-class object. The anonymous empty bigraph is represented by:
{}
A bigraph can be anonymous or named:
{ {}; } // An anonymous bigraph that contains only the empty (anonymous) bigraph.
A { B; } // A bigraph named "A" that contains another (empty) bigraph named "B"
Named parameters become 'sites' within the bigraph. They appear in the parameter list without a '$' delimeter, and within the body of the bigraph with a '$' delimeter:
A (x,y) {
$x;
B($y);
};
The treatment of types may be somewhat unfamiliar to users of other programming languages. A type annotation may be attached to any name or value:
B(l : string) {
C($l);
}
A : SomeType (x : int, y : string) {
$x;
B($y);
}
Lope features strong typing and type inference. In this case, the type of the parameter to B will be enforced (e.g. passing an integer would be an error). It is possible to leave type annotations off terms where the type can be reconstructed unambiguously:
B(l) {
C($l);
}
A : SomeType (x, y) {
$x;
B($y);
}
A(10,"abc");
A limited form of polymorphism is available - the implementation of this would be familiar to ML users. Basically, where no type constraints are placed upon a parameter, it will be generalised to a type variable ('a, 'b, ...) which acts as a 'place holder' for exactly one type. For example:
PolymorphicBigraph (x,y) {
$x;
$y;
}
The type of PolymorphicBigraph will be 'a * 'b -> PolymorphicBigraph {'a; 'b}. The '*' notation describes a tuple of values, that is, the type of (x,y) is 'a * 'b. The arrow (->) is used to separate inputs from outputs (the input is on the left hand side, and the output type is on the right hand side). So far, this is all ordinary ML-style type notation. The output type, however, is unlike anything seen in ML.
Because we have not provided a type annotation for PolymorphicBigraph, a new, unique type is automatically instantiated for it (PolymorphicBigraph {a; b}). The only value that inhabits this type is PolymorphicBigraph itself. The final piece of notation ({'a; 'b}) indicates the internal structure of PolymorphicBigraph as it is now. PolymorphicBigraph {int; string} would be a valid instantiation to concrete types (i.e., the instantiated type may be substituted for the uninstantiated type in all cases - they the the same type in some sense), however PolymorphicBigraph {'a; 'b} is a distinct type from PolymorphicBigraph {'a; 'b; 'c}.
While no computation on types is permitted (i.e. dynamic 'reflection-style' features are forbidden), there is a simple mechanism for using the types of bigraphs within other type expressions:
OtherBigraph (p,q) {
$p;
$q;
} : PolymorphicBigraph.type
This is purely syntactic sugar for writing the type 'a * 'b -> PolymorphicBigraph {'a; 'b} in full. It is enforced at compile time, and if PolymorphicBigraph is subsequently updated (to PolymorphicBigraph {'a; 'b; 'c}, for example), OtherBigraph will retain the original type.
There are a few standard values that are accessible on all bigraphs (---> just means 'evaluates to' in this context, and is not a Lope construct):
pb = PolymorphicBigraph("x",123);
pb.name ---> "pb"
pb.type ---> PolymorphicBigraph {string; int}
pb.child1 ---> "x" : string
pb.child2 ---> 123 : int
pb.child1.name ---> "" : string
These are essentially just macros, and are not modifiable.
Links can be named or anonymous:
station : Station (intervalW, intervalE) <wTL,wTR,eTL,eTR> {
Timer($intervalW, GW};
Timer($intervalE, GE};
$West;
$East;
}
tunnel : Tunnel (travelTime) <L,R> {
Timer($travelTime);
$tunnelTrain;
}
Underground {
E <westLine,eastLine>;
KingsCross = station(30,25);
wt1 = tunnel(10);
et1 = tunnel(15);
RussellSquare = station(25,45);
wt2 = tunnel(30);
et2 = tunnel(25);
Holborn = station(15,20);
W <westLine,eastLine>;
link E - KingsCross<wTR,eTR>;
link KingsCross<wTL> - wt1<R>;
link KingsCross<eTL> - et1<R>;
link wt1<L> - RussellSquare<wTR>;
link et1<L> - RussellSquare<eTR>;
link RussellSquare<wTL> - wt2<R>;
link RussellSquare<eTL> - et2<R>;
link wt2<L> - Holborn<wTR>;
link et2<L> - Holborn<eTR>;
link W - Holborn<wTL,eTL>;
}
While the example above uses named links, for our purposes we do not need them, so the example is presented again using anonymous links. The behaviour of the link keyword differs for anonymous links. The standard syntax link Bigraph1 - Bigraph2 will link the first n links together, where n is the smaller number of unconnected links on either bigraph. The effect of adding a subscript (e.g. link Bigraph1<2< - Bigraph2) is to limit the value of $n$.
Underground {
station : Station (intervalW, intervalE) <4> {
Timer($intervalW, GW};
Timer($intervalE, GE};
$West;
$East;
}
tunnel : Tunnel (travelTime,direction) <2> {
Timer($travelTime);
$tunnelTrain;
}
train : Train (direction) {
$direction;
}
E <2>;
KingsCross = station(30,25);
wt1 = tunnel(10,West);
et1 = tunnel(15,East);
RussellSquare = station(25,45);
wt2 = tunnel(30,West);
et2 = tunnel(25,East);
Holborn = station(15,20);
W <2>;
link E - KingsCross;
link KingsCross<1> - wt1;
link KingsCross<1> - et1;
link wt1 - RussellSquare;
link et1 - RussellSquare;
link RussellSquare<1> - wt2;
link RussellSquare<1> - et2;
link wt2 - Holborn;
link et2 - Holborn;
link W - Holborn;
// Insert our trains into the platform sites.
KingsCross.West = train (West);
Holborn.East = train (East);
}
Reaction rules are just bigraphs, and so their specification mostly follows from the syntax already used up to this point. The only difference is that we provide a convenience reaction keyword that provides a cue to those reading Lope programs that there is additional behaviour associated with these particular bigraphs.
reaction WestStationTrain {
redex { _ : Station {
GW;
$tr : Train
} <-> _ : Tunnel {
West;
{}
}
}
reactum { _ : Station {
{}
} <-> _ : Tunnel {
West;
$tr
}
}
}
The 'X <-> Y' link operator is a convenience shorthand for 'link X<1> - Y', indicating that there exists a link between the bigraphs on the left and right hand side. The wildcard ('_') may be used in place of explicit variable-based matching where it is unambiguous to do so. Ambiguous use of wildcards will result in a compile error. Use of wildcards is unambiguous if the same types appear in the same nested order, for example:
redex:
_ : X {
_ {
_ : Z {}
}
}
reactum:
_ : X {
Foo;
_ {
_ : Z {}
}
}
Reaction rules are parameterisable just as any other bigraph is, so we can rewrite this example to be generic for any direction of travel, and then we can instantiate the rule for east-bound and west-bound trains:
StationTrain (direction,token) {
redex { $st : Station {
$token;
$tr : Train { $direction }
} <-> _ : Tunnel {
$direction;
{}
}
}
reactum { $st : Station {
{}
} <-> _ : Tunnel {
$direction;
$tr
};
print ($direction.name + " train has left " + $st.name + " station")
}
}
reaction WestStationTrain (West,GW);
reaction EastStationTrain (East,GE);
So far the running example has been a simulation task, which ignores some of the programming-in-the-small features of Lope. This section will contain a series of traditional general-purpose programming tasks and data structures encoded in the Lope style. First though, we introduce an additional construct that provides a useful short-hand:
fun f x = E fn x => E
The effect of fun is a little subtle. While it is supposed to provide a very familiar notion of introducing a function named 'f' into the current environment, its real effect is to introduce a specialised type and corresponding reaction rules. You can assume that there is an encoding of something corresponding to the Lambda-calculus inside Lope, and the 'fun' keyword is a means of hiding this complexity and avoiding the need for the programmer to deal with binding and scope rules. In brief, a function like:
fun addTwo x = x + 2
Actually decomposes into a bigraph:
Application of the function (e.g. f(10)) is also a bigraph, with an accompanying reaction rule:
The reaction rule for applied functions is invoked at that point and appropriate substitution happens, allowing eventual reduction to a result:
So after all the rules have been applied, a single bigraph that wraps the result of evaluating the function application is left in the same context as the original function application. In real implementation terms, we may "hard code" reaction rules for arithmetic operations and such in order to make use of built-in hardware functionality more efficiently.
There is a little bit of trickery going on to do with primitive types (e.g. int, string, real and tuple types etc). Everything in Lope is a bigraph, but sometimes it is convenient to be able to refer to a boxed value (such as an int) within arithmetic expressions without having to manually unbox the value. For primitive types only, a bigraph containing only a single primitive value will be coerced to the type of that primitive value where appropriate. For example, MyIntValue { 32 } + 10 is equivalent to 32 + 10 for all intents and purposes.
We also allow pattern-matching using the same syntax as in redexes - pattern matching actually just introduces a reaction rule for each clause.
fun fact 0 = 1
| fact n = n * fact (n-1)
fun treeSum {} = 0
| treeSum (tree { left{y}; v; right{z} }) = v + treeSum y + treeSum z
List {
Nil;
Cons (h,t) {
($h,$t)
};
fun append Nil l = l
| append (Cons{(h,t)}) l = Cons(h,append(t,l));
myList = append([1,2,3],[4,5,6])
}
Primes (k) {
sieve(n) : sieve <in:int,out:int> {
handle $in -> if $in mod $n = 0 then $out <- $in else {};
}
Term {
handle $in -> Candidate { $in };
}
reaction extend {
redex { $s : sieve <-> Term { Candidate { $c } } }
reactum { $s <->>Sieve($c) <-> Term {} }
}
s2 = sieve(2);
t = Term;
link s2<out> - t<in>;
gen = Int.seq(3,$k); // seq is a built-in that will generate integers from 3..$k on a port
link gen - s2;
}