Pierre Courrieu
email: pierre.courrieu@univ-provence.fr

Thierry Ripoll

Firat Sabancioglu

Affinely Invariant Features in Visual Perception of Letters and Words

Keywords: Masked priming, Affine transformations, Rotations, Letter and word perception

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Most stimuli we can perceive in our environment do not loose their identity whenever they are translated in the visual field, their size is modified, they are slanted or rotated to a certain extend. One says that the perception of these stimuli is invariant to the considered transformations. However, one must take care that all possible transformations do not have equivalent effects on the perception of any type of stimulus. Visual perception seems quite robustly invariant to translations and size variations, however the effect of transformations such as symmetries or rotations seems more variable, depending on the nature of the stimulus.

For example, one can easily recognise a 180° rotated letter A, while recognising a 180° rotated familiar human face is not so evident. Understanding the nature of perceptual invariants is essential for suitably modelling shape recognition processes. One must not confound the idea of perceptual invariant with that of mental transformation. For example, well-known studies showed that mental rotations are gradual time-consuming operations whose duration depends on the angle of rotation [START_REF] Cooper | Mental rotation of random two-dimensional shapes[END_REF][START_REF] Cooper | Demonstration of a mental analog of an external rotation[END_REF][START_REF] Cooper | The time required to prepare for a rotated stimulus[END_REF]. If visual perception was invariant to rotations, in a general way, no such mental transformations would be necessary. Translation invariance provides a possible simple example. Assume that, before recognising a shape, the perception centres all points' coordinates on the centre of gravity of the shape. This provides translation invariance to the recognition process, while the complexity of the operation (theoretically) does not depend on the magnitude of the translation. A more general and realistic way of obtaining translation and scale invariance can be found in neuron-like models such as the so-called "Neocognitrons" [START_REF] Fukushima | Character recognition with neural networks[END_REF][START_REF] Fukushima | Recognition and segmentation of connected characters with selective attention[END_REF][START_REF] Fukushima | Neocognitron: a neural network model for mechanism of visual pattern recognition[END_REF]. Hence, a possible empirical support for distinguishing perceptual invariance from mental transformation is the time required for reducing the transformation, and its dependence on the magnitude of the transformation. We can reasonably speak of perceptual invariant whenever the transformation processing time is short and does not depend on the magnitude of the transformation (at least in a non negligible range). Another problem results from the fact that quite complex stimuli can be analysed at various scales, resulting in perceptual components (features) of various sizes that do not necessarily exhibit a homogeneous behaviour with respect to transformations. Consider for example printed words' perception. One knows that words are recognised through their component letters [START_REF] Mcclelland | Preliminary letter identification in the perception of words and nonwords[END_REF], however there are some reasons of thinking that more global features also contribute to word recognition, in parallel to component letters' recognition [START_REF] Allen | Holism revisited: evidence for parallel independent word-level and letter-level processing during word recognition[END_REF][START_REF] Allen | Evidence for a parallel input serial analysis model of word processing[END_REF][START_REF] Lété | Word-shape and word-lexical-frequency effects in lexicaldecision and naming tasks[END_REF]). Assume (for example convenience) that letter recognition, as well as word's global feature processing, are invariant to rotations, and a 180° rotated word is presented. Then global features are recognised, as well as individual component letters, however these ones appear in reversed order, that is, as an anagram of the word. Thus, a 180° rotated word can appear hard to recognise even if all its component features are rotationally invariants. On the other hand, if one presents a word where all letters have been individually 180° rotated, while their order is preserved, then the orthographic analysis suitably fit the word, however word's global features are broken down. The literature provides some interesting results concerning such manipulations. In particular, it was observed that globally 180° rotated words are easier to recognise than words whose letters have been individually 180° rotated [START_REF] Navon | Perception of misoriented words and letter strings[END_REF][START_REF] Tzelgov | On the recognition of words with inverted letters[END_REF]). In the above sketched perspective, this would mean that rotationally invariant global features play an important role in word recognition. However, this is not the conclusion of the authors, since the observed effects can also be interpreted in terms of a corrective mental rotation of the stimulus. In fact, the used word naming tasks do not allow for contrasting the corrective mental rotation hypothesis and the rotationally invariant feature hypothesis. Masked priming techniques are known to be much more suitable than simple recognition tasks to study early perceptual processes. In these methods, a prime stimulus is presented for a short duration (less than 100 ms), and then is Courrieu, Ripoll, & Sabancioglu./ Affinely invariant features 5/14 post-masked by a target stimulus on which the subject must perform a given task. The subject is usually not aware that he/she processed a prime, however this processing actually occurs and it can produce detectable effects on the processing of the target. Depending on the relations between the prime and the target, these effects can be either facilitating or inhibitory, they are detectable for prime durations of about 30 ms, and they increase up to prime durations of about 60 ms [START_REF] Ziegler | Visual and phonological codes in letter and word recognition: evidence from incremental priming[END_REF]. Letter priming allowed for detecting scale invariance in the perception of letters, in a range of half-twice the target size [START_REF] Petit | Masked partial priming of letter perception[END_REF]. Anagram priming [START_REF] Courrieu | Des lettres sans position dans la perception des mots[END_REF], and orthographic priming [START_REF] Humphreys | Orthographic processing in visual word identification[END_REF][START_REF] Peressotti | The role of letter identity and letter position in orthographic priming[END_REF] showed translation invariance of letters in words, while various hypothesis concerning letter order encoding have been proposed. Data obtained with other techniques such as unmasked priming and/or similarity judgement provided suspicion that certain letter global features could be invariant through symmetries or 180° rotations [START_REF] Courrieu | Segmental vs. dynamic analysis of letter shape by preschool children[END_REF][START_REF] Courrieu | Inverse discrimination time as a perceptual distance for alphabetic characters[END_REF][START_REF] Kimchi | Influence of past experience on perceptual grouping[END_REF], despite the fact that such invariants are not relevant for letter recognition since they lead to confuse letters such as b, d, p, and q. The main purpose of the following experiments is to test, using a masked priming technique, the hypothesis that letter and word recognition uses features that are invariant to 180° rotations.

Well-known priming effects obtained with prime scale reduction will be used as reference effects in order to compare their magnitude to that of rotated prime effects.

Experiment 1

In this experiment, we used an alphabetical decision task (letter / non-letter) on target stimuli that were letters or non-alphabetical symbols. The target was preceded by a 60 ms duration prime that was nominally similar to or different from the target character. The prime Courrieu, Ripoll, & Sabancioglu./ Affinely invariant features 6/14 characters where smaller than the targets, or they were 180° rotated. If letter perception uses features invariant to 180° rotation, then one can expect that rotated primes provide priming effects of about the same magnitude as scaled down primes, that is, faster response times for nominally similar than for different primes in both cases of transformations. On the other hand, if there are no rotation invariant features, one can expect priming effects for scaled down primes (known effect), but not for rotated primes.

Method

Subjects. Forty university students with normal vision participated in Experiment 1 on a voluntary base.

Apparatus. Subjects were tested individually on a Macintosh computer, the experiment being driven by PsyScope 1.2.5 software.

Materials.

A set of 16 upper-case letters was selected, with the constraint that none of these letters had the same shape when 180° rotated (H, I, O, X), or widely overlapped (N, Q, Z), or had a shape close to that of another letter (M/W, S/Z). The standard font Geneva was used, with size 14 for targets and rotated primes, and size 9 for scaled down primes. The same set of letters was used for primes and targets, which were paired in order to obtain 4 pairs for identical/scaled down priming condition, 4 pairs for different/scaled down priming condition, 4 pairs for identical/180° rotated priming condition, and 4 pairs for different/180° rotated priming condition. The pairing of primes and targets was varied using a Latin Square in such a way that each letter appeared in each priming condition, while a given subject saw a given target only once. A set of 16 non-alphabetical symbols was selected and paired in the same Courrieu, Ripoll, & Sabancioglu./ Affinely invariant features 7/14 way. In addition, 16 pairs of symbol-letter type and 16 pairs of letter-symbol type were used in order to avoid correlations between prime and target types in the experiment. The characters used for these non experimental pairs were different from experimental ones, as were those used for an initial practice session (10 pairs).

