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.