Alice Byrne

Promoting Exchanges in a Changing World (1948-60)"

Introduction

When Eric Ashby published his informal portrait of the Association of Universities of the British Commonwealth (AUBC) in 1963, he noted that the interchange and secondment of staff between Commonwealth universities had long been one of its perennial topics of discussion. He commented: "It is extraordinary how frequently this last topic is talked about and approved and yet how difficult it is to turn pious resolutions into fruitful action." [START_REF] Ashby | Community of Universities[END_REF] This chapter is concerned with the AUBC's first concerted attempt to do just this through the establishment of the Commonwealth University Interchange Scheme (CUIS) in 1948. It explores both the "pious resolutions" on which the scheme was founded and the reasons why it proved so difficult to turn them into "fruitful action." In particular, the scheme's administrators would grapple with the profound changes that were redefining the Commonwealth and their implications for academic exchange. Their story is one of failure: although the CUIS ran until 1980, within a decade of its launch it had already been largely superseded by the Commonwealth Scholarship and Fellowship Plan (CSFP). But this is also a story that reveals the tensions inherent in using an international framework to promote a transnational academic community whose members belonged to universities that were themselves guided by national imperatives.

As Ashby pointed out, the interchange of staff had been regularly discussed at meetings of the AUBC's predecessor, the Bureau of Empire Universities, since the beginning of the twentieth century. Tamson Pietsch has described the interwar consensus as to the importance of individual academics moving within the network of empire universities as a means of consolidating this "expansive British community." [START_REF] Pietsch | Empire of Scholars: Universities, Networks and the British Academic World, 1850-1939[END_REF] Yet the first comprehensive program of exchanges aimed exclusively at the universities of the Commonwealth did not come into existence until after World War II, by which time the "bonds of empire" that it was arguably intended to hold in place were already unraveling. [START_REF] Pietsch | Many Rhodes: Travelling Scholarships and Imperial Citizenship in the British Academic World, 1880-1940[END_REF] As we shall see, the CUIS failed to evolve into the large-scale program that its originators had imagined, largely because it did not match the pattern of development of academic communities in the "old" Dominions. At the same time, the establishment of the CUIS coincided with Indian independence and the subsequent mutation of the British Commonwealth into the Commonwealth.

At a basic level, the CUIS offered travel grants to encourage greater academic mobility between the countries of the Commonwealth. However, it was also an ambitious attempt to create a centralized, independent, university-led Commonwealth body, which would collect funds contributed by the governments of all the member states and use them to give concrete expression to the somewhat nebulous ties of the Commonwealth. Although the scheme was mainly funded by the U.K. government, and its committee met in London, it cannot be defined as a solely British enterprise. Nor did the project emanate from the U.K. government with clear foreign policy objectives in mind. The scheme sprang instead from the overlapping interests of different agencies, which did not necessarily agree as to its ideal form and purpose. This chapter deals first with the origins of the scheme, in an attempt to identify its objectives. It then focuses on its unsuccessful expansion, illustrating the tensions at work in the field of Commonwealth exchange. At heart, the different parties involved did not share the same visions of the Commonwealth, nor did they seek the same benefits from the scheme.

Establishing the CUIS

Aims and Objectives

The conception of the scheme may be ascribed to Sir Hector Hetherington, the Principal of Glasgow University and Chairman of the British Committee of Vice-Chancellors and Principals. Hetherington was the driving force behind the 1948 Congress, which revived the Bureau of Empire Universities, enabling its transformation into the Association of Universities of the British Commonwealth (significantly, the qualifying "British" was not dropped until 1963). The CUIS was thus part of a wider attempt to consolidate longstanding university connections within the Commonwealth after the disruption of war. Furthermore, Sir Hector had his finger in a multitude of cultural and educational pies at an international level. He worked with the Foreign Office in re-establishing exchange with West German universities, participated in a committee on cultural relations with India and was also involved in the Fulbright Program. [START_REF]Hetherington papers[END_REF] He was therefore particularly well-placed to judge how the refashioning of international relations would impact both the British universities and the wider British academic world. It seems reasonable to assume that he was concerned with making sure that British universities would be able to compete with their U.S. counterparts by encouraging the circulation of academics within the Commonwealth. Certainly the comparison with the Fulbright Program and the need to provide similar opportunities within the Commonwealth for the interchange of scholars was brought out explicitly in a 1953 report on the scheme. 5

Sir Hector Hetherington (1888-1965)

Sir Hector Hetherington began his career as a lecturer in philosophy and later held chairs in that discipline at Cardiff, Exeter and Glasgow. However, it was primarily in the field of university administration that he made his mark, first at Exeter and Liverpool before returning to Glasgow. During his time as Principal of the University of Glasgow (1936-61), he also served as chairman of the Committee of Vice-Chancellors and Principals. Outside of academia, he contributed to a large number of royal commissions, public bodies and private trusts, particularly those dealing with social and economic issues. He was a committee man par excellence, occupying important positions in over fifty educational and charitable organizations.

Hetherington's commitment to public service was international in scope, starting with his involvement in the League of Nations Labour Conference (1919). He was particularly active in pursuing university interests within the Commonwealth, gaining him recognition as the "doyen" of its Vice-Chancellors. In addition to his work for the AUBC and the British Council, he acted as chairman of the Colonial Universities Grants Committee from 1942 to 1948, and subsequently provided advice on university affairs in both India and Malta. He also possessed a broad network of personal and professional contacts among North American universities, many of which awarded him honorary degrees. In addition to his Commonwealth activities, he maintained regular correspondence with the U.S. Educational Commission in the U.K. and chaired the Commonwealth (Harkness) Fellowships Committee from 1951 to 1956.

