We propose a framework for the evaluation of implicitly parallel functional programs on message passing multiprocessors with special emphasis on the issue of load bounding. The model is based on a new encoding of the lambda-calculus in Milner's pi-calculus and combines lazy evaluation and eager (parallel) evaluation in the same framework. The pi-calculus encoding serves as the specification of a more concrete compilation scheme mapping a simple functional language into a message passing, parallel program. We show how and under which conditions we can guarantee successful load bounding based on this compilation scheme. Finally we discuss the architectural requirements for a machine to support our model efficiently and we present a simple RISC-style processor architecture which meets those criteria.

Thesis (M.A.)--Boston University / A complex modern society has presented its managers with the need to solve a variety of optimization problems. The desire to run a firm in such a way that profit is maximized, to schedule bombing runs to inflict a maximum of damage on an opponent consistent with acceptable losses, or to choose an assignment of available personnel which optimizes efficiency are typical examples. Such problems are called programming problems. The unifying idea here is that the limited resources (e.g. factors of production, planes, or personnel) which are available for use may be combined in a large (generally infinite) number of ways. The object is to choose from these possibilities the combination or combinations which will optimize a measure of the effectiveness of the enterprise. Mathematically, the programming problem is stated. [TRUNCATED]

This thesis is concerned with the problems that novices have in learning to program: in particular it is concerned with the difficulties experienced by novices learning at a distance, using instructional materials which have been designed especially for novices. One of the major problems for novices is how to link the new information which they encounter with their existing knowledge. Du Boulay, O'Shea and Monk (1981) suggest helping novices to bridge the gap between their existing knowledge and new information by teaching via a conceptual model, which serves to explain the new information in familiar terms. In this thesis the difficulties which novices have when learning to program with the help of a conceptual model were investigated. The curricula and conceptual models of four different programming languages are examined, all of which were designed to teach novices. Du Boulay, O'Shea and Monk (1981) have suggested criteria for analysing conceptual models. It is argued that these criteria, however, do not address the presentation of the conceptual model, and so are insufficient to evaluate them. An additional form of analysis was proposed and used, in addition to the criteria offered by Du Boulay et al. This is a way of describing the conceptual model which distinguishes three views of the conceptual model: state, procedure and function, and which highlights the different aspects which are important for the novice learner by identifying the different kinds of knowledge which are necessary to understand the conceptual model. This analysis of the conceptual models showed that the environments are not as exemplary as the du Boulay et al's criteria suggest, and indicated that three of the environments, SOLO, PT501 and DESMOND, lack a functional representation, and that the fourth, Open Logo, has other different problems. An empirical study was carried out to study the transfer effects of learning two of the languages, a high level and a low level language, sequentially. There was no evidence for such transfer effects. The difficulties novices have in learning the four different languages were also investigated. These studies show that even though the novices were studying environments designed for novices learning at a distance, they did not develop good levels of competence, and the problems they had fall into two main categories: programming and pedagogical. Although the different languages had different aims and curricula, novices had some problems which were common to all or most of the languages. These included understanding flow of control, developing and using programming plans, developing accurate mental models, and in the high level languages, understanding recursion. It is argued that some of these problems are related to the conceptual models. In particular, the difficulties novices had in developing and using plan knowledge, which is one of their main problems, can be explained by the lack of an appropriate functional description in the languages. The subjects' pedagogical problems arose from the relationship between the style and structure of the curriculum, its content, and the subjects themselves. In all the four texts the teaching material is very carefully structured and it is suggested that this may encourage the learner to adopt an over-dependent attitude towards the text, and in some cases, to work at an inappropriate syntactic level. The relationship between the distance learning situation and the novice programmer is discussed, and recommendations are made for improving the curricula used for teaching novices programming.

A necklace is a representative of an equivalence class of k-ary strings under rotation. Efficient algorithms for generating (i.e., listing) necklaces have been known for some time. Many applications, however, require a restricted class of necklaces for which no efficient generation algorithm previously existed. This dissertation addresses this problem by developing fast algorithms to generate the following restricted classes of necklaces: (a) unlabeled necklaces, (b) fixed density necklaces, (c) necklaces where the number of each alphabet symbol is fixed, (d) chord diagrams, (e) necklaces which avoid a particular Lyndon substring, and (f) bracelets. An analysis for each algorithm (a), (b), (e), and (f) shows that the amount of computation is proportional to the number of strings produced. Experimental results give a strong indication that the algorithms for (c) and (d) also achieve this time bound. In addition, a new derivation of the known formula for counting chord diagrams is presented, along with a linear time algorithm to generate a basis for the n-th homogeneous component of the free Lie algebra. / Graduate

