Shell scripting is the primary way for programmers to interact at a high level with operating systems. For decades bash shell scripts have thus been used to accomplish various tasks. But Bash has a counter-intuitive syntax that is not well understood by modern programmers and is no longer adequately supported, making it now difficult to maintain. Bash also suffers from poor performance, memory leakage problems, and limited functionality which make continued dependence on it problematic. At the request of our industrial partner, we therefore developed a source-to-source translator, bash2py, which converts bash scripts into Python. Bash2py leverages the open source bash code, and the internal parser employed by Bash to parse any bash script. However, bash2py re-implements the variable expansion that occurs in Bash to better generate correct Python code. Bash2py correctly converts most Bash into Python, but does require human intervention to handle constructs that cannot easily be automatically translated. In our experiments on real-world open source bash scripts bash2py successfully translates 90% of the code. Feedback from our industrial partner confirms the usefulness of bash2py in practice.

SUMMARY Although build systems control what code gets compiled into the final built product, they are often overlooked when studying software variability. The Linux kernel is one of the biggest open source software systems supporting variability and contains over 10,000 configurable features described in its Kconfig files. To understand the role of the build system in variability implementation, we use Linux as a case study. We study its build system, Kbuild, and extract the variability constraints in its Makefiles. We first provide a quantitative analysis of the variability in Kbuild. We then study how the variability constraints in the build system affect variability anomalies detected in Linux. We concentrate on dead and undead artifacts, and by extending previous work, we show that considering build system variability constraints allows more anomalies to be detected. We provide examples of such anomalies on both the code block and source file level. Our work shows that Kbuild contains a large percentage of the variability information in Linux, so it should not be ignored during variability analysis. Nonetheless, the anomalies we find suggest that variability on the file level in Kbuild is consistent with Kconfig, whereas the constraints on the code level are harder to keep consistent with both Kbuild and Kconfig. Copyright © 2013 John Wiley & Sons, Ltd.

The Linux kernel is one of the largest configurable open source software systems implementing static variability. In Linux, variability is scattered over three different artifacts: source code files, Kconfig files, and Makefiles. Previous work detected inconsistencies between these artifacts that led to anomalies in the intended variability of Linux. We call these variability anomalies. However, there has been no work done to analyze how these variability anomalies are introduced in the first place, and how they get fixed. In this work, we provide an analysis of the causes and fixes of variability anomalies in Linux. We first perform an exploratory case study that uses an existing set of patches which solve variability anomalies to identify patterns for their causes. The observations we make from this dataset allow us to develop four research questions which we then answer in a confirmatory case study on the scope of the whole Linux kernel. We show that variability anomalies exist for several releases in the kernel before they get fixed, and that contrary to our initial suspicion, typos in feature names do not commonly cause these anomalies. Our results show that variability anomalies are often introduced through incomplete patches that change Kconfig definitions without properly propagating these changes to the rest of the system. Anomalies are then commonly fixed through changes to the code rather than to Kconfig files.

Software development is difficult to model, particularly the noisy, non-stationary signals of changes per time unit, extracted from version control systems (VCSs). Currently researchers are utilizing timeseries analysis tools such as ARIMA to model these signals extracted from a project's VCS. Unfortunately current approaches are not very amenable to the underlying power-law distributions of this kind of signal. We propose modeling changes per time unit using multifractal analysis. This analysis can be used when a signal exhibits multi-scale self-similarity, as in the case of complex data drawn from power-law distributions. Specifically we utilize multifractal analysis to demonstrate that software development is multifractal, that is the signal is a fractal composed of multiple fractal dimensions along a range of Hurst exponents. Thus we show that software development has multi-scale self-similarity, that software development is multifractal. We also pose questions that we hope multifractal analysis can answer.