One of the most obvious obstacles to establishing a formal exchange program was financial.

Although some universities already ran bilateral exchanges with Commonwealth partners, a more ambitious scheme would inevitably require substantial funding. Hetherington's position at the heart of a wide network of educational and political relations enabled him to lay the groundwork for the scheme by obtaining an informal commitment from Patrick Gordon-Walker, the parliamentary Under-Secretary of State at the Commonwealth Relations Office (CRO), to provide £15,000 a year, channeled through the British Council. [START_REF]Correspondence between Symonds, Shreeve (British Council) and Hope[END_REF] The scheme offered obvious political advantages to the United Kingdom. The Empire and Commonwealth remained the cornerstone of the United Kingdom's claim to great power status and yet by the late 1940s, it had become an empire of "influence and identity" rather than one characterized by commercial and military power. [START_REF] Darwin | The Empire Project: The Rise and Fall of the British World-System 1830-1970[END_REF] Reinforcing a sense of community among its increasingly independent members through cultural and educational links would serve to bolster U.K. foreign policy.

With the assurance that some support would be forthcoming from the U.K.

government, Hetherington was able to invite delegates at the 1948 Congress of Empire

Universities to seek funding from the official bodies of their respective countries in order to "enable teaching staffs on leave to travel within the Commonwealth, and to facilitate visits of distinguished scholars of one part of the Commonwealth to another." 8 Attendance at the Congress was in itself proof of his audience's commitment to the Commonwealth.

Nevertheless, he sought to persuade them of the importance of extending opportunities for academics to circulate within the Commonwealth by arguing:

We are very different from one another. Each of us is bent on going his own way, yet in some genuine spiritual sense we belong together. We share in a great political and social experiment and our very diversity means that interchange between us is an experience which enlarges the resources of all of us. 9

Hetherington's introductory remarks carefully avoided any suggestion of British predominance within the proposed scheme, while reasserting the profound sense of community that held the Commonwealth together.

Structure and Key Players

A resolution in favor of establishing an interchange scheme was easily carried by the 1948 Congress. With Hetherington in the chair, a committee was formed that rapidly drew up a plan to offer travel grants to three different types of visitors: university teachers and officers on paid study leave who would spend at least six months in another Commonwealth country (category A); distinguished scholars invited by universities for shorter visits (category B); and, finally, postgraduate researchers, who were given the lowest priority (category C). The scheme thus sought to encourage the circulation of established scholars rather than students or future leaders. It was intended to maintain the long-established links between the universities of the Commonwealth, to bind them in a unit within which academics could pursue their careers, and to spread knowledge and good practice throughout the Commonwealth.

The CUIS committee was made up of representatives of the AUBC, the Committee of Vice-Chancellors and Principals of Universities in the United Kingdom and of the Universities Advisory Committee of the British Council. In practice, membership of the three bodies overlapped: Hetherington, for example, was active in all three and was largely responsible for the composition of the latter. There was an inevitable British bias and although three of the seven members were in fact Australian, they did not specifically represent Australian interests. Furthermore, the committee was comprised of university officials rather than representatives of public bodies, the only exception being the secretary who was provided by the British Council. Despite this, the Council would come to play an essential role in running the program.

The British Council was an arm's-length organization through which the U.K. government pursued its international cultural and educational policies. In 1934, the Council had been assigned the task of making "the life and thought of the British peoples more widely-known abroad" and many of its senior executives had defined this task in imperial terms. Its postwar policy was to encourage the countries of the Commonwealth to set up their own "sister" councils, with the British Council playing the role of the elder sibling. [START_REF] Byrne | The British Council and the British World 1934-1954[END_REF] The British Council envisaged the CUIS fitting into a comprehensive program of Commonwealth cultural relations, managed by this network of national councils. [START_REF] Dr | British Council Education Division, Proceedings of the Sixth Congress[END_REF] The Council naturally accepted the CRO's invitation to provide the secretariat for the CUIS and to administer the funds it provided. Unfortunately, the Treasury initially refused to sanction the necessary increase in the CRO's grant to the British Council and, despite the 1948 resolution, none of the universities took any steps toward obtaining funds from private or public bodies elsewhere in the Commonwealth. [START_REF] Cuis | [END_REF] The first round of awards was therefore funded out of the Council's budget by reducing the number of the Council's own dominion scholarships, to the consternation of some of its staff. [START_REF] Director-General | [END_REF] When CRO funding was finally established the following year, it was half the sum that had originally been promised. 14 In these circumstances, it is not surprising that there was a certain amount of confusion as to where responsibility for the interchange scheme lay. In theory the scheme was to be run in the interests of the Commonwealth universities, not of U.K. foreign policy, but given the involvement of different partners, the selection process inevitably proved problematic. The CUIS committee insisted that candidates should be selected according to their academic merit, whereas the Council tended to take other criteria into consideration. As the Council Representative in Australia put it: "from the point of view of the Council some candidates are good ambassadors and other of the recluse type are less good." [START_REF]Minute by Searls[END_REF] In practice, some Council representatives pressed to be given a say in the choice of candidates and their confidential comments were communicated discreetly to the CUIS committee. [START_REF] Searls | British Council Representative India[END_REF] The Council also on rare occasions did contribute directly to the scheme's budget to ensure funding for particular candidates and/or countries. The Council's role therefore went beyond simple administrative duties.