Procedure. Subject's eyes were at a distance of about 35 cm of the computer screen. First, an asterisk was displayed as a fixation point for one second. Then the asterisk was replaced by the prime for 60 milliseconds, and finally the target, which remained on the screen until the subject responded, replaced the prime. Subjects were instructed to respond as quickly and accurately as possible, by pressing a YES key at right if the target was a letter of the usual alphabet, or by pressing a NO key at left if the target was not a usual letter. The experiment began with 10 practice trials, followed by 64 trials in random and randomly varied order. Data analysis. Response times (in ms) for letters and symbols were submitted to standard analysis of variance separately, without any data filtering. Each analysis of variance was performed for subject population (F1 ratios), and for (target) item population (F2 ratios). The four priming conditions were described by two factors with two levels each: the prime relation to the target (similar, different), and the prime transformation (scaled down, 180° rotated). The conditions of the Latin Square defined a secondary four levels factor, with ten subjects (subject analysis), or four items (item analysis) in each condition.

Results

Courrieu, Ripoll, & Sabancioglu./ Affinely invariant features 8/14 Mean response times (and percents of errors) are presented in Table 1, together with the mean priming effects, that is the response time for different prime minus the response time for similar prime.

Letter targets. There was a significant main priming effect, that is, response times were significantly shorter with a similar prime than with a different prime (F1(1, 36)=12.529, p<.01; F2(1, 12)=7.538, p<.05). Subjects responded significantly faster when the prime was scaled down than when the prime was 180° rotated (F1(1, 36)=12.415, p<.01; F2(1, 12)=5.769, p<.05), no matter its relation to the target since there was no detectable interaction between the two main factors (F1<1, F2<1). This is the pattern expected if letters are perceived through features invariant to 180° rotation, except the main effect of the type of transformation which was not expected and will be discussed latter. Simple priming effects were also tested. The simple priming effect for scaled down primes was in fact not significant (F1(1, 36)=3.582, p<.07; F2(1, 12)=1.356, p<.27), however we know that this effect actually exists (Petit & Grainger, 2002, exp. 3). The simple priming effect for 180° rotated primes was significant in the subject analysis only (F1(1, 36)=9,873, p<.01; F2(1, 12)=3,736, p<.08). In fact, it seems that the random variance with unfiltered data was too large for allowing simple effects to reach conventional significance thresholds.

Discussion

The pattern of results corresponds to the one expected if letter perception uses some180° rotation invariant features, that is, priming is obtained with 180° rotated primes and is not weaker than priming with scaled down primes. An unexpected main effect of the type of transformation was obtained with letters, while no such an effect was observed with symbols.

Letters with scaled down primes were recognised faster than letters with 180° rotated primes, no matter the relation between the prime and the target. This suggests an interference effect simply depending on the size of the prime, thus probably occurring at a low visual processing level. Why, however, symbol perception is not affected by this visual interference? In fact, a number of symbols are unusual, if not unknown, for most subjects, and the set of possible symbols is a priori not closed, while the usual alphabet is a well-known finite set. Thus subjects probably attempted to recognise only letters, responding NO whenever no letter was recognised after a certain delay. In such a case, the response time to symbols is in fact independent of any prime characteristic, as we have actually observed.

Experiment 2

Experiment 2 is a transposition of Experiment 1 to word recognition level, and the experimental reasoning is the same.

Courrieu, Ripoll, & Sabancioglu./ Affinely invariant features 10/14

Method

The methodology is similar to that of Experiment 1, except that the task was replaced by a lexical decision (word / non-word), and stimuli were five lower-case letter words or regular pseudo-words. The log-frequency of use of words ranged from 2.944 to 10.585, on a scale where the most frequent word in French (preposition "de") has a log-frequency of 14.563.

Results

Mean response times (and percents of errors) are presented in Table 2, together with the mean priming effects.

Word targets. Response times were shorter with a similar prime than with a different prime, the main priming effect being significant in subject analysis (F1(1, 36)=7.928, p<.01), but only marginally significant in item analysis (F2(1, 12)=3.412, p<.09). Subjects responded significantly faster when the prime was scaled down than when the prime was 180° rotated

Discussion

The pattern of results for words is quite similar to that observed for letters in Experiment 1.

Thus a plausible conclusion could be that there are some 180° rotation invariant global features in the perception of words as well as in that of letters. However, results are not so clear. First, it seems that priming effects widely depend one some uncontrolled item characteristics, since these effects were not significant in item analysis. Second, while scaled down prime effects were clearly detectable in this experiment, the effect of 180° rotated primes remains questionable, according to the analysis of simple effects. An important characteristic of words is their frequency of use. Thus we computed the correlation between the log-frequency of the 16 target words and the main priming effect on these words, which resulted in a very low correlation (r=.003). The correlation between target's log-frequency and scaled down priming effect was r= -.02, while this correlation was r= .02 for rotated priming effect. In other words, priming effects do not depend on the frequency of use of target words. By chance, there was no correlation between the log-frequency of use of target words

Courrieu, Ripoll, & Sabancioglu./ Affinely invariant features 12/14 and that of their associated different prime words in the experiment (r= -.067). Then we computed the correlation of the main priming effect with the log-frequency of the different prime word, which provided r= .50, p<.05. The correlation with the log-frequency of the different prime word was r= .38 for scaled down priming, and r= .47 for rotated priming. Thus a possible explanation is that priming effects mainly resulted from inhibitory effects generated by the most frequent different prime words only. As for letters in Experiment 1, rotated primes produced stronger forward masking effects than scaled down primes, no matter their relation to the target. This effect was detectable for non-words as well as for words, despite the fact that non-words must not be recognised (as symbols in Experiment 1). This is probably because orthographic features (letters) of non-words must be recognised before attempting to access the mental lexicon.

Conclusion

Masked priming effects were obtained on letters with scaled down primes (known effect), and 180° rotated primes as well. This implies that letter perception uses some features invariant to 180° rotation. A similar pattern of results was observed with word stimuli, however the effect of scaled down primes was clearly detectable, while the effect of rotated primes was only marginally detectable. Moreover, it was observed that word priming effects critically depended on the frequency of use of the prime. It seems that priming effects generated by transformed primes are obtained only when the different prime is a frequent word. This suggests that only the most frequent words can be activated by a transformed prime in a delay of 60 milliseconds. Thus, if there are global features invariant to 180° rotation in the perception of words, this probably concerns frequent words only. Further investigations are needed for confirmation and clearly understanding the involved mechanisms.

Table 1 .

 1 Mean response times in milliseconds (and percents of errors) in Experiment 1. None of the experimental factors provided detectable effects for this type of stimulus (F1<1 and F2<1 for all variation sources).

		Similar prime	Different prime	Priming effect
	Letters
	Scaled down prime	523 (2.5%)	554 (0.0%)	31 ms
	180° rotated prime	564 (5.0%)	616 (4.4%)	52 ms
	Symbols
	Scaled down prime	618 (3.8%)	632 (3.8%)	14 ms
	180° rotated prime	605 (3.1%)	623 (1.3%)	18 ms

Table 2 .

 2 Mean response times in milliseconds (and percents of errors) in Experiment 2.

	(F1(1, 36)=16.975, p<.001; F2(1, 12)=15.858, p<.01), no matter its relation to the target since
	there was no detectable interaction between the two main factors (F1<1, F2<1). This fit the
	pattern expected if word perception uses certain global features invariant to 180° rotation.
	Simple priming effects were also tested. The simple priming effect for scaled down primes
	was quite clearly detectable (F1(1, 36)=4.493, p<.05; F2(1, 12)=4.744, p<.06), however the
	simple priming effect for 180° rotated primes was not clear (F1(1, 36)=2.452, p<.13; F2(1,
	12)=2.589, p<.14).


Natalia Tsirova
email: natalia.tsirova@clermont.in2p3.fr

Vladimir Karmanov
email: karmanov@lpcs.in2p3.fr

