Functions and procedures

Topics covered in this chapter:

When programs grow larger than the small examples presented so far, it becomes necessary to introduce some structure that makes them easier to read and to maintain. Usually, this is done by dividing the tasks that have to be executed into subtasks which may again be subdivided, and indicating the order in which these subtasks have to be executed and which are their activation conditions. To facilitate this structured approach, Mosel provides the concept of subroutines. Using subroutines, longer and more complex programs can be broken down into smaller subtasks that are easier to understand and to work with. Subroutines may be employed in the form of procedures or functions. Procedures are called as a program statement, they have no return value, functions must be called in an expression that uses their return value.

Mosel provides a set of predefined subroutines (for a comprehensive documentation the reader is referred to the Mosel Reference Manual), and it is possible to define new functions and procedures according to the needs of a specific program. A procedure that has occured repeatedly in this document is writeln. Typical examples of functions are mathematical functions like abs, floor, ln, sin etc.

Subroutine definition

User defined subroutines in Mosel have to be marked with procedure / end-procedure and function / end-function respectively. The return value of a function has to be assigned to returned as shown in the following example (model subrout.mos).

model "Simple subroutines"

 declarations
   a:integer
 end-declarations

 function three:integer
   returned := 3
 end-function

 procedure printstart
   writeln("The program starts here.")
 end-procedure

 printstart
 a:=three
 writeln("a = ", a)

end-model

This program will produce the following output:

The program starts here.
a = 3

Parameters

In many cases, the actions to be performed by a procedure or the return value expected from a function depend on the current value of one or several objects in the calling program. It is therefore possible to pass parameters into a subroutine. The (list of) parameter(s) is added in parantheses behind the name of the subroutine:

 function timestwo(b:integer):integer
   returned := 2*b
 end-function 

The structure of subroutines being very similar to the one of model, they may also include declarations sections for declaring local parameters that are only valid in the corresponding subroutine. It should be noted that such local parameters may mask global parameters within the scope of a subroutine, but they have no effect on the definition of the global parameter outside of the subroutine as is shown below in the extension of the example `Simple subroutines'. As in other programming languages, it is not possible to redefine function/procedure parameters in the corresponding subroutine (the declaration of local parameters must not hide these parameters). Mosel considers this as a mistake and prints an error message during compilation.

model "Simple subroutines"

 declarations
   a:integer
 end-declarations

 function three:integer
   returned := 3
 end-function

 function timestwo(b:integer):integer
   returned := 2*b
 end-function

 procedure printstart
   writeln("The program starts here.")
 end-procedure

 procedure hide_a_1
   declarations
     a: integer
   end-declarations

   a:=7
   writeln("Procedure hide_a_1: a = ", a)
 end-procedure

 procedure hide_a_2(a:integer)
   writeln("Procedure hide_a_2: a = ", a)
 end-procedure

 procedure hide_a_3(a:integer)
   declarations
     a: integer
   end-declarations

   a := 15
   writeln("Procedure hide_a_3: a = ", a)
 end-procedure

 printstart
 a:=three
 writeln("a = ", a)
 a:=timestwo(a)
 writeln("a = ", a)
 hide_a_1
 writeln("a = ", a)
 hide_a_2(-10)
 writeln("a = ", a)
 hide_a_3(a)
 writeln("a = ", a)

end-model 

During the compilation we get the error

Mosel: E-165 at (34,4) of `subrout.mos': Declaration of `a' hides a parameter.

This is due to the redefinition of a that is passed as an argument into procedure hide_a_3 and also appears in the declarations of this subroutine. We need to modify the definition of this procedure to correct this error, for example by renaming the subroutine argument:

 procedure hide_a_3(aa:integer) 

The program then results in the following output:

The program starts here.
a = 3
a = 6
Procedure hide_a_1: a = 7
a = 6
Procedure hide_a_2: a = -10
a = 6
Procedure hide_a_3: a = 15
a = 6

Variable number of arguments

A subroutine can be defined to take a variable number of arguments by stating a single argument name followed by the symbol ... as shown in the following code snippet (model subrout.mos).

! Subroutines with variable number of arguments
 function sumall(Values:...): integer
   returned:= sum(i in Values) i.integer
 end-function

 procedure showint(Optargs:...)
   forall(i as counter, v in Optargs)
     if v is integer: writeln("arg ", i, ": ", v.integer)
 end-procedure

 writeln("sum = ", sumall(1, 2, 3, 4, 5))

 showint(1.5,0,"abc",true,5)

which results in the following output:

sum = 15
arg 2: 0
arg 5: 5