Extending the Scheme

Obstacles to Expansion

Despite the CUIS committee's insistence on academic criteria, the political implications of the scheme were clearly drawn out in a report submitted to the AUBC's 1953 Congress. It stressed the role that university teachers played in training future elites and the importance of contact between universities as a means of ensuring the "mutual understanding of the differences of outlook" on which the Commonwealth depended. 17 This section was deliberately aimed at Commonwealth governments in the hope that they would fund the scheme. In particular, it wished to counter the belief that the Dominions basically shared the same outlook because of their "common origin." [START_REF]Minutes of the CUIS committee[END_REF] Even the U.K. government, the only one to actually fund the scheme, was skeptical of the need to support such programs with other "British" nations. As a result, the CUIS and the British Council's Commonwealth policy were both badly affected by postwar austerity budget cuts in the late 1940s and early 1950s, culminating in the closure of the Council's offices in Australia and New Zealand in 1954.

The easing of spending restrictions in the mid 1950s coincided with a shift in the U.K. government's policy, which, following its acceptance of the Drogheda Report (1954), directed the Council to give priority to developing countries. The Hill Report, commissioned in the wake of the Suez Crisis, recommended boosting public spending on educational work in developing countries as a way to restore the United Kingdom's much-damaged prestige. Thus, in the late 1950s, new funding became available for the developing parts of the Commonwealth and the Empire, including money earmarked for scholarships. [START_REF] Donaldson | The British Council: The First Fifty Years[END_REF] The future development of the CUIS would therefore be determined by the political priorities of Commonwealth governments, none of which considered the maintenance of a peculiarly British academic community a prime concern.

Lack of funds meant that in its first years, the CUIS remained little more than a pilot scheme. In April 1951, the CUIS committee noted with pleasure the Massey Report's recommendations in favor of widening Canada's international academic contact through scholarships, the Australian government's decision to create the Australian National University and the moves being made in India toward establishing a University Grants Committee. [START_REF]Minutes of the CUIS committee[END_REF] All of this progress seemed to augur well for the CUIS. However, in fact, as the countries of the Commonwealth set up their own institutions, the appeal of a centralized Commonwealth interchange scheme diminished. Investment in these projects tended to detract funding from Commonwealth plans while endowing these countries with sufficient national capacity as to make foreign travel less important. [START_REF] Pietsch | [END_REF] When the CUIS committee tried to win more committed support for the scheme at the AUBC's Seventh Congress in Cambridge in 1953, it found itself running up against political and constitutional issues.

One possibility explored by the CUIS committee was that of following the model of foreign university interchange administered by the British Council. In this system participating countries negotiated bilateral agreements. This was rejected almost outright, partly on the grounds that the United Kingdom would struggle to find enough candidates to send abroad. 22 The implication here was that, despite the rhetoric of the Commonwealth family, exchanges with European universities were more symmetrical. The committee also felt that decentralization was incompatible with a "unified Commonwealth project" and would not allow the whole Commonwealth to benefit from the larger contribution that the United Kingdom could be expected to make, "in view of its special position." [START_REF]Proceedings of the Seventh Congress of the Universities of the British Commonwealth[END_REF] It was taken as axiomatic that the United Kingdom would continue to play a dominant role. Although the committee was willing to admit new members if and when other Commonwealth bodies provided funding, the location of its meetings and the predominantly British nature of its composition were never called into question.

Commonwealth Reactions to the Committee's Plans

