Georgios Balikas

Ioannis Partalas

Eric Gaussier

Rohit Babbar

Reza Amini

Efficient Model Selection for Regularized Classification by Exploiting Unlabeled Data

Hyper-parameter tuning is a resource-intensive task when optimizing classification models. The commonly used k-fold cross validation can become intractable in large scale settings when a classifier has to learn billions of parameters. At the same time, in real-world, one often encounters multi-class classification scenarios with only a few labeled examples; model selection approaches often offer little improvement in such cases and the default values of learners are used. We propose bounds for classification on accuracy and macro measures (precision, recall, F1) that motivate efficient schemes for model selection and can benefit from the existence of unlabeled data. We demonstrate the advantages of those schemes by comparing them with k-fold cross validation and hold-out estimation in the setting of large scale classification.

Introduction

Model selection is an essential step in the pipeline of data analysis tasks. Having decided on the algorithm to be used, one should proceed to parameter selection that is the process of selecting a value for the model's hyper-parameter(s) expected to obtain the optimal performance on unseen examples. For instance, when using Support Vector Machines (SVM) or Logistic Regression (LR) in a classification task, one has to tune the regularization parameter λ which controls the complexity of the model.

The fundamental idea of parameter estimation methods is to validate the model's performance in fractions of the training data. In several learning scenarios however, except few labeled data, a larger set of unlabeled data may be available (for example in text classification) as the cost of assigning labels is high. This is the case for example of the transductive learning framework [START_REF]Semi-Supervised Learning[END_REF], where the data to be classified are available beforehand and can be leveraged during the training or inference procedures.

The situation we are investigating in this paper is when unlabeled data are available during the step of parameter selection in a classification problem. The challenge is to come up with a method that is able to leverage the information in the unlabeled data, instead of ignoring them as traditional model selection strategies such as k-fold cross validation (k-CV) do. To tackle this problem, we incorporate quantification techniques in order to infer the distribution of the examples on unlabeled data, which in turn is used to calculate upper bounds (Section 3) on the performance of a model that motivate an efficient model selection scheme (Section 4).

We place ourselves in the supervised learning paradigm where the i.i.d. assumption holds. Note that unlike semi-supervised and transductive learning paradigms that make use of the unlabeled data in the training process to improve the performance, we use the unlabeled data for hyper-parameter selection and, hence, the obtained performance in the test set depends on the amount of the available labeled data. Our method, which is an alternative to k-CV, motivates the selection of the optimal value for the model's hyper-parameter(s) from a finite set that in turn results in the optimal performance (again from a finite set of possible performances). In this work, we propose a hyper-parameter selection method that (i) benefits from unlabeled data, (ii) performs on par with k-CV but it is k times faster and (iii) has the same complexity as hold-out estimation but performs better due to the use of unlabeled data. We demonstrate the efficiency and the effectiveness of the proposed method in Section 5 where we present multi-class text classification results on several datasets with a large number of classes.

Related Work

Several approaches have been proposed for selecting the hyper-parameters of learning algorithms. The goal is always to select the hypothesis that minimizes the generalization error, which is approximated by the estimated error [START_REF] Mohri | Foundations of Machine Learning[END_REF]. A popular method to calculate the estimated error is the hold-out procedure that splits the data in a training and a validation set; the estimated error is calculated on the latter.

The k-CV technique repeats k times the hold-out procedure: in each round the available training data are partitioned into two complementary subsets, one for training and one for validation. To reduce variability, multiple rounds of crossvalidation are performed using different partitions and the validation results are averaged over the rounds. At the end, an hypothesis is selected e.g. by retraining the classifier on all data using the best values found for the hyper-parameters, or by averaging the hypotheses [START_REF] Bengio | No unbiased estimator of the variance of k-fold crossvalidation[END_REF]. A variant of this method is proposed by Blum et al. [START_REF] Blum | Beating the hold-out: Bounds for k-fold and progressive cross-validation[END_REF] with a progressive cross-validation procedure that begins by splitting the data in training and test. At each step, it tests an example which in the next round is used for training, resulting in as many hypotheses as the available test examples. To label an example, a hypothesis is randomly selected. This method has the advantage of using more examples for training than the hold-out and was shown to select a better hypothesis. In addition, the study in [START_REF] Kohavi | A study of cross-validation and bootstrap for accuracy estimation and model selection[END_REF] reviews accuracy estimation and model selection methods based on cross-validation and bootstrap. The former is shown to be better than the latter in different datasets, especially in terms of accuracy estimation (for which a stratified approach may be preferred).

The hold-out estimation and the k-CV when k is small are known to have large variance, a problem that can be partially compensated in k-CV by selecting high values for k (like 5 or 10) [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF][START_REF] Arlot | Why V=5 is enough in V-fold cross-validation[END_REF]. However, k-CV and its variants are computationally expensive and may be intractable in practice if one wants to search for the appropriate values in large-scale scenarios.

We propose here a different method that can select an appropriate model on unlabeled datasets. The advantages compared to the above-mentioned methods concern its efficiency and its ability to be applied when few labeled examples are available. It dispenses with the use of validation sets which can be cumbersome to produce in unbalanced or small datasets. It is, however, intended for model selection only, whereas cross-validation and hold-out estimation can be used for performance evaluation as well.

Accuracy and Macro-F1 Quantification Bounds

In this section, we propose an upper bound on several performance measures (accuracy and macro-F1) of a given classifier C on a dataset S which doesn't need to be labeled. We then use this bound, which is based on the class distribution induced by C on S, to perform model selection.

We consider mono-label multi-class classification problems, where observations x lie in an input space X ⊆ R d . Each observation x is associated with a label y ∈ Y, where |Y| > 2. We suppose that examples consist of pairs of (x, y) identically and independently distributed (i.i.d) according to a fixed, but unknown probability distribution D over X × Y (D X will denote the marginal probability for x in X ). In the context of text classification, x (i) ∈ X denotes the vector representation of document i and its label y (i) ∈ Y represents the category associated with x (i) . We further assume to have access to a training set S train = {(x (i) , y (i) )} N i=1 also generated i.i.d with respect to D. Quantification. As explained below, our analysis makes use of M

C(S) y

, the number of documents in the unlabeled set S assigned by classifier C to class y. Many classifiers do not directly assign a category to documents, but rather produce scores (probabilistic or not) for each category, from which a categorization decision can be made. The task of determining the number of instances of each target category in a set S is called quantification and was first proposed by Forman et al. [START_REF] Forman | Counting positives accurately despite inaccurate classification[END_REF][START_REF] Forman | Quantifying counts and costs via classification[END_REF]. Contrary to classification that identifies in which target categories an observation belongs, quantification is solely concerned with the estimation of the number of observations belonging to a target category (the positive examples). Note that a good quantifier is not necessarily a good classifier, and vice versa. For example, in a binary problem with 40 observations, a learner that outputs 20 False Positives and 20 False Negatives is a perfect quantifier but a really bad classifier.

Given a set of instances in S, quantifiers output, for each target category y of S, a number denoting the prediction of the relative frequency of category y in S. Quantification methods using general purpose learners are usually split ( [START_REF] Esuli | Optimizing text quantifiers for multivariate loss functions[END_REF]) in aggregative and non aggregative methods based on whether the quantification step requires the classification of the individual instances as a basic step or not. Quantification has been mainly used to estimate distribution drifts. We make a different use of it here, in the context of model selection, and rely on two popular quantification methods, namely: a) Classify and Count (CC) and b) Probabilistic Classify and Count (PCC) [START_REF] Esuli | Optimizing text quantifiers for multivariate loss functions[END_REF]. In CC, given a classifier C trained on a set S train , the relative frequency of a class y in a set S, denoted by p

C(S) y

, is obtained by counting the instances of S that classifier C assigns the target category y, that is p

C(S) y = M C(S)
y |S| , where |S| denotes the size of S. PCC extends CC using the posterior probabilities of an instance belonging to a category, leading to p