The unique subroutine argument, Values or Optargs respectively in the example above, is of the type list of any (see Section Unions), when accessing the elements of this list we therefore need to state their expected type in order to be able to perform any operations on them.

Recursion

The following example (model lcdiv2.mos) returns the largest common divisor of two numbers, just like the example `Lcdiv1' in the previous chapter. This time we implement this task using recursive function calls, that is, from within function lcdiv we call again function lcdiv.

model Lcdiv2

 function lcdiv(a,b:integer):integer
   if a=b then
     returned:=a
   elif a>b then
     returned:=lcdiv(b,a-b)
   else
     returned:=lcdiv(a,b-a)
   end-if
 end-function

 declarations
   A,B: integer
 end-declarations

 write("Enter two integer numbers:\n  A: ")
 readln(A)
 write("  B: ")
 readln(B)

 writeln("Largest common divisor: ", lcdiv(A,B))

end-model

This example uses a simple recursion (a subroutine calling itself). In Mosel, it is also possible to use cross-recursion, that is, subroutine A calls subroutine B which again calls A. The only pre-requisite is that any subroutine that is called prior to its definition must be declared before it is called by using the forward statement (see Section forward below).

forward

A subroutine has to be `known' at the place where it is called in a program. In the preceding examples we have defined all subroutines at the start of the programs but this may not always be feasible or desirable. Mosel therefore enables the user to declare a subroutine separately from its definition by using the keyword forward. Equivalently to using this keyword, the subroutine can be declared in a declarations block. The declaration of of a subroutine states its name, the parameters (type and name) and, in the case of a function, the type of the return value. The definition that must follow later in the program contains the body of the subroutine, that is, the actions to be executed by the subroutine.

The following example (model qsort1.mos) implements a quick sort algorithm for sorting a randomly generated array of numbers into ascending order—please note that the implementation discussed here is merely provided as a programming example, we would generally recommend that you use the qsort routine of the Mosel module mmsystem in your Mosel programs. The procedure qsort that starts the sorting algorithm is defined at the very end of the program, it therefore needs to be declared at the beginning, before it is called. Procedure startqsort calls the main sorting routine, qsort. Since the definition of this procedure precedes the place where it is called there is no need to declare it (but it still could be done). Procedure qsort calls yet again another subroutine, swap.

The idea of the quick sort algorithm is to partition the array that is to be sorted into two parts. The `left' part containing all values smaller than the partitioning value and the `right' part all the values that are larger than this value. The partitioning is then applied to the two subarrays, and so on, until all values are sorted.

model "Quick sort 1"

 parameters
   LIM=50
 end-parameters

 forward procedure startqsort(L:array(range) of integer)
(! Equivalent form of declaration:
 declarations
   procedure startqsort(L:array(range) of integer)
 end-declarations
!)

 declarations
   T:array(1..LIM) of integer
 end-declarations

 forall(i in 1..LIM) T(i):=round(.5+random*LIM)
 writeln(T)
 startqsort(T)
 writeln(T)

! Swap the positions of two numbers in an array
 procedure swap(L:array(range) of integer,i,j:integer)
   k:=L(i)
   L(i):=L(j)
   L(j):=k
 end-procedure

! Main sorting routine
 procedure qsort(L:array(range) of integer,s,e:integer)
   v:=L((s+e) div 2)              ! Determine the partitioning value
   i:=s; j:=e
   repeat                         ! Partition into two subarrays
     while(L(i)<v) i+=1
     while(L(j)>v) j-=1
     if i<j  then
       swap(L,i,j)
       i+=1; j-=1
     end-if
   until i>=j
                                  ! Recursively sort the two subarrays
   if j<e and s<j: qsort(L,s,j)
   if i>s and i<e: qsort(L,i,e)
 end-procedure

! Start of the sorting process
 procedure startqsort(L:array(r:range) of integer)
   qsort(L,getfirst(r),getlast(r))
 end-procedure

end-model

The quick sort example above demonstrates typical uses of subroutines, namely grouping actions that are executed repeatedly (qsort) and isolating subtasks (swap) in order to structure a program and increase its readability.

The calls to the procedures in this example are nested (procedure swap is called from qsort which is called from startqsort): in Mosel there is no limit as to the number of nested calls to subroutines (it is not possible, though, to define subroutines within a subroutine).

Overloading of subroutines

In Mosel, it is possible to re-use the names of subroutines, provided that every version has a different number and/or types of parameters. This functionality is commonly referred to as overloading.

An example of an overloaded function in Mosel is getsol: if a variable is passed as a parameter it returns its solution value, if the parameter is a constraint the function returns the evaluation of the corresponding linear expression using the current solution.