The committee's determination to maintain a centralized system faced opposition at the meeting of the heads of universities held immediately before the 1953 AUBC Congress. [START_REF] Foster | [END_REF] The resolution placed before the Congress referred, with deliberate ambiguity, to a "cooperatively administered fund" and was passed without receiving the votes of the delegates from Montreal. 25 The 1951 Massey Report, which had called for a new federal commitment to Canadian education and culture, had stoked French Canadian opposition to federal interference in higher education, which was constitutionally the preserve of provincial government. The St Laurent government then started an "intergovernmental tug-of-war" by offering universities federal grants that Quebec instructed its institutions to refuse. [START_REF] Cameron | The Federal Perspective[END_REF] In such circumstances, the Quebecois universities were unlikely to seek federal funding for a scholarship scheme administered from London. [START_REF]Minutes of the CUIS committee[END_REF] The National Conference of Canadian Universities subsequently informed the CUIS committee that it would not approach the federal government with a request for extra funds for the scheme because it was already trying to persuade it to establish federal scholarships. [START_REF] Ledds | [END_REF] According to Granatstein, until the Canada Council was set up in 1957, funding scholarships had simply not formed part of the "Canadian tradition." [START_REF] Granatstein | Canada 1957-1967: The Years of Uncertainty and Innovation[END_REF] Given the political sensitivity of this issue, it is no surprise that the Canada Council later refused to pay into the centralized Commonwealth fund, even though it did offer awards to candidates recommended by the CUIS committee. [START_REF] Trueman | [END_REF] The universities of New Zealand and Ceylon (Sri Lanka) also declined to approach their governments: the first argued that it was not an "opportune" moment, while the second cited university and government policy as well as emphasizing financial constraints. [START_REF] Mckenzie | Registrar University of New Zealand to AUBC[END_REF] Requesting central government funding was also problematic for the South African universities. Although the introduction of apartheid in 1948 does not appear to have affected the position of the South African universities within the AUBC, the 1953 Congress proceedings indicated attempts by their government to make university grants conditional on the strict implementation of racial segregation among students. 32 The South African universities nevertheless made a request to the National Party government, which had been returned to power in the 1953 elections. As a Afrikaner nationalist party with, at best, an ambivalent attitude to the United Kingdom and the Commonwealth, it was unlikely to be sympathetic to the CUIS. [START_REF] Koorts | An Ageing Anachronism: D. F. Malan as Prime Minister, 1948-1954[END_REF] The South African request was refused. [START_REF]Minutes of the CUIS committee[END_REF] Of all the Commonwealth countries, Australia was the most involved in the CUIS: it received the highest number of awards and the largest slice of the scheme's budget, as well as being better represented on the committee. [START_REF] Searls | Between 1949 and 1956[END_REF] The Australian universities proved more supportive, but opted to fund the scheme directly rather than approach the central government. [START_REF] Rowe | [END_REF] As in Canada, funding was a contentious issue as universities like Melbourne were seeking a commitment from all levels of government to finance their expansion. Their willingness to contribute to the CUIS depended on its perceived usefulness within the framework of the national development of higher education. The Australian grant averaged £ 2,000 per annum, but was not matched by any other Commonwealth country and the committee's budget remained insufficient for the proposed expansion. [START_REF]Minutes of the CUIS committee[END_REF] The CUIS committee had been hopeful that India would also provide a significant contribution to its funds, on a par with the £ 5,000 mooted for Canada and Australia. [START_REF] Searls | [END_REF] No such contribution was forthcoming, though the CUIS archives do not provide an explanation.

The CUIS and the "New" Commonwealth

The universities of the Indian subcontinent were clearly not integrated into the British academic world in the way that those of the "old" Commonwealth were. The CUIS committee's lack of knowledge of these institutions and of contacts with their executives made it more difficult for it to assess their candidates. [START_REF]Minutes of the CUIS committee[END_REF] This partly explains why comments from British Council representatives were unofficially welcome in relation to Indian and Pakistani applicants. [START_REF] Searls | [END_REF] The secretary of the interchange scheme was aware of the danger of "making invidious distinctions between the older and newer countries of the Commonwealth." Yet distinctions were made, albeit off the record. [START_REF] Symonds | British Council Representative Pakistan (Confidential)[END_REF] The fact that the awards only covered travel costs in itself indicates that the scheme was not devised with the needs of Indian and Pakistani candidates in mind. University teachers' salaries were much lower in these countries; even on fully paid leave, they struggled to meet the costs of living in Britain, especially if they had families to support back home. [START_REF]Minutes of the CUIS committee[END_REF] This reinforced asymmetrical nature of exchanges with the Indian subcontinent that Ramaswami Aiyar touched on. It also explains why the CUIS committee struggled at times to find sufficient candidates to take up travel grants in the late 1950s when more funds were made available for these countries. 45 This lack of attention to the needs of scholars from these countries is perhaps surprising given that, from the point of view of both the British Council and the U.K. government, university exchanges with the newer members of the Commonwealth were of far greater political importance than the longer-established patterns of mobility between the United Kingdom and the Dominions. Cultural and educational relations were seen as a way of maintaining a degree of U.K. influence over the new states, particularly when it enabled British academics to hold positions of authority in institutes of higher education and research where they might mold future leaders. [START_REF]Annual Report[END_REF] The universities were defined as the most important target for British Council activities in India, not least because they were seen as "breeding grounds" for communism. [START_REF] Philips | British Council Representative India, memorandum "Political Atmosphere in the Mofussil[END_REF] Keeping Indian higher education within a British sphere of influence became a Cold War objective, though resisting U.S. influence was considered equally important. [START_REF] Byrne | The British Council in India, 1945-1955: Preserving 'Old Relationships under New Forms[END_REF] The interchange scheme could contribute to this objective by facilitating the circulation of academics between the United Kingdom and India. This was a concrete way of responding to a 1954 memorandum by the U.K. High Commission in India, which urged strengthening and encouraging what it termed the "healthier elements" in Indian universities, i.e. pro-British professors and students. [START_REF] Acting | High Commissioner in India to Secretary of State for CRO[END_REF] Cold War imperatives and the shift to a developmental agenda meant that when pressure to limit public spending began to ease in the United Kingdom, priority would be given to increasing the number of CUIS travel grants to candidates from the Indian subcontinent. This coincided with the decision to extend the scheme to university institutes in the colonies, for which the committee had obtained approval from both the 1953 AUBC Congress and the Colonial Office. When the CUIS budget began to rise in the second half of the 1950s, this was largely thanks an annual £ 2,000 grant from the Colonial Development and Welfare Fund and, in 1959, an additional £ 6,000 per year from the CRO destined for India and Pakistan. [START_REF]Minutes of the CUIS committee[END_REF] At the February meeting of the committee in 1958, four category A awards were made to India; in the same month two years later, thirteen such awards were made, four of them financing travel to Australia. Indeed, thanks to the Australian and Colonial contributions, a limited number of awards were finally being used to promote travel between Commonwealth countries other than the United Kingdom. 51 However, sending colonial students to India elicited concern about communist indoctrination. [START_REF] Ormerod | [END_REF]

