Metafunctions

A Metafunction is a function written in the OpenMath host language which produces programs, functions or any portion of code from other OM objects. In its most trivial form, a Metafunction is like a macro.

A very trivial metafunction is one which will increment a given variable.

#  INCRement a variable  (OM --> OM)
INCR := proc( v )  Assign(v,v+1) end:

This will produce a simple assignment statement doing the increment. Once this is translated to a host language, the statement may look like

 v := v+1; 

 v++; 

Metafunctions are more than macros in the sense that we have the complete computing power of the host system to produce the code. For example, the production of the parabolic approximation could have been encapsulated in a metafunction. The order of the approximation could have been made a parameter of this function. In this case it is clear that the power of the metafunctions is related to the host system which executes the metafunction (Maple in this case) and goes beyond the power of macro processing.

The next function produces a block of code that will sort a specified portion of an arbitrary array with any key.

# Shell-sort metafunction (OM --> OM)
SORT := proc( r, lo, up, key )
  Block(
    Declaration(
      [d,i,j] = Integer,
      t = Type(r[]) ),
    ForWhile(
      Assign(d,up-lo+1),
      d > 1,
      Block(),
      Block(
        If( d<5, Assign(d,1), Assign(d,DIV(5*d-1,11)) ),
        ForLoop( i, up-d, -1, lo, Block(
          Assign( t, r[i] ),
          ForWhile(
            Assign( j, i+d ),
            j <= up and key(t) > key(r[j]),
            Assign( j, j+d ),
            Assign( r[j-d], r[j] )),
          Assign( r[j-d], t )))
      ))
  )
end:

The above can be used to instantiate the sorting of the array A in the range 1 to 100 on the absolute value of the sum of the first two components of each entry.

> SORT( A, 1, 100, x -> abs(x[1]+x[2]) );
Block(
  Declaration( [d, i, j] = Integer, t = Type(A[])),

  ForWhile( Assign(d, 100), 1 < d, Block(), Block(

    If(d < 5, Assign(d, 1), Assign(d, DIV(5 d - 1, 11))),

    ForLoop(i, 100 - d, -1, 1, Block(

      Assign(t, A[i]),

      ForWhile( Assign(j, i + d),

        j - 100 <= 0 and | A[j][1] + A[j][2] | < | t[1] + t[2] |,

        Assign(j, j + d), Assign(A[j - d], A[j])),

      Assign(A[j - d], t)))

    )))