Structure and Interpretation of Computer Programs

"The Structure and Interpretation of Computer Programs" is the entry-level subject in Computer Science at the Massachusetts Institute of Technology. It is required of all students at MIT who major in Electrical Engineering or in Computer Science, as one fourth of the "common core curriculum," which also includes two subjects on circuits and linear systems and a subject on the design of digital systems. We have been involved in the development of this subject since 1978, and we have taught this material in its present form since the fall of 1980 to approximately 600 students each year. Most of these students have had little or no prior formal training in computation, although most have played with computers a bit and a few have had extensive programming or hardware design experience. Our design of this introductory Computer Science subject reflects two major concerns. First we want to establish the idea that a computer language is not just a way of getting a computer to perform operations, but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute. Secondly, we believe that the essential material to be addressed by a subject at this level, is not the syntax of particular programming language constructs, nor clever algorithms for computing particular functions of efficiently, not even the mathematical analysis of algorithms and the foundations of computing, but rather the techniques used to control the intellectual complexity of large software systems.

OS Support for Portable Bulk Synchronous Parallel Programs

Predictability -- the ability to foretell that an implementation will not violate a set of specified reliability and timeliness requirements -- is a crucial, highly desirable property of responsive embedded systems. This paper overviews a development methodology for responsive systems, which enhances predictability by eliminating potential hazards resulting from physically-unsound specifications. The backbone of our methodology is the Time-constrained Reactive Automaton (TRA) formalism, which adopts a fundamental notion of space and time that restricts expressiveness in a way that allows the specification of only reactive, spontaneous, and causal computation. Using the TRA model, unrealistic systems – possessing properties such as clairvoyance, caprice, infinite capacity, or perfect timing -- cannot even be specified. We argue that this "ounce of prevention" at the specification level is likely to spare a lot of time and energy in the development cycle of responsive systems -- not to mention the elimination of potential hazards that would have gone, otherwise, unnoticed. The TRA model is presented to system developers through the Cleopatra programming language. Cleopatra features a C-like imperative syntax for the description of computation, which makes it easier to incorporate in applications already using C. It is event-driven, and thus appropriate for embedded process control applications. It is object-oriented and compositional, thus advocating modularity and reusability. Cleopatra is semantically sound; its objects can be transformed, mechanically and unambiguously, into formal TRA automata for verification purposes, which can be pursued using model-checking or theorem proving techniques. Since 1989, an ancestor of Cleopatra has been in use as a specification and simulation language for embedded time-critical robotic processes.

Ethics in neuroscience graduate training programs:Views and models from Canada

Consideration of the ethical, social, and policy implications of research has become increasingly important to scientists and scholars whose work focuses on brain and mind, but limited empirical data exist on the education in ethics available to them. We examined the current landscape of ethics training in neuroscience programs, beginning with the Canadian context specifically, to elucidate the perceived needs of mentors and trainees and offer recommendations for resource development to meet those needs. We surveyed neuroscientists at all training levels and interviewed directors of neuroscience programs and training grants. A total of 88% of survey respondents reported general interest in ethics, and 96% indicated a desire for more ethics content as it applies to brain research and clinical translation. Expert interviews revealed formal ethics education in over half of programs and in 90% of grants-based programs. Lack of time, resources, and expertise, however, are major barriers to expanding ethics content in neuroscience education. We conclude with an initial set of recommendations to address these barriers which includes the development of flexible, tailored ethics education tools, increased financial support for ethics training, and strategies for fostering collaboration between ethics experts, neuroscience program directors, and funding agencies. © 2010 the Authors. Journal Compilation © 2010 International Mind, Brain, and Education Society and Blackwell Publishing, Inc.

Paraphrasing:Generating parallel programs using refactoring

Refactoring is the process of changing the structure of a program without changing its behaviour. Refactoring has so far only really been deployed effectively for sequential programs. However, with the increased availability of multicore (and, soon, manycore) systems, refactoring can play an important role in helping both expert and non-expert parallel programmers structure and implement their parallel programs. This paper describes the design of a new refactoring tool that is aimed at increasing the programmability of parallel systems. To motivate our design, we refactor a number of examples in C, C++ and Erlang into good parallel implementations, using a set of formal pattern rewrite rules. © 2013 Springer-Verlag Berlin Heidelberg.

Adding metadata to Orc to support reasoning about grid programs

