Bilih Priyogi
email: bilih.priyogi31@ui.ac.id

Nungki Selviandro
email: nungki.selviandro21@ui.ac.id

Zainal A Hasibuan
email: zhasibua@cs.ui.ac.id

Mubarik Ahmad
email: mubarik.ahmad@yarsi.ac.id

Image Clustering using Multi-Visual Features

Keywords: Image Clustering, Visual Feature, K-Means Clustering, 1

This paper presents a research on clustering an image collection using multi-visual features. The proposed method extracted a set of visual features from each image and performed multi-dimensional K-Means clustering on the whole collection. Furthermore, this work experiments on different number of visual features combination for clustering. 2, 3, 5 and 7 pair of visual features chosen from a total of 8 visual features used, to measure the impact of using more visual features towards clustering performance. The result show that the accuracy of multi-visual features clustering is promising, but using too many visual features might set a drawback.

Introduction

There is an enormous growth in image collection all around the world, especially in the past few years with the emerging trend of social media. Many social media such as Facebook, Twittter, Path, and Instagram allow people to publish their own generated image, out to the world. Not to mention images produced from other areas such as from commerce, government, scientific and medical field. It is believed that the collections of data in the form of image contain precious information, as well as textual data does.

However, it is hard to obtain precious information from all of those image collections without an effective and efficient technique for image retrieval. Content-Based Image Retrieval (CBIR) address this issue by using visual contents of an image such as color, shape and texture, to decides the similarity and differences between images. Thus, we can explore and analyze images in collection based on its visual feature.

Furthermore, retrieving, exploring and analyzing from a huge amount of images will be a challenging problem. Thus, we need such method to organize the image in a way that enables efficient image retrieval. One of the proposed technique is clustering [START_REF] Chary | Similar Image Searching from Image Database using Cluster Mean : Sorting and Performance Estimation[END_REF] [2] [START_REF] Yildizier | Integrating Wavelets with Clustering and Indexing for Effective Content-Based Image Retrieval[END_REF], which is useful to discover the patterns and characteristics stored in image collection by dividing them into set of clusters. Images in each cluster share similar patterns, but very dissimilar to images in other clusters. In addition, [START_REF] Chary | Similar Image Searching from Image Database using Cluster Mean : Sorting and Performance Estimation[END_REF] also suggest that clustering could be used for faster image retrieval by minimizing the search area only in cluster which the image belong to, rather than exhaustively searching an entire image collection.

Another motivation of this research is the possibility of image-language semantic, which based on the idea of finding semantically related text in visually-similar images. This idea offers alternative way of exploring relationship among term's meaning across languages that could be used to build thesaurus, dictionaries, question answering modules etc. The argument is that similar images might contain text caption that is possibly related. For instance if we can recognize the similarity among images in Figure 1, then we might draw inferences that word 'beach' is related with 'pantai' and 'sanur'. Moreover, with some work on the reasoning part, we also can infer that 'sanur' is a 'beach' and 'pantai' is translation of 'beach' in Indonesian language.

Fig. 1.Image-Language Semantic

Furthermore, this research also wants to address the phenomenon called "curse of dimensionality", in which using more than one visual feature when clustering might improve the performance. This performance improvement will occur until certain number of features, or threshold, when the peak performance of multi-dimensional clustering will be obtained. Any features addition or increase in dimensionality beyond the threshold will suffer the clustering accuracy.

Proposed Method

Figure 2 illustrates the overview of proposed method in this research. For the sake of simplicity, the illustration only shows the clustering performed on image collection based on 3 visual features. This research also performed clustering based on 1, 2, 5 and 7 visual features to measure the impact of using more visual features, which follows similar process.

Color Layout

This descriptor extracts information of color spatial-distribution in an image [START_REF] Ohm | The MPEG-7 Color Descriptors[END_REF]. It divides an image to a 8x8 matrix and applies Discrete Cosine Transform based on YCbCr color space (Yellow, Chromatic blue, Chromatic red). This descriptor is not affected with image dilatation and able to distinguish a sketch image from one another.

Edge Histogram

This descriptor extracts local edge distribution in an image to a histogram [START_REF] Won | Efficient Use of MPEG-7 Edge Histogram Descriptor[END_REF]. Edge represents frequency and directionality of color changes on image. It divides an image into number of blocks, apply digital filtering and classify each block into one out of five edge categories. This descriptor is not affected with image rotation or translation.

FCTH (Fuzzy Color and Texture Histogram)

This descriptor extracts same information as CEDD does [START_REF] Chatzichristofis | FCTH : Fuzzy Color and Texture Histogram, a Low Level Feature for Accurate Image Retrieval[END_REF], but the difference is the extraction result size of FCTH 30% bigger than CEDD and the texture extraction process. FCTH extracts texture information by applying Haar transform to each of image blocks and classifying them with a fuzzy texture linking system. This descriptor also persists regardless of images distortion.

Gabor

This descriptor explores texture feature from an image by applying a series of linear filter in edge detection process. An image is processed through a set of Gabor filter which have different scale and orientation, then the average and standard deviation compared to original image is calculated. Gabor descriptor has many similarities with human visual system and proven to be capable of distinguishing image based on texture information [START_REF] Yang | Comparing SIFT Descriptors and Gabor Texture Features for Classification of Remote Sense Imagery[END_REF].

Scalable Color

This descriptor extracts statistical color information of an image in HSV color space into a histogram. Each bin in histogram represents number of pixels containing certain color. The extraction process also involving a Haar transform and a set of low-pass and high-pass filter [START_REF] Ohm | The MPEG-7 Color Descriptors[END_REF].

Tamura

This descriptor exploits texture feature in an image, such as coarseness, contrast, directionality, line-likeness, regularity and roughness [START_REF] Tamura | Textual Features Corresponding to Visual Perception[END_REF]. Now, only the first three characteristics implemented because considered to be the most important part in human vision. Coarseness related to size of texture element, contrast related to image quality and directionality related to orientation of texture.

Experiments

For the experiments, an image dataset was obtained from the website wang.ist.psu.edu/iwang/test1.tar. In this scheme, 50 images from 5 categories (each category contain 10 images) are tested against the proposed method. The 5 categories are bus, dinosaur, flower, horse, and mountain. Each image named with its correspondence categories in order to ease the process of accuracy measurement. The accuracy measurement based on the number of images that is properly clustered.

An image said to be in proper cluster if its category is the dominant category belong to the cluster. For example, cluster 1 occupied by 10 images that is 8 bus images, 1 flower image and 1 horse image, then it can be said that the cluster is a bus' cluster and there is 8 images properly clustered into this cluster.

If somehow there are two dominant categories, only one of them will be regarded as dominant category in a cluster by alphabetical order. For example in cluster 2 occupied by 5 horse images, 5 flower images and 1 mountain image, then flower will be picked as dominant category by alphabetical order. It should also be noted that either if we chose horse as dominant category, there still be a total of 5 images properly clustered. Each experiment's run tested a combination of visual feature for clustering purpose. To simplify the scope of research and as there is prior information of the number of categories existed in dataset, the k parameter in K -Means clustering is set to 5. So, each run will always resulting 5 clusters and the accuracy of it can be calculated as:

=

The total of all images clustered is the size of dataset, which are 50.

Results

Table 1 shows the overall results of experiments per clustering type, which this research used combination of 2, 3, 5 and 7 pair out of 8 visual features. In addition, clustering with only 1 feature also performed to have a thorough comparison of the advantage of high dimensionality clustering. The experiments take on all possible combination of visual features in each clustering type, which are 8 for 1D clustering, 28 for 2D clustering, 56 for 3D clustering, 56 for 5D clustering and 8 for 7D clustering.

The highest accuracy obtained by 3D clustering type, which uses CEDD-EdgeHistogram-ColorLayout as the visual feature combination. These three visual features evidently the best combination to distinguish visually similar images from another images. The lowest accuracy occurred in 3D clustering that uses visual feature combination of CEDD-EdgeHistogram-ScalableColor (see appendix).

Based on Table 1, the average accuracy of all runs in each clustering dimension generally decreasing when the number of visual feature used for clustering is increasing, except for 2D clustering. This fact shows the "curse of dimensionality" existence, which the threshold or number of features combination to get the best average accuracy would be 2.

If we look at other perspective, highest accuracy obtained, it would be fair to say that the "curse of dimensionality" also exist with the threshold would be 3. This means that using multi visual features would improve clustering performance until certain number of dimension. Nevertheless, employing too many visual features beyond the dimension's threshold might raise some confusion instead of clarity when distinguishing and classifying an image. There are 18 runs with accuracy equal or more than 0.9 as shown in Table 2. Most of them obtained with 3D clustering (9 out of 18), 5 of them used 2D clustering and 4 used 5D clustering. This shows that 3D clustering give most of the best clustering performance in this research.

Moreover, by taking a close look into images in each cluster result, it was found that the dinosaur category is the easiest category to cluster. Table 3 shows result of the proposed method which able to cluster the dinosaur images perfectly in 20 runs out of 56 -3D clustering runs done. Another category that ever been clustered perfectly in the experiments are horse and mountain category.

Conclusions and Future Possibilities

Based on the experiment results, clustering with multi visual features could improve clustering performance compared to using only one visual feature. Nevertheless, using too many visual features in combination might lower the accuracy of the result. In this research scope, combination of CEDD, Edge Histogram and Color Layout proven to be the most promising set of visual feature to cluster the image collection. Different visual extraction tools and another type of visual features might be worth to try in the future. Finding the right combination of type and number of visual feature for clustering might increase the chance to distinguish one image from another in more precise manner. Furthermore, finding the right number of clusters for K-Means clustering initialization is also a problem when dealing with real-world image collection which prior knowledge of clusters existed is unknown.