C(S) y = 1 |S| x∈S p(y|x)
, where p(y|x) is the posterior probability that an instance x of S belongs to y. We do not consider the adjusted version of those two approaches proposed in [START_REF] Bella | Quantification via probability estimators[END_REF] because they require the expensive k-fold cross-validation in the training set which is undesirable in large scale settings. Lastly, having a trained classifier, the computational complexity of quantification reduces to the prediction cost of a trained classifier. Quantification-based Bounds. We now present our main result which consists of quantification-based upper bounds on the accuracy (denoted A C(S) ), the macro-precision (denoted M aP C(S) ), the macro-recall (denoted M aR C(S) ) and the macro-F1 (denoted M aF C(S) ) of a classifier C on a dataset S which does not need to be labeled. Theorem 1. Let S = {(x (j) )} M j=1 be a set generated i.i.d. with respect to D X , p y the true prior probability for category y ∈ Y and Ny N py its empirical estimate obtained on S train . We consider here a classifier C trained on S train and we assume that the quantification method used is accurate in the sense that: M aR ( ) be defined as:

y∈Y min{p y × |S|, p C(S) y × |S|} |S| B C(S) A 1 |Y| y∈Y min{p y × |S|, p C(S) y × |S|} + |S| p C(S) y × |S| + |S| B C(S) M aP ( ) 1 |Y| y∈Y min{p y × |S|, p C(S) y × |S|} + |S| pC(S) y × |S| + |S| B C(S) M aR ( )
Then for any δ ∈]0, 1], with probability at least (1 -δ):

A C(S) ≤ B C(S) A + |Y|( log |Y| + log 1 δ 2N + ) (1)
M aP C(S) ≤ B C(S) M aP ( )+ log |Y| + log 1 δ 2N , M aR C(S) ≤ B C(S) M aR ( )+ log |Y| + log 1 δ 2N (2)
M aF C(S) ≤ 2B C(S) M aP ( )B C(S) M aR ( ) B C(S) M aP ( ) + B C(S) M aR ( ) + log |Y| + log 1 δ 2N (3)
Proof. (sketch) We first consider the case where S = S train . Using Hoeffding's inequality for random variables bounded in the interval [0, 1], we have the standard result that, for any δ ∈]0, 1], with probability at least (1 -δ):

∀y ∈ Y, p y ≤ py + log |Y| + log 1 δ 2N
The log |Y| factor is a result of the fact that the bound should hold simultaneously for all categories. This implies, using the quantification assumption, that, for any δ ∈]0, 1], with probability at least (1 -δ), ∀y ∈ Y: The above theorem is inspired by a previous result we have developed in the context of multi-class classification [START_REF] Babbar | Re-ranking approach to classification in large-scale power-law distributed category systems[END_REF]. We have generalized and extended it here through the consideration of macro measures and quantification. Even though this extension renders the developments more complex, it is crucial for model selection using unlabeled datasets.

| min{p y × |S|, M C(S) y } -min{p y × |S|, p C(S) y × |S|}| < |S|( log |Y| + log 1 δ 2N + ) (4)
When the Classify and Count (CC) quantification method is used, then, by definition, p