Following earlier work demonstrating the utility of Orc as a means of specifying and reasoning about grid applications we propose the enhancement of such specifications with metadata that provide a means to extend an Orc specification with implementation oriented information. We argue that such specifications provide a useful refinement step in allowing reasoning about implementation related issues ahead of actual implementation or even prototyping. As examples, we demonstrate how such extended specifications can be used for investigating security related issues and for evaluating the cost of handling grid resource faults. The approach emphasises a semi-formal style of reasoning that makes maximum use of programmer domain knowledge and experience.

Equational Reasoning about Object-Oriented Programs

Formal verification of software can be an enormous task. This fact brought some software engineers to claim that formal verification is not feasible in practice. One possible method of supporting the verification process is a programming language that provides powerful abstraction mechanisms combined with intensive reuse of code. In this thesis we present a strongly typed functional object-oriented programming language. This language features type operators of arbitrary kind corresponding to so-called type protocols. Sub classing and inheritance is based on higher-order matching, i.e., utilizes type protocols as basic tool for reuse of code. We define the operational and axiomatic semantics of this language formally. The latter is the basis of the interactive proof assistant VOOP (Verified Object-Oriented Programs) that allows the user to prove equational properties of programs interactively.

Using Network Analysis to Understand and Advance Falls Prevention Services and Programs

The purpose of this study was to understand referral linkages that exist among falls prevention agencies in a southern Ontario region using network analysis theory. This was a single case study which included fifteen individual interviews. The data was analyzed through the constant comparative approach. Ten themes emerged and are classified into internal and external factors. Themes associated with internal factors are: 1) health professionals initiating services; 2) communication strategies; 3) formal partnerships; 4) trust; 5) program awareness; and 6) referral policies. Themes associated with external factors are: 1) client characteristics; 2) primary and community care collaboration; 3) networking; and 4) funding. Recommendations to improve the referral pathway are: 1) electronic database; 2) electronic referral forms; 3) educating office staff; and 4) education days. This study outlined the benefit of using network analysis to understand referral pathways and the importance of implementing strategies that will improve falls prevention referral pathways.

Modeling of ALFA Programs Using PVS Theorem Prover

In Safety critical software failure can have a high price. Such software should be free of errors before it is put into operation. Application of formal methods in the Software Development Life Cycle helps to ensure that the software for safety critical missions are ultra reliable. PVS theorem prover, a formal method tool, can be used for the formal verification of software in ADA Language for Flight Software Application (ALFA.). This paper describes the modeling of ALFA programs for PVS theorem prover. An ALFA2PVS translator is developed which automatically converts the software in ALFA to PVS specification. By this approach the software can be verified formally with respect to underflow/overflow errors and divide by zero conditions without the actual execution of the code.

Modeling of ALFA Programs Using PVS Theorem Prover

In Safety critical software failure can have a high price. Such software should be free of errors before it is put into operation. Application of formal methods in the Software Development Life Cycle helps to ensure that the software for safety critical missions are ultra reliable. PVS theorem prover, a formal method tool, can be used for the formal verification of software in ADA Language for Flight Software Application (ALFA.). This paper describes the modeling of ALFA programs for PVS theorem prover. An ALFA2PVS translator is developed which automatically converts the software in ALFA to PVS specification. By this approach the software can be verified formally with respect to underflow/overflow errors and divide by zero conditions without the actual execution of the code

Protocols between programs and proofs

In this paper we describe a new protocol that we call the Curry-Howard protocol between a theory and the programs extracted from it. This protocol leads to the expansion of the theory and the production of more powerful programs. The methodology we use for automatically extracting “correct” programs from proofs is a development of the well-known Curry-Howard process. Program extraction has been developed by many authors, but our presentation is ultimately aimed at a practical, usable system and has a number of novel features. These include 1. a very simple and natural mimicking of ordinary mathematical practice and likewise the use of established computer programs when we obtain programs from formal proofs, and 2. a conceptual distinction between programs on the one hand, and proofs of theorems that yield programs on the other. An implementation of our methodology is the Fred system. As an example of our protocol we describe a constructive proof of the well-known theorem that every graph of even parity can be decomposed into a list of disjoint cycles. Given such a graph as input, the extracted program produces a list of the (non-trivial) disjoint cycles as promised.

Extraction of structured programs from specification proofs