Conclusion

The CUIS as it was drawn up in 1948 had represented the belated application of the ideas of the interwar period. As the 1950s gave way to the 1960s, Commonwealth interchange could no longer be defined in terms of traditional patterns of mobility between the United Kingdom as "mother country" and the Dominions. The failure to attract significant contributions from the "old" Commonwealth, combined with the U.K. government's new policy, led to a repositioning of the CUIS. The Commonwealth ceased to be conceived as a diverse but organic whole. Facilitating exchanges between the developed and developing countries of the Commonwealth came to the fore, arguably placing the CUIS in a better position to ease the transition to a vastly expanded multiracial Commonwealth. However, the success of the Canadian proposal for a Commonwealth Scholarship and Fellowship Plan (CSFP) in 1958 indicated that the future of Commonwealth exchanges lay in a looser, decentralized program. [START_REF] Perraton | Learning Abroad: A History of the Commonwealth Scholarship and Fellowship Plan[END_REF] The academics who had sought the British Council's support ten years earlier were quick to press the AUBC's case as the U.K. government's agent in administering the new fund. The British Council was assigned a secondary role. Above all, it was the CSFP that would attempt to give body to the new academic community of the Commonwealth which resulted from the expansion of universities in both its older member states and in the countries that were acceding to independence. The CUIS lived on as effectively a British rather than a Commonwealth program.

Alice Byrne lectures in

  Indian and Pakistani delegates at the 1953 AUBC Congress had nevertheless spoken in favor of the scheme, inasmuch as it could work in the interests of their scientific, technological and economic development and contribute to the expansion of their universities. Dr Bashir Ahmad, Vice-Chancellor of the University of the Panjab, warmly welcomed the proposed expansion of the scheme in 1953, whilst reminding delegates of the importance of supporting the development of certain parts of the Commonwealth as "real unity and solidarity can develop only between equal partners." 39 In the same discussion, Sir C.P. Ramaswami Aiyar of Annamalai University, India highlighted the importance of ensuring a two-way exchange of teachers as a means to encouraging "deep ideological comprehension." 40 The latter speaker wished to see more distinguished Indian scholars being sent abroad as a means of educating fellow members of the Commonwealth in Indian culture, serving also to enhance Indian prestige. The most recent members of the Commonwealth supported the CUIS as a way of furthering their national interests rather than consolidating a transnational academic community.

  British Studies at Aix Marseille University and is a member of the LERMA research group. Her research explores different facets of British cultural diplomacy in the twentieth century, ranging from cultural propaganda in World War II and the early Cold War to the development of educational and cultural exchanges within the Commonwealth.


Pierre-Etienne Moreau

Antoine Reilles
email: moreau|reilles@loria.fr

Rules and Strategies in Java

In this paper we present the essential feature we have considered when designing a new language based on rules and strategies. Relying on the implementation of Tom, we explain how these ingredients can be implemented and integrated in a Java environment.

Introduction

The notion of rewrite rule is an abstraction that can be used to model various processes. It has been used intensively to model, study, and analyze various parts of a complex system, from algorithms to running software. On one side it can be used to describe the behavior of a transition system for instance. On the other side, it provides a theoretical framework useful to certify and prove properties such as termination or confluence.

Besides its straightforward interpretation, the notion of rewrite rule can be used to produce efficient implementations. It has been successfully used in theorem provers and proof assistants such as RRL, Otter, Ci ME, Coq, as well as the main execution mechanism of rule based and functional languages such as ASF+SDF [START_REF] Van Den | Compiling language definitions: The ASF+SDF compiler[END_REF], Clean, Caml, ELAN [START_REF] Moreau | A compiler for rewrite programs in associativecommutative theories[END_REF], Maude [START_REF] Clavel | Reflection and strategies in rewriting logic[END_REF], and Stratego [START_REF] Visser | Building program optimizers with rewriting strategies[END_REF] for instance.

Programming with rewrite rules is apparently easy: a complex transformation can be decomposed into elementary transformations, encoded using a rewrite rule, then, we rely on the rule engine to fire a rule whenever it is possible. Most of the time, we are interested in getting a result whose computation is deterministic. In other words, the result should be reproducible, the set of rules should be terminating and confluent. However, things are rarely confluent by nature. One solution could be to use the Knuth-Bendix completion, but this is not realistic on large programs. In practice, starting from an initial signature and a simple set of rewrite rules, the programmer often modifies the signature and the rules in order to encode some control. From a software engineering point of view, this annihilates the elegance of term rewriting and makes the system much more complex and difficult to maintain.

A first solution to this problem is to assign a priority to each rule and to consider an execution mechanism that encodes a fixed order of reduction, such as innermost or outermost, also called call by value or call by name in functional programming languages. Another solution is to separate the control from the rules. Instead of encoding the control into the rules themselves, it is described in a distinct expression or language. The expressions that specifies how the rules should be applied are called strategies. The design of such a strategy language is not easy and several attempts and proposals have been made.

OBJ is one of the first languages that introduced an explicit form of strategy, called evaluation strategy. To each operator a list of integers can be attached to specify in which order the arguments should be evaluated.

Maude followed this approach and added the notion of meta-level. In this setting, a rewrite rule has a name, considered as a constant, and can be explicitly applied via the meta-apply operator. The application of a set of rules can be controlled by another program, expressed by rewriting and using meta-apply. This new program can also be controlled by another program from the meta-meta-level. This tower of reflexivity is very elegant and expressive, but a bit difficult to use.