Jean-François Mathiot
email: mathiot@clermont.in2p3.fr

Baryon structure in chiral effective field theory on the light front

We propose a new approach to treat the nucleon structure in terms of an effective chiral Lagrangian. We formulate the state vector, φ (p), of the nucleon in light-front dynamics, and solve the eigenvalue equation P2 φ (p) = M 2 φ (p) in a truncated Fock space. The effective Lagrangian is decomposed in terms of pion fields in order to match the Fock expansion of the state vector. We use a general renormalization scheme consistent with Fock state truncation. We present our first results in a two-body Fock space truncation.

Introduction

For the last 40 years pion-nucleon systems and their theoretical investigation within the general framework of chiral perturbation theory have been of great interest. Since the nucleon mass is not zero in the chiral limit, all momentum scales are involved in the calculation of baryon properties (like masses or electro-weak observables) beyond tree level. This is at variance with the meson sector for which a meaningful power expansion of any physical amplitude can be done. While there is not much freedom, thanks to chiral symmetry, for the construction of the effective Lagrangian in Chiral Perturbation Theory (CPT), L CPT , in terms of the pion field -or more precisely in terms of the U field defined by U = e iτ.π/ f π where f π is the pion decay constant -one should settle an appropriate approximation scheme in order to calculate baryon properties. Up to now, two main strategies have been adopted. The first one is to force the bare (and hence the physical) nucleon mass to be infinite, in Heavy Baryon Chiral Perturbation Theory [1]. In this case, by construction, an expansion in characteristic momenta can be developed. The second one is to use a specific regularization scheme [2] in order to separate contributions which exhibit a meaningful power expansion, and hide the other parts in appropriate counterterms. In both cases however, the explicit calculation of baryon properties relies on an extra approximation in the sense that physical amplitudes are further calculated by expanding L CPT in a finite number of pion fields.

Following [START_REF] Mathiot | Chiral effective field theory on the light front[END_REF], we propose to calculate nucleon properties using the general eigenvalue equation for the state vector projected on the light front. This non-perturbative equation is then solved in a truncated Fock space. This enables to consider irreducible contributions arising from ππNN contact interactions in a systematic way, as shown in Fig. (1). It was calculated in perturbation theory in [4]. This decomposition of the state vector in a finite number of Fock components implies to consider an effective Lagrangian which enables all possible elementary couplings between the pion and the nucleon fields to the same order. This is indeed easy to achieve in chiral perturbation theory since each derivative of the U field involves one derivative of the pion field. In the chiral limit, the chiral effective Lagrangian of order p involves p derivatives and at least p pion fields. In order to calculate the state vector in the N-body truncation, with one fermion and (N -1) pions, one has to include contributions up to 2(N -1) pion fields in the effective Lagrangian, as shown in Fig. (2). We thus should calculate the state vector in the N-body truncation with an effective Lagrangian, denoted by L N e f f , and given by

L N e f f = L p=2(N-1) CPT . (1.1)

Description of bound states in light-front dynamics

One of the main advantages of Light-Front Dynamics (LFD) is that the vacuum state of a

where P is the full momentum operator and M is the physical bound state mass. In the standard version of LFD the state vector is defined on the plane t + z c = 0. This plane is not invariant under spatial rotations. This may lead to many unpleasant consequences for any approximate calculation. We use in our work the so-called explicitly Covariant formulation of LFD (CLFD) [5]. Within this formalism, the state vector is defined on the plane characterized by the equation ω • x = 0, where ω is an arbitrary light-like 4-vector. The standard LFD plane corresponds to the particular choice ω = (1, 0, 0, -1). Of course, physical observables should coincide in both approaches in any exact calculation. However, in approximate calculations, the use of CLFD is of particular interest. In that case, this framework allows to separate physical observables from ωdependent unphysical ones in a very transparent way, while exact calculations should not depend on the arbitrary position of the light front.

In order to make definite predictions for physical observables we should define a renormalization scheme. It should be done with care since any truncation of the Fock space may induce uncancelled divergences. Let us look for instance to the calculation of the physical fermion propagator in second order perturbation theory as represented in Fig. (4). The propagator has three contributions: free propagator, the self-energy contribution and the mass counterterm. The last contribution corresponds to the one-body Fock sector (single fermion). It should however be opposite to the two-body Fock sector contribution (one fermion plus one boson) at p 2 = M 2 , in order to recover the free physical propagator. It is thus clear that if the Fock state is truncated, such cancellation, to all orders, may be broken. A general renormalization scheme to deal with Fock state truncation in Light-Front dynamics has been developed in [6].

Eigenvalue equation

In order to show how one should proceed, we start from the following typical pion-nucleon interaction Lagrangian

L int = - 1 2 g A F 0 Ψ γ µ γ 5 τ b ∂ µ φ b Ψ - 1 4F 2 0 Ψ γ µ τ • φ × ∂ µ φ Ψ. (3.1)
The first term is the standard pseudo-vector pion-nucleon coupling, and the second one is the leading contact ππNN interaction. Other contributions involving two pion fields arise from the second order πN chiral perturbation theory Lagrangian [7]. They can be included in a very similar way to the ππNN contact interaction. Solving the eigenvalue equation (2.1) [6], we can represent the system of coupled equations for the vertex functions in the two-body truncated Fock space by the diagrams of Fig. (5). It can be written as

ū(p 1 )Γ 1 u(p) = ū(p 1 )(V 1 +V 2 )u(p), (3.2) ū(k 1 )Γ 2 u(p) = ū(k 1 )(V 3 +V 4 )u(p). (3.3)
Here p is the momentum of the physical fermion, p 1 and k 1 are the momenta of the constituent fermion in the one-body and two-body Fock space truncation respectively. The graph denoted by V 4 corresponds to the second term in the interaction Lagrangian (3.1). The vertex functions Γ 1 and Γ 2 should be decomposed in independent spin structures. Using the explicit covariance of our approach, we can write

ū(k 1 )Γ 1 u(p) = (m 2 -M 2 )a 1 ū(k 1 )u(p) (3.4) ū(k 1 )Γ 2 u(p) = i ū(k 1 ) ( k 2 -ωτ) b 1 (R ⊥ , x) + m ω ω • p b 2 (R ⊥ , x) γ 5 u(p) , (3.5)
where is the off-shell energy, with s = (k 1 + k 2 ) 2 . The usual longitudinal momentum fraction, with respect to the position ω of the light front, is given by

τ = s -M 2 2 ω • p (3.6)
x = ω•k 2 ω•p . (3.7)
The transverse momentum R ⊥ with respect to ω is defined from

R 2 = k 2 -xp with R 2 = (R 0 2 , R ⊥ , R 0 2 ) , (3.8)
since by construction ω•R 2 = 0. The last component in (3.8) corresponds to the longitudinal momentum R 2 with respect to ω. The mass of the physical bound state is denoted by M, while m is the mass of the constituent fermion. In the final result, one should take the limit m → M. Generally speaking, b 1 (R ⊥ , x) and b 2 (R ⊥ , x) are scalar functions depending on the dynamical variables (momenta). In the two-body truncation, with the Lagrangian (3.1), they are just constants. The spin decomposition of the two-body component in terms of independent spin structures is of course not unique. We choose here the most convenient one. On the energy shell, i.e. for s = M 2 , the two-body vertex function Γ 2 should be independent of the arbitrary position of the light front, so that, since b 2 is a constant, one should have the condition b 2 = 0.

(3.9)

Due to the Fock state truncation, this may be however not the case in practice. In order to inforce this condition, one may consider an ω-dependent vertex counterterm in the effective Lagrangian, of the form 5) are a-priori divergent, and one should use an appropriate regularization scheme in order to give them a mathematical sens. In our preliminary study, we shall use the Pauli-Villars (PV) regularization scheme as applied to CLFD [6]. We thus should extend all physical components to incorporate PV particles. For simplicity, we have left over all indices relative to physical and PV particles in the vertex functions in the eigenvalue equations (3.2,3.3) and in Fig. (5).

