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 : 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:

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: 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:

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