C(S) y = M C(S)
y |S| , and can be set to 0. This leads to stricter bounds for all the measures. Furthermore, the condition min{p y , py , p M aR (0). Lastly, it can be noted that the quality of the bound is better for the macro measures than for the accuracy as the multiplying |Y| factor is dropped.

Theorem 1 states that the accuracy, macro-precision, macro-recall and macro-F1 of a classifier can be upper-bounded by quantities that are related to the behavior of the classifier on an unlabeled dataset, and that the quality of the bound depends on the number of classes, the size of the training set, the quality of the quantification method and the precision desired. These bounds represent necessary conditions for a classifier C to have high accuracy/macro-F1 4 . They can nevertheless be exploited, within a given family of classifiers obtained through e.g. different regularization parameters, to select good classifiers. Model Selection Using Quantification Bounds. We consider here a standard regularization setting in which one aims at minimizing a combination of the empirical error and the model complexity using the following template of the objective function:

ŵ = arg min R emp (w) + λReg(w)
where Reg(w) is the regularization term to avoid overfitting and R emp (.) represents the empirical error.

The parameter λ controls the trade-off between the empirical error and the regularization term. As mentioned before, λ is typically estimated through holdout estimation or k-fold cross-validation. We propose here to estimate it on the basis of the upper bounds presented in Theorem 1, as described in Algorithm 1. As one can note, for each value of λ, a classifier is trained and quantified on the unlabeled set S. If the quantification assumption of Theorem 1 is not valid, then one falls back on the Classification and Count method for quantification. The bounds, as computed by Inequalities 1 and 3 are used to select the "best" classifier. Tuning the hyper-parameter is, therefore, reduced to the problem of finding a classifier which yields the highest value of the bounds on a given set. In contrast with other selection methods, the set used to select the classifier can be an unlabeled set from the same distribution (unlabeled data is usually readily available, contrary to labeled data) or the test set in a transductive-like scenario.

In terms of complexity, the quantification cost is reduced to the prediction for the already trained classifier, which is linear in the cardinality of the set S on which quantification is performed. The computational cost for Algorithm 1 is thus the same as 1-fold cross-validation. Additionally, as only one hypothesis is generated for each parameter value by training to the whole set of labeled data one has just to select the hypothesis with the highest bound without the need of retraining the model in contrast to hold-out or k-fold cross-validation. More precisely, the complexity of our approach for m values of λ is O([Tr(N) + Pr(M)]×m), which is k times lower than the complexity of k-CV with re-training the learner for the selected λ value, given by O([Tr(( k-1 k )×N)+Pr(

Experimental Framework

To empirically evaluate the model selection method presented above we use the publicly available datasets of the LSHTC 2011 (Large Scale Hierarchical Text Classification) challenge [START_REF] Partalas | Lshtc: A benchmark for largescale text classification[END_REF]. Specifically, we make use of the Dmoz and Wikipedia datasets containing 27,875 and 36,504 categories respectively. The datasets are provided in a pre-processed format using stop-word removal and stemming while we transformed the term-frequency vectors to the tf*idf representation. For each of the datasets we randomly draw several datasets with increasing number of classes.

Table 1 presents the important statistics of the different datasets. As one can note, the number of categories in our datasets ranges from 250 to 2, 500, and the number of features from 26, 000 to 212, 000. An interesting property of the instances of those datasets is the fit to the power law distribution. As a result, there are several under-represented classes having a few labelled examples. Thus, model selection approaches using only a fraction of the labeled instances, such as hold out, may lead to sub-optimal decisions.

The classification problems defined from our datasets are multi-class, and we adopt a standard one-vs-rest approach to address them (the large datasets considered prevents one from using more complex multi-class approaches). The Dmoz dataset is single-labeled, i.e. each training/test instance is associated to a single target category. On the other hand, the Wikipedia dataset is multilabeled with the average labels per instance in the training set being 1.85. We transformed the multi-label problem to single label, both in the training and the test phase, by replicating the multi-labeled instances according to the number of their labels.

In order to empirically measure the effectiveness of model selection, we compare the following three methods: (i) k -CV, using k = 5 folds, (ii) hold-out estimation with a split of 70% and 30% for the training and the validation sets, and (iii) our method using as quantification set i) an unlabeled set denoted "quantification set" in Table 1: The properties of the datasets we used. The dataset name denotes the collection we sampled it from; its subscript denotes the number of categories.

Evaluation of the quantification methods. We first discuss the performance of the quantification methods presented above (CC and PCC), prior to comparing the results obtained by the different model selection methods (k-fold cross-validation, hold-out estimation, Bound UN and Bound Test ). Recall that Theorem 1 is based on the assumption that the quantity Max = max y∈Y |p

C(S) y - M C(S)
y |S| | is small. As mentioned above, this quantity is null for the quantification method CC, which thus agrees with our theoretical developments. The other quantification method considered, PCC, is based on the probabilities that an instance belongs to a class. When using LR, those probabilities are directly produced by the model. For SVMs, however, one needs to transform the confidence scores into probabilities, which can be done in several ways, as using a logistic function, a multivariate logistic regression function or neural networks based on logistic activation functions and without hidden layers (the latter two settings can be seen as generalizations of Platt's scaling for the multi-class problem). We obtained the best results with a simple logistic function defined as 1 1+e -σt , varying σ from 1 to 10. Table 2 displays the values of Max obtained for PCC for each of the dataset and for each classifier (the default hyper-parameter values of the classifiers are used), using the value of σ leading to the lowest value of Max . As one can note, although the values obtained are small in most cases (except for Dmoz 1000 and Dmoz 1500 ), there are not negligible compared to the class prior probabilities, which are in the range of 1 divided by the number of classes. Thus, the quantification method PCC does not fully agree with our theoretical development. It turns out that it also performs worse than CC in practice. We thus rely on this latter method for the rest of our experiments. dmz250 dmz500 dmz1000 dmz1500 dmz2500 wiki250 wiki500 wiki1000 wiki1500 wiki2500 SVM 0.0728 0.0967 0.1067 0.1125 0.0345 0.0287 0.0754 0.0310 0.0425 0.0365 LR 0.0942 0.0674 0.0889 0.1111 0.0530 0.0219 0.0517 0.0481 0.0310 0.0294

Table 2: Evaluation of the assumption of Theorem 1 concerning the quantification step. For each dataset, we present Max for the PCC quantification method.

Model Selection Evaluation. We evaluate model selection methods for two families of classifiers: (i) SVMs, and (ii) LR which are among the best performing models in text classification. We explore for both classifiers the value for the regularization parameter λ ∈ {10 -3 , 10 -2 , . . . , 10 4 }. We used the implementations in Python's scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] that are wrappers of the LibLinear package [START_REF] Fan | LIBLINEAR: A library for large linear classification[END_REF].

We report the scores obtained in Accuracy and Macro-F (MaF) measure when a classifier is applied on the test set. In particular, for each dataset of Table 1 the model selection methods are used only for selecting the regularization parameter λ when optimizing for the repsective measure. After the selection of λ, the classifier is retrained on the entire training set, and we report its performance in the test set. This last step of retraining is not required for our method since the classifier is trained in the overall labeled set from the beginning. Also, as hold-out estimation may be sensitive to the initial split, we perform 10 different random splits training/validation and report the mean and the standard deviation of the scores obtained for both evaluation measures.

Figure 1 illustrates the model selection decisions for the different methods using an SVM on the Wikipedia dataset with 1, 500 classes for the MaF measure. The curve MaF corresponds to the actual MaF on the test set. Although each parameter estimation method selects the value for λ that seems to maximize the performance, the goal in this example, ultimately, is to select the value that maximizes the performance of MaF. For instance, hold-out, by selecting λ = 10 -1 , fails to select the optimal λ value, while all other the methods succeed. Here, the 5-CV approach requires 1310 sec., whereas the bound approach only requires 302 sec. (the computations are performed on a standard desktop machine, using parallelized implementations on 4-cores). The bound approach is thus 4.33 times faster, a result consistent over all experiments and in agreement with the complexity of each approach (Section 3). Lastly, we notice that the curve for Bound UN with the quantification method CC follows the MaF curve more strictly than the curve with the quantification method PCC. Table 3 presents the evaluation of the three model selection methods using as classifiers SVM and LR respectively. As one can note, the performance of the method proposed here is equivalent to the one of cross-validation, for all datasets, and for both classifiers and performance measures (accuracy and MaF). The performance of SVM is furthermore higher than the one of LR on all datasets, and for both evaluation measures, the difference being more important for the MaF. The performance of cross-validation however comes with the cost of extra processing time, as our method achieves a k speed-up compared to cross-validation. If both methods can easily be parallelized (at least on the basis of the number of values of the hyper-parameter to be tested), k-fold cross validation requires k times more computing resources than our method.

Unlike cross-validation, hold-out estimation fails to provide a good model in many instances. This is particularly true for SVMs and the MaF measure, for which the model provided by hold-out estimation lies way behind the ones provided by Bound UN and Bound Test on several collections as Dmoz 1500 and Dmoz 2500 . The difference is less important for LR, but the final results in that case are not as good as in the SVM case.

Conclusions

We have presented in this work a new method for model selection that is able to exploit unlabeled data (this is in contrast with current model selection methods). To do so, we have introduced quantification-based bounds for accuracy and macro performance measures. We have then shown how to apply this bound in practice, in the case where unlabeled data is available in conjunction with labeled data, and in a transductive-like setting where the instances to be classified are known in advance. The experimental results, obtained on 10 datasets with different number of classes ranging from 250 to 2,500, show that the method proposed here is equivalent, in terms of the quality of the model selected, to k-fold cross-validation, while being k times faster. It furthermore consistently outperforms hold-out estimation for SVM classification, for both accuracy and macro-F1, the difference being more important for macro-F1. Furthermore, and contrary to hold-out estimation, our method needs neither a validation/train splitting procedure nor a retraining procedure.

In our future work we plan to investigate the application of a generalized versino of the proposed model selection approach in cases where more than one hyper-parameters have to be tuned. In this framework, we also plan to

  ∃ , min{p y , py , p C(S) y }, ∀y ∈ Y : |p C(S)

  min{p y × |S|, M C(S) y } corresponds to an upper bound on the number of documents of S correctly classified by C in class y. Hence, the accuracy of C on S is upper bounded by: y∈Y min{p y × |S|, M C(S) y } |S| which leads, using Inequality 4, to Inequality 1. The other bounds can be derived in the same way.

C

  quantification assumption implies that the term |S| is negligible compared to |S| × py or |S| × p

1 kAlgorithm 1

 11 ×N)]×k×m+T(N)), where Tr(N), Pr(N) are the training and predicting costs for N examples. Model selection using the proposed bounds Require: Training data Strain = {(x (i) , y (i) )} N i=1 , unlabeled data S = {(x (j) )} M j=1 and learning algorithm (SVM, Logistic Regression, ...) 1: for each value of λ (typically λ ∈ {10 -4 , 10 -3 , . . . , 10 2 , 10 3 } do) 2: Train a classifier C λ using Strain 3: Perform quantification of C λ on S using method Mq (typically CC or PCC) 4: If Mq = CC, set = 0 5: If Mq = CC, set = maxy∈Y min{py, p C(end for 10: Select C λ with the highest accuracy/macro-F1 bound

Fig. 1 :

 1 Fig. 1: Model selection process for SVM on the wiki 1500 for MaF. The squares denote the best performance for each method.

Table 1 ,

 1 and ii) the test set which may be available during training in a transductive alike scenario. The corresponding methods are called Bound UN and Bound Test respectively.

	Dataset #Training inst. #Quantification inst. #Test inst. #Features # Parameters
	dmoz250	1,542	2,401	1,023	55,610	13,902,500
	dmoz500	2,137	3,042	1,356	77,274	38,637,000
	dmoz1000	6,806	10,785	4,510	138,879 138,879,000
	dmoz1500	9,039	14,002	5,958	170,828 256,242,000
	dmoz2500	12,832	19,188	8,342	212,073 530,182,500
	wiki250	1,917	3,095	1,003	26,699	6,674,750
	wiki500	4,912	8,190	2,391	46,556	23,278,000
	wiki1000	7,887	12,790	4,067	60,788	60,788,000
	wiki1500	12,156	19,776	6,160	79,973 110,959,500
	wiki2500	22,642	37,398	11,171	109,694 274,235,000

This work was done when the author was at University of Grenoble, Alpes.

They do not provide a sufficient condition since it is possible, in an adversarial setup, to achieve an upper bound of 1 on the accuracy by simply assigning instances to categories in the same proportion as in the training set.

Acknowledgements

This work is partially supported by the CIFRE N 28/2015 and by the LabEx PERSYVAL Lab ANR-11-LABX-0025.

research the extension of the theoretical and experimental findings to multilabel classification problems i.e., multi-class classfication problems where each instance can be given more than one categories at once.


François Derkx

Bérengère Lebental

Erick Merliot

Jean Dumoulin

Frédéric Bourquin

The mini climatic city a dedicated space for technological innovations devoted to Sustainable City

Our cities, from megalopolis to rural commune, are systems of an extraordinary technological and human complexity. Their balance is threatened by the growing population and rarefaction of resources. Massive urbanization endanges the environment, while global climate change, through natural hazards generated (climatic, hydrological and geological), threats people and goods. Connect the city, that is to say, design and spread systems able to route, between multiple actors, a very large amount of heterogeneous information natures and analyzed for various purposes, is at the heart of the hopes to make our cities more sustainable: climate-resilient, energy efficient and actresses of the energy transition, attractive to individuals and companies, health and environment friendly. If multiple players are already aware of this need, progress is slow because, beyond the only connectivity, it is the urban intelligence that will create the sustainable city, through coordinated capabilities of Perception, Decision and Action: to measure phenomena; to analyze their impact on urban sustainability in order to define strategies for improvement; to effectively act on the cause of the phenomenon. In this very active context with a strong societal impact, the Sense-City project aims to accelerate research and innovation in the field of sustainable city, particularly in the field of micro and nanosensors. The project is centered around a "mini climatic City", a unique mobile environmental chamber in Europe of 400m 2 that can accommodate realistic models of city main components, namely buildings, infrastructures, distribution networks or basements. This R&D test place, available in draft form from January 2015 and in finalized version in 2016, will allow to validate, in realistic conditions, innovative technologies performances for the sustainable city, especially microand nano-sensors, at the end of their development laboratory and upstream of industrialization. R & D platform located in the heart of the Cité Descartes in Paris Est and open to both academic as industrial and communities, Sense-City participates in the positioning of the Cité Descartes as a flagship tertiary center for the city of the future. The areas of interest cover the energy performance of buildings and neighborhoods, the sanitary quality of the frame (indoor air pollution), the quality and sustainability of urban networks (transport, fluid), the quality of outdoor air, soil and water, control of waste storage areas, sustainability and infrastructure security. In the framework of this project, a first outdoor test bed was designed and built in 2014. Various sensing capacity have been implemented and first experimentations started in 2015. The project partners, IFSTTAR, ESIEE-CCIP LPICM (UMR CNRS Ecole Polytechnique), CSTB, INRIA and UPEM, controls the entire value chain for the development of innovative products for the sustainable city, nano or prototyping microsensors up to validation in real conditions, not to mention the steps of integration, packaging and deployment of the sensors or the processing steps, modeling and representation of information.


Christophe Dony
email: dony@lirmm.fr

A Fully Object-Oriented Exception Handling System: Rationale and Smalltalk Implementation

This paper motivates and presents the specification and the implementation of an exception handling system for an dynamically typed object-oriented language. A full object-oriented representation of exceptions and handlers, a meta-object protocol to handle using either termination or resumption makes the system powerful as well as extendible and solves various exception handling issues. Three kind of dynamic scope handlers (expression handlers, class handlers and default ones) make it possible to define reusable and fault-tolerant software modules. The implementation of the system is readable and simple to understand because achieved entirely in Objectworks Smalltalk, thanks to the reflective facilities of this language.

Introduction

The program structures for handling exceptional events [START_REF] Goodenough | Exception Handling: Issues and a Proposed Notation[END_REF] [START_REF] Levin | Program structures for exceptional condition handling[END_REF] [13] [START_REF] Christian | Exception Handling and Software Fault-Tolerance[END_REF] [24] [START_REF] Knudsen | Better Exception Handling in Block Structured Systems[END_REF] have been designed to implement software entities able to return well defined and foreseen answers, whatever may happen while they are active, even though an exceptional situation occurs. The end of the 1970s saw the development of exception handling systems dedicated to procedural programming. All specifications have all been influenced by Goodenough's seminal paper [START_REF] Goodenough | Exception Handling: Issues and a Proposed Notation[END_REF]. Well known implementations include MESA [START_REF] Mitchell | MESA Language Manual[END_REF], CLU [START_REF] Liskov | Exception Handling in CLU[END_REF] or ADA [START_REF] Ichbiah | Preliminary ADA Reference Manual. Rationale for the Design of the ADA Programming Language[END_REF]. Exception handling systems have later been integrated into object-oriented languages at the end of the 1980s (Zetalisp+Flavors [START_REF] Moon | Signaling and Handling Conditions[END_REF], CommonLisp(+CLOS) [START_REF] Pitman | Error/Condition Handling[END_REF], Eiffel [START_REF] Meyer | Disciplined exceptions[END_REF], Objectworks Smalltalk [START_REF]Objectworks for Smalltalk-80[END_REF], C++ [START_REF] Koenig | Stroustrup: Exception Handling for C++[END_REF], or more recently in Java.

This papers presents an overview of the specification and implementation of an exception handling system initially conceived [START_REF] Dony | An Exception Handling System for an Object-Oriented Language[END_REF] for the Lore Object-Oriented Language and adapted to Smalltalk [START_REF] Dony | Exception handling & Object-Oriented Programming: Towards a Synthesis[END_REF]. The key-ideas of this system are (1) to apply object-oriented design to the whole system, to define a reusable and open class library for exception handling allowing systems designers to reuse it to produce dedicated exception handling systems and (2) to take into account the specificity of objectoriented programming by integrating expression and class handlers allowing users to define functional, class-based or even component-based fault tolerant modules.

Implementations of exception handling systems are rarely presented because they are generally done at a low level (compilers, virtual machines) and hard to describe in the context of a paper. The implementation of this system is reasonably readable and simple to understand because achieved entirely in Objectworks Smalltalk, thanks to the reflective facilities of this language. The main implementation issues detailed in the paper are: the internal representation of handlers, the algorithm for searching them -knowing that both resumption and termination are allowed, the achievement of termination and resumption, which takes into account some possible user-defined unwind protections. Our EHS has been specified and implemented as the same period than Objectworks Smalltalk's one and both share many similarities (except for class and default handlers) but none of their implementations have been published yet.

Section 2 recalls some definitions and introduces our notations. Section 3 presents our EHS specification and motivates the main choices. Section 4 presents the implementation. Point to point comparison with related works is scattered in the different sections. Sections 3 require that readers have a minimal knowledge of the Smalltalk syntax. Section 4 supposes a higher knowledge of that system but should be globally readable by anyone knowing object-oriented languages.

Definitions, Terminology, Notation

Software failures reveal either programming errors or the application of correct programs to an ill-formed set of data. An exception can be defined as a situation leading to an impossibility of finishing an operation. The problem of handling exceptions is to provide materials allowing to establish communication between a function or procedure which detects an exceptional condition, while performing an operation, and those functions or objects or modules that are clients of this operation (or have something to do with it) and wish to dynamically handle the situation. An exception handling system (EHS) allow users to signal exceptions and to associate handlers to entities (according to the language, an entity may be a program, a class, an object, a procedure, a statement or an expression). To signal an exception amounts to identify the exceptional situation, to interrupt the usual sequence of operations, to look for a relevant handler, to invoke it and to pass it relevant information about the exceptional situation, such as the context in which the situation arose. To handle means to set the system back to a coherent state. Handlers can usually choose, knowing about their definition context and using arguments provided by the signaler, whether to (1) transfer control to the statement following the signaling one (resumption), [START_REF] Christian | Exception Handling and Software Fault-Tolerance[END_REF] discard the execution context between the signaling statement and the one to which the handler is attached (termination) or (3) signal the same or a new exception, which is generally called propagation and should be interpreted as a delegation of responsibility to a more general handler.

For the examples in this paper, we use two different syntax (cf. Figure 1) for handlers declaration and definitions: firstly a general one inspired of what can be found in procedural languages, secondly the Smalltalk syntax used in our system.

Specifications

This section discusses the main issues related to the design of an EHS in a non concurrent context, explains our choices and presents the specifications of our system.

Resumption and Termination: a Dual Model

Choosing which control structures are available to write handlers bodies is one of the first crucial decision to be taken when designing an EHS and impacts the whole specification and implementation. Most exception handling systems only propose the termination model, others propose both termination and resumption (let us call this the dual model) and a few ones only propose resumption [START_REF] Levin | Program structures for exceptional condition handling[END_REF]. The respective merits of termination and resumption have already been widely discussed in many papers, e.g. [START_REF] Goodenough | Exception Handling: Issues and a Proposed Notation[END_REF][START_REF] Liskov | Exception Handling in CLU[END_REF]. Let us just recall that to forbid termination is a very specific choice because many exceptions are really fatal. To forbid resumption is a way to produce EHS simple to use and to implement, although reducing the expressive power since some exceptions are really proceedable in some contexts. The resumption model is indeed more expensive in computation time and space, more complex to implement (see section 4) and also makes program static analysis more complex. It is however useful and time-saving in any application in which proceedable exceptions are raised, especially in interactive application in which users or operators, can choose a solution to recover from an exceptional situation. For example, interactive WEB applications can take benefit of resumption to restart calculus after a network interruption.

Handlers Scope and Fault-Tolerant Encapsulations

The scope of handlers, and as a consequence the way they are searched when an exception is signaled, determines what kinds of fault tolerant modules are offered by a system. The issue is the same whatever kind of modules are considered, classes, methods, etc.

Lexical Scope Handlers.

Lexical scope handlers are by definition accessible when located in the program textual part in which they are lexically visible. A handler for an exception raised within an inner module, if not found locally, is searched in a lexically englobing one. Lexical scope handlers allow users to define modules that handle all exceptions raised within their scope, they allow to check statically which handler will be invoked for each exception signaled within the module. Their main drawback is that exceptions are never propagated to modules clients. Various systems (e.g. Beta [START_REF] Knudsen | Better Exception Handling in Block Structured Systems[END_REF] or Smalltalk-80 [6, p.102]) provide lexical scope handlers. As an example, let us consider the standard Smalltalk-80 ones (cf. Figure 2). The Smalltalk historical EHS specification only uses the language standard constructions; this is the same for Beta and this is one of the great advantages of this static approach. Exceptions are signaled within methods by sending to self, a message (e.g. error:). Handlers are standard methods defined on classes (let us call them class handlers) and are invoked by a standard message sending: they can only be found in the class (or one of its super-classes, they are of course inherited) in which the signaling method is defined. This means that, as far as exceptions are never propagated to operations callers, a method has no way to regain control, either to hide the occurrence of an exception (modularity) or to execute some recovery actions, when one of the methods it has invoked failed. We come back in section 3.5 on the potential interest of class handlers in term of expressive power and reusability. object method error method doesNotUnderstand .... application1 method error application2 method doesNotUnderstand "default handlers" "user-defined handlers" class subclass Fig. 2. Smalltalk-80 lexical scope class handlers Dynamic Scope Handlers. On the other hand, dynamic scope handlers are searched in the execution stack when an exception is raised. They allow standard and exceptional responses to be specified in software modules interfaces. For a given module, internal exceptions are those handled internally, and external exceptions (sometimes called failures) those propagated to the module's clients. Dynamic scope handlers allow clients to retrieve control when the modules they use fail and to give execution context dependent answers to these failures. The semantic of the signaling process is then to transfer the problem from a place where it can only be noted to a place where it could be interpreted. The following example illustrates the first idea: the client module, a procedure process-yield correctly encapsulates its private's use of its a list by trapping the exceptions possibly raised by the list manipulation and by propagating an exception (InactiveProcess) of the same conceptual level than the achieved service. The second idea (giving caller context dependent answers) is illustrated the pgcd example. This is just a toy example, more expensive than the standard version without exception handling, but short enough to be presented here. All handlers in our system have a dynamic scope. Most of earlier EHS for procedural languages such as PL/I, Clu, or Mesa, and recent ones, for object oriented languages (Clos, C++, Java) are based on a stack-oriented research of dynamic scope handlers (limited to one stack level in CLU). New evolution of the Beta EHS integrates such handlers [START_REF] Knudsen | Exception Handling and Fault Tolerance in Beta[END_REF].

Status of Exceptions

The next issue to be discussed is the status of exceptions and of exceptional events. How are exceptions represented and referenced? How can they be manipulated or inspected?

Exceptional Events as First-Class Objects. The idea that consists in representing each conceptual exception by a class and each of its concrete occurrences (what we call exceptional events) as an instance (an exception object) of that class can initially be found in Taxis [18], Zetalisp [START_REF] Moon | Signaling and Handling Conditions[END_REF] or [START_REF] Borgida | Language Features for Flexible Handling of Exceptions in Information Systems[END_REF] and is now almost a consensus; all todays object oriented systems have integrated it. Let us shortly recall its main interests.

-Exceptions can be organized into a knowledge sharing inheritance hierarchy.

-It is possible trap different events with a single handler.

-Signalers can communicate with handlers [START_REF] Miller | Issues with Exception Handling in Object-Oriented Systems[END_REF] pass to handlers the instance of the signaled exception which holds in its slots all the information about the exceptional situation. -New user-defined exceptions can be created as subclasses of existing ones. There is no distinction between system and user-defined ones, all can be signaled and handled in the same way.

ExceptionalEvent ExceptionClass

Class Object class instance subclass class Exceptions as First Class Entities. The systems that pioneered the above idea did not brought it to its limits; for example in Zetalisp, signaling and handling primitive are not standard methods invocable by sending messages to exceptions objects. We have extended the above idea towards a complete object-oriented representation of all entities composing the EHS and towards an EH meta-object protocol to handle exceptions. Another language in which similar ideas can be found is Objectworks Smalltalk. The first step in that direction has led us to make conceptual exception first class entities by defining exception classes as instances of a metaclass. The Figure 3 shows the two kernel classes of our specification for what concerns exceptions representation. Each occurrence of an exception is an instance of a subclass of the class ExceptionalEvent that holds basic protocols for handling All exceptions classes are instances of the meta-class ExceptionClass1 that holds basic protocols for signaling and are subclass of ExceptionalEvent. The next sections detail the advantages of that organization.

Basic Primitives

The dual model of exception handling imposes that primitives for termination and resumption be available to write handler bodies. All our basic primitives to handle exceptions (exit and retry for termination, resume for resumption and signal for propagation) are implemented by standard methods defined on a set of kernel exception classes (cf. Figure 4) and constitute a meta-object protocol (following the CLos definition of term) for exception handling.

Kernel Exception Classes and Basic

Handling Primitives. ExceptionalEvent is then divided into FatalEvent, to which are attached termination primitives, and ProceedableEvent to which are attached those for resumption. The slot signalingContext is to be dynamically bound at each occurrence of an exception to the signaling context. The slot propositions (instance variable of the meta-class) is used to store for each exception some propositions for interactive handling as initially proposed in Zetalisp. From the user's viewpoint, the system is then based on three predefined exception classes.

-Error is the class of exceptional events for which resumption is never possible whatever the context in which the event is signaled. -Warning is the class of exceptional events for which the termination is impossible.

-Finally, multiple inheritance is simulated to create the exception-class Event in order to allow both capabilities.

Basic Signaling Primitive. Within EHSs supporting the dual model, a set of primitives is generally provided to support the various signaling cases. E.g., in Goodenough's proposal, signaling with escape states that termination is mandatory, notify forces resumption and signal lets the handler responsible for the decision. In our system, signal is the single basic signaling primitive because knowing whether the signaled exception is proceedable or not only depends of its type (its position in the exception hierarchy). To signal an exception amounts to send the exception class the message signal whose corresponding method is defined on ExceptionClass (i.e. on ExceptionalEvent class in the Smalltalk implementation). Signal creates the "exception object" and assigns its slots with, on the one hand values given by the signaler and on the other hand, values owned by the system (e.g. signalingContext), cf. Figure 5 for an example. Signal finally sends to the initialized instance the message lookForAndInvokeHandler (cf. Figure 4), which will find and invoke a handler.

Additional Primitives and Control Structures

Unconditional Restorations. The dual model raises various issues that require additional primitives. The first issue is the restoration of coherent program states. Any method has to ensure that it will leave data, memory and resources in a coherent state whatever happens during its execution. A first solution to that problem, found in many systems is to give programmers the ability to define handlers that trap all exceptions to re-signal (propagate) the trapped one. The following example illustrates that solution, in a procedural-like syntax with the classical file example. It also highlights the fact that this solutions forces programmers to write restoration actions twice, once for normal and once for exceptional exit.

File f;. {open(f); workOn(f);. close(f); {when any-exception (e) do {close(f); signal(e);}}} However, that solution does not work properly in the dual model because a later handler may entail resumption and put the system back into an incoherent state in which f would be closed but should not be. To avoid writing more complex handlers and the duplication of the close instruction, an ad-hoc. primitive (cf. cleanup handlers in [START_REF] Goodenough | Exception Handling: Issues and a Proposed Notation[END_REF] or Lisp's unwind-protect) is necessary to allow users to write unconditional restoration statements executed whenever the procedure's related stack frame is really discarded. The exception handling system has to take this primitive into account while performing termination, by executing in the right order and in the right environment the restorations (cf. Section 4.5). In our system, the file example can thus be written as follows:

f := File new. [f.

Various Kind of Handlers

This section deals with issues related to handler definition and shows how to create various kind of handlers in our system. It is first classical to associate handlers to pieces of code (expressions, blocks, procedure or programs). Besides, different researches have investigated the idea of associating handlers with data structures [START_REF] Levin | Program structures for exceptional condition handling[END_REF] thus controlling exceptional situations arising when manipulating them. Within an object-oriented language, it is also natural to wonder whether it is interesting to associate handlers to objects or to classes and with which semantics Finally many solutions have been proposed in existing systems to store the most general, execution context independent, default handlers

Expression handlers.

For what concerns pieces of code, we offer the possibility to associate handlers to any kind of Smalltalk expressions. This is done by grouping the expressions into a lexical closure 3 (a block in Smalltalk) and by sending this block the message when:do. The first argument <exception-name> is the exception to be trapped and the second one is the handler. Handlers have one parameter bound at handling-time to the current exception object. Class Handlers. To associate handlers with individual objects is not compatible with the class-based model in which all instances of a class have to share the same behavior. Besides, we have quoted in section 3.2 the existence of handlers associated with classes in Smalltalk-80 and in Beta. We propose to define equivalent handlers but to give them a dynamic scope. A class handler associated with a class C for an exception E will thus be able to trap all occurrences of E raised anywhere during the execution of any method of C or of C's subclasses. Such class-handlers allow programmers to control which exceptions can be propagated outside of any methods of a class, to control for example, that overflow and EmptyStack are the only exceptions that can be propagated outside of any method defined on the class Stack. These class handlers also induce original reusability schemes based on inheritance. Consider again the class Stack. Now suppose that a class of stacks that are able to grow is needed. A simple solution to this consists is creating a Stack subclass named GrowingStack, on which is defined a handler for overflow and a method grow, this handler can resume the interrupted method, whatever its name and its location, after having grown the stack buffer. Class-handlers have been widely used in this way in Smalltalk-80 extensions to modify message sending, e.g. to implement Encapsulator or to implement asynchronous message sending in the Briot's Actalk System. A few systems provide dynamic scope class handlers (see. e.g. [START_REF] Purchase | Message Pattern Specifications: A New Technique for Handling Bugs in Parallel Object Oriented Systems[END_REF]). In our system, class handlers can be attached to any class by using the method when:do:, defined on ClassDescription, with the following syntax: The first argument is the exception to be trapped and the second one is a string. This method when:do: first calls the Smalltalk compiler to compile the handler string in the environment of the protected class so that instance and class variables defined on the class can be accessed. Then it inserts the created handler in the handler collection of the class and of its subclasses. For each class, class-handlers are ordered compared to the exceptions they are defined for. Class-handlers cost nothing while exceptions are not signaled; they only are taken into account at signaling time.

Default Handers. Interesting but somehow semantically complex propositions to define default handlers at various program levels can be found e.g. in [START_REF] Pitman | Condition Handling in the Lisp Language Family[END_REF]. We have chosen a simpler point of view in which default handlers are considered as the place where the most general information regarding how to handle an occurrence of an exception, independently of any execution context, should be stored. We propose to associate them to exceptions by defining them as methods (named defaultHandle) defined on exception classes. The system most general default handler is defined on ExceptionalEvent and can be overridden in subclasses, each exception can thus own its specific default handler. Default handlers are invoked by sending the message defaultHandle to the exception object as shown in the top-level loop example (cf. Section 3.7). We have integrated the idea of interactive propositions found in Zetalisp, which exploits exception hierarchies. A proposition is a couple of two method names, one to display a string and one to execute a corresponding action. Propositions are stored for each exception in the slot named propositions defined on ExceptionClass and displayed when the most general default handler is invoked.

Writing Handlers Bodies in a Generic Way

All kind of handlers can use the same primitives in the same generic way to put the program execution back into a coherent state. Genericity first means that neither programmers nor implementors have to perform tests to ensure that operations incompatible with the signaled exception will not be invoked -Note that his rule is violated for resumption where the slot protocolForResumption is tested by the system. For example, any attempt to send the message exit: to an object which is not a FatalEvent will fail. Genericity also means that the operations relevant to the current exception object will automatically be selected even though an abstract (multiple) exception has been caught.

Termination Examples.

Sending to the exception object the message exitWith: entails termination. The execution stack frames located between the signaler and the handler are discarded while recovery blocks are executed. The argument's value becomes the value returned by the expressions to which the handler is attached. Here is our system's version of the above function pgcd, now defined on class Integer, that uses termination. For what concerns a class-handler, which is invoked when an exception is about to be propagated outside of a method C defined on a protected class, termination ends C's execution and the exit value becomes the value returned by C's invocation. The following example is an implementation of the growing stack example described in Section 3.6, it highlights the interest of the retry primitive. Finally, default-handlers are conceptually attached to the program main procedure (or to the top-level loop in an interpreted environment), thus termination in a defaulthandler ends the program execution (or returns to the top-level). Here is an example of applying termination that uses both exit and retry , to implement a top-level loop. The only way to exit the loop is to signal the exception LoopExit. If any other exception is trapped, its default handler is invoked and finally, whatever it does, the loop is re-entered.

Implementation

This section describes some key-points of the above specification implementation which is entirely achieved in Objectworks Smalltalk without any modification to the virtual machine. This has been possible thanks to the reflective capabilities offered by this programming environment, particularly because methods, lexical closures and the execution stack are or can be made first class objects. The main focus is put on the representation of exceptions, of handlers and on the signaling algorithm taking into account expression, class and default handlers within a context in which both resumption and termination are allowed. The interest of this section is to describe this algorithm in its real implantation context.

Objectworks Smalltalk EHS specification has considerably evolved since the blue book specification and share many common points with our specification, except for what concerns class handlers and less importantly interactive propositions. The implementation of Objectworks EHS, as far as I know never described in any paper, also shares common point with ours but is more efficient because part of it have been moved to the virtual machine. In particular, stack frames are no more reified but are accessed at the virtual machine level.

Exception Classes

The class ExceptionalEvent (cf. Figure 6), the root of our exception classes hierarchy, declares four instance variables, three of them are of interest here. SignalingContext is used to store the stack frame (we will frequently call stack frame "contexts" because Smalltalk objects that represent them are called "contexts objects") in which the exception has been signaled. HandlerContext is used to store the context in which a handler is found. ErrorString allows users to pass a string argument to handlers. ExceptionalEvent also declares different class variables, four of which (BottomStackMethod, HandleMethod, InvokeHandlerMethod and UnwindMethod) designed to store references to particular methods addresses that will be used during handler research and invocation.

Object subclass: #ExceptionalEvent instanceVariableNames: 'errorString signalingContext handlerContext private ' classVariableNames: 'BottomStackMethod HandleMethod InvokeHandlerMethod RetryMark UnwindMethod ' initialize "defined on ExceptionalEvent class" HandleMethod := BlockClosure compiledMethodAt: #when:do:. UnwindMethod := BlockClosure compiledMethodAt: #unwindProtect:. BottomStackMethod := SmalltalkCompiler compiledMethodAt: #evaluate:in:to:notifying:ifFail:. InvokeHandlerMethod := ExceptionalEvent compiledMethodAt: #invokeHandler:with:. RetryMark := #().

Fig. 6. ExceptionalEvent class (detail)

Note for example that the method when:do: allowing users to define expression handlers is represented by a Smalltalk object that can be retrieved by sending to the class BlockClosure, on which the method is defined, the message compiledMethodAt:. SpecialMark contains a unique mark used to implement the retry method Finally, this class also defines an interactive proposition named askForRetry.

Status and Storage of Handlers

Default handlers are standard methods defined on exceptions classes under the selector handlesDefault. They do not raise any structure or storage problems.

Handlers associated to expressions. Handlers associated to expressions have to be executed in the environment in which they have been created. The resumption model forbids destroying the stack frames located between the signaler frame and the handler frame in order to allow the calculus to be eventually restarted. To invoke a handler thus supposes to go back to a previously defined environment without destroying the execution stack. A first solutions to this problem is to copy the stack at signaling time (e.g. with an equivalent of the scheme call-cc primitive), to destructively search a handler, to execute the handler in its context, now located on top of the stack, and finally to replace the current stack by the copy made at signaling time. We have neither implemented this solution nor seen it implemented. A second solution is to execute the handler on top of the stack but in its definition context, i.e. in such a way that free variables of the handler get their value and are assigned in the handler definition context. This supposes that handlers be lexical closures.

The method when:do: to associate handlers to expressions is defined (cf. below) on the class BlockClosure that represents lexical closures in Smalltalk. The receiver (self) is a block containing the protected expressions. The method simply sends self the message value, which entails the execution of the protected expressions. If an exception is raised during this execution, the system will find the handler as the second argument (handlerBlock) stored in the stack frame created by the method when:do:. when: exception do: handlerBlock "Defined on BlockClosure" ^self value Handlers Associated to Classes. Handlers associated to classes are some kind of compiled methods, of which they inherit the basic structure, the specific part of their structure being described by the ClassHandler class (see below). The instance variable domain stores the class on which the class handler has been defined, for example, the class GrowingStack for our Section 3.6 example. The event instance variable stores the exception for which the class is protected (Overflow in our example). The instance variable receiver is to be bound at handler invocation time to the object that is active when the trapped exception is raised.

CompiledMethod subclass: #ClassHandler instanceVariableNames: 'event domain receiver ' classVariableNames: 'SortBlock '

Class-handlers are stored for each class into a sorted collection from the most specific to the most general. For that purpose, we have added an instance variable named classHandlerSet to the kernel class ClassDescription with defines the basic structure of all Smalltalk classes. Albeit they have a compiled method status, classhandlers are not stored in the classes method dictionary for three reasons: they should not to be directly invoked by users, they are not connected to external selectors and they have to be stored in a specific order.

Signaling

In its simplest form, signaling simply consists in creating the exception object, an instance of the class that receives the signal message, in initializing its fields and in sending to the exception object a message to look for handlers. See next section for an explanation about the thisContext variable.

signal

"defined on ExceptionalEvent class" ^self new initialize signal signal "defined on ExceptionalEvent " signalingContext := thisContext. ^self lookForAndInvokeHandler

Handler Search

This section describes the method that looks for a handler after an exception has been raised. A simplified version is primarily presented. The complete version is described afterwards.

Accessing the Stack.

As far as handlers are searched into the stack, the first issue is to access it. The Objectworks environment is able, when asked, to represent the execution stack frames as first-class objects, instances of various subclasses of the Context class. This is powerful example of reflection because that object can not only be viewed but also modified. Modifying the slot sender of such an object effectively produces a non local jump when returning from the method in which the modification is done. At any time during a computation, creating the object representing the current stack frame can be done by accessing the read-only variable called thisContext. Its slots contain all the information needed to implement our system: -the receiver of the message the execution of which has created the frame, -the method that has been invoked as a consequence of this message, -the sender of the current frame, i.e. the calling frame lower in the stack.

A simplified Algorithm for Finding Handlers. Figure 7 describes a simplified algorithm that search a handler without taking into account exceptions signaled within handlers. When a handler is found, it is immediately invoked.

The implementation of the simplified algorithm. Figure 8 shows the method implementing this simplified algorithm. The lookForAndInvokeHandler method is defined on ExceptionalEvent and invoked while signaling by sending this message to the exception object. Within this method, self is the current exception object for which a handler is searched.

-The search starts at the signaling context sender. The signaling context is retrieved in the signalingContext instance variable of the exception object (Figure 8, line 1). UnwindContexts is a local variable used to monitor the collection of recovery actions found while going down the stack.

-A loop is entered (2) and will be exited, by returning ("^" is the smalltalk's return instruction.) the value of the method invokeHandler:with:; control never returns to the instruction following the invokeHandler:with: message sending.

Let E be the signaled exception, Let F initially be the sender of the stack frame in which the message signal has been sent, Let UnwindContexts be an empty ordered collection.

L: If F is the bottom of the stack frame then invoke default handler for E else If the frame F has been established by an invocation of the method when:do: -When a handler is found, this method (cf. section 4.5) is called (lines 5,8,12) with the handler as first argument and the unwind blocks collection monitored during the search as second argument. The handler is either a block or a kind of compiled method. The stack frame in which it is located is stored in the handlerContext slot of the exception object [START_REF] Dony | Exception handling & Object-Oriented Programming: Towards a Synthesis[END_REF][START_REF] Goodenough | Exception Handling: Issues and a Proposed Notation[END_REF][START_REF] Knudsen | Exception Handling and Fault Tolerance in Beta[END_REF] and will be used to achieve handling.

and
-The test in (3) is true when the bottom of the stack is reached. This means that no expression or class handler has been found. A default handler is invoked by sending the message handlesDefault to the exception object [START_REF] Garcia | Architectural-based Reflective Approach to Incorporating Exception Handling into Dependable Software[END_REF].

-The test in ( 6) is true if the current frame method is when:do: and if the exception object is an element of the class a reference to which is stored in the first argument of the method (arguments of the current frame method can be accessed by sending the message localAt: to the context object). This means that an expression handler has been found. Its body is stored in the second argument of the when:do: method [START_REF] Ichbiah | Preliminary ADA Reference Manual. Rationale for the Design of the ADA Programming Language[END_REF].

-The method isProtectedFor: sent to the class C of the receiver of the current frame method, returns either a class-handler for the current exception if one is present on C or nil. In the first case, the handler is invoked [START_REF] Levin | Program structures for exceptional condition handling[END_REF]. Before that, the receiver in the method that raised the exception is stored in the class handler's receiver slot [START_REF] Koenig | Stroustrup: Exception Handling for C++[END_REF].

-Lines 13 and 14 deal with unconditional recovery actions defined in unwind blocks. If only termination was supported, this would be the place to execute these actions. Supporting the dual model (termination and resumption) imposes to monitor all unwind blocks found between the signaling context and the handler context, to pass that collection to the handler and to execute them if the handler entails termination.

-In [START_REF] Mitchell | MESA Language Manual[END_REF], no handler has been found in the current frame, the loop's body is entered again with the variable currentContext pointing to the previous stack frame.

The complete version taking into account exceptions signaled within handlers. The real algorithm is more complex since it supports the dual model (termination and resumption) which imposes that handlers be executed while the signaling context has not been destroyed. The algorithm has thus to ensure that, when an exception is signaled within a handler (either an expression, class or default one), the new search starts just below the frame in which the current handler has been found, thus preventing its recursive invocation. Signaling the exception InactiveProcess in the handler for ItemNotFound is an example of such as situation as shown in Section 3.2. Figure 9 presents the complete version of the method that looks for and invoke handlers.

-The test in line 9 determines whether the current frame has been created by the invocation of invokeHandler:with:. If true, this means that the current exception has been raised within a handler and execution continues in line 9. Otherwise the standard algorithm described in the previous section is executed (line 21).

-In line 9, let e2 be the current exception object and h1 be the handler that as been invoked to trap the first exception e1. The current context objet represents the frame created by the invocation of h1; its receiver slot contains the exception object e1.

-It is first necessary to update the unwindContexts collection by concatenating ("," is the concatenation operation) (lines 11 and 12) the current recovery action collection to the collection collected during the search for h1 which is stored in the stack as the second argument of the current context method. When found, the handler h2 for e2 will have in hand the whole set of recovery actions found between e1 signaling frame and h2 definition frame, to be executed if h2 entails a termination. (2) currentContext := signalingContext.

(3) [true] whileTrue: [ (4) method := currentContext method.

(

"same code than lines 6 to 15 in Figure 8" -The handler for e2 now has to be searched below the frame in which h1 has been defined and which is stored in e1's handlerContext slot. As specified by the instruction in line 13, the currentContext is assigned to h1 definition context.

-Before continuing the search in the previous frame (line 20) a special case has to be handled. If h1 is a default handler, its definition context is the bottom of the stack frame and in such a case, tested in line 14, the search is stopped and the most general default handler has to be invoked (line 18).

Handler invocation

The method to invoke handlers is shown in Figure 10. All handlers (either lexical closure or class-handlers) are invoked by receiving the value: message with argument the current exception objet (cf. Figure 10,line 5). Two marks are stored in the stack (lines 3 and 5) just below that invocation point using the method mark:catch: which is an equivalent of the classical lisp catch function.

Termination will be implemented by a non local exit to the mark named #exit and resumption by a non local exit to the mark named #resume (see next section). If termination is ordered, control reaches line 7. There, all unconditional restorations monitored during the handler search are executed by the method fastUnwind:. Then the current execution frame is assigned to the handler context (line 8); this effectively discards all stack frames between the signaling and the handling point. Finally, the given exit value is tested (line 9). If this value equals the retry dedicated special mark, a retry has been ordered and the expressions to which the handler were associated are executed again (line 10), otherwise the exit value is simply returned as the value of these expressions (line 11). If resumption is ordered, control reaches line [START_REF] Levin | Program structures for exceptional condition handling[END_REF] and the resume value is simply returned as the value of the handler invocation. It is the responsibility of the signaler to examine the returned value and to achieve the selected solution to restart the standard execution. Termination. Termination is simply implemented within the exit primitive (cf. Figure 11) by a destructive non local exit down to the #exit mark previously stored in the stack. The method mark:exit: is an equivalent of the throw classical lisp function.

If the retry protocol is chosen, the value passed to throw is our registered special mark.

"Methods defined on FatalEvent class" retry "exit and execute protected operation again." self mark: #exit throw: SpecialMark. exit self exitWith: nil.! exitWith: aValue self mark: #exit throw: aValue. There is no room to present other aspects of the system such as interactive propositions; however, their implementation does not raise any problem. The complete implementation can be downloaded from the author WEB page.

Conclusion

We have presented a specification and implementation of an open and expressive exception handling system for a dynamically typed object-oriented language. It provides a full object-oriented representation of exceptions and handlers. This now classical organization allows users to organize exceptions in an inheritance hierarchy reflecting the possible sharing of structures and behavior, and to trap any subset of exceptions with a single handler. The ability to define handling primitive on classes and to invoke them via message sending to the exception object makes it impossible to perform an inappropriate action for a given exception. The distribution of handling primitives on various abstract exception classes simplifies the signaling process by restricting the number of signaling primitives. Handlers can be associated to expressions and classes. We have shown the interest of associating dynamic scope handlers with classes. Class handlers are more than a powerful shorthand, they induce original ways to use inclusion polymorphism reusability. This system architecture can also be considered as a framework for developing dedicated exception handling systems. It is for example very easy to use it to generate, by subclassing, other systems in which, for example, resumption or termination are forbidden. Its meta-object protocol for handing, made of a set of methods defined on exception classes, can be used as a basis to add new and dedicated EH control structures. We can see today a renewest interest for open, reflective and dynamically typed languages used for example to assemble components (cf. [START_REF] Garcia | Architectural-based Reflective Approach to Incorporating Exception Handling into Dependable Software[END_REF]) or to develop WEB applications that require powerful and flexible exception handling systems similar to the one presented here.

We finally have presented the key issues of the implementation of the dual model of exception handling in the context of a reflective, dynamically.typed object-oriented langage.

  procedure process-yeld (a-process) {remove(Active-process-list, a-process); {when itemNotFound(e) do {signal (InactiveProcess)}}} function pgcd (int a, b) {loop {aux := a; a := b ; b := modulo(aux, b)}; {when division-by-zero(e) do {exit(aux)}}}

Fig. 3 .

 3 Fig. 3. Kernel exception classes.

Fig. 4 .

 4 Fig. 4. Basic exception classes, associated attributes and methods.

[

  <protected expression>] when: <exception-name> do: [<handler parameter> | <handler body>]

  <protected class> when : <exception-name> do : '<handler parameter> | <handler body>'

"

  computes the pgcd of a and b" [[true] whiletrue: [aux := a. a := b. b := aux modulo: b]] when: division-by-zero do: [:e | e exitWith: aux]

Fig. 8 .

 8 Fig. 8. An implementation of the simplified algorithm in Fifure 7.

lookForAndInvokeHandler"

  defined on ExceptionalEvent" | currentContext classHandler method unwindContexts dejaVus | unwindContexts := OrderedCollection new.

Fig. 9 .

 9 Fig. 9. The complete version of handler search.

Fig. 10 .

 10 Fig. 10. Handler Invocation.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Implementing TerminationResumption. Resumption (cf. Figure12) is simply implemented by a destructive non local exit towards the #resume mark previously stored in the stack at handler invocation time. The resumeWith:with: primitive checks that the handler has chosen a protocol for resumption effectively proposed by the signaler before entailing the non local exit.

  Resumption raises another important issue: it should not be achieved without the agreement of both the signaler and the handler when, although the handler is responsible for saying what to do, the effective computation restart is performed by the signaler in its environment. In any cases, the signaler should be able to predict which kind of restarts he is ready to achieve. A slot named protocolForResumption, defined on ProceedableEvent provides a basic solution to this problem2 . The signaler can use it to indicate, at signaling time, the options among which a handler can choose in order to achieve resumption. Assigning it to nil means that resumption is impossible. In conjunction, a handler wanting to entail resumption has to indicate which protocols it has chosen. In the figure5example, handlers can for example use the message messageValue: which itself entails resumption by using the correct protocol. Example of definition of a new exception, to represent runtime message sending failure. Its occurrences are either proceedable or fatal; thus it is a subclass of Event. While signaling it, the signaler can pass arguments to handlers to indicate which kind of resumption it is ready to achieve.

	open. f.workOn.]
	unwindProtect: [f.close]]
	Cooperation for Resumption. Signaling the exception with propositions for resumption
	result :=
	DoesNotUnderstand
	signalWith ProtocolsForResumption:
	#(supplyValue newReceiver newSelector)
	messageReceiver: anObject
	messageSelector: aSymbol
	messageArgs: anArray.
	"if control returns here, result is tested and the corresponding actions performed"
	Fig. 5.

Event subclass: #DoesNotUnderstand instanceVariableNames: 'messageReceiver messageSelector messageArgs ' methodsFor: 'handling' messageValue: "resume with a message value ..." newSelector: "resume with a new selector ..." newReceiver: "resume with a new receiver ..." ....................

  if the associated handler H traps the exception E, then invoke H. else let C be the class of the receiver of the current frame method.

	If a handler H for the exception E is defined on C,
	then invoke H.
	else if F has been established by an invocation of unwindProtect:,
	then append the argument to UnwindContexts end-if
	let F be F 's sender (stack previous frame) and goto L.
	end-if
	end-if
	end-if
	Fig. 7. A simplified version of the algorithm to search a handler.
	lookForAndInvokeHandler
	"defined on ExceptionalEvent"
	| currentContext classHandler method |	"local variables"
	currentContext := signalingContext sender.		(1)
	unwindContexts := OrderedCollection new.
	[true] whileTrue:		(2)
	[method := currentContext method.
	"if the bottom of the stack is reached, invoke default handlers"
	(method == BottomStackMethod)		(3)
	ifTrue: [handlerContext := currentContext sender.		(4)
	^self invokeHandler: [:e | e handlesDefault] with: unwindContexts]	(5)
	ifFalse: [
	"looking for an expression handler"
	(method == HandleMethod and:
	[self isKindOf: (currentContext localAt: 1)])		(6)
	ifTrue:
	[handlerContext := currentContext.		(7)
	^self invokeHandler: (currentContext localAt: 2)
	with: unwindContexts]		(8)
	"looking for a class handler in the class of the current context receiver"
	classHandler := currentContext receiver class isProtectedFor: self.	(9)
	classHandler isNil ifFalse: [
	handlerContext := currentContext.		(10)
	classHandler receiver: currentContext receiver.		(11)
	^self invokeHandler: classHandler with: unwindContexts]		(12)
	"no handler here, but check if this context contains an unwind blocks"
	(method == UnwindMethod)		(13)
	ifTrue: [unwindContexts addLast: (currentContext localAt: 1)].	(14)
	"no handler here, going down one frame"
	currentContext := currentContext sender		(15)
	] "end of ifFalse: method == BottomStackMethod"
	] "end of the while loop

When explicitly manipulated, meta-classes are Class subclasses. In our Smalltalk-80 implementation, ExceptionClass is implemented by the automatically created metaclass ExceptionalEvent class. Each exception class has its own (automatically created) meta-class subclass of ExceptionalEvent class.

[START_REF] Pitman | Error/Condition Handling[END_REF] has proposed for this problem a more sophisticated solution: some new dedicated control structures (e.g. restart-case) provide a user-friendly way (with a case-like syntax) of writing code such as the one in the example and allow users to dynamically create new options for proceeding.

This is the price to pay to implement handler definition by a message sending.