The goal of program analysis is to determine automatically properties of the run-time behavior of a program. Tools of software development, such as compilers, program-verification systems, and program-comprehension systems, are in large part based on program analyses. Most semantics-based program analyses model the run-time behavior of a program as a trace of execution states and compute a property of these states. Typically, this property is drawn from a predetermined language of semantic information, such as aliasing descriptions or types of values. The standard methodology of program analysis is to construct the property as a fixed point, a single execution step at a time. I explain that these ubiquitous methodological choices -- the a priori choice of the describable program properties and the single-step construction of these properties -- have some fundamental limitations and can result in poor precision.
In this talk, I present a different approach to semantics-based program analysis. My methodology is based on transfer relations that precisely describe the changes between the state of memory one point during execution and the state of memory at some later point in the execution. I isolate a language TR of concise computer-representable presentations of transfer relations. I also give an algorithm © that, given two transfer relations from TR, symbolically constructs a third transfer relation in TR that is semantically equivalent to their relational composition. An analysis designer begins by describing the operational semantics of a source language as a set of TR-terms that precisely describe the atomic steps of execution. Then an analysis algorithm repeatedly applies © to build a precise run-time description of any finite control path of interest.
I show that TR is expressive enough to describe a wide variety of source-language features, including heap-allocated mutable data structures, arrays, pointers, and first-class functions. I then explain how my analysis methodology overcomes some current limitations of program analysis. The transfer relations themselves are relational program properties that would be difficult or impossible to formulate with classical approaches to program analysis. Furthermore, the classical limitation of program analysis to build a property a single execution step at a time can result in dramatic loss of precision, but this may be overcome by using © to compose multiple steps before applying a classical analysis. Also, it is possible to compute some precise properties of loops symbolically, avoiding the inevitable imprecision of a fixed-point computation.
In a concurrent object-oriented environment, objects interact through sending and receiving messages. A race occurs when a target object is presented with multiple requests competing for selection. This talk addresses two types of such races and a mechanism required to enable the object to make intelligent decisions in managing pending requests. The proposed concurrency constructs serve to illustrate how to formulate scheduling policies that are both adaptive and reusable. An adaptive scheduling policy enables an object to select requests based on some pre-defined preference information and possibly feedback from the environment. A reusable scheduling policy promotes code reuse in designing new objects.
Another critical issue in a concurrent programming environment is scheduling control. In a real-time system, the scheduler need be preemptive and priority driven in order to react to the real-time system's highly dynamic and adaptive nature. We have extended the capsule construct in such a way that programmers can specify the priority (preference) order among the operations of a object. Thus, when multiple operations executed by a client object are competing for execution inside the object, a predictable result can be guaranteed. We call the enhanced capsule a DPC-capsule (Dynamic Preference Control-capsule), because the scheduling control, specified in the new construct, is decided at run time.
Conventional compilers are usually targeted for a specific language and machine and are based on features specific to these targets. Though the sources and the targets of these compilers are well understood they are not defined as mathematical objects, rather they are specified as high-level language notations of the computations carried out by the target machine. Consequently the compiler is not based on a mathematical relationship between its source and target and therefore the correctness proof of the compiler cannot be formally established. The language specification mechanisms used by the compiler freezes the notation one can use for program development while problem domain is a dynamic, evolving area of endeavor. This increases the language proliferation which in turn makes program development a task more difficult than necessary. The sequential Von Neumann heritage of the computations expressed by conventional languages and processed by compilers is challenged by the recent high performance computing systems and shows the need for developing new paradigms for language and compiler specification.
This paper brings a contribution towards an algebraic alternative for language design and compiler construction whose fundamental principles are: (1) decomposition of programming languages into simpler components, (2) development of machine independent specification and implementation tools for each language component, and (3) mathematical integration of language component processing algorithms into an algebraic compiler. Here we address the machine-independent semantic specification of programming language constructs and its processing by an algebraic compiler. For this purpose, we classify the language constructs used to express computations following the model of lambda calculus and develop three groups of construct specification rules:
In this paper we use transition systems to develop formal definitions of the machine independent semantics of language constructs specified by these rules. In addition, we demonstrate the implementation of the component of an algebraic compiler which performs a complete syntax and semantic analysis of a source language program. The data structure constructed by this component paired with the target image specification of the constructs handled by this system is used to generate target code. Examples of language specification and processing using constructs of conventional programming languages are given.
Though Java was originally designed for embedded systems applications, Java lacks support for real-time programming. This talk describes a set of standard extensions to Java that enable development of portable real-time software components using Java-related technologies. These standard extensions, which are currently under development at NewMonics, are being marketed under the PERC name.
Design patterns are distilled from many real systems to catalog common programming practice. However, some object-oriented design patterns are distorted or overly complicated because of the lack of supporting programming language constructs or mechanisms. We have analyzed several published design patterns looking for idiomatic ways of working around constraints of the implementation language. Based on this analysis, we present a set of general-purpose language constructs and mechanisms that, if provided by a statically typed, object-oriented language, would better support the implementation of design patterns and, transitively, benefit the construction of many real systems. In particular, our catalog of language constructs include subtyping separate from inheritance, lexically scoped closure objects independent of classes, and multimethod dispatch. The proposed constructs and mechanisms are not radically new, but rather are adopted from a variety of languages and programming language research and combined in a new, orthogonal manner. We are currently working on designing the language Brew based on the proposed object model on top of core Java.
Many parallel computing systems allow processors to communicate with each other by loading and storing objects in a distributed shared memory (DSM). However, to achieve reasonable efficiency, these DSM schemes generally compromise the coherence of shared objects. The result is that the programming model treats shared objects very differently from local objects.
In this presentation, we discuss how C++ templates can be used to extend the C++ type system with arbitrary shared object types so that the only programmer-visible distinction between manipulation of shared and local objects is their declared types. The efficiency of these templates is evaluated using the replicated shared memory (RSM) mechanism provided by workstation clusters using PAPERS (http://garage.ecn.purdue.edu/~papers/ ).
PSL is a new presentation specification language for structured documents. It is the first such language that is fully configurable and it is also extensible. PSL is able to support a very general form of out-of-order layout without having to provide a general system of tree transformations. PSL also makes an explicit distinction between the specified layout of the elements of a document and the actual layout that results from the formatting process. PSL's syntax and semantics are simple and general.
This talk describes the syntax and semantics of PSL using a simple text document as a running example and compares PSL to a number of other presentation specification languages.
The Worldwide Web, originally a simple mechanism for hypertext document distribution, is rapidly becoming a standard infrastructure for complex interactive services. The ubiquity of the hypertext metaphor and browser technology make a web interface attractive for a variety of business uses: ``intranet'' applications for internal processes (such as project management); ``internet'' applications that provide services to external customers (such as personal communications management) or customer care (such as ordering and trouble reporting); and software bundled with products (such as equipment management interfaces).
These applications may involve complex transactions requiring persistent server-side information, coordination of multiple participants, and the need to accommodate access via multiple media (e.g., Web browser, phone, email). The software problems arising from these requirements typically are addressed by an ad-hoc mix of software tools that are not necessarily well suited to the application domain. As a result, these services are difficult to develop, even harder to maintain and modify, and tend to scale poorly---familiar problems of large-scale software engineering.
MAWL is an application-oriented language and compiler designed to produce complex web services. The design of the MAWL system draws on the principles of application language engineering to facilitate not just service creation but the entire software development lifecycle. MAWL improves a service provider's ability to develop, analyze, monitor, administer, and modify web services.
The core of a MAWL service is a centralized service logic, written in a language specifically designed to express flow of control, management of state (including that of concurrent user sessions that share data), and the content of information flow between server and client. The presentation details of the client interactions are encapsulated in pages written in an extended dialect of HTML that allows dynamic customization of their content. Presentation details irrelevant to service logic are specified separately, allowing developers with different skills to work on disjoint aspects of the service. Furthermore, this separation enables the compiler to produce different implementations of the same service logic.
MAWL also provides new functionality to web services by allowing the integration of alternative user interfaces. The Phone Markup Language (PML) is a dialect of HTML specialized to describe content for interpretation over a telephone. We have developed a platform that allows PML documents to be served over a telephone by special purpose audio browsers; as in the hypertext model, the documents themselves may reside on any web server in the network, or may be dynamically generated by server scripts. The current platform supports the functionality necessary for simple voice response services and call processing.
The combination of MAWL and PML permits the creation of services that the user can access via web browser or telephone. The ability to create such services in a single environment appears to be unique.
A path profile determines how many times each acyclic path in a routine executes. This type of profiling subsumes the more common basic block and edge profiling, which only approximate path frequencies. Path profiles have many potential uses in program performance tuning, profile-directed compilation, and software test coverage.
This paper describes a new algorithm for path profiling. This simple, fast algorithm selects and places profile instrumentation to minimize run-time overhead. Instrumented programs run with overhead comparable to the best previous profiling techniques. On the SPEC95 benchmarks, path profiling overhead averaged 31%, as compared to 16% for efficient edge profiling. Path profiling also identifies longer paths than a previous technique, which predicted paths from edge profiles (average of 88, versus 34 instructions). Moreover, profiling shows that the SPEC95 train input datasets covered most of the paths executed in the ref datasets.
Paths through graphs are a very basic way of describing the dynamic behavior of software systems. A path profile contains a set of dynamic paths from one or more executions of a program or system. Two other talks in this workshop discuss systems that generate path profiles:
PathView is a java applet that supports analysis of path profiles. PathView enables analysis of the paths in conjunction with other node and edge-based statistics. PathView uses multiple views to allow exploration of different aspects of path data: a path viewer shows a set of paths; a bar chart view shows distributions of discrete data; a histogram view shows distributions of continuous data; a table viewer shows relational data. The views are linked so that selection in one view is reflected in the other views, providing a dynamic querying capability. PathView uses an extensible relational interface for data, so new sources of data can easily be incorporated.
We have used PathView to analyze service logs generated by the MAWL system, as well path profile data of SPEC95 benchmarks generated by PP. I will illustrate PathView with a MAWL service called the LunchBot, a service for ordering take-out lunch, and several of the SPEC95 benchmarks.