Fig.

  Fig. 2.Proposed Method Overview

Fig. 3 .

 3 Fig. 3.Image Dataset

  Gabor-Tamura-ScalableColor-ColorLayout-0.56 5D -CEDD-Tamura-EdgeHistogram-ScalableColor-ColorLayout-0.56 5D -FCTH-Gabor-EdgeHistogram-ScalableColor-ColorLayout-0.7 dinosaur; 5D -FCTH-Gabor-Tamura-EdgeHistogram-ColorLayout-0.56 5D -FCTH-Gabor-Tamura-EdgeHistogram-ScalableColor-0.52 5D -FCTH-Gabor-Tamura-ScalableColor-ColorLayout-0.56 5D -FCTH-Tamura-EdgeHistogram-ScalableColor-ColorLayout-0.56 5D -Gabor-Tamura-EdgeHistogram-ScalableColor-ColorLayout-FCTH-Gabor-Tamura-EdgeHistogram-ScalableColor-ColorLayout-0.56

  2.Proposed Method OverviewVisual feature extraction of each image yields a value to represent an image in the visual feature's context and distinguish one image from another. Then based on visual information, image clustered to organize visually-similar image in the same cluster. K-Means clustering algorithm is used to cluster images based on value from the extraction process of different visual features combination.

	In other words, the
	clustering done in high dimensional space (2, 3, 5 and 7) in which each image
	considered as a point with coordinate of the n-axis (n = {2, 3, 5, 7}). These are the K-
	Means algorithm used in this research :
	1. Choose number of cluster output desired, k.
	2. Randomly make k clusters and calculate center point of each cluster, or randomly
	choose k points as initial center point.
	3. Assign each point to cluster with nearest center point.
	4. Re-calculate the center point of each cluster.
	5. Repeat step number 3 and 4 until the convergence criterion achieved (there is no
	membership change in each cluster or until some number of iteration)
	There are 8 descriptors used to extract visual features in this research, this choice
	based on the all available and usable descriptors in tools used. The tools used for
	visual extraction is LIRE (Lucene Image Retrieval) java-based API. Here are some
	overviews of descriptors used:
	1. Auto Color Correlogram
	This descriptor extracts the color spatial correlation information in image [5]. It is
	known for its simple computation and small extraction result size. This descriptor
	is not affected regardless of changes in background or point of view.
	2. CEDD (Color and Edge Directivity Descriptor)
	This descriptor extracts a combination of color and texture from an image into one
	histogram [6]. The color information extracted based on HSV (Hue, Saturation,
	Values) color space, whereas texture information extracted by classifying each
	pixel into one or more texture category. CEDD uses relative modest amount of
	computing resource in extraction process comparer to MPEG-7 descriptors
	(Scalable Color, Color Layout, Edge Histogram etc.).

Table 1 .

 1 Experiment Results per Clustering Type

	Type	Total Combination	Highest Accuracy	Lowest Accuracy	Average Accuracy
	1D	8	0.88	0.54	0.688
	2D	28	0.94	0.52	0.691

Table 2 .

 2 Run Result with Accuracy >= 0.9

	Type	Features	Accuracy
	3D	CEDD-EdgeHistogram-ColorLayout	0.98
	5D	AutoColorCorrelogram-CEDD-Gabor-EdgeHistogram-ColorLayout	0.96
	5D	CEDD-FCTH-Gabor-EdgeHistogram-ColorLayout	0.96
	3D	FCTH-EdgeHistogram-ColorLayout	0.96
	3D	AutoColorCorrelogram-EdgeHistogram-ColorLayout	0.94
	5D	AutoColorCorrelogram-FCTH-Gabor-EdgeHistogram-ColorLayout	0.94
	3D	AutoColorCorrelogram-Gabor-ColorLayout	0.94
	2D	EdgeHistogram-ColorLayout	0.94
	2D	Gabor-ColorLayout	0.94
	3D	Gabor-EdgeHistogram-ColorLayout	0.94
	3D	AutoColorCorrelogram-CEDD-EdgeHistogram	0.92
	2D	CEDD-EdgeHistogram	0.92
	3D	CEDD-FCTH-ColorLayout	0.92
	2D	FCTH-EdgeHistogram	0.92
	5D	AutoColorCorrelogram-CEDD-FCTH-Gabor-ColorLayout	0.9
	2D	AutoColorCorrelogram-FCTH	0.9
	3D	CEDD-Gabor-ColorLayout	0.9
	3D	FCTH-Gabor-ColorLayout	0.9

Table 3 .

 3 Perfectly Clustered Categories per Clustering Type

	Type	Perfectly Clustered
	1D	dinosaur (2x), horse (1x)
	2D	dinosaur (12x), horse(2x)
	3D	dinosaur (20x), horse(7x), mountain (1x)
	5D	dinosaur (15x), horse(5x)
	7D	dinosaur (1x)


Josef Kufner
email: kufnejos@fel.cvut.cz

Radek Mařík

Self-generating Programs -Cascade of the Blocks

When building complex applications the only way not to get lost is to split the application into simpler components. Current programming languages, including object oriented ones, offer very good utilities to create such components. However, when the components are created, they need to be connected together. Unluckily, these languages are not a very suitable tool for that. To help with composition of the components we introduce cascade -a dynamic acyclic structure built from blocks, inspired by the Function Block approach. The cascade generates itself on-the-fly during its evaluation to match requirements specified by input data and automatically orders an execution of the individual blocks. Thus the structure of a given cascade does not need to be predefined entirely during its composing/implementation and fixed during its execution as it is usually assumed by the most approaches. It also provides a real-time and fully automatic visualization of all blocks and their connections to ease debugging and an inspection of the application.

Introduction

In last 30 years object oriented languages have developed to state, where they are a pretty good tool for creating components, but when it comes to composing these components together, the situation is far from perfect.

There are not many successful and widely used tools or design patterns to compose applications. Probably the most known approach, which is well established in the field of programmable logic controllers, is Function Blocks [START_REF] John | IEC 61131-3: Programming Industrial Automation Systems: Concepts and Programming Languages, Requirements for Programming Systems, Decision-Making AIDS[END_REF], and its simplified variant, used by unix shells, known as Pipes and Filters. Despite these approaches are decades old [START_REF] Ritchie | The evolution of the unix time-sharing system[END_REF], they are used in only few specific areas, and there is very low development activity in this direction.

A basic idea of both Function Blocks and Pipes and Filters is to split a complex application to simpler blocks, and then connect them together using well defined and simple interfaces. This adds one level of abstraction into the application and simplifies significantly all involved components. Simpler components are easier to develop. Well defined interfaces improve reusability of the components. In total, it means faster and more effective development.

From other point of view the connections between blocks can be easily visualized in a very intuitive way and conversely these connections can be specified using a graphical editor. This significantly lowers programming skill requirements and allows non-programmers to build or modify applications if a suitable GUI tool is provided.

A main limitation of Function Blocks is that blocks are often connected together in advance by a programmer and this structure remains static for the rest of its life time. Therefore, an application cannot easily adapt itself to changing requirements and environment, it can usually change only few parameters. The next few sections will present how to introduce dynamics into these static structures and what possibilities it brings.

In this paper we introduce cascade, a dynamic acyclic structure built of blocks. The next two sections [START_REF] Ritchie | The evolution of the unix time-sharing system[END_REF][START_REF] Cormen | Introduction to Algorithms[END_REF] describe the blocks and how they are composed into a cascade, including a description of their important properties. Then, we explain the most interesting features of the cascade in Section 4. Finally, in the last two sections [START_REF] Mierswa | Yale: Rapid prototyping for complex data mining tasks[END_REF][START_REF] Konstantinides | The Khoros software development environment for image and signal processing[END_REF] a practical use of cascade is described and it is also compared to existing tools and approaches.

Creating the blocks

As mentioned above, object oriented languages are very good tools to create components. So it is convenient to use them to create blocks.

In cascade a block is atomic entity of a given type (class), which has named inputs and outputs, each block instance is identified by unique ID, and can be executed. During execution the block typically reads its inputs, performs an action on received data, and puts results to its outputs.

The symbol used in this paper to represent a block is in Figure 1a. There are an ID and a block type in the header, named inputs on the left side and outputs on the right. A color of the header represents the current state of the block. At the bottom a short note may be added, for example a reason of failure. The block is implemented as a class, which inherits from the abstract block class. This abstract class implements a required infrastructure to manage inputs, outputs and execution of the block. Execution itself consists of calling main method of the block class.

Each block instance is executed only once. During its lifetime block goes through a few states as presented in Fig. 1b. It starts in the state queued, where waits for execution. Then it enters state running, and when execution is completed, one of the final states zombie (success), disabled, or failed is entered. In the final state the block exists only to maintain its outputs for other blocks 1 . This means that the block can process only one set of input data. To process another data set, a new block instance must be created. But because the lifetime of the block ends before another input data arrive, it causes no trouble (this will be explained later).

Connecting the blocks

To create something interesting out of the blocks, we need to connect them together. These connections are established by attaching an input of the second block to the output of the first block -the connections are always specified at inputs, never at outputs. So the input knows where its value came from, but the output does not know whether it is connected somewhere at all. Transfers of values over the earlier established connections are also initiated by the inputs. That means the outputs are passive publishers only. By connecting blocks together a cascade is being built.