δ L int = i Z 3 Ψ ω γ 5 τ b φ b Ψ. ( 3
The general strategy to solve the coupled eigenvalue equations shown in Fig. ( 5) is detailed in [6]. Its solution for the simplest case, namely, without the ππNN contact interaction, i.e. without the graph V 4 from the system presented in Fig. ( 5) can be found analytically as a function of PV masses. The necessary condition (3.9) is satisfied automatically. We are analyzing the ωindependent component. It should correspond exactly to the perturbative calculation.

We also have found a solution in the more general case given by the Lagrangian (3.1), i.e. with ππNN contact interaction. The solution is also analytic but much more complicated and in that case the physical component b 2 (s = M 2 ) is a constant different from 0. It should be killed by an appropriate counterterm (3.10).

Perspectives

We have outlined in this preliminary study the main steps in the calculation of nucleon properties within light front chiral effective field theory. Our formalism is based on the Fock expansion of the nucleon state vector, projected on the light front. Using the properties of the explicitly covariant formulation of light-front dynamics, and an adequate renormalization scheme when the Fock expansion is truncated, we have calculated explicitly the spin components of the state vector in the two-body truncation.

We are now analyzing our results in terms of an expansion of the nucleon mass as a function of the pion mass, and calculate the scalar form factor.

Figure 1 :

 1 Figure 1: Two-body irreducible contribution to the nucleon state vector.

(N - 1

 1 ) bosons (N -1) bosons

Figure 2 :

 2 Figure 2: General vertex including a maximum of (N -1) pion fields in the initial and final states.

Figure 3 :

 3 Figure 3: Vertex function of order n for the N-body Fock space truncation.

Figure 4 :

 4 Figure 4: Renormalization of the fermion propagator in second order of perturbation theory

Figure 5 :

 5 Figure 5: System of equations for the pion-nucleon vertex functions in the two-body Fock space truncation.

  .10) This amounts to extend the pion-nucleon vertex in Fig. (5) by a new contribution proportional to Z 3 ω. The loop contributions of Fig. (


Pierre Hyvernat
email: pierre.hyvernat@univ-savoie.fr

A Completeness Theorem for "Total Boolean Functions" July 2008

, Christine Tasson introduces an algebraic notion of totality for a denotational model of linear logic. The notion of total boolean function is, in a way, quite intuitive. This note provides a positive answer to the question of completeness of the "boolean centroidal calculus" w.r.t. total boolean functions.

0. Introduction. Even though the question answered in this note has its roots in denotational semantics for the differential λ-calculus ( [START_REF] Ehrhard | The Differential λ-calculus[END_REF] and [START_REF] Ehrhard | Finiteness Spaces[END_REF], see also [START_REF] Vaux | On Linear Combinations of λ-Terms[END_REF]), no background in proof-theory is necessary to understand the problem. In the end, it boils down to a question about a special kind of polynomials in 2n variables over an arbitrary field k. This note is almost "self-contained", assuming only mild knowledge about polynomials and vector spaces (and a modicum about affine spaces).

The only exotic (??) technology is the following formula for counting monomials or multisets. The number of different monomials of degree d over n variables is usually denoted n d . A simple counting argument shows that the number of monomials of degree at most d in n variables is n+1 d . A closed formula for n d in terms of the usual binomial coefficient is given by:

n d = n + d -1 n .
Thus, the number of monomials of degree at most d in n variables is given by n+d n .

1. Total boolean polynomials. The category of finite dimensional vector spaces give a denotational model for multiplicative additive linear logic. Adding the exponential is a nontrivial task and requires infinite dimensional spaces and thus, topology. Moreover, we need to find a subclass of spaces satisfying E ≃ E * * . Finiteness spaces (see [START_REF] Ehrhard | Finiteness Spaces[END_REF]) give a solution. We won't need the details of this technology, but it is interesting to note that objects are topological vector spaces, and that morphisms (in the co-Kleisli category of the !-comonad) are "analytic functions", i.e. power series.

Of particular interest is the space B used to interpret the booleans: this is the vector space k 2 , where k is the ambient field. A morphism from B n to B is a pair (P 1 , P 2 ) of "finite" power series (polynomials) in 2n variables, where each pair (X 2i-1 , X 2i ) of variables corresponds to the i-th argument of the function.

A boolean value (a, b) is total if a + b = 1; and a pair of polynomials is total if it sends total values to total values. This means that a pair (P 1 , P 2 ) of polynomials in 2n variables is total iff

a 1 + a 2 = 1, . . . , a 2n-1 + a 2n = 1 ⇒ P 1 (a 1 , . . . , a 2n ) + P 2 (a 1 , . . . , a 2n ) = 1 .
We first restrict our attention to the case of an infinite field k: the above condition is then equivalent to the stronger condition (a pair of polynomials satisfying this condition is called strongly total)

( * ) P 1 X 1 , 1 -X 1 , . . . , X 2n-1 , 1 -X 2n-1 + P 2 X 1 , 1 -X 1 , . . . , X 2n-1 , 1 -X 2n-1 = 1 .
The proof of this is easy but interesting: refer to any algebra textbook ("Algebra" by Lang, corollary 1.7 in chapter IV for example) if you are in a hurry... The constructions presented below also work for finite fields, but give a weaker result: see the remark at the end of section 5.

Lemma.

• Strongly total polynomials form an affine subspace of k

[X 1 , . . . , X 2n ] × k[X 1 , . . . , X 2n ]; • total polynomials form an affine subspace of k[X 1 , . . . , X 2n ] × k[X 1 , . . . , X 2n ].
2. The centroidal calculus for boolean functions. The centroidal calculus produces pairs of polynomials (P 1 , P 2 ) using

• constants: T := (1, 0) and F := (0, 1);

• pairs of variables: (X 1 , X 2 );

• if (P 1 , P 2 ) then (Q 1 , Q 2 ) else (R 1 , R 2 ) := (P 1 Q 1 + P 2 R 1 , P 1 Q 2 + P 2 R 2 ); • affine combinations: n i=1 α i (P i,1 , P i,2 )
where

n i=1 α i = 1.
A pair of polynomials is centroidal if it is generated by the above operations.

Lemma. Centroidal polynomials form an affine subspace of

k[X 1 , . . . , X 2n ] × k[X 1 , . . . , X 2n ].
A note on terminology: "affine calculus" would be a much better name than "centroidal calculus"; but in the context of linear logic, this would lead to endless confusion.

The following proposition answers the natural question that was raised by Christine Tasson and Thomas Ehrhard:

Proposition. Suppose the field k is infinite; then the spaces of centroidal polynomials and of total polynomials coincide.

That centroidal polynomials are total is a direct consequence of their definition: all centroidal polynomials are in fact strongly total, in the sense of ( * ). The rest of this note is devoted to the converse.

Tips and tricks for centroidal polynomials.

Here is a collection of recipes for constructing centroidal polynomials:

• (α, 1 -α) := α T + (1 -α) F;
• ¬(P 1 , P 2 ) = (P 2 , P 1 ) := if (P 1 , P 2 ) then F else T;

• (P 1 , P 2 ) * (Q 1 , Q 2 ) = (P 1 Q 1 , P 1 Q 2 + P 2 ) := if (P 1 , P 2 ) then (Q 1 , Q 2 ) else F;* • (P 1 , P 2 ) + = (P 1 + P 2 , 0) := if (P 1 , P 2 ) then T else T; • π 1 (P 1 , P 2 ) = (P 1 , 1 -P 1 ) := F + (P 1 , P 2 ) + -¬(P 1 , P 2 ).
Using those, we can get more complex centroidal polynomials:

(a) suppose P 1 is any polynomial; we can always get a centroidal term (P 1 , P 2 ) for some polynomial P 2 :

-using " * ", we can get any monomial (M, . . .), -if M is such a monomial, α its coefficient in P 1 and m the total number of monomials in P 1 , (mαM, . . .) = if (mα, 1 -mα) then (M, . . .) else F, -we can then sum those monomials using coefficients 1/m to get (P 1 , . . .).

(b) If (P 1 , 0) is centroidal and if Q 1 is any polynomial, then (P 1 -1)Q 1 , 1 is centroidal: -thanks to the previous point, we can obtain (Q 1 , Q 2 ) for some Q 2 , -(P 1 -1)Q 1 , 1 = (Q 1 , Q 2 ) * (P 1 , 0) + F -(Q 1 , Q 2 ).
* This operation is neither commutative nor associative!

(c) If (P 1 , P 2 ) is centroidal and if Q 1 is any polynomial, then (P 1 + Q 1 , P 2 -Q 1 ) is also centroidal: (P 1 + Q 1 , P 2 -Q 1 ) = (P 1 , P 2 ) + (Q 1 + Q 2 , 0) -(Q 2 , Q 1 )
The last point implies in particular that it is equivalent to show that (P 1 , P 2 ) is centroidal and to show that (P 1 + P 2 , 0) is centroidal.

4. An interesting vector space. Write k[X 1 , . . . , X n ] d for the vector space of polynomials of degree at most d. The operator ϕ

: k[X 1 , . . . , X 2n ] d → k[X 1 , . . . , X n ] d with ϕ : P (X 1 , . . . , X 2n ) → P (X 1 , 1 -X 1 , . . . , X n , 1 -X n ) is linear and surjective. Since the dimension of k[X 1 , . . . , X n ] d is n+d n , we get dim ker(ϕ) = 2n + d 2n - n + d n .
It is easy to see that the following polynomials are all in the kernel of ϕ:

(X 1 + X 2 ) i1 × . . . × (X 2n-1 + X 2n ) in -1 × X j1 1 × . . . × X jn 2n-1
where ( k i k ) + ( k j k ) ≤ d and at least one of the i k is non zero.

Lemma. The above polynomials are linearly independent.

Proof: suppose α k P k = 0 where each P k is one of the above vectors. We show that the coefficient of any (X 1 + X 2 ) i1 . . . (X 2n-1 + X 2n ) in -1 X j1 1 . . . X jn 2n-1 is zero by induction on k j k .

• If k j k = 0: since the linear combination is zero, this implies that the global coefficient of each monomial is zero. Since (X 1 + X 2 ) i1 . . . (X 2n-1 + X 2n ) in -1 is the only polynomial contributing to the monomial X i1 2 . . . X in 2n , its coefficient must be zero.

• The polynomial (X 1 + X 2 ) i1 . . . (X 2n-1 + X 2n ) in -1 X j1 1 . . . X jn 2n-1 is the only polynomial contributing to X i1 2 . . . X in 2n X j1 1 . . . X jn 2n-1 because, by induction hypothesis, all the polynomials with fewer X 2k-1 's have zero for coefficient. This implies that the above coefficient is also zero...

Corollary. The above polynomials form a basis for ker(ϕ).

Proof: the number of those polynomials is exactly 2n+d 2n -n+d n : • the first term accounts for the polynomials with

( k i k ) + ( k j k ) ≤ d,
• the second term removes the polynomials where all the i k 's are zero. We have a family of 2n+d 2n -n+d n linearly independent polynomials in a space of the same dimension: they necessarily form a basis. 5. Back to total polynomials. Abusing our terminology, we say that a single polynomial P is total [resp. centroidal] if the pair (P, 0) is total [resp. centroidal].

We saw in section 3 that it is sufficient to show that all the total P are centroidal. Since the space of total polynomials is just the affine space 1 + ker(ϕ), the following polynomials form a basis for the space of total polynomials: 1 + (X 1 + X 2 ) i1 × . . . × (X 2n-1 + X 2n ) in -1 × X j1 1 × . . . × X jn 2n-1

This work has been partially funded by the French project CHOCO (ANR-07-BLAN-0324).

We thus only need to show that each element in this basis is indeed centroidal. Each (X 1 + X 2 , 0) is centroidal, so that each (X 1 + X 2 ) i1 . . . (X 2n-1 + X 2n ) in is also centroidal (using the " * " operation); we can find a centroidal X j1 1 . . . X jn 2n-1 , Q and apply point (b) of section 3 to obtain

The " + " operation allows to conclude the proof of the proposition.

Everything we've done so far also apply to finite fields, but the result we obtain is Proposition. Suppose the field k is finite; then the space of centroidal polynomials is exactly the space of "strongly total" polynomials (see ( * ) in section 1). This space is a strict subspace of the space of total polynomials.

Proof: we only need to show that centroidal polynomials are a strict subspace of total polynomials. Take the polynomial 1 + X(X + 1)(X + 2) . . . (X + l) where l + 1 is the cardinality of the field. This polynomial is total but not strongly total: it thus can't be encoded in the centroidal calculus.

6. Some examples: the "parallel" or and Gustave's function. In order to write smaller formulas, we occasionally use a single letter P to denote a pair (P 1 , P 2 ) of polynomials.

Using the usual encoding with the "if" primitive, the usual "or" function is easily programmed in the centroidal calculus:

However, this function is not commutative: in general, (P 1 , P 2 ) ∨ (Q 1 , Q 2 ) is not the same as (Q 1 , Q 2 ) ∨ (P 1 , P 2 ), except for total values. To get a commutative version, one needs to use sums:

This "or" is indeed commutative, and F is neutral; but we do not have (P 1 , P 2 ) ∨ T = T.

The simplest really well-behaved "or" function seems to be the following:

This "or" function is truly commutative, has F as a neutral element and T as an absorbent element. It is probably the closest one can get to the "parallel-or".

Exercise: with the above "or", we have 1/2 , 1/2 ∨ 1/2 , 1/2 = 3/4 , 1/4 . Design two other "or" functions which are truly commutative, have (1, 0) for absorbent element and (0, 1) for neutral element and are such that:

- -Gerard Berry's "Gustave function" is a ternary boolean function. It is the first and simplest example of stable but non-sequential function; and it can be shown to have polynomial

in Lefschetz totality spaces. It is trivial matter to check that this function is total. Here is one way to obtain it in the centroidal calculus:

• P := (X * Y ) * Z;

= X1Y1Z1 , X2+X1Y2+X1Y1Z2

• Q := (¬X * ¬Z) * ¬Y ;

= X2Y2Z2 , X1+X2Z1+X2Y1Z2

• R := π 1 (Y * ¬Z);

= Y1Z2 , 1-Y1Z2

• S := π 1 (X) + ¬X -T;

= X1+X2-1 , 1

• U := if R then S else T;

= Z2Y1(X1+X2-1) , 1

Expressing the corresponding polynomial in the basis given in section 5 seems to yield an even bigger centroidal expression:

where each basic polynomial can be expressed in the centroidal calculus using the recipes from section 3.


Queinnec Christian
email: christian.queinnec@upmc.fr

AN INFRASTRUCTURE FOR MECHANISED GRADING

Keywords:

Mechanised grading is now mature. In this paper, we propose elements for the next step: building a commodity infrastructure for grading. We propose -an architecture for a grading component able to be embedded into various learning environments, -a set of extensible Internet-based protocols to interact with this component, and -a self-contained file format to thoroughly define an exercise in order to ease deployment. The infrastructure was designed to be scalable, robust and secure. First experiments with a partial implementation of this platform show the versatility and the neutrality of the grading component. It does not impose any IDE and it respects the tenets of the embedding learning environment or course-based system.

History

Around 2000, with the help of some colleagues from UPMC, we set up two experimentations involving mechanised grading. In the first experiment (reported in [START_REF] Brygoo | Experiment around a training engine[END_REF]), we adjoined to the DrScheme programming environment (an Integrated Development Environment (or IDE) devoted to the Scheme programming language [START_REF] Findler | Drscheme: A programming environment for scheme[END_REF]) a mechanised grading facility: the student chooses an exercise, reads the stem, types then debugs his program and finally hits the "Check" button to obtain a mark and a page explaining the tests that were performed and led to that mark. This mechanised grader is a stand-alone plug-in to DrScheme; every year since 2001, around 700 students have had used it on their home computer (night and day) or during lab sessions.

In the second experiment (reported in [START_REF] Queinnec | Une expérience de notation en masse[END_REF])), we organised general programming examinations or contests where we had several hundreds of undergraduate students to grade in a short time. Centralised mechanised grading was our sole option. Therefore we wrote unit tests to check students' programs considered as black boxes.