Replication is a technique widely used in parallel and distributed systems to provide qualities such as performance, scalability, reliability and availability to their clients. These qualities comprise the non-functional requirements of the system. But the functional requirement consistency may also get affected as a side-effect of replication. Different replica control protocols provide different levels of consistency from the system. In this paper we present the middleware based McRep replication protocol that supports multiple consistency model in a distributed system with replicated data. Both correctness criteria and divergence aspects of a consistency model can be specified in the McRep configuration. Supported correctness criteria include linearizability, sequential consistency, serializability, snapshot isolation and causal consistency. Bounds on divergence can be specified in either version metric or delay metric. Our approach allows the same middleware to be used for applications requiring different consistency guarantees, eliminating the need for mastering a new replication middleware or framework for every application. We carried out experiments to compare the performance of various consistency requirements in terms of response time, concurrency conflict and bandwidth overhead. We demonstrate that in McRep workloads only pay for the consistency guarantees they actually need.

The development process for a given software system is a combination of an idealized, prescribed model and a messy set of ad hoc practices. To some degree, process compliance can be enforced by supporting tools that require various steps be followed in order; however, this approach is often perceived as heavyweight and inflexible by developers, who generally prefer that tools support their desired work habits rather than limit their choices. An alternative approach to monitoring process compliance is to instrument the various tools and repositories that developers use - such as version control systems, bug-trackers, and mailing-list archives - and to build models of the de facto development process through observation, analysis, and inference. In this paper, we present a technique for recovering a project's software development processes from a variety of existing artifacts. We first apply unsupervised and supervised techniques - including word-bags, topic analysis, summary statistics, and Bayesian classifiers - to annotate software artifacts by related topics, maintenance types, and non-functional requirements. We map the analysis results onto a time-line based view of the Unified Process development model, which we call Recovered Unified Process Views. We demonstrate our approach for extracting these process views on two case studies: FreeBSD and SQLite.

Replication is a technique widely used for achieving qualities like scalability, high performance, high availability and fault tolerance in computer systems. Consistency of the system state is another quality that may also vary as a side effect of replication. There are various configurations of replication architecture and of replica control protocols that provide various levels of these system qualities. In this paper we determine an optimal overall configuration, called the OSSR (Optimal Single Site Replication) Configuration, to maximize performance and scalability based on single site replication. We propose a corresponding OSSR Protocol that implements this configuration. The OSSR Protocol provides optimal or near optimal performance and scalability for both read and write intensive applications. While increased performance from existing replication protocols comes at the cost of reduced consistency, the OSSR Protocol provides a consistency guarantee good enough for most applications. We compare the performance and scalability of this protocol with three other protocols, each having a variation in one of the configuration parameters, to demonstrate its optimality.

As development on a software project progresses, developers shift their focus between different topics and tasks many times. Managers and newcomer developers often seek ways of understanding what tasks have recently been worked on and how much effort has gone into each; for example, a manager might wonder what unexpected tasks occupied their team's attention during a period when they were supposed to have been implementing new features. Tools such as Latent Dirichlet Allocation (LDA) and Latent Semantic Indexing (LSI) can be used to extract a set of independent topics from a corpus of commit-log comments. Previous work in the area has created a single set of topics by analyzing comments from the entire lifetime of the project. In this paper, we propose windowing the topic analysis to give a more nuanced view of the system's evolution. By using a defined time-window of, for example, one month, we can track which topics come and go over time, and which ones recur. We propose visualizations of this model that allows us to explore the evolving stream of topics of development occurring over time. We demonstrate that windowed topic analysis offers advantages over topic analysis applied to a project's lifetime because many topics are quite local.

Large software systems undergo significant evolution during their lifespan, yet often individual changes are not well documented. In this work, we seek to automatically classify large changes into various categories of maintenance tasks - corrective, adaptive, perfective, feature addition, and non-functional improvement - using machine learning techniques. In a previous paper, we found that many commits could be classified easily and reliably based solely on the manual analysis of the commit metadata and commit messages (i.e., without reference to the source code). Our extension is the automation of classification by training machine learners on features extracted from the commit metadata, such as the word distribution of a commit message, commit author, and modules modified. We validated the results of the learners via 10-fold cross validation, which achieved accuracies consistently above 50%, indicating good to fair results. We found that the identity of the author of a commit provided much information about the maintenance class of a commit, almost as much as the words of the commit message. This implies that for most large commits, the Source Control System (SCS) commit messages plus the commit author identity is enough information to accurately and automatically categorize the nature of the maintenance task.