We present a method using an extended logical system for obtaining programs from specifications written in a sublanguage of CASL. These programs are “correct” in the sense that they satisfy their specifications. The technique we use is to extract programs from proofs in formal logic by techniques due to Curry and Howard. The logical calculus, however, is novel because it adds structural rules corresponding to the standard ways of modifying specifications: translating (renaming), taking unions, and hiding signatures. Although programs extracted by the Curry-Howard process can be very cumbersome, we use a number of simplifications that ensure that the programs extracted are in a language close to a standard high-level programming language. We use this to produce an executable refinement of a given specification and we then provide a method for producing a program module that maximally respects the original structure of the specification. Throughout the paper we demonstrate the technique with a simple example.

Community language programs in Australian schools: policy at the crossroads

The linguistic situation in Australia today presents an intriguing case for sociolinguistic inquiries. Despite the recent waves of migration from non Anglo-Celtic regions, the majority of Australians today are primarily monolingual with English being the dominant language. More critical, perhaps, is the diminishing appeal of second language learning even among second generation speakers of the large ethnic communities. This is indeed ironic giving that prior to white settlement in Australia, the Aboriginal inhabitants were predominantly multilingual with more than 250 languages (and many of their dialects) spoken by the 300 000 original inhabitants at the time when Captain James Cook's ship reached Botany Bay in Sydney in 1770. Given the size of the post-War migration, it was not until 1987 that the Australian government adopted a formal national policy on languages becoming 'the first English-speaking country to have such a policy and the first in the world to have a multilingual languages policy' (Australian Alliance for Languages 2001: 2). This paper will discuss the historical context for multilingualism in Australia and the current trend in government policy and funding. It will provide insights into community language programs and the challenges of remaining viable and relevant in the current social and political climate. Statistical analyses will be used to highlight emerging trends and future prospects.

A content analysis of early childhood teachers’ theoretical and practical experiences with infants and toddlers in Australian teacher education programs

 In Australia, the growth in the provision of early childhood services for very young children aged birth to three years has placed increased demands on pre-service teachers as new policy stipulates the need for qualified early childhood teachers. While many teacher education programs offer early childhood courses, they have traditionally had a greater focus on kindergarten and the formal years of schooling. Less is known about the amount of time devoted to developing the specialist educational capacity for teaching and caring for infants and toddlers. This paper explores 55 Australian early childhood teacher undergraduate education programs to provide data regarding what pre-service teachers learn about children from birth to three years of age during their formal program of study. It explores: if pre-service teachers engage in practical experiences with this age range; what content they learn; and how knowledge for this age range is assessed. Utilising information from fully accessible public program websites, data in the form of course details were examined to reveal the extent and nature of courses inclusive of teaching and learning focusing on children aged from birth to three years. Of the 55 programs, 18 programs provided practical experience with infants and toddlers, and to a lesser extent content was evident and assessed. Most of the programs which included a focus on birth to three years of age were delivered by Victorian institutions. Findings are important for the future of early childhood teacher education in Australia and hold key messages for teacher registration bodies.

Graduate Nurse Program Coordinators' perspectives on graduate nurse programs in Victoria, Australia: A descriptive qualitative approach

Aims: The purpose of this study was to describe the formal preparation nursing graduates are given throughout their first year of nursing in terms of educational structure and content of work-based year-long graduate nurse programs, from the perspectives of Graduate Nurse Program Coordinators. Background: In Australia, graduate nurse programs aim to provide a supportive learning environment, assisting nursing graduates in applying their theory to practice and supporting them in becoming safe, competent and responsible professionals. Internationally, research has demonstrated an increase in the job satisfaction and more importantly retention rates of newly qualified nurses who are supported in their first year of employment in some type of transition program. Method: Using a descriptive qualitative approach, individual semi-structured interviews were used. These interviews were audio recorded, transcribed verbatim and thematically analysed to reveal themes and sub-themes. Results: The interviews provided an insight into the various aspects of preparation that nursing graduates are given in their first year of practice with the main theme to emerge from analysis, nature of transition programs. The three subthemes associated with nature of transition programs consisted of composition of rotations and study days and supernumerary strategies. Findings indicate variation in pedagogical models underpinning graduate nurse programs across Victoria. Clinical rotations varied between three to twelve months, the number of study days offered were between four and thirteen days and there was variation in supernumerary time and strategies within the programs investigated.