Soon afterthat, we designed a framework and implemented some libraries to ease the production of mechanised graders that is, specialised programs that grade students' files for a given exercise. From 2001, we have been grading several hundred examinations per year.

Around 2005, our various experiences with different programming languages such as Scheme, C, Ada, PHP, Perl, Java, make or shell convince us that mechanised grading was mature enough for courses that mainly rely on some programming language(s) both for exercises and/or examinations. We proposed to unify our previous experiments into a generalised framework and a multi-language grading architecture to ease the production of graders and to lessen the associated chores. Our goal was to build 1. an autonomous and scalable grader that may be embedded within various systems, 2. REST-based [START_REF] Fielding | Principled design of the modern web architecture[END_REF] protocols to interact with this grader, 3. a file format for self-contained deployable exercises.

While building this grader, we added new goals in order to provide a grading infrastructure that is, grad-ing as a software service (SaaS).

We will present, in the first section, the advantages of mechanised grading and some of our goals. The second section will describe an overview of the architecture, nicknamed FW4EX (for" framework for exercises"), and its prominent features. In the third section, we will summarise the results of our lattest experiments using the FW4EX architecture. Related works is addressed in the fourth section.

Mechanised grading

Writing a program is a complex activity requiring 1. to understand a specification, 2. to imagine a solution, 3. to write it down in some programming language and within some environment development (IDE), 4. finally to test it to make sure it complies with the specification.