ELAN has its origins in OBJ, but followed another approach. Instead of having a meta-level, ELAN was the first language to introduce an explicit strategy language to control the application of rules. Each rule has a name which corresponds to an elementary strategy. A strategy can then be combined with another one using operators such as ; (sequence), repeat, dont-care, and dont-know for instance. This strategy language was both very expressive and easy to use.

Stratego has been inspired by ELAN, Maude, and the functional programming style. It introduces a quite elegant and simple strategy language. Similarly to ELAN, a rule is an elementary strategy that can be combined with strategy operators such as ; (sequence), <+ (left-choice), etc. The main contribution comes from the introduction of a recursion operator and two generic congruence operators All and One, that can be used to describe higher-level strategies such as top-down, innermost or outermost. In this setting, we have T opDown(s) = µx s ; All(x), which applies s to a term t, and then recursively applies the T opDown(s) strategy to the immediate subterms of t.

ASF+SDF has also a strategy language, in the same spirit as the OBJ's one. To each operator an annotation can be attached, that specifies its behavior. The combination of traversal and bottom-up indicates that a given set of rules should be applied in a bottom-up way for example. This approach is of course less general than the previous ones, but it is an interesting trade-of between expressiveness and simplicity to use.

During the last decade we have accumulated an important experience in both implementing and using rule based languages. In this paper we try to isolate the essential constructs and features that have to be considered when designing a new rule and strategy based language. In a second part, we explain how those features can be smoothly integrated and efficiently implemented into an object oriented programming language such as Java.

Our wish list

Starting from the ELAN experience, we have tried to design a new language based on the same concepts. This process leads us to analyse what were the good points, and what were the points that could be improved. The ELAN language clearly has many interesting constructs, in particular the notion of rules, strategies, and equational matching. Unfortunately, its cohabitation with largely used programming languages such as C or Java needs some improvement. In particular, it could be very interesting to use the constructs provided by ELAN in those programming languages themselves. Starting from that situation, our goal was to design a new language, called Tom, with a comparable expressiveness, but in a more accessible programming environment. In this section we present what are the requirements and the essential features that have been considered when designing the Tom programming language.

Terms A first requirement was to be able to describe and manipulate tree shaped structures, or terms. The ELAN experience showed that it is more convenient to manipulate many sorted terms, especially since this simple typing of terms does help catching many programming errors. Languages such as ASF+SDF, ELAN or Maude do mix the term algebra used to express the rules and the concrete input syntax of the specifications. This feature is very convenient to prototype transformations, but makes the implementation of the language much more complex. In order to keep the language and the implementation simple, we wanted to keep the syntax of rules in a prefix notation, like in many functional programming languages.

Describing elementary transformations.

When designing complex applications, it is important to be able to decompose the various transformations into different rewrite systems or elementary transformations, and then decide which rule apply to which term. A first step towards this goal is to let the user define labeled rules:

[ℓ] l → r A same label can be given to several rules to define a rewrite system. The application of such system has to be explicitly specified by the user. Given a term t, the application of a labeled rule performs a single step of reduction at the root position, if t is matched by a left-hand side. Otherwise, the application fails.

Computing canonical forms.

Another important feature inherited from ELAN is the ability to automatically maintain terms in normal form with respect to a rewrite system. This is done via the definition of unlabeled rules which are applied until getting an irreducible term. The considered rewrite system has of course to be confluent and terminating.

Using unlabeled rules, it is possible to specify a canonical form for the term data structures of the application, such as representing logical formulas in disjunc-tive normal form, or enforcing constant expression evaluation in a programming language. For instance, the following rule set can be used to express how to build boolean formulas in disjunctive normal form: Not(And(l,r)) -> Or(Not(l),Not(r)) Not(Or(l,r))

-> And(Not(l),Not(r)) Not(True())

-> False() Not(False())

-> True() Not(Not(x))

-> x And(x,Or(y,z)) -> Or(And(x,y),And(x,z)) And(Or(y,z),x) -> Or(And(y,x),And(z,x))

Maintaining a data structure in canonical form is an essential feature that improves the quality of software. The programmer does no longer have to take care of this maintenance by calling normalisation functions. In addition, this makes the writing of elementary transformations simpler since only canonical forms have to be considered.

Controlling the rewriting.

In our case, the situation is a bit particular since in addition to the notion of rule, there is an underlying Turing complete language, namely Java. To control the application of rules, an attracting possibility would be to use Java directly. This language natively offers the composition (;), the repetition (while), and many other control statements. However, the more we use Java, the more it becomes complex to reason about programs and to perform proofs. How to show that a rewrite system is terminating under a given strategy when this strategy is expressed in Java? Therefore, the problem is to find a good strategy language which is both expressive and simple to use.

As mentioned in the introduction, we have studied and experimented the expressiveness of several existing strategy languages. The one proposed by Stratego [START_REF] Visser | Building program optimizers with rewriting strategies[END_REF] has several interesting properties. It is atomic, being composed of less than 10 elementary combinators. It is expressive, allowing the definition of various traversal strategies. Initially not tailored to support non-deterministic searches, we will see that this limitation can be removed in a simple and elegant way, using context information.