The cascade is a directed acyclic graph composed of blocks, where edges are connections between outputs and inputs of the blocks.

When a block is inserted into cascade, its inputs are already entirely defined. It means, that a connection to another block or a constant is assigned to each of its inputs. At this moment, connections are specified using block ID and output name. Later, when block is being executed, actual block instances assigned to these block IDs are resolved, so the specified connections can be established and values transferred from outputs to inputs. Thanks to that, it does not matter in which order blocks are inserted into cascade, as long as there are all required blocks present before they need to be executed.

Evaluation

Evaluation of the cascade is a process, in which the blocks are executed in a correct order, and data from the outputs of executed blocks are passed to the inputs of the blocks waiting for execution.

By creating a connection between two blocks, a dependency (precedence constraint) is defined, and these dependencies define the partial order, in which blocks need to be executed. For single threaded evaluation, a simple depth-firstsearch algorithm with cycle detection can be used to calculate topological order compatible with given partial order [START_REF] Cormen | Introduction to Algorithms[END_REF].

Since DFS algorithm requires a starting point to be defined, selected blocks (typically output generators2 ) are enqueued to a queue, when inserted into cascade. Then the DFS is executed for each block in the queue. If a block is not enqueued, it will not be executed, unless some other block is connected to its outputs. This allows preparing set of often, but not always, used blocks and let them execute only when required. Evaluation of the cascade ends, when execution of the last block is finished and the queue is empty.

These features relieve the programmer from an explicit specification of execution order, which is required in traditional procedural languages.

Visualization

It is very easy to automatically visualize connections between blocks. Once cascade evaluation is finished, its content can be exported as a code for Graphviz 3 , which will automatically arrange given graph into a nice image, and this generated image can be displayed next to results of the program with no effort. It is a very useful debugging tool.

Note that there is no need for a step-by-step tracing of cascade evaluation, since the generated image represents the entire process, including errors and presence of values on connections.

For example, Figure 2 shows a cascade used for editing an article on a simple web site. An article is loaded by the block load, then is passed to the block form, which is displayed to user by the block show_form. Because form has not been submitted yet, the block update, which will store changes in the article, is disabled (a grey arrow represents false or null value). This figure was rendered by Graphviz and similar figures are generated automatically when creating web sites with a framework based on the cascade (see section 6).

Basic definitions

It is necessary to define few basic concepts and a used notation, before a behavior of cascade can be described in detail.

A block name in the text is written using monospaced font, for example A. An execution of the block A starts with an event A (i.e. begin of the execution) and ends with an event Ā (i.e. end of the execution).

During the event A the main method of the block is called. Within the main method block reads its inputs, performs an operation on received data, and sets its outputs. During the event Ā cascade performs all requested output forwarding (see section 4.4) and the block execution is finished. The block itself performs nothing at this point.

Because any execution of a block must begin before it ends, a trivial precedence constraint is required for each block:

A ≺ Ā (1)

Automatic parallelization

One of the first questions usually asked after a short look at the cascade is whether the blocks can be executed in parallel. A short answer is "yes, of course" and in this section we try to explain how straightforward it is. Let there are blocks A, B and C, where C is connected to some outputs of blocks A and B, as displayed in Figure 3. Because the begin of block execution precedes its end, trivial precedence constraints are defined:

A ≺ Ā, B ≺ B, C ≺ C (2)
Due to the connections, execution of the blocks A and B must be finished before execution of C begins:

Ā ≺ C, B ≺ C (3)
When this cascade is evaluated in single thread, blocks have to be executed in a topological order, which is compatible with partial order defined by precedence constraints (2) and (3). Assuming non-preemptive execution of the blocks, there are two compatible orders:

A ≺ Ā ≺ B ≺ B ≺ C ≺ C (4) B ≺ B ≺ A ≺ Ā ≺ C ≺ C (5)
Both ( 4) and ( 5) will give exactly the same results, because blocks A and B are completely independent. Therefore these two blocks can be executed in parallel with no trouble:

A ≺ Ā B ≺ B ≺ C ≺ C (6)
A naive implementation of a parallel execution can be done by spawning a new thread for each block, and using a simple locking mechanism to postpone execution of blocks with unsolved dependencies. More efficient implementations may involve a thread pool and per-thread block queues for solving dependencies. Since cascade is being used to generate web pages, the block-level parallelization was not investigated any further, because all web servers implement parallelization on per-request basics.

Growing cascade

So far, everything mentioned here is more or less in practical use by various tools, especially in data mining, image processing and similar areas. What makes cascade unique, is the ability to grow during the evaluation.

When block is being executed, it can also insert new blocks into cascade. Inputs of these blocks can be connected to the outputs of any other blocks (as long as circular dependencies are not created) and it can be enqueued to the queue for execution. The algorithm described in section 3 will handle these new blocks exactly the same way as previous blocks, because it iterates over the queue and the new blocks will be enqueued there before the enqueuing block is finished.

Namespaces

To avoid collisions between block IDs, each block inserts new blocks into its own namespace only. These namespaces are visualized using a dashed rectangle with an owner block ID under the top edge of the namespace rectangle.

In traditional languages like C namespaces are used to manage visibility (scope) of local variables, where code located outside of a namespace cannot access a variable defined inside this namespace, but the inner code can reach global variables. However the global variables can be hidden by local variables.

The same approach is used in the cascade with a small difference -it is possible to explicitly access content of a namespace from outside, so connections across the namespaces can be made with no limitation.

To identify block other namespace, a dot notation is used. For example block B in the namespace of block A in the root namespace is referred as .A.B (see Figure 4b). If there is no leading dot, the first block is searched in the namespace of current block and all its parent namespaces up to the root. By specifying additional blocks it is possible to enter namespaces of other and completely unrelated blocks.

Since the primary purpose of namespaces is to avoid collisions in IDs, there is no reason to deny connections from the blocks outside of the namespace (see block D in Figure 4b). This allows to extend existing applications by attaching additional blocks without need to change the application.

Dependencies during the growth

The secondary purpose of the namespaces is to help handling dependencies on blocks that are not yet present in the cascade.

Take a look at Figure 4a. The block D is connected to a so far nonexistent block C inside the namespace of the block A, and block A has not been executed yet. In this moment, the only known precedence constraint is C ≺ D and because there is no connection between A and D, block D could be executed before A. But that would end up with a "block C not found" error.

Since the only block, which can insert blocks into namespace of the block A, is the block A, additional precedence constraint can be introduced: Each block depends on its parent (creator). Therefore cascade in Figure 4a contains following precedence constraints:

Ā ≺ C, C ≺ D (7)
And because block C is not present yet, the only compatible topological order is:

A ≺ Ā ≺ D ≺ D (8)
Block A inserts blocks B and C into the cascade during its execution and additional precedence constraints are created:

B ≺ C, Ā ≺ C, Ā ≺ B ( 9
)
Note that Ā ≺ C is there for the second time, because of the connection between blocks A and C. And constraint Ā ≺ B is already fulfilled, because block A has been executed already. Now, after the block A is finished, the cascade contains new blocks and new precedence constraints, so new topological order must be calculated before a next block is executed. The only topological order compatible with [START_REF] Sohrabi | Htn planning with preferences[END_REF] and ( 9) is:

A ≺ Ā executed ≺ B ≺ B ≺ C ≺ C ≺ D ≺ D queued (10)

Safety of the growth

It is not possible to break an already evaluated part of the cascade by adding new blocks. Reason is fairly simple -the new blocks are always appended after the evaluated blocks. That means the new precedence constraints are never in conflict with already existing constraints, and the new topological order is always compatible with the old one.

Each block is executed only after execution of all blocks it depends on. And because connections are specified only when a block is inserted into the cascade, the already executed part of the cascade cannot be modified. It also means that all precedence constraints in the executed part of the cascade have been fulfilled.

When inserting a new block, there are two kinds of connections which can be created: a connection to an already executed block, and connection to enqueued or missing block. When connected to the already executed block, any new precedence constraint is already fulfilled. When connected to the enqueued or missing block, the order of these blocks can be easily arranged to match the new constraints -the situation is same as before execution of the first block.

For example, the only difference between topological orders ( 8) and ( 10) is in added blocks B and C, thus the relative order of all actions occurring in ( 8) is same as in (10).

Nesting of the blocks and output forwarding

The basic idea of solving complex problems is to hierarchically decompose them into simpler problems. Function call and return statement are the primary tool for this decomposition in λ-calculus and all derived languages (syntactical details are not important at this point). The function call is used to breakdown a problem and the return statement to collect partial results, so they can be put together to the final result. But the cascade evaluation is one-way process. The entire concept of return value makes no sense here. Everything in the cascade goes forward and never looks back. Also there is no stack in the cascade where return address could be stored, so even if something would want to return a result, it has no chance of knowing where to.

To allow a hierarchical problem decomposition in the cascade, a slightly different tool was created -output forwarding. When block solves some problem, it presents results on its outputs. When block delegates solving to some other blocks, the results are on their outputs. To achieve the same final state as before, the results must be transferred to the original outputs of the delegating block. This schema exhibits similar behavior as the return statement.

From other point of view, there is no need to transfer result values back, if all connections are redirected to the forwarded outputs. Both approaches are equivalent and they both preserve all properties of the cascade mentioned earlier.

For example, let block A perform a complex task and block D display result of this task -see Figure 5. Block A inserts blocks B and C into the cascade, and passes a parameter from its input to the input of the block B and then collects a result from block C, which received a partial result from the block B. The final result is then published on an output of the block A. Figure 5 presents this solution as it is usual in λ-calculus based languages.

