No description available.

No description available.

In lazy functional programming modularity is often achieved by using intermediate data structures to combine separate parts of a program. Each intermediate data structure is produced by one part and consumed by another one. Deforestation optimises a functional program by transformation into a program which does not produce such intermediate data structures. In this thesis we present a new method for deforestation, which combines a known method,short cut deforestation, with a new analysis that is based on type inference. Short cut deforestation eliminates an intermediate list by a single, local transformation. In return, short cut deforestation expects both producer and consumer of the intermediate list in a certain form. Whereas the required form of the consumer is generally considered desirable in a well-structured program anyway, the required form of the producer is only a crutch to enable deforestation. Hence only the list-producing functions of the standard libraries were defined in the desired form and short cut deforestation has been confined to compositions of these functions. Here, we present an algorithm which transforms an arbitrary producer into the required form. Starting from the observation that short cut deforestation is based on a parametricity theorem of the second-order typed lambda-calculus, we show how the construction of the required form can be reduced to a type inference problem. Typability for the second-order typed lambda-calculus is undecidable, but we only need to solve a partial type inference problem. For this problem we develop an algorithm based on the well-known Hindley-Milner type inference algorithm. The transformation of a producer often requires inlining of some function definitions. Type inference even indicates which function definitions need to be inlined. However, only limited inlining across module boundaries is practically feasible. Therefore, we extend the previously developed algorithm to split a function definition into a worker definition and a wrapper definition. We only need to inline the small wrapper definition, which transfers all information required for deforestation. The flexibility of type inference allows us to remove intermediate lists which original short cut deforestation cannot remove, even with hand-crafted producers. In contrast to most previous work on deforestation, we give a detailed proof of completeness and semantic correctness of our transformation.

No description available.

Wireless networks allow communication between multiple devices (nodes) without the use of wires. Range in such networks is often limited restricting the use of networks to small offices and homes; however, it is possible to use nodes to forward packets for others thereby extending the communication range of individual nodes. Networks employing such forwarding are called Multi-Hop Ad Hoc Networks (MANETS) Discovering routes in MANETS is a challenging task given that the topology is flat and node addresses reveal nothing about their place in the network. In addition, nodes may move or leave changing the network topology quickly. Existing approaches to discovering locations involve either broadcast dissemination or broadcast route discovery throughout the entire network. The reliance on the use of techniques that use broadcast schemes restricts the size of network that the techniques are applicable to. Routing in large scale ad hoc networks is therefore achieved by the use of geographical forwarding. Each node is required to know its location and that of its neighbours so that it may use this information for forward packets. The next hop chosen is the neighbour that is closest to the destination and a number of techniques are used to handle scenarios here the network has areas void of nodes. Use of such geographical routing techniques requires knowledge of the destination's location. This is provided by location servers and the literature proposes a number of methods of providing them. Unfortunately many of the schemes are limited by using a proportion of the network that increases with size, thereby immediately limiting the scalability. Only one technique is surveyed that provides high scalability but it has a number of limitations in terms of handling node mobility and failure. Ad hoc networks have limited capacity and so the inspiration for a technique to address these shortcomings comes from observations of nature. Birds and ants are able to organise themselves without direct communication through the observation of their environment and their peers. They provide an emergent intelligence based on individual actions rather than group collaboration. This thesis attempts to discover whether software agents can mimic this by creating a group of agents to store location information in a specific location. Instead of requiring central co-ordination, the agents observe one another and make individual decisions to create an emergent intelligence that causes them to resist mobility and node failures. The new technique is called a Self Organising Location Server (SOLS) and is compared against existing approaches to location servers. Most existing techniques do not scale well whereas SOLS uses a new idea of a home location. The use of this idea and the self organising behaviour of the agents that store the information results in significant benefits in performance. SOLS significantly out performs Terminode home region, the only other scalable approach surveyed. SOLS is able to tolerate much higher node failure rates than expected in likely implementations of large scale ad hoc networks. In addition, SOLS successfully mitigates node mobility which is likely to be encountered in an ad hoc network.

No description available.

No description available.

Genetic Programming (GP) is a technique which uses an evolutionary metaphor to automatically generate computer programs. Although GP proclaims to evolve computer programs, historically it has been used to produce code which more closely resembles mathematical formulae than the well structured programs that modern programmers aim to produce. The objective of this thesis is to explore the use of GP in generating high-level imperative programs and to present some novel techniques to progress this aim. A novel set of extensions to Montana’s Strongly Typed Genetic Programming system are presented that provide a mechanism for constraining the structure of program trees. It is demonstrated that these constraints are sufficient to evolve programs with a naturally imperative structure and to support the use of many common high-level imperative language constructs such as loops. Further simple algorithm modifications are made to support additional constructs, such as variable declarations that create new limited-scope variables. Six non-trivial problems, including sorting and the general even parity problem, are used to experimentally compare the performance of the systems and configurations proposed. Software metrics are widely used in the software engineering process for many purposes, but are largely unused in GP. A detailed analysis of evolved programs is presented using seven different metrics, including cyclomatic complexity and Halstead’s program effort. The relationship between these metrics and a program’s fitness and evaluation time is explored. It is discovered that these metrics are poorly suited for application to improve GP performance, but other potential uses are proposed.

No description available.

No description available.