module Functional: sig end
'I : any -> any
I
combinator: I == \x.x
. 'K : any -> funct
K
combinator: K(a) == \x.a
. 'B : funct -> funct -> funct
B
combinator: B(f, a) == \x.f(a(x))
. 'C : funct -> any -> funct
C
combinator: C(f, a) == \x.(f(x))(a)
. 'S : funct -> funct -> funct
S
combinator: S(f, a) == \x.(f(x))(a(x))
. 'S4 : funct -> funct -> funct -> funct
S4
combinator: S4(f, a, b) == \x.f(a(x), b(x))
. 'IF : funct -> funct -> funct -> funct
IF
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 -> funct
S4_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 -> funct
B_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 n
th 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)
computes the series
x0 = pre(x)
x1 = f(x0)
x2 = f(inter(x1))
...
xp = ...
xn = f(inter(xp))
where 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;;
the expression
0.0 == g['fixpoint](2.0);;
evaluates to 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);;
returns 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);;
write the following output:
1.000000
0.500000
0.250000
0.125000
before returning the value 0.062500
.
trans P = { x => x, (0-x) };;
P[*]((0, 1, -2, 3, 4, -5, set:()));;
returns
(-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5):'set
The 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));;
returns
(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1):'seq
fun 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);;
write the following output:
pre: : iteration=0: 234
inter: : iteration=1: 235
inter: : iteration=2: 236
post: : iteration=3: 237
before returning the value 237
. 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)
returns
<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)
where nexp
evaluates to the integer n
, computes the n
-fold application
of f
to x0
, that is:
f(...f(0)...)
where 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)
evaluates to 3
.
With the definition
fun g(x) = x/2.0;;
the expression
1.0 == g['iter=5](2*2*2*2*2);;
evaluates to true
.'iteration
variable:
fun h(x) = (?("iteration: "+'iteration); x+1);;
h['iter=3](0)
write the following output:
iteration: 1
iteration: 2
iteration: 3
before returning the value 3
.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);;
write the following output:
pre: : iteration=0: 11
inter: : iteration=1: 12
inter: : iteration=2: 13
post: : iteration=3: 14
before returning the value 14
. 'prelude : funct
'interlude : funct
'postlude : funct
'fixrule : any