The cascade is a flat structure and does not allow nesting of the blocks. It emulates this hierarchy using namespaces, but all blocks are in the flat space. Therefore, blocks B and C are inserted next to the block A, as presented in Figure 6.

Note that output forwarding can be chained over multiple outputs. For example some other blocks could request forwarding of the output of the block A in Figure 6. In such cases output forwarding is solved recursively with no trouble.

Output forwarding adds exactly the same precedence constraint as any other connection between the blocks. The situation here is almost the same as on Figure 4b. When the value copying approach is used, the output forwarding adds the following constraint:

C ≺ Ā (11)
This is because all connected blocks are tied to the Ā event, so it is easier to delay this event until dependencies are solved. If the second (redirecting) ap- proach is used, the situation would be exactly the same as presented in Figure 7, but an implementation of this transformation may be too complicated. All constraints in the example cascade in Figure 6 are:

.A A in1 out1 in2 out2 B in1 out in2 C in1 out in2 D in1 out in2
Ā ≺ B, Ā ≺ C, B ≺ C, Ā ≺ D, C ≺ Ā
And the compatible topological order is:

A ≺ B ≺ B ≺ C ≺ C ≺ Ā ≺ D ≺ D (12)

Semantics of the output forwarding

Using the output forwarding a block says to the cascade: "When I'm done, set my output to a value which is on that output of that block." From a block's point of view the output forwarding is exactly the same process as setting a value to an output. Only difference is in specifying what value will be set -output forwarding uses a reference instead of a value. The namespaces and the output forwarding were both designed to allow a hierarchical decomposition of a problem, but they are completely independent tools in contrast to a function call and a return statement in λ-calculus based languages. And since the output forwarding is not limited to any particular namespace, it allows creation of a very unusual use cases, where the "return values" can be picked up anywhere in the cascade.

Comparison with other approaches

Probably the most similar approach to the cascade is Function Block programming [START_REF] John | IEC 61131-3: Programming Industrial Automation Systems: Concepts and Programming Languages, Requirements for Programming Systems, Decision-Making AIDS[END_REF], which has a very long history in industrial automation to program PLCs 4 . The main difference from the cascade is that blocks and connections between them are static. The connections are left unchanged as long as the programmer does not upload a new version of software into PLC. The second difference is in data transmitted via inputs and outputs. In the cascade once output is set, it stays constant forever. But in Function Blocks it is a stream of values.

Various data processing tools like Orange [START_REF] Curk | Microarray data mining with visual programming[END_REF], Khoros Cantata [START_REF] Konstantinides | The Khoros software development environment for image and signal processing[END_REF], and Rapid Miner [START_REF] Mierswa | Yale: Rapid prototyping for complex data mining tasks[END_REF] adopted the function blocks approach with some modifications. But the basic difference still stands -all these tools use a static structure built from blocks by the programmer.

λ-calculus differs from the cascade in the semantics of a return statement and in a heavy use of a stack. Because there is no stack in the cascade, the return statement is thrown away and replaced by the output forwarding mechanism, which has a slightly different semantics, but it can be used to achieve the same goals.

Cascade exhibits a number of shared features with Hierarchical Task Networks (HTN) planning [START_REF] Sohrabi | Htn planning with preferences[END_REF]. HTN planning provides a much more sophisticated approach including backtracking and different constraint mechanisms, such as constraint refinement, constraint satisfaction, constraint propagation, etc. Cascade trades these advanced methods with an execution speed. The fast execution is achieved by the elimination of decomposition alternatives.

The preference calculus based on properties of partial order relations forms a foundation of dependency trees heavily used in scheduling theory [START_REF] Rasconi | SEaM: analyzing schedule executability through simulation[END_REF].

A dependency injection is a software design pattern used to ease dependencies in the code [START_REF] Schwarz | Seuss: Decoupling responsibilities from static methods for fine-grained configurability[END_REF]. A basic idea is in a separation of tool users (code) from creators (factory) of the tool (object), so the creators can be easily replaced. In the cascade, this approach is very natural to use, since it is easy to wrap the creator into a common block and let users connect to this block and retrieve the tool. Thanks to the embedded visualization of the cascade it is very easy to track these dependencies in an application.

Real world application

Web framework

The cascade serves as a core of a push-style web framework written in PHP, where cascade takes a place of a controller (as in MVP pattern). Since a cascade does not have any own inputs and outputs, specialized blocks are used as a connectors to receive input data from a HTTP request and to pass response data into a template engine (view). Processing of any HTTP request is split into two stages. During the first stage the cascade is evaluated and response data are prepared as a result. In the second stage the template engine generates a final web page using the prepared data.

When a development mode is enabled, each web page contains automatically generated visualization of a cascade used to create that page (see Section 3.2), so the debugging tool is always at hand. Also a simple profiler is embedded into the framework. An average time needed to evaluate a cascade in real applications (ca. 20-40 blocks per page) is approximately 30 ms and an overhead of the cascade is less than 3 ms of that time, which is as good as widely used web frameworks.

Modular applications

Extensible applications typically declare places, where they can be extended, which is usually done using hooks or virtual methods. The cascade uses different approach. It offers user a set of blocks and it is up to him what he will build. And when there is some special need, which cannot be satisfied using available blocks, an additional set of blocks shall be created.

The cascade introduces an unified mechanism allowing various blocks from foreign sets to be connected into one structure, but it does not specify, how this structure should look like. It is a job for the framework built above the cascade to specify common fragments of these structures and define configuration style, so the solid base for application is created.

Rebuild rather than modify

The cascade tries to make maximal use of block reusability. When a new part of an application is to be created, a many of required blocks are already available for use, so the new part of the application can be built in a little time. Thanks to this, a need for adjusting existing structures to suit current needs is significantly reduced, because they can be thrown away and easily replaced.

Generating the application

To avoid repetition while composing blocks, it is possible to algorithmically generate these structures. A block which inserts additional blocks into the cascade is not limited on how it should get a list of these blocks. It may be from a static configuration file or a database, but the block can interpret these data and use them as templates or as parameters of a predefined template.

The cascade is designed to support this behavior. The dynamic insertion of blocks into the cascade is its key feature. The way, how the cascade is built (see Section 3), makes very easy to attach new blocks to existing sources of data. Because the order of blocks is not significant while inserting them into the cascade, the generating blocks can be much simpler than traditional code generators. Also, it is easy to use multiple blocks to generate a single structure, since connections can be made across namespaces (see Section 4.1).

When this approach is combined with sufficient metadata about entities in the application, the results may be very interesting.

Conclusion

In practice the cascade made development more effective, because it supports a better code reusability while creating a new application, and it helps the developer to analyse an old code when modifying or extending an existing application. The graphical representation of the code is very helpful when tracking from where broken data arrived and what happen to them on their way. It reduces significantly time required to locate a source of problems.

A dynamic nature of the cascade allows the programmer to cover a large number of options while using a fairly simple structure to describe them. And since the execution order is driven by the cascade, the programmer does not have to care about it. That means less code and less space for errors.

A main contribution of the cascade is extending the time-proven function blocks approach with new features making it suitable for many new use cases and preparing base ground for further research.

Figure 1 :

 1 Figure 1: The block

Figure 2 :

 2 Figure 2: Cascade example

Figure 3 :

 3 Figure 3: Automatic parallelization example

  Cascade before execution of the block A Cascade after execution of the block A

Figure 4 :

 4 Figure 4: Growing cascade

Figure 5 :Figure 6 :

 56 Figure 5: Idea of nested blocks

Figure 7 :

 7 Figure 7: Equivalent cascade without output forwarding

Therefore the successful state is called zombie, like terminated unix process whose return value has not been picked up by parent process.

Output generator is a block which prepares data for a future HTTP response as a side-effect. The prepared data are passed to template engine when cascade evaluation is finished.


Josef Kufner
email: kufnejos@fel.cvut.cz

Radek Mařík

State Machine Abstraction Layer

Smalldb uses a non-deterministic parametric finite automaton combined with Kripke structures to describe lifetime of an entity, usually stored in a traditional SQL database. It allows to formally prove some interesting properties of resulting application, like access control of users, and provides primary source of metadata for various parts of the application, for example automatically generated user interface and documentation.

Introduction

The most common task for a web application is to present some entities to an user, and sometimes the user is allowed to modify these entities or to create a new one. Algorithms behind these actions are usually very simple, typically implemented using few SQL queries. The tricky part of web development is keeping track of the behavior and lifetime of all entities in application. As number and complexity of the entities are growing, it is getting harder for a programmer to orientate in the application, and situation is even worse when it comes to testing.

Smalldb brings a bit forgotten art of state machines into the web development, unifying specifications of all entities in an application, creating a single source of all important metadata about many aspects of each entity, and allowing to build formal proofs of application behavior.

The basic idea of Smalldb is to describe lifetime of each entity using state machine, and map all significant user actions to state transitions. To make the best of this approach, the state machine definition is extended with additional metadata, which are not essential for the state machine itself, but can be used by user interface, documentation generator, or any other part of the application related to the given entity.

Smalldb operates at two levels of abstraction within the application. At the lower level it handles database access, it acts as the model in MVC pattern. At higher level of abstraction it can describe API, URIs and behavior of large parts of the application, however, it does not directly implement these parts.