Maintainers face the daunting task of wading through a collection of both new and old revisions, trying to ferret out revisions which warrant personal inspection. One can rank revisions by size/lines of code (LOC), but often, due to the distribution of the size of changes, revisions will be of similar size. If we can't rank revisions by LOC perhaps we can rank by Halstead's and McCabe's complexity metrics? However, these metrics are problematic when applied to code fragments (revisions) written in multiple languages: special parsers are required which may not support the language or dialect used; analysis tools may not understand code fragments. We propose using the statistical moments of indentation as a lightweight, language independent, revision/diff friendly metric which actually proxies classical complexity metrics. We have extensively evaluated our approach against the entire CVS histories of the 278 of the most popular and most active SourceForge projects. We found that our results are linearly correlated and rank-correlated with traditional measures of complexity, suggesting that measuring indentation is a cheap and accurate proxy for code complexity of revisions. Thus ranking revisions by the standard deviation and summation of indentation will be very similar to ranking revisions by complexity.

Research in the mining of software repositories has frequently ignored commits that include a large number of files (we call these large commits). The main goal of this paper is to understand the rationale behind large commits, and if there is anything we can learn from them. To address this goal we performed a case study that included the manual classification of large commits of nine open source projects. The contributions include a taxonomy of large commits, which are grouped according to their intention. We contrast large commits against small commits and show that large commits are more perfective while small commits are more corrective. These large commits provide us with a window on the development practices of maintenance teams.

In a previous study, we showed that indentation was regular across multiple languages and the variance in the level of indentation of a block of revised code is correlated with metrics such as McCabe cyclomatic complexity. Building on that work the current paper investigates the relationship between the "shape'' of the indentation of the revised code block (the "revision'') and the corresponding syntactic structure of the code. We annotated revisions matching these three indentation shapes: "flat'' (all lines are equally indented), "slash'' (indentation becomes increasingly deep), or "bubble'' (indentation increases and then decreases). We then classified the code structure as one of: function definition, loop, expression, comment, etc. We studied thousands of revisions, coming from over 200 software projects, written in a variety of languages. Our study indicates that indentation shape correlates positively with code structure; that is, certain shapes typically correspond to certain code structures. For example, flat shapes commonly correspond to comments while bubble shapes commonly correspond to conditionals and function definitions. These results can form the basis of a tool framework that can analyze code in a language independent way to support browsing targeted to viewing particular code structures such as conditionals or comments.

In a software system, it is inevitable that components will occasionally fail to produce acceptable results and become unavailable to serve its clients. Replication is the technique often used to increase the availability of a system. But replication introduces the issue of inconsistency among the replicas. TACT is a middleware toolkit for building services that can make a controlled and systematic tradeoff between the availability and the data consistency in the system. This paper presents a tradeoff model TOM that gives various properties and constraints that apply to a tradeoff situation. Using this model we show that the tradeoff in TACT is essentially 4 dimensional rather than just 2. The capacity and demand of the system adds additional dimensions to the basic availability and consistency tradeoff. We also show how TOM can be used to fulfil the QoS goals of the system with dynamically changing load and failure characteristics

Studying the release-time activities of a software project — that is, activities that occur around the time of a major or minor release — can provide insights into both the development processes used and the nature of the system itself. Although tools rarely record detailed logs of developer behavior, we can infer release-time activities from available data, such as logs from revision control systems, bug tracking systems, etc. In this paper, we discuss the results of a case study in mining patterns of release-time behavior from the revision control systems of four open source database systems. We partitioned the development artifacts into four classes — source code, tests, build files, and documentation — to be able to characterize the behavioral patterns more precisely. We found, for example, that there were consistent activity patterns around release time within each of the individual projects; we also found that these patterns did not persist across systems, leading us to hypothesize that the four projects follow different but consistent development patterns of activity around releases.