Any problem that arises during this life-cycle forces the student to re-iterate parts of this cycle. A way to assess this skill is to let students program with professional tools and to check programmatically whether their programs comply with the specification. Professionally, this is called "unit testing" and popular frameworks such as JUnit1 were developed for that activity. To use professional tools and to obey professional rules was something we wanted our students to be exposed to.

There are some differences though with usual unit testing.

• Unit testing is designed to give a binary answer:

1 (pass) or 0 (fail). In a grading context, we want to give a more representative and accurate mark for the student's work say a mark between 0 and 20 (as usual in French universities). This may be done by multiplying the tests and combining their partial results.

• Unit testing frameworks often depend on one programming language. However some specifications leave the choice of the programming language to use up to the student. Therefore, a grading framework has to cope with multiple languages.

To design mechanised graders is a hot topic as illustrated by the numerous papers presented these last years like Quiver [START_REF] Ellsworth | The quiver system[END_REF], Robo-Prof [START_REF] Daly | Assessing the assessment of programming ability[END_REF], TorqueMOODa [START_REF] Hill | The grader in programmingland[END_REF], gradem [START_REF] Noonan | The back end of a grading system[END_REF], APOGEE [START_REF] Fu | Apogee: automated project grading and instant feedback system for web based computing[END_REF]. An overview of this topic may be found in (Douce et al., 2005a). Among well known systems containing graders are CourseMaker [START_REF] Higgins | Automated assessment and experiences of teaching programming[END_REF], BOSS [START_REF] Joy | The boss online submission and assessment system[END_REF] and now ASAP [START_REF] Douce | A technical perspective on asapautomated system for assessment of programming[END_REF].

Mechanised graders offer multiple advantages:

• consistency: students are graded uniformly (and anonymously) without the biases due to (multiple) human grader(s).

• fairness: if one student finds a problem in the specification or the associated tests then all students benefit from the upgraded grader.

• persistence: once created, assessments are forever available for students who may practise them whenever they want, in the same conditions the assessment was initially offered. We dubbed this "dynamic annals" [START_REF] Queinnec | Une expérience de notation en masse[END_REF].

Many colleagues have a negative feeling against mechanised grading. Unit tests consider programs as opaque black boxes; quite often (but see [START_REF] Higgins | Automated assessment and experiences of teaching programming[END_REF], [START_REF] Joy | The boss online submission and assessment system[END_REF]) they do not consider or appreciate style, performance, good algorithmic usage, etc. We think that some aspects of this critic are due to youth problems:

• Style checkers (CheckStyle2 , PMD3 , FindBugs 4for Java, Perl::Critic5 for Perl, etc.) exist and are more and more professionally used. To incorporate them in unit tests will lessen this critic. Performance may also be checked given appropriate environment setup and non-toy problem size. However these improvements will dramatically increase grading duration.

• Since we collect all the answers to our assessments, we expect to be able to build a taxonomy of common errors and to mechanically recognise instances of these errors in order to provide appropriate answers.

• Unit testing may produce very detailed reports of all tests whether they passed or failed. To analyse these traces is a useful skill to be acquired by students (as elsewhere observed, good debuggers are likely to be good programmers while the inverse is less than true) if some familiarity with these tools is organised ahead of assessments.

Therefore a grading component must be able to grade exercises in various programming languages, various settings: complete programs (stand-alone, client or/and server), program fragments (function, method, class). A grading component must be able to be put to work as part of a learning environment or other systems: it must not dictate whether exercises are summative or formative, it must be as independent as possible from scholar databases.