In the next two sections an example of typical entity in web application is presented. In section 4 Smalldb state machine is formally defined. And section 5 describes relation between state machine instances and underlaying database. A basic implementation with some interesting implications is roughly described in section 6. Section 7 introduces Smalldb as a primary metadata source. Remaining sections are dedicated to application correctness.

REST resource as a state machine

Let's start with simple example of generic resource (entity) in RESTful application [START_REF] Fielding | Architectural styles and the design of network-based software architectures[END_REF]. RESTful applications typically use HTTP API to manipulate resources. Since REST does not specify a structure of a resource nor exact form of the API (simply because it is out of REST's scope), it is impossible to use this API without additional understanding of application behind this API. However, HTTP defines only a limited set of usable methods, so a general example can be provided.

Figure 1 presents a generic state machine equivalent to a REST resource. The resource is created by HTTP POST request on a collection, where the resource is to be stored. Then it can be modified using HTTP PUT (or similar HTTP methods), and finally it can be removed using HTTP DELETE method.

Without further investigation of the resource an influence of the "modify" transition cannot be determined, but we can safely assume the resource is more complex than Figure 1 presents, otherwise the "modify" transition would make no sense.

Transitions from the initial state and to the final state represents creation and destruction of the resource and the machine itself. These two states are denoted as a separate features, but they both represent the same thing -resource does not exist. This semantics is one of the key ideas behind Smalldb.

Real-world example

When building real web application, situation is rarely as simple as example in previous section. Typically there is more actions to perform on an entity, and the entity passes through a few states during its lifetime.

A very common application on the Web is a blog. Typical blog is based on publication of posts. Each post is edited for some time after its creation, and then it is published. Some posts are deleted, but they can also be undeleted (at least in this example).

A state machine representing lifetime of the post is in Figure 2. As we can see, there are three states and a few transitions between them. Note that there is no final state in this state machine. That is because the blog post is never completely destroyed.

There is one interesting feature in this state machine -the undelete action. In both HTTP specification and REST there is nothing like it. It is possible to implement it using an additional attribute of the blog post, but it does not fit well into RESTful API, for example there is no counterpart to HTTP DELETE method. Similar troubles occur when controlling nontrivial long-running asynchronous processes, since it is unnatural to express events and commands in REST.

There is also one big problem with both this and previous examples. If these state machines are interpreted as usual finite automata, the edit action has no effect. Invoking the edit action makes no difference, because it starts and ends in the same state. To justify this behavior, the state machine must use a concept very similar to Kripke structures. Each state represents a possibly infinite group of sub-states, which have common behavior described by the encapsulating state. Therefore, the edit transition is in fact a transition between different sub-states within the same state, i.e. sub-states belong to the same equivalency class. Omitting these sub-states from the state diagram is very practical since it allows easy comprehension. The sub-states are implemented using "properties" of the state machine instance, for example title, author and text of the blog post (this concept will be described in Section 4.4). As previous examples showed, it is necessary to modify and extend definition of finite automaton [START_REF] Gill | Introduction to the theory of finite-state machines, ser. McGraw-Hill electronic sciences series[END_REF], to make any use of it. In this section a Smalldb state machine is formally defined and its features are explained. The definition is designed to follow an actual implementation as close as possible, so it can be used to formally infer properties of final applications.

Smalldb state machine definition

Smalldb state machine is modified non-deterministic parametric finite automaton, defined as a tuple (Q, P , s, P 0 , Σ, Λ, M , α, δ), where:

-Q is finite
∈ P * , m ∈ M , e in ∈ Σ, e out ∈ Λ. -α is assertion function: α(q t , m) → Q t+1 , where q t ∈ Q, Q t+1 ⊂ Q, e in ∈ Σ. ∀m ∈ M : s(P t+1 ) ∈ α(s(P t ), m)
⇔ (∃e in : m(P t , e in ) → (P t+1 , e out )) δ is transition function: δ(q t , e in , u) → m, where q t ∈ Q, e in ∈ Σ, m ∈ M , and u represents current user's permissions and/or other session-related attributes.

Explanation of non-determinism

Non-determinism in the state machine has one specific purpose. It expresses possibility of a failure and uncertainty of the result of invoked action. For example when the blog post (see Section 3) is undeleted, it is not known in advance in which state the blog post will end, because if user has no permission to publish, the result state will be "writing", even if the blog post was already published.

Similar situations occur when invoked action can fail. For example when the blog post cannot be published, because requested URI is already used by another post, or if some external material must be downloaded during publication and remote server is inaccessible.

In all these cases, a requested action is invoked, but which transition of state machine is used, is determined by result of invoked action.

Simplified deterministic definition

Because the complete definition described in section 4.1 is a bit too complex, here is a simplified deterministic definition with most of unimportant features thrown away. These features are present in the implementation, but they are not important for a basic understanding. This definition may also be useful for some formal proofs, where these two definition can be considered equivalent, if thrown away features are not significant for the proof. Please keep in mind, that the rest of this paper always refers to the full definition in the section 4.1.

The simplified definition is: Smalldb state machine is defined as a tuple (Q, q 0 , Σ, Λ, δ , m ), where:

-Q is finite set of states. -q 0 is starting state, q 0 ∈ Q. -Σ is set of input events.
-Λ is set of output events (optional).

δ is transition function: δ (q t , e in , w) → q t+1 , where q t , q t+1 ∈ Q, e in ∈ Σ, and w is unpredictable influence of external entities. m is output function: m (q t , e in , w) → e out , where e in ∈ Σ, e out ∈ Λ, q t ∈ Q, and w is the same external influence as in δ .

This is basically Mealy (or Moore1 ) machine [START_REF] Moore | Gedanken Experiments on Sequential Machines[END_REF][START_REF] Mealy | A Method for Synthesizing Sequential Circuits[END_REF], only difference is in introducing additional constraint w to handle possibility of failure. However, the w is not known in advance when transition is triggered (see Section 4.2). Main simplification is made by chaining transition function δ and assertion function α into one transition function δ :

∀q t ∀e in ∀w : δ (q t , e in , w) = Q t+1 ⇔ α(q t , δ(q t , e in , w)) = Q t+1
This simplification assumes, that the implementation of the transitions is flawless, which is way too optimistic for real applications.

Properties and state function

As came out in the blog post example (see Section 3), finite state automaton is not powerful enough to store all arbitrary data of an entity. To overcome this limitation, Smalldb state machine has properties. Each property is identified by name, and rest is up to the application. Properties can be implemented as a simple key-value store, columns in SQL table, member variables in OOP class, or anything like that.

Since properties are not explicitly limited in size, they can store very big, theoretically infinite, amount of data, data of high precision, or very complex structures. To handle these data effectively, the state function is used to determine state of the machine. The state function converts properties to single value, the state, which is easy to handle and understand.

Because applying the state function on different sets of properties can (and often will) result in the same state, the state represents entire equivalence class, rather than single value. This approach is very similar to Kripke structures [START_REF] Schneider | Verification of Reactive Systems: Formal Methods and Algorithms[END_REF].

The state function must be defined for every possible set of properties:

∀P ∈ P * : s(P ) ∈ S
On the other side, an inverse function to s usually does not exist, so it is not possible to reconstruct properties from state. The only exception is a null state q 0 , in which entity represented by state machine does not exist and properties are set to P 0 , in short, q 0 = s(P 0 ).

Typically the state function is very simple. In trivial case (like the first example in section 2) it only detects existence of a state machine. In more common cases (like the blog post example in section 3) it is equal to one of properties, or checks whether a property fits in a predefined range (for example, if date of publication is in future). Since the state function is key piece of the machine definition and it is used very often, it should be kept as simple and fast as possible.

The state is not explicitly stored and it is calculated every time it is requested. If both the state function and a property storage allow, the state may be cached to increase performance, but it is not possible to allow it in general. However, it is usually possible to store some precalculated data within properties to make state function calculations very fast.

Input events

The input events Σ can be understood as actions requested by user. The action is usually composed of method name m ∈ M and its arguments. Input events are implementation specific and their whole purpose is to invoke one of expected transitions in a state machine.

Output events

The output events Λ are simply side effects of methods M , other than modifications of state machine's properties. These events usually include feedback to user and/or sending notification to an event bus interface, so other parts of application can be informed about change.

Methods

The methods M implement each transition of the state machine. They modify properties and perform all necessary tasks to complete the transition. These methods are ordinary machine-specific protected methods as known from object oriented languages, invoked by universal implementation of the state machine. Since the methods cannot be invoked directly, access to them is controlled by state machine, and it is possible to implement advanced and universal access control mechanism to secure an entire application.

There is a few methods with special meaning in object oriented languages. If ∀e in ∀u : m c = δ (s(P 0 ), e in , u), then m c is known as constructor or factory method. If ∀q ∈ Q : α(q, m d ) = s(P 0 ), then m d is known as destructor. However, in Smalldb both these methods are ordinary methods with no special meaning, and both can occur multiple times in single state machine.

Transitions and transition function

Main difference from classic non-deterministic finite automaton is in division of each transition into two steps. The transition function δ covers only the first step. The second step is performed by method m ∈ M , which was selected by the transition function δ. Point of this separation is to localize the source of nondeterminism (see Section 4.2) and accurately describe a real implementation.

The complete transition process looks like this (explanation will follow):

(P t , e in ) δ(s(Pt),ein,u) ---------→ (P t , e in , m) m(Pt,ein) -------→ P t+1 α(s(Pt),m) -------→ s(P t+1 )
Before a transition is invoked, only the properties P t and the input event e in are known. First, the transition function δ is evaluated, which results in the method m being identified. Then the m is invoked and the properties get updated. Finally, the assertion function is evaluated to check, whether the state machine ended in correct state.