Function abs (for obtaining the absolute value of a number) has different return types depending on the type of the input parameter: if an integer is input it returns an integer value, if it is called with a real value as input parameter it returns a real.

Function getcoeff is an example of a function that takes different numbers of parameters: if called with a single parameter (of type linctr) it returns the constant term of the input constraint, if a constraint and a variable are passed as parameters it returns the coefficient of the variable in the given constraint.

The user may define (additional) overloaded versions of any subroutines defined by Mosel as well as for his own functions and procedures. Note that it is not possible to overload a function with a procedure and vice versa.

Using the possibility to overload subroutines, we may rewrite the preceding example `Quick sort' as follows (model qsort2.mos).

model "Quick sort 2"

 parameters
   LIM=50
 end-parameters

 forward procedure qsort(L:array(range) of integer)
(! Equivalent form of declaration:
 declarations
   procedure qsort(L:array(range) of integer)
 end-declarations
!)

 declarations
   T:array(1..LIM) of integer
 end-declarations

 forall(i in 1..LIM) T(i):=round(.5+random*LIM)
 writeln(T)
 qsort(T)
 writeln(T)

 procedure swap(L:array(range) of integer,i,j:integer)
  (...)                        (same procedure body as in the preceding example)
 end-procedure

 procedure qsort(L:array(range) of integer,s,e:integer)
  (...)                        (same procedure body as in the preceding example)
 end-procedure

! Start of the sorting process
 procedure qsort(L:array(r:range) of integer)
   qsort(L,getfirst(r),getlast(r))
 end-procedure

end-model

The procedure startqsort is now also called qsort. The procedure bearing this name in the first implementation keeps its name too; it has got two additional parameters which suffice to ensure that the right version of the procedure is called. To the contrary, it is not possible to give procedure swap the same name qsort because it takes exactly the same parameters as the original procedure qsort and hence it would not be possible to differentiate between these two procedures any more.

Subroutine references

A subroutine reference is an entity that is able to store a reference to a procedure or a function. A subroutine reference is considered as undefined until it has been associated to an actual subroutine via an assignment; the value assigned to the entity must have a compatible type and will usually be the result of the 'reference to' operator -> to prevent calling of the operand. This association may be cancelled using reset. A subroutine reference can be used wherever the corresponding type is expected, in particular for an assignment that initializes another subroutine reference, or for specifying a callback routine (see the example in Section Branch-and-Cut).

The following example declares myfct as a reference to a function returning a real and expecting a real as parameter; this symbol is then used to hold and invoke the function div2. When a subroutine reference is assigned to a generic union entity the type needs to be indicated when calling the subroutine:

function div2(r:real):real
  returned:=r/2
end-function

declarations
  myfct: function(real):real        ! Subroutine reference
  u: any
  realfct=function(real):real       ! Subroutine type definition
end-declarations

myfct:=->div2
writeln("div2(10)=", myfct(10))     ! Output:  div2(10)=5

u:=->div2
! In order to call 'u' as a subroutine we need to indicate its type
writeln("div2(10)=", u.realfct(10)) 

Subroutine types can be used like any other types in the declaration of structured Mosel entities:

declarations
  L: list of function(real):real               ! List of subroutines
! or equivalently:
!  L: list of realfct
  arfct:array(string) of function(real):real   ! Array of subroutines
end-declarations

L:=[->cos,->sin,->arctan,->abs,->exp,->div2]
forall(i in [-1.0,0.5]) do
  write("i=", i)
  forall(f in L) write(f(i), " ")
  writeln
end-do

! Syntax for calling an element of an array of subroutines with arguments
arfct("cos"):= ->cos
writeln("cos(1)=", arfct("cos")(1))

Note that the Mosel compiler does not guarantee which routine is returned if the name of a subroutine refers to several implementations (i.e. the routine has been overloaded) and the context does not make it possible to select a particular version. In the example above, the abs routine has several versions (it is defined for integer and for real numbers), however, given that the list L is declared with the type 'function of real returning a real' the referene to the real-valued version of abs is added to the list.

Subroutines can also occur as return type of a function as is shown in the following code snippet (notice the use of isdefined to test whether the subroutine has returned a valid subroutine reference).

function choose(name:string):function(real):real
  case name of
    "cos": returned:= ->cos
    "abs": returned:= ->abs
    "div": returned:= ->div2
    else writeln("Unknown selection '", name, "'")
  end-case
end-function

fsel:=choose("cos")
if isdefined(->fsel) then
  writeln("cos(1)=", fsel(1))
end-if

fsel:=choose("error")
if not isdefined(->fsel) then
  writeln("no function selected")
end-if 

Executing this code will produce the following output:

cos(1)=0.5403023059
Unknown selection 'error'
no function selected