# OCLexec — Code generation from UML/OCL

These are some examples of UML/OCL specifications that OCLexec can generate code for. More examples can be found in the downloadable distribution.

## An Elementary Calculator

As a warm up, here is a toy OCL specification of a calculator:

`context Calculator::add(x: Integer):`

post: value = value@pre + x

context Calculator::subtract(x: Integer):

post: value = value@pre - x

context Calculator::multiply(x: Integer):

post: value = value@pre * x

context Calculator::divide(x: Integer):

post: value = value@pre.div(x)

context Calculator::squareRoot():

post: value * value = value@pre

The attribute `value`

represents the value stored in the calculator. Every operation specifies how the value in the post-state is related to the value in the pre-state. Note that the specification of the `squareRoot`

operation is declarative, i.e., it does not indicate how the post-value can be computed from the pre-value. Of course OCLexec can also execute operations like this.

## Graph Search

The following UML diagram with OCL annotations models a graph with a search operation.

`context Vertex::findPath(end: Vertex): Sequence(Vertex) post: result->at(1) = self post: result->at(result->size()) = end post: Sequence{1..result->size()-1} ->forAll(i | result->at(i).succ->includes(result->at(i+1)))`

The postconditions of the operation characterize valid paths in the graphs that are searched for. The first two postconditions specify that the first vertex on the path is the vertex the operation is called on and that the last vertex is the argument vertex, respectively. The third postcondition specifies that the entire path consists of adjacent vertices.

Code generated by OCLexec from this model can find paths in graphs with dozens of vertices in a few seconds.

## Some Problems in Job Scheduling

Now we discuss some specifications motivated in the context of job scheduling. See this paper for a deeper discussion of these examples.

The following UML diagram models a build tool.

A `Project`

comprises several `CompilationUnits`

. In general, the task of the build tool is to arrange all `CompilationUnits`

into adequate `CompilationJobs`

. A `CompilationJob`

designates an ordered sequence of `CompilationUnits`

that are to be processed in order to complete the job. The assignment of `CompilationUnits`

to `CompilationJobs`

may be driven by various considerations. In particular, there can be dependencies between `CompilationUnits`

, which is modeled by an association. Moreover, `CompilationUnits`

can have different `sizes`

.

### Even Distribution (Subset Sum)

As first example, we consider a plain optimization task that is representative for many similar ones with an operations research background. The goal is to achieve efficient parallel processing of `CompilationJobs`

by assigning `CompilationUnits`

to `CompilationJobs`

such that the longest execution time of any `CompilationJob`

is minimized and the entire process is completed as early as possible. This is accomplished by the operation `getBalancedCompilationJobs`

specified in the OCL code below, which returns a set of `CompilationJobs`

that arrange the `CompilationUnits`

of the `Project`

such that total execution time is minimized.

`context Project::getBalancedCompilationJobs(n: Integer):`

Set(CompilationJob)

post allUnitsReturned:

result->collect(compilationUnits)->asSet()

= compilationUnits@pre

post jobLimitMet: result->size() <= n

minimize:

let

jobSizes: Bag(Integer)

= result->collectNested(job |

job->compilationUnits

->collectNested(size@pre)->sum())

in

jobSizes->max()

modifies only: compilationUnits::compilationJob

The parameter `n`

indicates the maximal number of `CompilationJobs`

created and would usually correspond to the number of CPUs available. The postcondition `allUnitsReturned`

specifies that the set of `compilationUnits`

included in the returned `CompilationJobs`

are exactly the `CompilationJobs`

of the `Project`

for which the operation is called. The postcondition `jobLimitMet`

limits the number of returned `CompilationJobs`

to the argument passed to the operation. In this operation contract, most of the behavior is specified in the `minimize`

clause. In this objective function, we first compute the total sizes of all returned `CompilationJobs`

by applying `collectNested`

and `sum`

. We use `collectNested`

here in order to make explicit for readability that no flattening is performed. Then the value of the objective function is defined to be the maximum of all total job sizes, which is an estimate of the total execution time. Finally, the `modifies only`

clause specifies that the attribute `compilationJob`

may only be changed for the `compilationUnits`

belonging to the `Project`

for which the operation is called and that the values of all other attributes may not be affected by the operation.

This problem of optimizing parallel execution is NP-hard since the subset sum problem can be reduced to it. Thus, even a relatively simple implementation is likely to be substantially more complex than this OCL specification.

OCLexec is efficient enough about to deal with scenarios with up to about 5 compilation units.

### Topological Sorting

The task of the next operation `getOrderedCompilationJobs`

that we specify is to find a compilation order that respects the dependencies of the `CompilationUnits`

. In other words, we desire a topologically sorted sequence of the compilation units. The specification is shown below.

`context Project::getOrderedCompilationJobs(): CompilationJob`

post allUnitsReturned:

(not result.oclIsUndefined())

implies

result.compilationUnits->asSet()

= compilationUnits@pre

post resultSorted:

(not result.oclIsUndefined())

implies

let

units: OrderedSet(CompilationUnit)

= result.compilationUnits

in

Sequence{2..units->size()}

->forAll(i | Sequence{1..i-1}

->forAll(j | units->at(j).dependsOn@pre

->excludes(units->at(i))))

minimize: if result.oclIsUndefined() then 1 else 0 endif

modifies only: compilationUnits::compilationJob

An interesting aspect of this operation is that there is no valid compilation order if the dependency graph has a cycle. In this case the operation should return `null`

. The postcondition `allUnitsReturned`

specifies that if the result is not `null`

, i.e., a solution exists, then the set of `CompilationJobs`

returned are exactly the `CompilationJobs`

of the `Project`

. The postcondition `resultSorted`

states that, if the result is not `null`

, no `CompilationUnit`

depends on another unit occurring later in the returned sequence.

This operation does not solve an optimization problem at first sight. The `minimize`

clause of the specification expresses that the operation should return a non-null result whenever possible, i.e., when it is not excluded by the postconditions. The presence of the objective function is essential for the specification to be complete, since otherwise an implementation that always returns `null`

even if a valid compilation order exists would satisfy the specification. This technique of preferring non-null results by means of an objective function is applicable in general to problems that do not always have a solution.