We thus decided to base our strategy language on elementary combinators, that are combined with labeled rules to build more complex strategies. Given a set of rules, there are two fundamental operators for combining rules: the choice operator Choice(s 1 , s 2 ) which applies s 2 only if the application of s 1 fails. The sequence operator Sequence(s 1 , s 2 ) which applies s 1 , and then, if that succeeds, applies s 2 . The different combinators are described in Figure 1.

Recursive strategy definitions are essential to describe the common rewriting strategies such as top-down, bottom-up and leftmost-innermost. For instance, bottom-up is defined as BottomU p(v) = Sequence(All(BottomU p(v)), v)

The basic strategy combinators and the strategies that are created by composing them are generic, and will perform equally on any data structure, when the labeled rules are specific to the data structure (since they perform pattern matching and

Combinator Semantics

Identity() Does nothing, and returns the original term

Fail() Always fails

All(v)

Applies v to all direct subterms in sequence term construction). In order to build elegantly some transformations, we need data structure dependent strategy combinators, such as congruence strategies. They are used to decompose terms and to apply strategies to subterms. For example, the congruence strategy for the And constructor, noted And has two arguments, which are strategies to be applied respectively to the left and right subterms of an And. _And(s1,s2) applied to the term And(x,y) will apply s1 to x and s2 to y, and will fail if applied to a term that is not rooted by And.

Choice(v 1 ,v 2 ) Applies v 1 , then v 2 if v 1 failed Sequence(v 1 ,v 2 ) Applies v 1 , then v 2 .

Knowing the context.

Usually, a rule application, even under strategies, is context free. When a rule or a strategy is applied, the result only depends on the term to which the strategy is applied. However, it is common to require some knowledge about the context when applying a strategy. For example, we may want to know if a particular subterm is in positive or negative position in a formula. For that, context information such as the list of terms that were traversed by the strategy before accessing the current subterm, or the position of the current subterm in the traversed term should be accessible when evaluating the right hand side of a labeled rule. The explicit representation of the notion of position also corresponds to classical operations found in the literature, such as the access to a given subterm (t |ω ) or the replacement (t[u] ω ) for instance.

Exploring a search space.

Many applications of rule based systems do require the manipulation of non deterministic rewrite systems. For instance, cryptographic protocol verification can be treated as a reachability problem in a particular non deterministic rewrite system that models the protocol. We thus require the strategy language to be able to support non determinism, by letting the user compute the set of successors of the application of a set of rules, and also the successors of the application of rules to different redexes. In ELAN, only the first case can be easily implemented. Such a control should be flexible enough to support the exploration of a search space in a depth-first or breadth-first manner.

Integration into Java.

Considered separately, each feature mentioned previously is not a revolution and already appears in a form or another in an existing rule based language, except the explicit representation of position information which is a real contribution. The main difficulty of our approach is to integrate everything into Java. This is also the main contribution of this work.

Our approach

As presented in [START_REF] Moreau | A Pattern Matching Compiler for Multiple Target Languages[END_REF][START_REF] Balland | Tom: Piggybacking rewriting on java[END_REF], the main component of our system is the Tom compiler. It mainly introduces two constructs: a '<term> to build an algebraic term, and a %match construct, similar to switch/case which executes an action (a Java statement) when a pattern matches a given subject. This system does not impose a specific term data structure: the implementation of the term data structure becomes a parameter of the Tom compiler, using a mapping mechanism. An advantage of this approach is to make the %match construct usable on any kind of data structure. The counterpart is that the user has to provide an implementation.

Terms

To help the programmer, we have designed a tool called Gom [START_REF] Reilles | Canonical abstract syntax trees[END_REF] that takes an algebraic signature as input and generates a Java implementation of this signature. This work is an extension of [START_REF] Van Den | A generator of efficient strongly typed abstract syntax trees in java[END_REF]. The interaction between Tom and Gom is illustrated in Figure 2. In this formalism, a specification for boolean expressions can be the following: The language provides modularity with the use of the imports keyword. Java classes implementing this structure are then generated, providing a typed interface as well as an efficient implementation based on maximal sharing. Following the factory design pattern, these classes provide static construction functions.

Computing canonical forms.

The implementation of canonization functions can be done by encoding a rewrite system into functions: to each defined symbol a function is associated. These functions are called when a term has to be built, and the corresponding normal form is returned. The main drawback of this approach is that the user (a Java programmer) can forget to call these normalisation functions and directly use the factory generated by Gom instead. This would result in terms which are no longer in normal form. To avoid this problem, we consider that the notion of unlabeled rule is strongly tied to the term data structure that is used in the application. We thus propose to define the set of unlabeled rules in conjunction to the definition of the data structure, in the Gom formalism. The code that implements the normalisation function will then be generated in the construction functions provided by the factory. An important consequence of this design is the impossibility to build a term which is not in normal form. Therefore, the boolean formulae that should only be manipulated in disjunctive normal form can be defined as follows: Another way to take the strategy application context into account is to use the notion of position in a term. The idea is to come back to the textbook notion of rewriting, resorting to the notion of position to identify a particular subterm or redex (t |ω or t[u] ω for example). The novelty here is to give access to the current position in a term while traversing it. This position can be manipulated as a first class object in the programming language.

To implement such a feature, each strategy combinator has to maintain the path from the root to the currently traversed term. This information is automatically maintained by the elementary combinators provided by the library: Sequence, All, One, etc. From a user perspective, the current position is returned by the function getPosition(). The object representing the position is not mutable and can be stored to be reused later. It will not be further modified when the strategy continues its traversal.