Of course, it must also be simple to use, robust in face of crashes, secure (respect privacy and anonymity, resistant to pirates and malicious student's works). Finally, our dreamt grading component also ought to be scalable in order take benefit of new technologies such as cloud computing (Amazon EC2 for instance) or Internet-based storage (Amazon S3 for instance) if demand for grading should increase.

The FW4EX project

The FW4EX project aims to build such a grading component under three additional constraints listed in this Section. These are:

• Exercises must be easily deployed. Copying the artefact defining an exercise into an appropriate directory should be sufficient. This requires a precise format for artefacts defining exercises and their whole life-cycle.

• IDEs should be FW4EX-clients. Students should program with appropriate tools. Using an IDE is the current way of programming therefore IDEs must be able to propose exercises, gather student's files, submit them for grading and display grading reports. Fortunately, IDEs (Eclipse, NetBeans, Scintilla, Emacs, etc.) often offer a plugin architecture that makes easy to add a button or a menu item for that task. In order to simplify these plugins, interactions with the FW4EX-related servers only use the HTTP protocol and more precisely RESTbased style [START_REF] Fielding | Principled design of the modern web architecture[END_REF].

• Segregate functionalities into separate components. FW4EX-related functionalities are componentised so they may be organised into appropriate workflows (including human reviewers for instance). Moreover these components should cope with firewalls, university-imposed authentication method, provide skinning and be scalable. Given that these components are accessed via HTTP, they are called servers and altogether form the building blocks for a grading infrastructure. These servers gather related functionalities such as serving exercises (e server(s)), acquiring student's files (a server(s)) or, serving grading re-ports (s server(s)). A single physical machine or a cloud of virtual machines may implement all or part of these logical servers depending on the topological constraints, the expected load or throughput, the intended availability and the configuration of the workflow.

We think that these three goals provide a strong basis for a universal and versatile grading infrastructure. This infrastructure takes care of storing/retrieving exercises, accepting/grading submissions, storing submissions and their associated grading reports thus relieving teachers from all these chores. FW4EX aims to be a grading infrastructure in the line of SaaS (Software as a Service).

This infrastructure provides many opportunities for the creation of appropriate eco-systems as:

• Authoring tools to build artefacts defining exercises.

• Teaching tools to design sets (scenarii) of exercises, analyze answers, compute statistics, etc.

• Deploying tools to instantiate networks of servers to operate within a university (with a single physical server, serving without any authentication, all aspects of FW4EX) or within a cloud for a worldwide company where scalability, latency and accountability are of paramount importance.

To achieve these goals, we offer an artefact format for exercises (see Section 3.1), a series of HTTP protocols (Section 3.4) and some returns of experience (Section 4).

The FW4EX architecture

The FW4EX framework takes benefit of our previous experiments and tries to address a variety of use cases. In this Section, we present the main lines of the architecture, the protocols and the format of exercises.

Figure 1 shows a simplified sketch of the logical architecture of the FW4EX platform. This architecture supposes the presence of Internet and heavily relies on REST-based services [START_REF] Fielding | Principled design of the modern web architecture[END_REF].

From the student's point of view, after choosing (or be assigned) an exercise, his browser (or any FW4EX-compliant client, see Section 3.4) fetches a zipped file (from an exercises server e) containing the stem and all the necessary files or documents required to practise the exercise. When ready, the student submits his work (to an acquisition server a) where it will be picked by a grading server gd that will instantiate an appropriate grading slave (m 1 or m 2 ) to grade the student's files. Once graded, a final report (an XML file) is made available to the student (on some storage server s) as well as its initial submitted work.

Exercises servers e only serve exercises i.e., static files. Exercises servers may be implemented with Amazon S3 technologies. In our experience, these servers are often proxyed via a portal (see Figure 1) allowing students to choose exercises among the set prescribed by their teachers. The portal also skins the exercises with the university's web conventions (colors, logos, authentication, etc.).

Acquisition servers a are stand-alone servers that must be as robust as possible since they must be always available (day and night) to accept students' works. To increase their robustness, they do not depend on the presence of the central databases. They may be deployed within firewalled networks, and maybe polled with encrypted tunnels towards the grading machinery thus ensuring robust security.

Storage servers s only serve reports i.e., static anonymous XML files. These servers do not need to access the central databases therefore they are robust: students may then get feedback whenever they want (day and night). To preserve anonymity, reports may only be fetched via non guessable md5-based urls. Storage servers may be implemented with Amazon S3 technology. In our experience, reports from storage servers are often accessed via portals that skin the reports with the university's web conventions.

Teachers prescribe sets of exercises to students and may access their resulting reports. Teachers may also collect students' works (jobs) by any convenient mean and submit batches of jobs for grading. Teachers have (authenticated) access to grades and names through the t server.

The author of an exercise also has access to the anonymous reports produced by his exercise in order to improve it.

Information confinement is strict: grading slaves grade anonymous files, storage servers store anony-mous files. Among all servers, only grading servers gd and t (see below) are aware of students' identities.

Servers are customised for one task only. This offers numerous advantages -redundancy to cope with fault tolerancy, -concurrency to increase throughput, -versatility where a new version of a component may be plugged into the architecture and compared (in speed, resource consumption, accuracy) with its previous version without disrupting the entire infrastructure.

For security reasons, the grading machinery is (quite often) not publicly nor directly reachable. The grading slaves are virtual machines run with QEMU, VMware, VirtualBox, etc. as explained in Section 3.2.

Exercise format

An exercise is a tar gzipped file (not dissimilar to a Java jar file or an OpenDocument file) containing an XML descriptor and all the files required to operate the exercise. This central descriptor rules the various aspects of the entire life-cycle of the exercise, successively: autocheck, publish, download, install, grade. These phases are shortly explained hereafter in increasing complexity order.

download The descriptor specifies the stem and the files required by the student in order to practise the exercise. The descriptor also describes for each question, the files or directories expected from the student and may contain additional hints such as a template to fill for an answer or the size of the expected work. In the case of an exercise with a single question expecting a single file, an FW4EXcompliant client (see Section 3.4) may use these hints to display an appropriate widget to capture interactively an answer on one or multiple lines.

grade The descriptor defines which scripts (written in whatever scripting language) are used to grade student's files and how these scripts may be combined. It also specifies which kind of grading slave is required that is, which OS (Debian, Windows, etc), which CPU, etc. The descriptor also mentions CPU duration limits, output limits, etc.

install The descriptor defines how an exercise is installed on a grading slave (usually a virtual machine) or on a student's computer. This installation may require to uncompress data files, to precompile libraries, etc. The installation on a grading slave is different from the installation on the student's computer since grading scripts are not disclosed to the student nor they are communicated to the student's computer.

autocheck The descriptor defines a number of "pseudo jobs" paired with the expected grade they should get. This allows -to check whether the grading slave contains all the software required to grade a specific exercise, -to ensure non regression when an author evolves an exercise. Most often it is advised to have at least three pseudo jobs: the null one that contains nothing and expects to obtain a 0/20 grade. The perfect one that should be graded 20/20 and an intermediate one that checks that in-between grades are indeed possible! publish When installed and autochecked, an exercise is ready to grade real students works. It is then publicly available.

The descriptor also defines some meta-data to characterise the exercise: name, requirements, summary, tags, etc. These are needed by e servers to inform students and teachers about the exercises that are ready to be selected.

The XML descriptor is the file that ties all the information required to operate the exercise through all the steps of its life-cycle. The exercise file is autonomous and, similarly to a WebApp, it may be deployed or migrated from one application server to some others.

Stems, reports and other information coming out of the grading platform are XML documents therefore, they are skinnable via XSLT style sheets to fit university look and feel. They may also be processed to fill scholar databases, grade books or any other tool that needs information about grading. These normalized XML documents isolate the grading infrastructure from local idiosyncrasies.

Confinement

Our experience shows us that students make mistakes (infinite loops, deadlocks, etc.). Their programs need to be confined in time and cpu consumption. Their production must also be limited: not much than a given number of bytes written to files or on output streams. Though rare, some students' programs are malicious and must be tightly restricted (are they allowed to post mails, to open sockets, to start background processes, to destroy resources to prevent grading other student's files, etc.) For all these reasons, we run students' programs under students' accounts (so they do not harm teachers' files) within virtual machines (QEMU or VMware) and pay much attention to offer the same initial conditions for all jobs.

To use virtual machines also guarantees to be able to reproduce for ever the same conditions in which an exercise should be graded. We previously had bad experiences with updates breaking configuration or runtime of some languages. Virtual machines also allows to offer various Operating Systems (Debian, Windows, etc.), CPUs or networked machines for clientserver programs (for instance in PHP).

Our experience also shows us that authors make mistakes. Their programs need to be similarly confined otherwise they may bog down servers, destroy common resources and harm student's experience. To grade an exercise is therefore a complex task where student's errors should appear in student's report, author's errors should appear in author's reports and FW4EX errors should be routed to FW4EX maintainers.

Grading scripts

Scripts are regular programs written in whatever language fits the task. They are run within the directory where student's files are deployed, they may read or run author's owned files (stored elsewhere) as well as read or run FW4EX libraries (stored elsewhere).

Grading may be performed by comparison (with teachers' solutions) or by verification (checking whether some property is obtained). Grading by comparison requires the author of the exercise to write his own solution but allows to randomly generate input data.

The exercise descriptor also specifies how to combine the various scripts that is, stop at first error, ignore some errors, etc.

Support libraries help writing very concise grading scripts -for specific languages (for instance in Java, we refine the JUnit framework to count the number of successful/failed assertions in addition to the number of successful/failed tests) or -for specific situations (for instance in bash, input data may be given as command options, input streams, data file names, etc.).

FW4EX-compliant clients

We strongly believe that, apart for introductory courses to Computer Science, programming should be done with professional tools such as usual programming environment (IDE). Browsers, applets cannot be considered as decent substitutes for real IDE. An FW4EX-compliant client is an IDE (often an IDE plug-in) able to speak to the three types of public servers (e, a and s) according to some REST protocols [START_REF] Fielding | Principled design of the modern web architecture[END_REF].

These protocols allow a student to authenticate, to obtain stem, to submit work and to, finally, get a report. When submitting a job and following REST principles, the client receives the URL where the report will pop up on some s server.

From an author's point of view, it is similarly possible to submit an exercise, get the corresponding autocheck report leading to the grading reports of the pseudo-jobs. Additional services exist for FW4EX maintainers to manage jobs, exercises, configuration.

Presently we have three FW4EX-compliant clients. The first is an AJAX FW4EX-compliant client running in any regular browser. It fulfills all of the needs but for the installation of the exercise on the student's computer which cannot be fully automated for security reason. It manages the display to accommodate various types of exercises (see experiments in Section 4): one-liners are captured via a one-line text widget, short scripts are captured via a textarea widget, multiple files are captured via a file upload widget.

Since it mostly handles XML documents, the AJAX FW4EX-compliant client imposes its own XSLT style sheets to display them with the wished look and feel. Additional treatments may also be performed such as using a tree widget to iconize series of lengthy tests in the grading report. The report is therefore largely independent of the display technology.

The AJAX FW4EX-compliant client may be embedded in a university portal.

Two other clients were developped as proofs of concepts: one for Eclipse (for Java, C, php, etc.) and one for Scite6 . In these IDEs, similarly to what we did for DrScheme [START_REF] Brygoo | Experiment around a training engine[END_REF], a single button or menu will manage authentication, show stem, install accompanying files, pack student's work, submit it and display the associated report, if available, as annotations to source code.

Experiments with FW4EX

We deployed the FW4EX platform in September 2008. Two experiments were conducted during the two teaching semesters, a third one took place at the end of January 2009 with quite a different modality.

One-liners

For a course on Posix skill (mainly shell and Makefile) we deploy approximately 40 exercises. These exercises are "one liners" since they contain a single question that asks for options (for utilities such as tr, sort, sed, etc.) or for whole commands for various tasks (sifting, sorting, regexp-ing, etc.). Stems are terse and imprecise (but always give an example of use) in order to let students think about limit cases such as empty streams, empty files, files out of the current directory, files with weird names, etc. The goal of these formative exercises was to encourage students to read the associated man pages in order to be familiar with the 2 to 4 most useful options with each of these utilities.

These exercises are permanently available for all students, students are not limited in number of submissions. Reports are very detailed, every test is explained, results are shown and reasons for success or failure are verbalised. Students have to analyse these reports and sometimes discover that some limit cases are indeed possible with respect to the stem. In the actual deployment, grading reports are obtained after 20 seconds. Such a duration compels students to consider that the grader is not a fast debugging tool so debug should be done appropriately on their computer before asking to be graded.

We offer roughly 5 exercises per week for 7 weeks. We start from exercises asking for options and end with exercises asking for small shell scripts (less than 10 lines). With help of the support libraries, grading scripts were reduced to a line or two.

On the 120 students enrolled for the course, half of them tried at least one exercise. The platform had been serving (night and day) around 3500 submissions per semester.

The exercises were not prescribed, only voluntary students try them. As already reported [START_REF] Woit | Effectiveness of online assessment[END_REF], students did not volunteer easily. Apart the initial curiosity of the first week, we only noted the usual peak during the week that precede examinations.

Examinations

In the same course, we use the FW4EX platform to grade the mid-term examination and the two final examinations. The examinations contain three summative exercises each containing 1 to 6 rather independent questions. Contrarily to the one-liners, examinations are very carefully specified. Stems are precise, they ask for scripts (or Makefile rules) performing various tasks. Examples are always given, deliverables are specified and some hints are given about how grading will be performed.

These examinations last 3 hours. As usual the mid-term examination mainly serves to prepare the students for the final examinations. The student's works are sent to the grader after the examination therefore students do no have any feedback during the examination.

In this setting, we had 120 sets of students' files to grade. The exercise file (containing the examination) was prepared with 6 pseudo jobs. We grade the whole set of students' files 4 times in order to tune the grader: we had to cope with misnamed scripts or files, to fix an encoding problem (UTF8 versus Latin1) and to slightly alter the weight of two questions. Approximately 60 seconds were necessary to grade one student.

The design and test of these examinations (writing the stem, writing a solution, writing the grading scripts and testing them over pseudo jobs) around two days of work.

Five days were necessary for the examinations before the reports and grades were made available to the students (a student may only access his own report). Among these five days, three were alloted to the teaching assistants to check whether the results were agreeing with the behaviour of the students during lab sessions.

The mid-term examination was also made available as a regular (although huge) exercise itself. Students may then retry this examination in a less stressed context (at home) but, at the same time, be graded by the exact grader used at the examination. This is what we call "dynamic annals". Only 6 students retried the examination, 1 among them got a grade greater than 19/20 in 4 attempts, the others topped at 6/20 with 1 to 6 attempts before abandon.

The examination was held on the computers of the laboratories where no plagiarism was possible. Plagiarism detection will be considered as an option for batch grading.

Programming contest

The "Journée Francilienne de Programmation" is a programming contest for undergraduate students from various Parisian universities. A dozen of programming languages are indeed possible to solve the proposed problem. The contest lasts 5 hours during which 12 teams of voluntary students regularly submit their work (120 uploads) and get their grade (the average grading time was 45 seconds) in order to appreciate how they perform with respect to the other teams. Besides individual grading, the portal runs additional scripts using the reports from FW4EX to deliver bonus points to teams' works (mainly based on the speed of programs).

The next edition of this contest will use the same grading infrastructure.

Summary of experiments

These three experiments show the versatility of the FW4EX platform. One-liners are multiply submitted and graded whereas examinations are just graded once. Examinations and contests are read offline by humans but one-liners are just automatically graded. One-liners are graded in a couple of seconds, examinations and contests take a minute.

Related work

While there are many mechanised graders on the market, there are often tailored to a single programming language or tightly bound to scholar databases or imposing a precise workflow. All this characteristics make difficult to re-use these embedded graders.

The BOSS Online Submission System7 [START_REF] Joy | The boss online submission and assessment system[END_REF] is a course management tool. It allows students to submit assignments online securely, and contains a selection of tools to allow staff to mark assignments online and to manage their modules efficiently. Plagiarism detection software is included. Interaction with BOSS may use an application or a web front end.

BOSS is a complete course-oriented web application whereas FW4EX is only a set of protocols to operate a grading infrastructure. On the other hand FW4EX achieves better robustness against malicious submissions and scalability. However due to the flexible architecture of BOSS that uses factories to hide implementation choices or binding constraints with external resources, it would not be difficult to let BOSS use FW4EX.

CourseMaker8 [START_REF] Higgins | Automated assessment and experiences of teaching programming[END_REF]) is a webbased, easy-to-use course creation package commercialised by the Connect company. It is now roughly similar in functionalities to Blackboard or Sakai. Like BOSS, it contains a number of tools -to check typography, syntax, comments, -and to detect plagiarism. CourseMaker is a complete solution that contains courses documents, exchanges information with scholar databases, deploys student clients application or web-based forms to collect work. CourseMaker hosts, on its proper network, courses along with their exercises as QTI9 files.

There again, FW4EX is different. While Course-Maker is course-oriented, FW4EX is exercise-centric.

ASAP [START_REF] Douce | A technical perspective on asapautomated system for assessment of programming[END_REF] is a new initiative that shares a number of goals with FW4EX. ASAP is com-ponentized with respect to the JISC (Joint Information Systems Committee) e-learning framework. It separates grading from submission and it also uses XML documents as a way to transmit information between components. FW4EX improves on ASAP with its emphasis on protocols, its robustness with the use of virtual machines and its attention to the whole lifecycle of exercises.

Conclusion

In this paper, we present the FW4EX project, an attempt to build a grading infrastructure that can be put to work into various learning environments. A set of REST-based protocols allows these systems or IDEs to operate the grader. A "standard" descriptor and a file format specification are proposed to reduce the deployment of new exercises to a simple file copy. We finally describe some experiments that illustrate the neutrality and versatility of the associated platform: one-liners, full examinations, programming contests in multiple programming languages.

We believe that this project provides a strong basis to foster an eco-system for mechanised grading thus allowing teachers to focus on the sole exercises and not on the grading infrastructure. Yes, this is more work for teachers to imagine a stem, write (and test) a solution, design some grading scripts but, once done, this may last for ever! More information on the FW4EX project is available on the site paracamplus.org.

Figure 1 :

 1 Figure 1: Sketch of the logical architecture of the FW4EX platform. The arrow tells which machine initiates connections.

www.junit.org

checkstyle.sourceforge.net

pmd.sourceforge.net

findbugs.sourceforge.net

perlcritic.com

www.scintilla.org

http://www.dcs.warwick.ac.uk/boss/

www.coursemaker.co.uk

www.imsglobal.org