# Module Functional

`module Functional: `sig  end``
Functional and Transformational programing: lambda and transformations, etc.

` 'I : `any -> any``
The `I` combinator: `I == \x.x`.
` 'K : `any -> funct``
The `K` combinator: `K(a) == \x.a`.
` 'B : `funct -> funct -> funct``
The `B` combinator: `B(f, a) == \x.f(a(x))`.
` 'C : `funct -> any -> funct``
The `C` combinator: `C(f, a) == \x.(f(x))(a)`.
` 'S : `funct -> funct -> funct``
The `S` combinator: `S(f, a) == \x.(f(x))(a(x))`.
` 'S4 : `funct -> funct -> funct -> funct``
The `S4` combinator: `S4(f, a, b) == \x.f(a(x), b(x))`.
` 'IF : `funct -> funct -> funct -> funct``
The `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``
The `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``
The `B_K` combinator: `B_K == B(K)`. In other words: `B_K(f, x, y) == f(x)`.
` 'fixpoint : `any``
The `'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.
If the argument of `'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.
When one (or several) of these function is not explicitly specified as optionnal arguments, then the fixed-point evaluation proceed as this functions is the identity `\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.
``  ``

Example :With the definition
``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`.
``   ``

Example :Here is an example involving a collection.
``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``

Example :Here is another example involving the use of the optionnal wrapping functions :
``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`.
``   ``

Example :The index of the iteration, the fixpoint predicate and the postlude function can be used together to stop a fixed-point computation when a maximal number of steps has been reached (to avoid infinite loops):
``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>``

See : 'iter
See : 'fixrule
` 'strategy : `symbol``
The `'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).
The application of a transformation `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:

• For every rule, according to the left-hand side of each rule, the `H` function is computed (for example, for the first rule, `H = #`X * #`Y1` where `#`X` represents the number of ``X` in the collection).
• For every rule, the value `A = H * C` is computed.
• For every rule, the value `tau = (1/A) * ln(1 / random())` is computed.
The rule which has the smallest `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``
The `'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](...)) ``

Example :
``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`.
Example :Here is an example involving the use of the `'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`.
Example :Finally, here is an example involving the use of the optionnal wrapping functions :
``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`.
See : 'fixpoint
See : 'iteration
See : 'prelude
See : 'interlude
See : 'postlude
` 'prelude : `funct``
Optionnal wrapper function for iterated application.
See : 'fixpoint
See : 'iter
` 'interlude : `funct``
Optionnal wrapper function for iterated application.
See : 'fixpoint
See : 'iter
` 'postlude : `funct``
Optionnal wrapper function for iterated application.
See : 'fixpoint
` 'fixrule : `any``
`'fixrule` is equivalent to `'fixpoint`. Reserved for future use.
See : 'fixpoint
See : 'iter