Abstraction in computer programming provides a means of reducing complexity by emphasising the significant information (program behaviour) whilst suppressing the immaterial (program implementation). This aids program construction, improves reliability and maintainability, and eases the application of formal correctness proofs. The importance of data abstraction in the specification, design and implementation of large systems raises the question as to whether such methods may be applied in the context of programming languages designed before the widespread use of abstraction techniques. The program structuring facilities available in FORTRAN 77 support a form of encapsulation for simple data structures. In light of this mechanism provided by the language, state-based specification was found to be most appropriate. A specification technique incorporating object-oriented techniques is particularly suitable and allows a library of object classes to be specified and then implemented in sequential FORTRAN 77. Refinement extends the object classes so as to provide the commonly occurring generators for use in iterative constructs. Therefore, the advantages of data abstraction methods may be obtained in an early procedural language such as FORTRAN 77. Data abstraction provides data independence : a change in the representation for a particular class of objects affects only the code that implements the associated operations. This allows parallel implementations to be considered, without changes to the original specification or to any user-code. The provision of such parallel data structures is required for the migration of sequential systems onto parallel distributed memory architectures. As an illustration of this approach a general 2P2-2P (for integer P≥3) search tree utilising a pipeline of processors in a distributed memory architecture is shown to provide a means of implementing the object classes. Variations in both the number of processors allocated to the pipeline and the value of P allows the optimal search structure for a given architecture to be determined. These structures are highly efficient leading to improvements in both throughput and response time as processors are added to the array. An efficient parallel implementation of object classes is therefore achieved within the tight interface provided by abstraction.

A study in game-playing programming is made using the game of pentominoes which has a very large branching factor and where there exists almost no precise, factual information to guide the conduct of the play. The difficulties encountered imply that some apparent advantages of heuristic techniques are more heavily problem-dependent than is usually conceded. A guiding device capable of learning is incorporated which significantly improves the program's play in competition with versions lacking it and shows subjective improvement with human competition. / Science, Faculty of / Computer Science, Department of / Graduate

A theoretical technique for the minimization of a function by a random search is presented. The search is a modification of the Optimum Step Size Random Search of Schumer and Steiglitz to include reversals. A theory for updating the step size is presented upon which an implementation of a search algorithm suitable for high-dimensional functions with no requirements for derivative evaluations is based. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

The purpose of this thesis is to develop a solution to the problem of determining the minimal spanning tree with degree restraints for a given non-directional graph. Section 1 gives an introduction to the problem. A set of definitions describing the graphical terminology used in the body of the thesis, is presented along with a description of the problem. At the end of this section a few applications of the problem are given. Section 2 outlines the method of solution used. The algorithm incorporates a branch and bound technique and this problem solving method is discussed in general in the first part of the section. Some other applications of branching and bounding are also discussed. Next, the complete algorithm is described along with a proof of optimality. A sample problem is worked through to illustrate the method of solution. Two different minimal spanning tree algorithms, one by R.C. Prim, the other by J.B. Kruskal, are used in the main core of the solution algorithm. These two approaches are discussed with the aid of a sample problem, at the end of Section 2. Computer programs were written to test the algorithms. Several sets of data were compiled for various sizes of graphs and values of degree restrictions. The results of these runs were tabulated and are discussed in Section 3. Next, a comparison is made of the method discussed here and a solution involving linear programming. Section 3 also presents some useful heuristic approaches at sub-optimization which effectively reduce the amount of computation. Section 4 summarizes the results of Section 3 and indicates the best approach to use for a specific problem. / Science, Faculty of / Computer Science, Department of / Graduate

Three recent random search algorithms are compared on the basis of efficiency, and on the basis of sensitivity to noise, scaling and the number of variables. A general discussion of random search methods points out their advantages and disadvantages in relation to deterministic methods. A new random vector generator is described in the appendix. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

The present Thesis addresses the problem of specification and verification of communicating systems with value passing. We assume that such systems are described in the well-known Calculus of Communicating Systems, or rather, in its value passing version. As a specification language we propose an extension of the Modal μ-Calculus, a poly-modal first-order logic with recursion. For this logic we develop a proof system for verifying judgements of the form b ⊢ Ε : Φ where E is a sequential CCS term and b is a Boolean assumption about the value variables occurring free in E and Φ. Proofs conducted in this proof system follow the structure of the process term and the formula. This syntactic approach makes proofs easier to comprehend and machine assist. To avoid the introduction of global proof rules we adopt a technique of tagging fixpoint formulae with all relevant information needed for the discharge of reoccurring sequents. We provide such tagged formulae with a suitable semantics. The resulting proof system is shown to be sound in general and complete (relative to external reasoning about values) for a large class of sequential processes and logic formulae. We explore the idea of using tags to three different settings: value passing, extended sequents. and negative tagging. / Graduate