The transition function δ also checks, if an user is authorized to invoke the requested transition. User's permissions are represented by u. This check can be used alone (without transition invocation) to determine, which parts of user interface should be presented to user.

Assertion function

A simple condition must be always valid:

s(m(P t , e in )) ∈ α(s(P t ), m)
Otherwise there is an error in the function m.

Purpose of the assertion function α is to describe expected behavior of m and validate its real behavior at run-time. Since m is piece of code written by humans, it is very likely to be wrong.

Space of state machines

Everything said so far was only about definition of a state machine. This definition is like a class in an object oriented language -it is useless until instances are created. In contrast with the class instances, the state machine instances are persistent. Definition is implemented in source code or written in configuration files, and properties of all state machine instances are stored in database.

But there is one more conceptual difference: The state machine instances are not created. All machines come to existence by defining a structure of a machine ID, which identifies machine instance in the space of all machines.

At the beginning, all machines are in null state q 0 , which means "machine does not exist" (yes, it is slightly misleading). Since it is known, that properties of a machine in q 0 state are equal to P 0 , there is no need to allocate storage for all these machines.

Machine ID is unique across entire application. There is no specification how such ID should look like, but pair of machine type and serial number is a good start. A string representation of the ID is URI, a world wide unique identifier. Conversion between string URI and application-specific ID should be simple and fast operation which does not require determining a state of given machine.

Once machine instance is identified, a transition can be invoked. Once machine enters state different than q 0 , its properties are stored in database. This corresponds with calling a constructor in an object oriented language. When machine enters the q 0 state again, its properties are removed from database, like when destructor is called. But keep in mind that machine still exists, it only does not use any memory.

Smalldb and SQL database

An SQL database can be used to store machine properties. In that case, each row of the database table represents one state machine instance, and each column one property. The table name and primary key are used as the machine ID. Machines in q 0 state do not have their row in the table.

It is useful to implement the state function using an SQL statement, so it can be used as regular part of SQL query. That way it is easy and effective to obtain list of machines in given state.

Machine methods M typically call few SQL queries to perform state transitions. It is not very practical to implement the methods in SQL completely, since it is usually necessary to interact with other non-SQL components of the application.

RESTful HTTP API

URI as a string representation of the machine ID was chosen to introduce Smalldb HTTP API. This API respects the REST approach [START_REF] Fielding | Architectural styles and the design of network-based software architectures[END_REF], and mapping to Smalldb state machine is very straightforward: HTTP GET request can be used to read state machine status and properties, HTTP POST request to invoke a transition. This may remind RPC2 a little, where procedures on remote machine were invoked. Smalldb tries to pick the best of both REST and RPC, since these approaches are not in direct conflict. Entities are identified using URI, just like REST requires. Transitions are identified in RPC fashion, but structure of the machine behind this API is unified and data are retrieved in standard way, so close coupling does not happen, in contrast with RPC.