The expressive power provided by the explicit representation of positions is very high. For example, this feature is essential to implemented non deterministic exploration. Given a rewrite system implemented by a strategy, to compute the set of all possible successors, a two step algorithm can be used. First, a top-down traversal is performed to identify all possible redexes. This set of redexes can be represented by a list of pairs (t, ω i ) where t is the term, and each ω i correspond to the position of a redex. In a second step, the list is iterated, and the successors of t |ω i are computed and collected.

Conclusion

The design of a language that integrates the notions of rules and strategies in a mainstream programming language such as Java is not an easy task. We described the constructs and features that are required, and we showed how they can be integrated into the Java language.

This results in a language in which formally defining algorithms using terms, rules, and strategies is easy and elegant, without losing the flexibility and versatility of the underlying host language. It makes possible the mixture between the formal definition of a logic system, using Tom, with user code that provides a fully fledged interface implemented using low level code. The integration of formal aspects into a classical programming language eases a gradual integration of formal methods into existing projects. In practice, this integration becomes natural since the use of algebraic constructs, as those provided by Tom, makes the code smaller, more readable and robust.

Fig. 2 .

 2 Fig.2. Given a signature (ADT), a Java implementation is generated. In addition, a mapping that makes the implementation a parameter of Tom is generated. The algebraic data structure can be directly manipulated in a Tom program. The compilation process translates the data structure and the rule based program into Java classes, that can be combined with other libraries.

  l:Bool,r:Bool) | Or(l:Bool,r:Bool) | Var(name:String) }

  Fails if one of them failsIfThenElse(c,v 1 ,v 2 ) Applies c, then if c success, applies v 1 , otherwise v 2

	Not(v)	Fails if v is applicable, returns identity otherwise
	Omega(i,v)	Applies v to the i-th sub-term if it exists, fails otherwise
	One(v)	Applies v to all sub-terms in order, until a success
		Fig. 1. Elementary strategy combinators

Moreau and Reilles

And(x,Or(y,z)) -> Or(And(x,y),And(x,z)) And(Or(y,z),x) -> Or(And(y,x),And(z,x)) } } This construct ensures that there is no way to obtain a term that is not normal with respect to the rewrite system. It is also possible to use conditional rewrite rules in the ruleset, which lets the definition of ordered or balanced trees more convenient.

Describing elementary transformations.

The notion of labeled rule cannot be implemented with the same approach. A labeled rule corresponds to an elementary strategy that has to be manipulated as an object. Therefore, its implementation cannot be a function: this is not a first order object in Java. In our setting, an elementary strategy is implemented by a class which has an apply function. The implementation of such a class is generated automatically when using the %strategy keyword:

The construction %strategy swap() defines a labeled rule whose name is swap. Similarly to the %match construct, the right-hand side of a rule can be any Java statement. In this example, return 'Or(Var(y),Var(x)) is used to return an object of sort Bool. Such a rule can then be applied to a term using the apply function. The following instructions applies the swap strategy to a simple term, storing the result in the res variable: Bool b = 'Or(Var("b"),Var("a")); Bool res = 'swap().apply(b); Controlling the rewriting.

In [START_REF] Visser | Visitor combination and traversal control[END_REF], J. Visser introduced a new pattern to implement elementary combinators. This work, implemented in JJTraveler, is very important since it makes available in Java the combinator that exists in the Stratego language. A minor drawback of the approach is the implementation of the elementary strategies (the labeled rules), which requires some extra effort from the user. In particular, a quite complex interface has to be instantiated for each labeled rule. This code is now automatically generated by the %strategy keyword. A simple solution to implement our strategy language would have been to reuse JJTraveler in combination with the %strategy construct. This was our first attempt.

When programming with rules and strategies, as in Stratego [START_REF] Visser | A core language for rewriting[END_REF][START_REF] Visser | Building program optimizers with rewriting strategies[END_REF] and ELAN [START_REF] Borovanský | Le contrôle de la réécriture: étude et implantation d'un formalisme de stratégies[END_REF],

the definition of recursive composed strategies is very frequent. The definition of common rewriting strategies such as top-down, bottom-up, and leftmost-innermost is done via the use of an explicit recursion operator µ. This operator, like the let rec construct in functional languages, is essential. However, in JJTraveler this µ operator does not exist. Thus, the graph that represents the recursive strategy has to be encoded directly in Java. This is not easy and error prone. For example, the construction of the BottomUp strategy µx All(x) ; s is encoded as follows:

This graph is obtained by first allocating a Sequence with a dummy pointer set to null. Then the correct graph is built. This is clearly not the abstraction level we want to provide. In our framework, which is an extension of JJTraveler, we allow the definition of strategies that explicitly use the µ recursion operator. In Java, the bottom-up strategy can be implemented as follows:

Strategy BottomUp(Strategy s) { return 'mu(x, Sequence(All(x),s)); } This strategy can then be used to apply a strategy s to each node of a term u with t = 'BottomUp(s).visit(u).

Context and position

When analysing source code, context free information is not enough. For instance, when verifying a particular part of a program, sometimes we require to know what are the variables that are defined in the context, as well as their type. Such information can be obtained by letting user strategies to use a mutable state, that will be altered during the tree traversal. When finding a variable declaration for instance, the variable is stored, and further on, when finding a variable, it can be compared to what has been previously stored: