module Functional: sig end 'I : any -> anyI combinator: I == \x.x. 'K : any -> functK combinator: K(a) == \x.a. 'B : funct -> funct -> functB combinator: B(f, a) == \x.f(a(x)). 'C : funct -> any -> functC combinator: C(f, a) == \x.(f(x))(a). 'S : funct -> funct -> functS combinator: S(f, a) == \x.(f(x))(a(x)). 'S4 : funct -> funct -> funct -> functS4 combinator: S4(f, a, b) == \x.f(a(x), b(x)). 'IF : funct -> funct -> funct -> functIF combinator: IF(c, t, f) == \x.if c(x) then t(x) else f(x) fi.
Beware that this combinator is strict, that is: c, t and f are evaluated
(but f(x) is not evaluated if c(x) is true and t(x) is not evaluated if c(x) is false). 'S4_S : funct -> funct -> functS4_S combinator: S4_S == S4(S). In other words:
S4_S(a, b, x, y) = S(a(x), b(x), y) = (a(x, y))(b(x, y)). 'B_K : funct -> functB_K combinator: B_K == B(K). In other words: B_K(f, x, y) == f(x). 'fixpoint : any'fixpoint keyword specifies fixed-point iteration in function application.
'fixpoint is a predefined identifier used as an optional argument to indicate
that the function applied must be iterated until a fixpoint is reached. This can
be used with several variations :
f['fixpoint](x0) compute the fixed point of f starting from x0, that is, it computes
f(x0), f(f(x0)), ..., f(...f(x0)...), ... until two consecutive elements in this
series become equal (and this last value is returned).
f[*](x0) is an abbreviation for f['fixpoint](x0). This abbreviation can be used only
if there is no other optionnal argument.
f['fixpoint=eq](x0) computes the fixed point of f starting from x0 but eq is
used as an equality predicate. eq must be a function that takes two arguments. These two
arguments are consecutive values in the previous series and they are provided to eq in
the according order.
'fixpoint does not evaluates to a function, an error is raised.
Recall that a transformation is a function and then 'fixpoint specifications apply
equally to transformation applications.
The index of the current iteration is available within the body of the iterated function
as the value of the global variable 'iteration.
Optionnal wrapping functions
The fixed point iterations of f can be wrapped by the optionnal wrapping functions 'prelude,
'interlude and 'postlude. Such functions are unary functions and:
'prelude is applied prior any iteration and its results constitute the starting point
for the iteration.
'interlude is applied between two iterations. If the result of the nth iteration is xn
then the (n+1) iteration is computed as f(interlude(xn)).
'postlude is applied finally to get the final result of the fixed point computation.\x.x.
Usually these functions simply return the argument and are used only to produce a side-effect, for instance to trace a function iteration or to cumulate some output in a file. However, they can be used to return another value. This is not a recommended practice but see the last example in this section where this feature is used to avoid infinite loops. To summarize the use of the optionnal wrapping function, expression
f['fixpoint=eq, 'prelude=pre, 'interlude=inter, 'postlude=pos](x) x0 = pre(x) x1 = f(x0) x2 = f(inter(x1)) ... xp = ... xn = f(inter(xp)) p == n-1. The last element xn computed in this series is such that eq(xp, xn) holds.
And the returned results is post(xn). Note that if the pre/inter/post-lude functions are not
provided, the computation is exactly the fixed point computation described above.
fun g(x) = x/2.0;; 0.0 == g['fixpoint](2.0);;true. Beware that the default comparaison function is the MGS 'equal
predicate which is not necessarily adapted for numerical convergence. The predicate used
to test that the fixpoint is reached can be explicitly provided :
g['fixpoint=\x,y.abs(x-y) < 0.07](2.0);;0.062500. Indeed, g(0.062500) = 0.031250 and abs(0.062500 - 0.031250) = 0.031250
which is less than 0.07.
The successive values during the iteration of g can be traced using the 'interlude
wrapping function:
g['fixpoint=(\x,y.abs(x-y) < 0.07), 'interlude=\x.(?(x); x)](2.0);; 1.000000 0.500000 0.250000 0.125000 0.062500.
trans P = { x => x, (0-x) };; P[*]((0, 1, -2, 3, 4, -5, set:()));;(-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5):'setThe predicate used to test that a fixed-point is reached is arbitrary:
trans T = { x => x, x };; T['fixpoint=\x,y.size(y)>20]((0,1));;(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1):'seqfun pp(message, value)= (?(message+": iteration="+'iteration+": "+value); value);; fun k(x) = x+1;;k['prelude = pp("pre: "), postlude = pp("post: "), 'interlude=pp("inter: "), 'fixpoint=(\x,y. y >= 237)](234);; pre: : iteration=0: 234 inter: : iteration=1: 235 inter: : iteration=2: 236 post: : iteration=3: 237237. Note the partial application of function pp to give
a value to the optional wrapping function 'prelude, 'interlude and 'postlude.
fun m(x) = x+1;; m['fixpoint = (\x, y. if 'iteration>100 then true else x == y fi), 'postlude = \x. if 'iteration>100 then <undef: max number of iterations in fixed point reached> else x fi](3)<undef: max number of iterations in fixed point reached> 'strategy : symbol'strategy keyword allows to choose a rule application strategy different
to the default MGS maximal parallel strategy. For example, one can use a
asynchronous gillespie-like stochastic rule application strategy by using the
`gillespie strategy. The different strategies are:
`default: maximal parallel strategy (synchronous) with priority of the
first rules over the last ones,
`asynchronous: asynchronous strategy with priority of the first rules
over the last ones,
`singleStochastic: maximal parallel strategy (synchronous) with a randomly
choosen priority between rules,
`multiStochastic: maximal parallel strategy (synchronous) without
priority between rules,
`stochastic: true stochastic (asynchronous) with the explicit probability
given on each rule,
`gillespie: a asynchronous gillespie-like stochastic strategy (see below).
T with a strategy `s on a topological
collection c is written
T[ 'strategy = `s ](c) ;;
or
T[ strategy = `s ](c) ;;
The following details the different strategies:
['strategy = `default]
This strategy consits in a maximal parallel application of the rules with priority
to the first rules. Applying a transformation T = trans { r1; r2; ... } is
applying r1 until no sub-collection matches with the pattern of r1, applying
r2 until no sub-collection matches with the pattern of r2, and so on.
A maximal parallel application strategy corresponds to a synchronous simulation mode. Several instancies of the pattern are matched and rewritten at the same time. Of course these instancies can't overlap.
As an example, let t and l be respectively the transformation
trans t = { x => x + 1 ; x => x + 2 } ;;
and the topological collection
l := (1,2,3,4,5,6,seq:()) ;;
The `default application of t on l produces the sequence (2,3,4,5,6,7,seq:()) .
Indeed, the first rule (with a greater priority) is applied until no element
matches. Therefore, the second rule is never applied because the first one has
consumed all the elements of l.
['strategy = `asynchronous]The priority is given to the first rules, and only one rule is applied one time, if such a rule exists. In other word, only one path is rewritten if it is possible.
['strategy = `singleStochastic]
This strategy is same as `default but the priority between rules is choosen randomly.
For the same example as previously, the `singleStochastic strategy can produces two
results (2,3,4,5,6,7,seq:()) and (3,4,5,6,7,8,seq:()) with a probability of 0.5.
['strategy = `multiStochastic]
This strategy is same as `default but there is no priority between rules.
['strategy = `stochastic]
This strategy is a true asynchronous stochastic strategy. One can specify the probabiliy of each rule
using the following P= construction. The probability given as argument of P can be an integer
or a float value or even a function (that will receive the collection, onto which the transformation
is appliedsformation as argument and that is supposed to return either an integer or a float value:
trans T = {
x ={ P = (\x.(0.25)) }=> x+1;
x ={ P = 0.25 }=> x+10;
x ={ P = 0.5 }=> x+100
}
['strategy = `gillespie]
The `gillespie rule application strategy allows the use of many options in
the rules specification, according to Gillespie's original stochastic
simulation algorithm. Indeed, Gillespie's standart algorithm requires to
compute the smallest tau of a set of rules R to choose which rule Ri should be selected and the amount of time resulting from the selection of
that rule. For example, let's look at the set of coupled, autocatalytic
reactions due to Lotka (Volterra investigated later these equations to
mathematically model a prey-predator ecosystem). The rules are stated as:
X + Y1 -> X + 2 Y1 with C = 0.001
Y1 + Y2 -> 2 Y2 with C = 0.01
Y2 -> Z with C = 10
The first rule states how a certain prey species Y1 reproduces by feeding
on a certain foodstuff X; the second rule expresses how a certain species
of predator Y2 reproduces by feeding of a species Y1; finally, the last
rules expresses the disparition of species Y2 by natural causes.
For each rule, following Gillespie's words, the stochastic reaction
constant C corresponding to the average probability that a particular
combination of reactant molecules will react accordingly in the next
infinitesimal time interval dt, is given. Its expression in MGS is
straightforward (species are represented by symbols, C constants are given
as rule options using the C constructions):
trans lotka_volterra = {
`X, `Y1 ={ C = 0.001 }=> #2 `Y1, `X;
`Y1, `Y2 ={ C = 0.01 }=> #2 `Y2;
`Y2 ={ C = 10 }=> `Z
}
The application of the transformation to an initial condition requires the use
of the `gillespie option:
lotka_volterra['fixpoint=(\x1,x2.('tau == 5.0)), 'strategy = `gillespie](bagify((#1000 `X, #100 `Y1, #100 `Y2)));;
Each rule applications increments the system variable 'tau by the computed
amount of time. During the transformation application, one is able to use the
value of 'tau to perform any kind of computation. The application of the
example given above stops once 'tau as reached a simulation time of
5.0. The use of 'iter = x, 'fixpoint enables a fine control on the
number of transformatio applications.
The C constants given in the MGS program above is used by the language to
compute the new value of tau after the rule applications. It follows this
scheme:
H
function is computed (for example, for the first rule, H = #`X * #`Y1
where #`X represents the number of `X in the collection).
A = H * C is computed.
tau = (1/A) * ln(1 / random()) is computed.
tau is selected and applied only
once. 'tau is incremented by the tau associated with the selected rule.
One that would like to explicitly compute the A value (for complex reactions involving
not only reacting molecules but also enzymes, inhibitors, facilitators, ...) may use the
following construction:
trans lotka_volterra = {
`X, `Y1 ={ A = \coll.(coll#`X * coll#`Y1 * 0.001) }=> #2 `Y1, `X;
...
}
'iter : int'iter keyword specifies bounded iteration in function application.
'iter is a predefined identifier used as an optional argument to indicate
the iterated application of a function.
f['iter=nexp](x0)nexp evaluates to the integer n, computes the n-fold application
of f to x0, that is:
f(...f(0)...)f is applied n times. By convention, f['iter=0](x0) returns x0.
If the argument of 'iter is strictly negative, then <undef> is returned.
If the argument of 'iter does not evaluates to an integer, an error is raised.
The expression f[nexp](x0) can be used to abbreviate f['iter=nexp](x0) if there is
no other option specification.
The index of the current iteration is available within the body of the iterated function
as the value of the global variable 'iteration.
The optionnal wrapping functions 'prelude, 'interlude and 'postlude can be provided:
cf. 'fixpoint for an explanation of this feature. Note that f['iter=0, ...](...) does not
apply any wrapping function and f['iter=1, ...](...) apply only the 'prelude and 'postlude
functions (if they are present) since there is no iteration. In any case, for n>=0,
f['iter=n+1](...) == f(f['iter=n](...)) fun f(x) = x+1;; f['iter=3](0)3.
With the definition
fun g(x) = x/2.0;; 1.0 == g['iter=5](2*2*2*2*2);;true.'iteration variable:
fun h(x) = (?("iteration: "+'iteration); x+1);;h['iter=3](0) iteration: 1 iteration: 2 iteration: 33.fun pp(message, value)= (?(message+": iteration="+'iteration+": "+value); value);; fun k(x) = x+1;;k['prelude = pp("pre: "), postlude = pp("post: "), 'interlude=pp("inter: "), 'iter=3](11);; pre: : iteration=0: 11 inter: : iteration=1: 12 inter: : iteration=2: 13 post: : iteration=3: 1414. 'prelude : funct
'interlude : funct
'postlude : funct
'fixrule : any