We examine eleven large open source software systems and present empirical evidence for the existence of fractal structures in software evolution. In our study, fractal structures are measured as power laws throughout the lifetime of each software system. We describe two specific power law related phenomena: the probability distribution of software changes decreases as a power function of change sizes; and the time series of software change exhibits long range correlations with power law behavior. The existence of such spatial (across the system) and temporal (over the system lifetime) power laws suggests that self-organized criticality (SOC) occurs in the evolution of open source systems. As a result, SOC may be useful as a conceptual framework for understanding software evolution dynamics (the cause and mechanism of change or growth). We also discuss the implications of SOC to software practices.

Coupling and cohesion between subsystems are commonly studied metrics when analyzing the architecture of software systems. It is usually desirable for subsystems to have high cohesion within the subsystem and to have low coupling to other subsystems. High cohesion implies cohesive concerns and low coupling implies localized changes. We extend the ideas of coupling and cohesion to code cloning. A code clone is a segment of code that has been created through duplication of another piece of code. Previous research has shown that in some instances code cloning is desirable, whereas in other cases it is not. We believe that it is justifiable to have code cloning within subsystems (high cohesion), whereas it is not justifiable and likely not desirable to have it across subsystems (high coupling). We present an approach, which consists of a framework that generates and filters cloning data and a visualization technique which graphically highlights clone cohesion and coupling between architectural subsystems. Our approach can be used by developers to locate undesirable cloning in their software system. We demonstrate our approach through a case study on the SCSI drivers in the Linux kernel.

No abstract available

To remain competitive in the fast paced world of software development, managers must optimize the usage of their limited resources to deliver quality products on time and within budget. In this paper, we present an approach (the top ten list) which highlights to managers the ten most susceptible subsystems (directories) to have a fault. Managers can focus testing resources to the subsystems suggested by the list. The list is updated dynamically as the development of the system progresses. We present heuristics to create the top ten list and develop techniques to measure the performance of these heuristics. To validate our work, we apply our presented approach to six large open source projects (three operating systems: NetBSD, FreeBSD, OpenBSD; a window manager: KDE; an office productivity suite: KOffice; and a database management system: Postgres). Furthermore, we examine the benefits of increasing the size of the top ten list and study its performance.

To aid software analysis and maintenance tasks, a number of software clustering algorithms have been proposed to automatically partition a software system into meaningful subsystems or clusters. However, it is unknown whether these algorithms produce similar meaningful clusterings for similar versions of a real-life software system under continual change and growth. This paper describes a comparative study of six software clustering algorithms. We applied each of the algorithms to subsequent versions from five large open source systems. We conducted comparisons based on three criteria respectively: stability (Does the clustering change only modestly as the system undergoes modest updating?), authoritative-ness (Does the clustering reasonably approximate the structure an authority provides?) and extremity of cluster distribution (Does the clustering avoid huge clusters and many very small clusters?). Experimental results indicate that the studied algorithms exhibit distinct characteristics. For example, the clusterings from the most stable algorithm bear little similarity to the implemented system structure, while the clusterings from the least stable algorithm has the best cluster distribution. Based on obtained results, we claim that current automatic clustering algorithms need significant improvement to provide continual support for large software projects.