Question is, how to specify the transition to invoke. Probably the best approach is to append transition name to URI using query part (for example http://example.org/post/123?action=edit). This may not be as elegant as somebody could wish, but it is compatible with old plain HTML forms, because HTTP GET on such URI with the transition name can result in obtaining a form, which will be used to create HTTP POST request later. This makes it possible to use Smalldb without need to create a complex JavaScript frontend.

But if more interactive frontend is required, a HTTP header Accept can be used to specify other format than HTML page, and retrieve data in JSON or XML, just like any modern RESTful API offers. Also a HTTP GET on URI with a transition name specified can return transition definition, like HTTP OPTIONS does in REST API.

This approach was chosen pragmatically for the best compatibility with current stable (old) and widely available technologies.

Smalldb implementation

Prototype

A basic implementation is composed of two base abstract classes, Backend and StateMachine, and two helper classes, Reference and Router.

The Backend class manages StateMachine instances and takes care of stuff like shared database connection. It acts as both factory and container class. The Backend must be able to determine a type of requested machine from its ID, to prepare correct instance of StateMachine class, and delegate almost all requests to it. This way the Backend is responsible for entire state machine space without even touching it. Classes derived from the Backend class implement application specific way to access list of known state machines (descendants of StateMachine class).

The abstract StateMachine class and classes derived from it contain definition of the state machine and implementation of methods M (see Section 4.1). There is only one instance of StateMachine class per Backend and state machine type, which handles all state machines instances of given type. So the StateMachine instances are responsible for disjunctive subspaces of state machine space. When transition is to be invoked, machine ID and input event is passed to a StateMachine::invokeTransition method, which validates request using machine definition and executes appropriate protected method implementing the transition.

The Reference class is mostly only syntactic sugar to make application code prettier. It is created by Backend's factory method, which takes state machine ID as an argument. It contains the ID and a reference to both the Backend and the corresponding StateMachine (obtained from the Backend). The Reference is used as proxy object to invoke state machine transitions and retrieve its state and properties. Its implementation is very specific to used language. Usage of Reference object is similar to Active Record pattern, however, the semantics is different.

Finally, the Router class is a little helper used to translate URI to state machine ID and back. Each application may require specific mapping of URIs, so the instance of Router class is injected into Backend during its initialization.

Metaprogramming

Since the StateMachine class is responsible for loading of a state machine configuration, it is possible to generate the configuration dynamically in StateMachine constructor. This allows to create more general state machines for similar entities using one StateMachine class initialized with different configuration.

It is also possible to determine state machine properties from structure of SQL tables, and load rest of the definition from the SQL database too. This way it is possible to define new state machines and entities without need to write a single line of code, using only an administration interface of the application.

Spontaneous transitions

When state function includes time or some third party data source, it may happen that state machine will change from one state to another without executing any code. Since this changes happen completely on their own and without any influence of Smalldb, it is not possible to perform any reaction when they happen.

There are two ways of dealing with this problem. The first way is to live with them and simply avoid any need of reaction. This approach can be useful in simple cases where an entity should be visible only after specified date. For example the blog post (see Section 3) can have "time of publication" property and state function defined like "if time of publication is in the future, post is in state writing, otherwise post is published".

Other way is to not include these variables into the state function and schedule transitions using cron or similar tool. This, however, usually require introduction of "enqueued" state. For example the blog post will have additional "is published" boolean property and there will be regular task executed every ten minutes, which will look for "enqueued" posts with "time of publication" in the past and will invoke their "publish" transition.

The spontaneous transitions can be useful tool, it is only necessary to be aware of their presence and handle them carefully. They also should be marked in state diagram in generated documentation.

State machine metadata

Role of the Smalldb state machine in an application is wider than it is typical for a model layer (as M in MVC), because Smalldb provides many useful metadata for the rest of the application. The state machine definition can be extended to cover the most of entity behavior, which allows Smalldb to be the primary and only source of metadata in the application.

Having this one central source makes the application simpler and more secure. Simpler because metadata are separated from application logic, so they do not have to be repeated everywhere, which also makes maintainability easier and development faster. More secure because metadata located at one place are easier to validate and manage.

Other important benefit of centralized metadata source is generated documentation. Since the metadata are used all over the application, it is practically guaranteed that they will be kept up to date, otherwise the application will get broken. And in addition, the metadata in the state machine definition are already collected and prepared for a further processing. All this makes it very valuable source for documentation generator.

For example, the Figures 1 and2 used in examples (sections 2 and 3) were rendered automatically from a state machine definition in JSON using Graphviz [START_REF] Ellson | Graphviz and dynagraph -static and dynamic graph drawing tools[END_REF] and a simple, 120 lines long, convertor script.

Additional use for these metadata is in generating user interface, determining which parts of it user can see and use, user input validation, access control, or API generating. And if metadata are stored in static configuration files or database, they can be modified using administration interface embedded in the application, which allows to easily alter many aspects of the application itself. Dynamically generated metadata then allows building of large and adaptive applications with very little effort.

Application correctness

A lot of research was done in model checking and finite automata, resulting in tools, like Uppaal [START_REF] Behrmann | A tutorial on uppaal[END_REF], which allows to formally verify statements about given automaton. Since Smalldb is built on top of such automata, it is very convenient to use these tools to verify Smalldb state machines. And thanks to existence of formal definition of Smalldb state machine, it is possible to export state machine definition to these tools correctly.

Access control verification

Verification of basic properties, like state reachability3 , safety 4 and liveness 5 , is nice to have in basic set of tests, however, these properties are not very useful on their own. Situation gets much more interesting, when user permissions are introduced.

User access is verified just before transition is invoked. Therefore, an user with limited access is allowed to use only subset of transitions in state diagram, and some states may become unreachable. If expected reachability of a state by given user is stated in the state machine definition, it is easy to use the earlier mentioned tools to verify it. And in the most cases, any allowed transition originating from unreachable state means security problem.

Similar situation is with liveness property, where unintentional dead ends, created by insufficient permissions, can be detected.

Because access control is enforced by general implementation of state machine (in abstract StateMachine class, see Section 6), which can be well tested and it is not modified often, probability of creating security issue is significantly reduced.

Optimizations vs. understandability

In the era of discrete logical circuits, a state reduction was very important task, because circuits were expensive and less states means less circuits.

In Smalldb, a state machine is used in very different fashion. The state machine is expected to express real behavior of a represented entity in a way, which can be understood and validated by non-technical user (customer). A connection between understandability of state diagram and automated generation of this diagram from the single source of truth (see Section 7) is important feature, since it eliminates an area, where errors and misunderstandings can occur -a gap between expectations and software specification.

From this point of view, any state diagram optimizations are undesirable.

Computational power of Smalldb machine

Classical finite state automaton is not Turing complete, because it has limited amount of memory, so it cannot be used, for example, to count sheeps before sleeping. But in Smalldb state machine this limitation was overcome by introducing properties and methods implemented in Turing-complete language (see Section 4.1), so the sheep counting can be done using one state, increment loopback transition and sheep counter property. Smalldb state machine is a hybrid of two worlds. On one side, there is nice non-deterministic finite automaton, which allows all the nice stuff described in this paper. On the other side, there are Turing-complete methods M , the barely controllable mighty beasts, which do the hard work. As long as these two parts are together, the computational power is the same as of the language used to implement the methods M .

By introducing properties and state function, the used automaton cannot be easily considered finite, since single state represents an equivalence class of property sets, which is not required to be finite. It is also possible to let methods M to modify state machine definition on the fly. And since both state function and transition function are also implemented using Turing-complete language, it is possible to define them in the way where the amount of the states is not finite at all. However, rest of this paper does not consider these possibilities and, for sake of clarity, expects reasonable definitions of all mentioned functions.

A practical example of self-modifying Smalldb state machine is a graphical editor of state machine definition which uses Smalldb to store modified configuration.

Troubles with methods M

Because methods M (see Section 4.7) are Turing complete, it is not possible to deduce their behavior automatically. This means it is not possible to predict, whether all transitions of the same name will be used by machine, and therefore some of the states considered reachable, when methods M were not took into account, may not be ever reached. This problem can be partially solved by careful testing and reviewing of the methods M .

Another problem is, when some of the methods are flawed and machine ends up in other state than transition allowed. This is detected by assertion function and it must be reported as a fatal error to a programmer.

Smalldb cannot solve these troubles completely, but it is designed to locate these kinds of errors as accurate as possible.

Workflow correctness

State machine cooperation

The workflow can be understood as cooperation of multiple entities with compatible goals. When these entities are specified as Smalldb state machines, it is relatively straightforward to involve tool like Uppaal (see Section 8), and let it calculate, what will happen, when these entities are put together.

Once state machine instances are required to cooperate, there is a danger that state machines will got stuck in deadlock. As Smalldb state machines represent entity lifetime, the cooperation troubles may mean there is something wrong with processes outside an application.

But the Smalldb state machine does not have to represent the entity within an application only. It also can be used to describe behavior of external entities, however, such entity should not be included in the application.

BPMN and BPEL

Entity lifetime is closely related to users' workflow and related processes. BPMN 6 and BPEL 7 were developed to describe them in some formal way. It should be possible to extract a formal model of each entity included in the process from BPMN and/or BPEL description, and convert them to Smalldb state machines. Then the state machine representing an application entity can be used as starting point of its implementation. And the other state machines, which represents humans and external applications, can be used to execute a simulation of complete process.

This approach should eliminate need for software specification when there is model of the entire process. Another benefit could be possibility of testing and formal proving of the application not against its specification, but rather against other entities in the process, removing the gap between what is expected and what is specified. This area will require a lot of research and it is mostly out of the scope of Smalldb and this paper, however, it might be inspirational to put a bit wider context here.

Conclusion

Smalldb represents valuable source of metadata in an application, and allows to formally verify various aspects of the application, while maintaining practical usability and development effectivity.

From certain points of view it is similar to object oriented programming, where invoking of a transition is similar to method call in OOP, but with benefits of additional validation and better documentation of entity lifetime, which helps to manage complex and long-term behavior of the entities.

Smalldb also allows definition of simple RESTful HTTP API, which includes some aspects of RPC, to make the API more universal and easier to use. This API is also compatible with standard HTML forms, so it can be used on web sites without creating complex JavaScript clients.

Smalldb is meant as both as production-ready solution and as a building block for further research of software synthesis. However, there are areas left unexplored in integration of Smalldb with business process modeling (see section 9) and various aspects of verification.

Figure 1 .

 1 Figure 1. REST resource state machine

Figure 2 .

 2 Figure 2. State diagram of blog post

6

  BPMN: Business Process Model and Notation 7 BPEL: Business Process Execution Language

  set of states.-P is set of named properties. P * is (possibly infinite) set of all possible values of P . P t is state of these properties in time t. P t ∈ P * . s is state function s(P t ) → q, where q ∈ Q, P t ∈ P * . -P 0 is set of initial values of properties P , P 0 ∈ P * .-Σ is set of parametrized input events.-Λ is set of parametrized output events (optional). -M is finite set of methods: m(P t , e in ) → (P t+1 , e out ), where P t , P t+1

Slight differences between Mealy and Moore machines are not important here, and ein may or may not be used in m .

RPC: Remote Procedure Call

State reachability: "Is there path to every state?"

Safety property: "Something bad will never happen."

Liveness property: "Machine will not get stuck."


Aldo Suwandi
email: aldosuwandi@gmail.com

Inggriani Liem

Saiful Akbar

Concern Based SaaS Application Architectural Design

Keywords: SaaS, Software as a Service, Concern, Aspect Oriented Software Development

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Traditional software users are typically overburdened with operational work such as maintenance and software deployment. SaaS model is raised to overcome these problems. Many software companies start adopting this model. Instead of buying, more and more individual users and companies rent software. Software maintenance and deployment that were previously handled by users now is handled by ISV.

Based on [START_REF] Turner | Turning Software into a Service[END_REF], [START_REF]What is Software as a Service[END_REF], [START_REF] Carraro | Software as a Service (SaaS): An Enterprise Perspective[END_REF], [START_REF] Sommerville | [END_REF], [START_REF] Laplante | Distinguishing Between SaaS and SOA[END_REF], [START_REF] Chou | Software as a Service (SaaS) as an outsourcing model: an economic model analysis[END_REF], SaaS is a hosted software and delivered over a network on a subscription basis. SaaS operational systems could be categorized into platform centric or service provider centric [START_REF] Hancheng | An Anatomy to SaaS Business Mode Based on Internet[END_REF]. ISV and tenant are two main factors of SaaS operational systems. The maturity of SaaS application is determined by tenancy, configurability, and scalability [START_REF] Chong | SaaS Simple Maturity Model[END_REF].

Seven pricing models for SaaS application has been studied by Kalisa [START_REF] Kalisa | Kajian Software as a Service denganStudiKasusRumahSakit di Daerah Rural danTerpencil[END_REF]. Billing should be built as part of SaaS application [START_REF] Tang | Framework for SaaS Management Platform[END_REF]. However, this functionality must be flexible because each tenant may have a preference of its his own billing scheme.

Enhancement of SaaS application design is required. Aspect oriented software development is one of the application development model to improve the structuring, reusability, and reduce the complexity of the model compared with object oriented model [START_REF] Brichau | Aspect-Oriented Software Development -An Introduction[END_REF].

Our research has studied "concerns" that should be considered to develop SaaS application based on AOSD. Separation of concern is a fundamental principle to facilitate software deployment [START_REF] Sutton | Concern Modeling for Aspect-Oriented Software Development[END_REF]. Concern is interest which pertains to the system's development, its operation or any other aspects that are critical or otherwise important to one or more stakeholders [START_REF]IEEE recommended practice for architectural description of software-intensivesystem[END_REF]. Core concern represents functional requirement. Cross-cutting concern represents non-functional requirement. Object oriented model is appropriate for core concern development, whereas AOSD is better for developing cross-cutting concern. Cross-cutting concern could be implemented with aspect oriented programming (AOP). Implementation of AOP is based on four design elements, namely aspect, join point, point cut and advice [START_REF] Sommerville | [END_REF]. Aspect is a class consisting of one or a number of advices. Join point is a point on program that will be intercepted by the aspect class. Point cut is a boolean expression that determines join point. Advice is a method containing a logical process to be executed when the class aspect intercepts.

In this paper, we describe our approach in using AOSD for identifying general SaaS requirements, proposing a SaaS system architecture that contains all of the proposed concerns, and the proof of concept for the proposed architecture.

Related Work

Chate [START_REF] Chate | Convert your web application to a multi-tenant SaaS solution[END_REF] proposed a way to build multi-tenant SaaS application either from scratch or from existing application. Corrent's SaaS-Factory is used to convert legacy database into a new multi-tenant database. Tang, et al [START_REF] Tang | Framework for SaaS Management Platform[END_REF] proposed SaaS Platform Management Framework as modules that can be considered to manage SaaS application platform. The platform of this framework consists of two levels, namely business and operations. Business contains related modules with billing management, whilst operation contains related modules with operational system such as metering, configuration, monitoring, etc. Those modules should be considered when implementing SaaS management platform. Different from Chate [START_REF] Chate | Convert your web application to a multi-tenant SaaS solution[END_REF] and from Tang et all [START_REF] Tang | Framework for SaaS Management Platform[END_REF], in this paper we focused on applying AOSD as fundamental technique to build a SaaS framework for the benefit of ISV and tenant. We also provided dashboard in the environment that we consider important for monitoring the operation of SaaS. We believe that aspect oriented software development (AOSD) can contribute as a fundamental approach for operating applications in a SaaS environment.

Separation of Concern

In AOSD, separation of concern is the first phase of design. Concern affecting SaaS application could be identified from SaaS application requirement. Two main actors of SaaS application are tenant and ISV. Tenant's main purpose is to use application functionalities as a service. Multi-tenant SaaS application should be configurable to fulfill tenant's requirement varieties. Furthermore tenant should have an isolated data, that can only be accessed or modified by authorized users.

To make it easier for the tenant, ISV manages application deployment and maintenance for them. ISV could have one or many applications to be operated with SaaS model. ISV requires design enhancement on SaaS application to reduce maintenance and development cost to operate multiple SaaS application. It is also important for ISV to know the performance of each SaaS operated application. Furthermore ISV also needs information of resources usage and transaction by each tenant. In order for an application to be considered as having high level maturity, not only it has to have billing functionality, but it also has to be configurable and scalable, and have multitenant [START_REF] Kalisa | Kajian Software as a Service denganStudiKasusRumahSakit di Daerah Rural danTerpencil[END_REF].

In this research we focused on the design of configurable multi-tenant SaaS application. We specify six main generic-requirements of SaaS application:

a. Tenant should have appropriate functional requirement needed. b. Tenant should have their own copy of data. c. ISV should be provided with a centralized application management enabling it to operate many SaaS applications. d. ISV should be informed of each application's performance status. e. ISV should be informed of resources which are used by tenant in each application.

f. ISV should be provided with transaction management in order to manage billing transaction of each application.

These six main user requirements are shown in the diagram below (see Figure 1). User requirements derive one or more concerns. We proposed eight concerns depicted on Figure 1. Those concerns are configurability, discriminator, measurement monitoring, tenant management, billing management, performance management, and application management. We derived those concerns from ISV and tenant requirement, and crosscutting elements of SaaS application. Concerns are grouped into core concern and cross-cutting concern, referring to AOSD terminology. Concerns are implemented into module, service, or library. Those concerns are integrated into SaaS system architecture that consists of SaaS operational system and set of applications.

Core concerns are implemented as modules. Concern configuration is attached into application main functionality, to support variation of configuration as proposed by W.-T.Tsai [START_REF] Tsai | SaaS Multi-Tenant Application Customization[END_REF] i.e. GUI, service, workflow, data, and QoS. Other core concerns such as tenant management, billing management, performance management, and application management will be implemented as modules on SaaS operational system's dashboard. This dashboard provides centralized SaaS operational system information from set of applications (application x1, x2, ....., xn). It will facilitate ISV to monitor and to control its SaaS operated applications.

Discriminator, monitoring, and measurement are considered as cross-cutting concern, used by all SaaS applications. These concerns are implemented into web service or library. The Service helps application to communicate with SaaS operational system. The Library contains of aspect classes, representing the interoperability of application with SaaS operational system. These classes reduces the complexity of application operational model of SaaS application. Aspect classes in the library will be implemented with AOP.

Implementation

To test our proposed SaaS system architecture, a case study has been conducted as a proof of concept. A SaaS system called Olympus shown on Figure 3. has been developed as SaaS system implementation of the designed architecture in Figure 2.

Figure 3. Example of Implementation

We have developed and implemented SaaS application (Vulcan) and ISV dashboard (Plutus). To prove that it is easy to integrate an existing application to our proposed SaaS application, we use Affablebean, an e-commerce application [START_REF]The NetBeans E-commerce Tutorial -Designing the Application[END_REF]. We have implemented Vulcan and Affablebean in different mode of SaaS operation and billing.

Vulcan and Plutus have been developed using Spring Framework [START_REF]Spring Framework[END_REF], Spring AOP [START_REF]Spring Framework[END_REF], Jerseyclient [START_REF]Jersey -RESTful Web Services in Java[END_REF] and Jamon library [START_REF] Souza | JAMon (Java Application Monitor)[END_REF]. Spring Framework and Spring AOP are chosen as the application framework because of their support to AOP. Jersey client library is used as a client for REST web service. Jamon is used as a library application monitoring.

ISV configures SaaS operational system such as billing model and application info through Plutus dashboard. AOP facilitates billing model on SaaS operated application without modification of existing code. AOP also increases reusability. For example if an application has a number of resources to be measured, programmer's task is to implement annotation with boolean expression as join point where the resource is used.

ISV is provided with performance information such as application's method response time and error report on performance management. This information will help ISV tracing error on application and to decide maintenance activity. Performance management works by monitoring service and monitoring aspect. Techniques that have been implemented for billing can be used to monitor SaaS application.

We also integrate applications one by one, to simulate how applications in the architecture grow. Those applications are integrated with Plutus via combination of provided service and library to be operated as SaaS model. ISV configures SaaS operational system such as billing model and application info through Plutus dashboard.

Vulcan is a problem set databank application that facilitates tenant to manage, review, publish and create various types of questions such as multiple choice, true/false, short answer, etc. Test is extracted from data bank based on a predefined test blueprint. Vulcan provides web services to external system that is authorized to use the test. The implementation of configurable concern permits each tenant to define his own theme, question type, question statistics management, and question additional attributes. Parameterization technique is used to implement theme configuration. User preferred theme is saved in Vulcan database and will be used for differentiating one tenant from others. Metadata file configuration is used to implement question type modification and question statistic management. Tenant can configure the provided metadata in XML to modify or to create a new question type and statistic model. XML extension technique [START_REF] Aulbach | A Comparison of Flexible Schema for Software as a Service[END_REF] is used to implement flexible attribute of question. Inside Plutus, Vulcan turned into multi-tenant SaaS application used by many academic institutions. ISV configures billing model of each Vulcan tenant. The number of questions and time usage of Vulcan can be limited by a specific implementation of measurement modules.

Affablebean is an existing web application that builds by NetBeans team for JEE application development tutorial. The main functionality of this application is being a point of sales between Affablebean store and customer. Before being integrated to Plutus environment, Affablebean is modified to be a multi-tenant SaaS application. It is assumed that there are a number of Affablebean stores, where each store has different kinds of product and customer. Instead of usage limitation, the resource model in Affablebean is implemented by a period of time Before integrating a new application to the environment, we have to configure and to tailor it to a multitenant SaaS application, then to register the application to the environment. The following steps illustrate the process: a. Change the old database connection to new multi-tenant database. This connection will be provided when ISV registers their application to Plutus. We adopted shared database separated schema model for supporting multi-tenant database ar-chitecture. ISV should save the application database schema. The saved database schema will be used to automatically generate new parameterized schema (schema with all table name extended with tenant identifier) for each tenant when ISV registers new tenant b. Extend the Plutus library to support the new database. All supporting libraries needed by new application should also be included. c. Include service identifier method, provided by Plutus library on SaaS application login method. It permits application to be recognized by the system. This method is used to identify tenant and billing method when they login to SaaS application. d. Define annotation in measurement and monitoring class using Plutus library, to specify which method or class needed to be metered or monitored.

Testing

Our SaaS system has been tested in two folds: testing the environment and dashboard, and then testing the integration of a new operated SaaS Application as shown in Figure 4. Each fold consists of unit testing, functional and integration testing. Both of the testing process (adding new application and SaaS environment) can be done separately until interoperability testing is done.

The flow of unit testing, functional testing, interoperability testing for the environment and dashboard is shown in Figure 4. JUnit is used to test each class containing services and module of Dashboard. All Plutus Dashboard functional requirement [START_REF] Suwandi | Kajian Aspek pada Aplikasi SaaS[END_REF] has also been tested. Once the environment is ready, we can add SaaS application to the environment by doing the configuration steps that have been explained in section 5. This process can be easily done without modifying the existing application code, as we take benefit from AOP technology.

JUnit is also used for testing each application (Vulcan, Affablebean) before integration. The purpose of functional testing is to assure that each application will meet the requirement. This functional testing was performed on each functional requirement of Vulcan and Plutus. Vulcan has 18 functional requirements [START_REF] Suwandi | Kajian Aspek pada Aplikasi SaaS[END_REF] and has been tested with test scenarios in Figure 4. Once an application passed Unit and functional test, it is ready to be deployed in Olympus.

Interoperability testing is used to show how easy is to start an existing application to operate. For this test, Vulcan and Affablebean are integrated into Plutus. These tests are conducted after functional testing is done. We register Vulcan and Affablebean in Plutus application management and configure billing management. We also include Plutus library in those application projects, and configure aspect class in Plutus library according to their needs. All of these integration processes do not require modification from the existing code. However, the three testing processes must be done, each time ISV needs to add a new application to the environment.

Conclusion

In this research we have identified general SaaS application requirement from two points of views that of ISV and of tenant. Concerns are derived from those requirements. Eight (8) concerns are identified, including tenant management, discriminator, monitoring, performance management, measurement, billing management, and application management. Each concern has been implemented as modules, service, or library. This research also proposed SaaS system architecture that contains all of the proposed concerns. Those eight concerns are implemented as library and services. As a result, an architecture consists of sets of SaaS applications and a SaaS operational system are proposed. Each application in the set of applications will utilize SaaS operational system as a centralized management system, so it can be operated as SaaS model. By using AOSD approaches on this architectural design, both ISV and tenant can take benefit. Using the AOP technology, ISV easily deploy an application before operation where tenant can have his own database and configuration. Furthermore, through resource measurement and performance monitoring, ISV and tenant have a transparent and accountable billing. ISV can separate its concern to tenant requirement, and reuse Plutus. Integration of Affablebean showed that the architecture permits a non aspect oriented application to be integrated and operated as SaaS after small effort of tailoring.

Fig. 1 .

 1 Fig. 1.Concern Derivation Process and Result

Fig. 2 .

 2 Fig. 2. Proposed SaaS System Architecture

Fig. 4 .

 4 Fig. 4. The Whole Testing Proces