. source control systems store changes to the source code as development progresses, . defect tracking systems follow the resolution of software defects, and . archived communications between project personnel record rationale for decisions throughout the life of a project. The data in these repositories is available for most large software projects and represents a detailed and rich record of the historical development of software systems. Until recently these repositories were used primarily for their intended activities such as maintaining versions of the source code or tracking the status of a defect. Software practitioners and researchers are beginning to recognize the potential benefit of mining this information for other purposes. Research is now proceeding to uncover the ways in which mining these repositories can help support the maintenance of software systems, improve software design/reuse, and empirically validate novel ideas and techniques. Unfortunately, software repositories are not designed to facilitate empirical understanding of a software project. Software tools (such as version control and defect tracking systems) tend to have various anomalies and issues in their recorded information. Tools may be used differently in different projects, and different tools are often used in different organizations. More importantly, the quantities of interest such as development effort are usually not directly captured. A key challenge is to build useful theories and models of software development that can be empirically validated using the information in software repositories. There has been progress in overcoming some of these challenges by constructing tools and developing methods to extract, clean, and validate information from software repositories. A workshop on the topic of mining software repositories (MSR 2004: http://msr.uwaterloo.ca) was held on 25 May 2004 in Edinburgh, UK, in conjunction with the 26th IEEE International Conference on Software Engineering (ICSE). A following workshop (MSR 2005) was held on 17 May 2005 in Saint Louis, Missouri, in conjunction with the 27th ICSE. Each workshop had submissions from over 14 countries. Both workshops had over 50 attendees, making the MSR workshop series the most attended ICSE workshop for the last two years. These workshops have established a community of researchers and practitioners who are working to recover and use the data stored in software repositories to further understanding of software development practices.

Software systems contain entities, such as functions and variables, which are related to each other. As a software system evolves to accommodate new features and repair bugs, changes occur to these entities. Developers must ensure that related entities are updated to be consistent with these changes. This paper addresses the question: How does a change in one source code entity propagate to other entities? We propose several heuristics to predict change propagation. We present a framework to measure the performance of our proposed heuristics. We validate our results empirically using data obtained by analyzing the development history for five large open source software systems.

We propose an approach (based on water transformations) to migrate Web applications between various Web development frameworks. This migration process preserves the structure of the code and the location of comments to ease future manual maintenance of the migrated code. Developers can move their applications to the framework that meets their current needs instead of being locked into their initial development framework. We give an example of using our approach to migrate a Web application written using active server pages (ASP) framework to Netscape server pages (NSP) framework.

Benchmarks have been used in computer science to compare the performance of computer systems, information retrieval algorithms, databases, and many other technologies. The creation and widespread use of a benchmark within a research area is frequently accompanied by rapid technical progress and community building. These observations have led us to formulate a theory of benchmarking within scientific disciplines. Based on this theory, we challenge software engineering research to become more scientific and cohesive by working as a community to define benchmarks. In support of this challenge, we present a case study of the reverse engineering community, where we have successfully used benchmarks to advance the state of research.

Web applications are the legacy software of the future. Developed under tight schedules, with high employee turn over, and in a rapidly evolving environment, these systems are often poorly structured and poorly documented. Maintaining such systems is problematic.This paper presents an approach to recover the architecture of such systems, in order to make maintenance more manageable. Our lightweight approach is flexible and retargetable to the various technologies that are used in developing web applications. The approach extracts the structure of dynamic web applications and shows the interaction between their various components such as databases, distributed objects, and web pages. The recovery process uses a set of specialized extractors to analyze the source code and binaries of web applications. The extracted data is manipulated to reduce the complexity of the architectural diagrams. Developers can use the extracted architecture to gain a better understanding of web applications and to assist in their maintenance.

In order to understand, analyze and modify software, we commonly examine and manipulate its architecture. For example, we may want to examine the architecture at different levels of abstraction. We can view such manipulations as architectural transformations, and more specifically, as graph transformations. We evaluate relational algebra as a way of specifying and automating the architectural transformations. Specifically, we examine Grok, a relational calculator that is part of the PBS toolkit. We show that relational algebra is practical in that we are able to specify many of the transformations commonly occurring during software maintenance and, using a tool like Grok, we are able to manipulate, quite efficiently, large software graphs; this is a "win". However, this approach is not well suited to express some types of transforms involving patterns of edges and nodes; this is a "loss". By means of a set of examples, the paper makes clear when the approach wins and when it loses.

No abstract available.

In order to understand and improve software, we commonly examine and manipulate its architecture. For example, we may want to examine the architecture at different levels of abstraction or zoom-in on one portion of the system. We may discover that the extracted architecture has deviated from our mental model of the software and hence we may want to repair it. The paper identifies the commonality between these architectural transformation actions, i.e., by manipulating the architecture in order to understand analyze, and modify the software structure, we are in fact performing graph transformations. We categorize useful architectural transformations and describe them within the framework of graph transformations. By describing them in a unified way, we gain a better understanding of the transformations and thus, can work towards modeling, specifying and automating them.

In order to understand, analyze and possibly modify software, we commonly examine and manipulate its architecture. For example, we may want to examine the architecture at different levels of abstraction or repair the architecture if it has deviated from our mental model of the software. We can view such manipulations as architectural transformations, and more specifically, as graph transformations. In this paper, we use graph rewriting to specify these transformations so that we can work towards automating them. Specifically, we use the PROGRES tool to formulate executable graph-rewriting specifications for various architectural transformations in order to demonstrate the strengths of using graph rewriting. We have applied our executable specifications to small graphs and our results confirm that graph rewriting offers a high-level visual notation that can be used to neatly specify graph modifications, as well as supporting prototype implementations. It also provides a convenient and intuitive framework for exploring various architectural transformations.

Article Linux as a case study: its extracted software architecture Share on Authors: Ivan T. Bowman Dept. of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada Dept. of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, CanadaView Profile , Richard C. Holt Dept. of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada Dept. of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, CanadaView Profile , Neil V. Brewster Dept. of Electrical and Computer Engineering, University of Toronto, Toronto, Ontario M5S 1A4, Canada Dept. of Electrical and Computer Engineering, University of Toronto, Toronto, Ontario M5S 1A4, CanadaView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 555–563https://doi.org/10.1145/302405.302691Published:16 May 1999 116citation2,631DownloadsMetricsTotal Citations116Total Downloads2,631Last 12 Months30Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Software architecture visualization tools tend to support browsing, that is, exploration by following concepts. If architectural diagrams are to be used during daily software maintenance tasks, these tools also need to support specific fact-finding through searching. Searching is essential to program comprehension and hypothesis testing. Furthermore, searching allows users to reverse the abstractions in architectural diagrams and access facts in the underlying program code. We consider the problem of searching and browsing software architectures using perspectives from information retrieval and program comprehension. After analyzing our own user studies and results from the literature, we propose a solution: the Searchable Bookshelf, an architecture visualization tool that supports both navigation styles. We also present a prototype of our tool which is an extension of an existing architecture visualization tool.

Joining a software development team is like moving to a new country to start employment; the immigrant has a lot to learn about the job, the local customs, and sometimes a new language. In an exploratory case study, we interviewed four software immigrants, in order to characterize their naturalization process. Seven patterns in four major categories were found. In this paper, these patterns are substantiated, and their implications discussed. The lessons learned from this study can be applied equally to improving the naturalization process, and to the formulation of further research questions.

An important product of the software design phase is the specification of the software structure at various levels of detail. Without reliable design documentation, significant software systems become less accessible to software engineers because structural information is buried in the intricate implementation source code. Reverse engineering techniques aim at recovering the structure of software systems, from the source code and mental models of developers, in order to make these systems more understandable to those maintaining them. Many reverse engineering techniques rely on creating a decomposition hierarchy by recursively clustering related software components (e.g., variables, procedures, classes, modules) into composite components (e.g., subsystems). Component clustering is necessary for managing complexity, and therefore is an important step in the reverse engineering process. We argue that the clustering of interconnections is also necessary during reverse engineering, We propose an approach, based on a formalism called tube graphs, to specifying system structure that considers both composite software components and composite interconnections between these components. We present efficient algorithms for software interconnection clustering, which nicely complement existing software component clustering algorithms.

There have been many systems developed that attempt to recover design and structure from code. We present our experience with using one such tool, SoFi, to extract design structure from a large industrial system written in C. We compare the extracted structure to that which was intended by the designers of the system. We observe and categorize, for our system, the reasons why these two views differ. We observe that seemingly minor decisions in implementation, can have a large impact an the extracted design, and draw some conclusions about the practicality of trying to recover "intended designs" from source code.

Object-oriented programming was introduced in the 1980s and is now being used extensively in industry, but academia has not generally included it as a main stream topic for instruction. Part of the difficulty is the lack of good software to support teaching of object orientation. This paper describes an approach that teaches OO concepts across the Computer Science undergraduate curriculum, beginning in the introductory course, using the Object-Oriented Turing system.

No abstract available.

There are a number of programming languages and tools available to educators for teaching programming to un- dergraduate computer science students.Although efforts have been made to integrate these languages and tools into programming environments, these environments generally do not have all of the ingredients that would make them useful at all levels of a typical undergraduate curriculum.Current technology used in most undergraduate courses is suitable for teaching students how to code in a particular programming language.Software development tools for activities other than coding such as requirements analysis, design, maintenance, and so on, are not provided.In addition, most programming languages in current use cannot be used in both beginner and advanced courses.We describe a "curriculum-cycle" environment for teaching programming, called Object-Oriented Turing (OOT), and elaborate on the pedagogical experience of using 00T at all levels of our university's undergraduate curriculum.

A set of language-independent schedulability analysis techniques is presented. Utilizing knowledge of implementation- and hardware-dependent information in a table-driven fashion, these techniques provide accurate worst-case time bounds and other schedulability information. A prototype schedulability analyzer has been developed to demonstrate the effectiveness of these techniques. The analyzer consists of a partially language-dependent front-end, targeted at real-time Euclid, a real-time language specifically designed with a set of schedulability analysis provisions built-in, and a language-dependent back-end. The analyzer has been used on a number of realistic real-time programs run on a multiple-microprocessor system. Predicted program performance differs only marginally from the actual performance.>

Abstract This paper describes a new systematic approach to code generation. The approach is based on an orthogonal model, in which implementation of language‐level operators (‘operators’) and addressing operators (‘operands’) is achieved by two independent subtasks. Each of these phases is specified using a set of decision trees that encode the set of possible implementation templates for each language feature and the set of constraints under which each can be applied. Code selection in each phase is achieved by interpreting these trees using a single comprehensive selection algorithm. The method easily extends to machine independence across a large class of target computers by abstracting the implementation templates into machine‐independent implementation strategies. The selection algorithm is then modified to select between implementation strategies based on a machine capability ‘menu’ that describes each target machine in terms of the subset of implementation strategies for which it has corresponding instruction sequences. The method has been used to implement a prototype machine‐independent code generator for the Concurrent Euclid programming language whose generated code density is consistently within four per cent of production machine‐dependent code generators across its entire target class of five modern computers.

The trusted computing base (TCB) of a secure operating system can have its security policy enforced by a small, provably correct security manager. The design of the Secure TUNIS (Toronto University system) operating system divides security concerns into policy (implemented by its security manager) and mechanism (implemented by the rest of the operating system). It is shown that this separation is a key concept in allowing Secure TUNIS to be validated, due to the isolation of security critical code and data in a small module. This design provides the basis of an implementation of a POSIX (Unix) kernel that can be certified at security levels of B3 and above. The security policy, as implemented by Secure TUNIS, is given.>

Data descriptors, which have evolved from Wilcox's value descriptors [16], are a notation for representing run-time data objects at compile time. One of the principal reasons for developing this notation was to aid in the rapid construction of code generators, especially for new microprocessors. Each data descriptor contains a base, a displacement, and a level of indirection. For example, a variable x lying at displacement 28 from base register B3 is represented by this data descriptor: @B3.28. The general form of a data descriptor is @ k b.d.i where k gives the number of levels of indirection, b is a base, d is a displacement, and I is an index. Data descriptors are convenient for representing addressing in Fortran (with static allocation and common blocks), in Pascal and Turing (with automatic allocation and stack frames), and in more general languages such as Euclid and PL/I. This generality of data descriptors allows code generation to be largely independent of the source language. Data descriptors are able to encode the addressing modes of typical computer architectures such as the IBM 360 and the PDP-11. This generality of data descriptors allows code generation to be largely machine independent. This paper gives a machine independent method of storage allocation that uses data descriptors. Techniques are given for local optimization of basic arithmetic and addressing code using data descriptors. Target machine dependencies are isolated so that the part of the code generator that handles high-level addressing (such as subscripting) is machine independent. The techniques described in this paper have proven effective in the rapid development of a number of production code generators.

Abstract This paper presents a syntax‐directed editor dubbed SRE, for syntax recognizing editor. Unlike other syntax‐directed editors, SRE enables the user to edit programs with nearly the same natural and unrestrictive ease as a conventional text editor. In addition, it helps identify syntax errors and many typing errors before leaving the editor and attempting to compile a program. Programs are also formatted during entry, thereby providing immediate visual feedback of the recognized structure. The editor replaces the scanner/parser pass of a conventional compiler and thus reduces compilation time substantially.

S/SL (Syntax/Semantic Language) is a language that was developed for implementing compilers.A subset called SL (Syntax Language) has the same recognition power as do LR(k) parsers.Complete S/SL includes invocation of semantic operations implemented in another language such as PASCAL.S/SL implies a top-down programming methodology.First, a data-free algorithm is developed in S/SL.The algorithm invokes operations on "semantic mechanisms."A semantic mechanism is an abstract object, specified, from the point of view of the S/SL, only by the effect of operations upon the object.Later, the mechanisms are implemented apart from the S/SL program.The separation of the algorithm from the data and the division of data into mechanisms reduce the effort needed to understand and maintain the resulting software.S/SL has been used to construct compilers for SPECKLE (a PL/I subset), PT (a PASCAL subset), Toronto EUCLID, and Concurrent EUCLID.It has been used to implement scanners, parsers, semantic analyzers, and code generators.S/SL programs are implemented by translating them into tables of integers.A "table walker" program executes the S/SL program by interpreting this table.The translation of S/SL programs into tables is performed by a program called the S/SL processor.This processor serves a function analogous to that served by an LR(k) parser generator.The implementation of S/SL is simple and portable.It is available in a small subset of PASCAL that can easily be transliterated into other high-level languages.

article Free Access Share on A Model for Implementing EUCLID Modules and Prototypes Authors: Richard C. Holt Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada M5S 1A1 Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada M5S 1A1View Profile , David B. Wortman Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada M5S 1A1 Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada M5S 1A1View Profile Authors Info & Claims ACM Transactions on Programming Languages and SystemsVolume 4Issue 4Oct. 1982 pp 552–562https://doi.org/10.1145/69622.357183Published:01 October 1982Publication History 5citation236DownloadsMetricsTotal Citations5Total Downloads236Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper gives a brief introduction to a sequence of subsets of the PL/I language that has been designed for the purpose of teaching introductory computer, programming.The six subsets, called SP/I, SP/2, ..., SP/6, restrict PL/I to language features which the authors feel encourage good programming habits.Each subset introduces new language features while retaining features introduced in earlier subsets.

First, a “meta theory” of computer systems is developed so that the terms “process” and “deadlock” can be defined. Next, “reusable resources” are introduced to model objects which are shared among processes, and “consumable resources” are introduced to model signals or messages passed among processes. Then a simple graph model of computer systems is developed, and its deadlock properties are investigated. This graph model is useful for teaching purposes, unifies a number of previous results, and leads to efficient deadlock detection and prevention algorithms.