bluuebunny/crossref_metadata_2025 huggingface dataset:
Supporting ada memory management in the iAPX-432
Authors: Pollack Fred J. , Cox George W. , Hammerstrom Dan W. , Kahn Kevin C. , Lai Konrad K. , Rattner Justin R.
Published: November 2005

In this paper, we describe how the memory management mechanisms of the Intel iAPX-432 are used to implement the visibility rules of Ada. At any point in the execution of an Ada® program on the 432, the program has a protected address space that corresponds exactly to the program's accessibility at the corresponding point in the program's source. This close match of architecture and language did not occur because the 432 was designed to execute Ada—it was not. Rather, both Ada and the 432 are the result of very similar design goals.

To illustrate this point, we compare, in their support for Ada, the memory management mechanisms of the 432 to those of traditional computers. The most notable differences occur in heap-space management and multitasking. With respect to the former, we describe a degree of hardware/software cooperation that is not typical of other systems. In the latter area, we show how Ada's view of sharing is the same as the 432, but differs totally from the sharing permitted by traditional systems. A description of these differences provide some insight into the problems of implementing an Ada compiler for a traditional architecture.
Some requirements for architectural support of software debugging
Authors: Johnson Mark Scott
Published: November 2005

Architectural support of high-level, symbolic debugging is described at three levels of abstraction: the user's view of desired debugging functionality, the debugger implementor's view of architectural requirements that support the functionality, and the computer architect's view of architectural features or attributes that implement the requirements. References are made where possible to computing systems that meet the requirements. The paper is written from the viewpoint of debugger implementors, and is addressed primarily to computer architects.
The effect of the PDP-11 architecture on code generation for chill
Authors: Middelburg C. A.
Published: November 2005

This paper outlines the implementation of the CCITT*) high level programming language CHILL on PDP-11 computers in the CHILL compiler constructed at the Dr. Neher Laboratories. The characteristics and structure of the compiler are briefly described. The relationship between the PDP-11 architecture and the implementation of CHILL is outlined in more detail.
A case study of VAX-11 instruction set usage for compiler execution
Authors: Wiecek Cheryl A.
Published: November 2005

Analysis of an instruction set as large and varied as the one specified for the VAX-11 architecture is important for aiding processor design evaluation. This paper looks at dynamic VAX-11 instruction set usage by one class of programs, and discusses the methodology and tools which have been developed to provide that information. Six VAX/VMS native mode compilers from Digital Equipment Corporation were used: BASIC, BLISS, COBOL, FORTRAN, PASCAL, and PL/I. A summary of results generated by analyzing executions of these six compilers is presented. Information is included for instruction and class frequency, general instruction features, operand specifiers, the memory data stream, register utilization, instruction sequencing, and branch displacements.
An overview of Knowledge Representation
Authors: Mylopoulos John
Published: November 2005

This is a brief overview of terminology and issues related to Knowledge Representation (here-after KR) research, intended primarily for researchers working on Semantic Data Models within Database Management and Program Specifications within Programming Languages/Software Engineering.

Knowledge Representation is a central problem in Artificial Intelligence (AI) today. Its importance stems from the fact that the current design paradigm for “intelligent” systems stresses the need for expert knowledge in the system along with associated knowledge-handling facilities. This paradigm is in sharp contrast to earlier ones which might be termed “power-oriented” [Goldstein and Papert 77] in that they placed an emphasis on general purpose heuristic search techniques [Nilsson 71].
Abstraction in databases
Authors: McLeod Dennis , Smith John Miles
Published: November 2005

This paper surveys current research and practice concerning abstraction in database systems. Classical and semantic database models are reviewed and emphasized, as fundamental database abstraction mechanisms.
Data abstraction from a programming language viewpoint
Authors: Rowe Lawrence A.
Published: November 2005

This paper traces the development of data abstraction concepts in programming languages. A data abstraction, or abstract data type, describes a collection of abstract entities and operations on the entities. A program which uses a data abstraction can access or modify the entities only through the abstract operations.

Specific research topics discussed in the paper include: the role of type in a programming language, the formal specification of the semantics of a data abstraction, data abstraction language construct design issues, type hierarchies, and type-checking.
Integration of data base design in programming languages
Authors: Amble Tore
Published: November 2005

In 1978, the ASTRA research group at the University of Trondheim was formed to create a prototype of a relational data base machine with appropriate software. A major part of this development was the definition and implementation of an integrated data definition and manipulation language ASTRAL (1).
Data and activities
Authors: Borgida Alexander T. , Greenspan Sol
Published: November 2005

We wish to briefly discuss recent work in conceptual modelling from a slightly different point of view in order to highlight the parallels between data and transactions, and then mention some benefits of this view.

A time-honoured way of describing a system (portion of the world) is by positing a domain of objects and then inter-relating them through function and predicate symbols. The resulting description is a set of axioms in a FOPC. If the world is dynamic, one usually augments the description with the notion of time or state, in which case axioms can be divided naturally into “general laws” (heretofore
constraints
) holding in all states, and state-specific “facts”. Given states, one then also has the ability to describe state transitions (
events
) as predicates on pairs of states or, as shown below, as objects in their own right.
Some contrasts and considerations of an approach to modelling
Authors: Feather Martin S.
Published: November 2005

We consider the approach to modelling that our group has been developing, first to highlight differences between this and the approaches of other researchers, second to raise some issues related to understandability of models that we feel are common to modelling in general. The principles underlying our approach may be found in Balzer's position paper to this workshop.
Integrating a network-structured database into an object-oriented programming language
Authors: Goldstein Ira
Published: November 2005

Smalltalk is an object-oriented language (Ingalls78, KayGoldberg77, Hewitt73). PIE is a subsystem that extends Smalltalk's descriptive power by supporting the creation, storage, retrieval and manipulation of network structures (GoldsteinBobrow80a,b,c; BobrowGoldstein80). These networks have been employed to represent software, documentation, electronic mail, calendars, people, addresses, bibliographic references and other items that together comprise the personal information space of a user of an office information system. By employing a common network representation, PIE supports an integrated environment for software development and office-related tasks. PIE has been developed collaboratively with Dan Bobrow, and is presently being used on an experimental basis by a small community at Xerox PARC.

Smalltalk represents entities in the external world as objects. An object has a state—i.e. an assignment of values to a set of state variables—and a class. The class of an object defines the behavior of the object in terms of a set of methods. Thus the class is a generic description of a collection of objects, while the objects associated with a class provide a particular description of the state of individual instances.
A logical view of types
Authors: Hayes Patrick J. , Hendrix Gary G.
Published: November 2005

People working in the areas of data abstraction, databases, and conceptual modeling have argued at considerable length over the meanings of such terms as “abstraction” and “type.”* Rather than add to this debate by offering yet another set of definitions, in the paragraphs below we shall attempt to show how ordinary predicate calculus can be used to talk about most (perhaps all) the notions for which the terms “abstraction” and “type” are currently being used in various quarters of computer science. We do not intend to argue that predicate calculus is a suitable tool for implementing types, but rather that it provides a well-understood, uniform conceptual framework and notation for describing and precisely comparing various ideas on typing—and that special notations developed for this purpose are therefore unnecessary.
Mediating the views of databases and database users
Authors: Hendrix Gary G.
Published: November 2005

The Natural-Language/Deduction group at SRI International has undertaken several large projects integrating knowledge representation, the modeling and use of distributed conventional databases, logical deduction, and natural-language processing. One of the largest projects, LADDER [2], involved accessing data distributed over a computer network by using queries expressed in English. Work with LADDER (and several similar systems) has revealed that:

(1) Users wish to talk about data in terms of the enterprise in which the data are to be used. Users do not confine their questions to concepts and terminology covered by the database per se.

(2) Users are seldom satisfied with access only to the data in a database. They need to know the KIND of data available (i.e., they want to ask questions about the DB schema), and they expect systems to include information that can be computed from “common knowledge” and information stored explicitly in the database (e.g., if a database records where two ships are, users expect the system to know the distance between them).

(3) Users are not satisfied with access to an existing database. They want to tell the system new facts. Some of these are not suitable for storage in conventional databases (e.g., statements involving quantification), and some involve counter factuals (e.g., “Suppose the ship were 100 miles south of its current location...”).

(4) Given natural-language access to a DBMS, users expect to interact in natural language with other types of software, too. Moreover, they expect the various underlying software packages to understand one another's results (e.g., User: “Who is the commander of the ship?” System: “Admiral Brown.” User: “Send him a copy of Smith's memo.” The mailer is expected to understand the output from the database).
Heterogeneous databases and high level abstraction
Authors: Katz Randy H.
Published: November 2005

A heterogeneous database management system combines multiple dissimilar models of data within a single integrated system. The objective is to allow a user to access data independently of how it is actually organized. For example, a user may access a database as though it were stored relationally (i.e., in tables) [CODD70], even though it is actually stored as a CODASYL/DBTG or network database [CODA71]. In addition, different subpieces of the database may be organized under different data models. The heterogeneous database system must present these to the user as an integrated whole. The user's model of his data may be different from any of the models chosen to implement it.

Rather than construct a new database system from scratch, we are interested in constructing a heterogeneous system out of existing systems. The key difficulties with this approach are: (1) the formulation of database design methods that are applicable to a variety of different data models, and (2) the development of techniques to translate programs and data between dissimilar data models. In this paper, we briefly describe how high level abstraction has been applied to these problems. The use of abstraction in database systems is related to the application of abstraction techniques in programming languages and artificial intelligence research.
Axiomatic information modeling
Authors: Lundberg Bengt , Bubenko Janis A
Published: November 2005

The obvious task in information modeling is to arrive at a model which is correct. However, the concept of correctness has many faces e g the model must correctly reflect the properties of the application at hand, and it must adequately select relevant parts of the application. The former case requires that the information model is “satisfied by the application”. The latter case is dependent on the intended use of the model. The problem of satisfyability is, in most information modeling approaches, considered to be an intuitive task. From logic we know that a theory, here seen as an information model, can only be satisfied if it is consistent. Thus, by applying predicate logic to information modeling, we should have a possibility of checking the satisfyability of an information model. However, in order to ensure that the information model is satisfied by the application in mind, requires an intuitive reasoning.

Consequently, our plans include to further elaborate the use of predicate logic in information modeling. It furthermore includes a study of possibilities and limitations of such an approach. The results obtained so far will be shortly reviewed in the following.
Use of database organization in the Consul system
Authors: Mark William
Published: November 2005

A fundamental aspect of the Consul system is the way the organization of the database defines the system's operation and unifies its components. Accessing and maintaining the database is the focus of all system activities, from parsing English to executing programs.
On conceptual database modelling
Authors: McLeod Dennis
Published: November 2005

This research was supported, in part, by the Joint Services Electronics Program through the Air Force Office of Scientific research under contract F44620-76-C-0061.
Data bases
Authors: Reiter Raymond
Published: November 2005

My work in data base theory is a natural outgrowth of my longstanding concern with the problem of representing and reasoning with domain specific knowledge, a problem of major concern in Artificial Intelligence. In data base terminology this is the conceptual modelling issue. My own methodological bias favours logic as a representation language for conceptual modelling, a bias which historically arose within AI in response to AI's emphasis on the ability to reason deductively with representations. In this position paper I shall argue that logic has other advantages for data base theory. Specifically my objective is to provide the outline of a logical reconstruction of certain aspects of conventional data base theory.
Multiple points of view in modelling programs
Authors: Rich Charles
Published: November 2005

An important issue discussed at the workshop on data abstraction is the need to represent multiple, overlapping points of view and relationships between them. The first two sections of this paper motivate the use of multiple and overlapping points of view in modelling programs and data structures. The final section of the paper briefly describes a new formalism, called

overlays

, which has been developed for this purpose, and which may be of general interest.

The overall goal of the research from which this paper is drawn is to compile a

library

of standard, generally used data and control abstractions to be used in the interactive analysis, synthesis and verification of programs. Multiple points of view were needed in this context is in order to decompose the data and control structures of users' programs in a way which makes explicit their relationship to the library of standard abstractions.
A conceptual schema for Knowledge-based systems
Authors: Sowa John F.
Published: November 2005

Knowledge-based systems are data bases with more powerful front ends for dealing with the meaning of data. This paper discusses requirements for a conceptual schema that is general enough to support knowledge bases as well as ordinary data bases. It presents seven features that such a schema must support and evaluates various approaches to data base semantics in terms of them. The AI notations for semantic networks or conceptual graphs are highly general ones that can support all seven features.
The extension of data abstraction to database management
Authors: Wasserman Anthony I.
Published: November 2005

The long-term goal of the User Software Engineering (USE) project at the University of California, San Francisco, is to provide an integrated homogeneous programming environment for the design and development of interactive information systems. Realization of this goal involves the development of new software tools, their integration with existing tools, and the creation of an information system development methodology in which these tools are systematically used [1,2].

The successful construction of interactive information systems requires the utilization of principles of user-centered design [3,4,5], combined with features traditionally associated with the separate areas of programming languages, operating systems, and data base management [6]. It has become increasingly clear that the key to being able to provide such a unified view lies in providing a unified view of data [7]. The potential benefits of such a unification are considerable, including:

1) conceptual simplification of the system structure permitting, for example, joint design of data structures and data bases

2) the elimination of duplication or inconsistencies among diverse software components

3) the ability to achieve greater reliability in systems because of reduced dependence upon multiple software systems
Constructive Abstract Data types (CAD)
Authors: Wedekind Hartmut H.
Published: November 2005

1. Distinction from conventional approaches

The motivation for CAD is to extend the idea of data abstraction to application programming. Conventional approaches confine themselves to operational concepts of system programming like STACK, QUEUE etc. and do not consider concepts like CONTRACT, INVOICE etc. of the application world (AW) with an arbitrary number of operations applicable to them, including those of the ad hoc type.
Slicing and partial evaluation of CORBA component model designs for avionics system
Authors: Hatcliff John , Deng William , Dwyer Matthew B. , Jung Georg , Ranganath Venkatesh , Robby Robby
Published: November 2005

The use of component models such as Enterprise Java Beans and the CORBA Component Model (CCM) in application development is expanding rapidly. Even in real-time safety-critical and mission-critical domains, component-based development is beginning to take hold as a mechanism for in-corporating non-functional aspects such as real-time, quality-of-service, and distribution.
Storeless semantics and alias logic
Authors: Bozga Marius , Iosif Radu , Laknech Yassine
Published: November 2005

Pioneering work has been done by Jonkers [18] to define a semantics of pointer manipulating programs that is abstract in the sense of ignoring low-level aspects such as dangling pointers and garbage objects. We explore the principles of such storeless semantics from a logical point of view, first defining a simple logic to completely characterize heap structures up to isomorphism. Second, we extend this language to a full-blown alias logic (AL) that allows to express regular properties of unbounded heap structures. Along the development, we present an operational storeless semantics and give sound and complete total correctness axioms for deterministic programs in the form of Hoare triples, using AL.
Using thread-level speculation to simplify manual parallelization
Authors: Prabhu Manohar K. , Olukotun Kunle
Published: November 2005

In this paper, we provide examples of how thread-level speculation
(TLS) simplifies manual parallelization and enhances its
performance. A number of techniques for manual parallelization
using TLS are presented and results are provided that indicate the
performance contribution of each technique on seven SPEC CPU2000
benchmark applications. We also provide indications of the
programming effort required to parallelize each benchmark. TLS
parallelization yielded a 110% speedup on our four floating point
applications and a 70% speedup on our three integer applications,
while requiring only approximately 80 programmer hours and 150
lines of non-template code per application. These results support
the idea that manual parallelization using TLS is an efficient way
to extract fine-grain thread-level parallelism.
Automated application-level checkpointing of MPI programs
Authors: Bronevetsky Greg , Marques Daniel , Pingali Keshav , Stodghill Paul
Published: November 2005

The running times of many computational science applications, such as protein-folding using
ab initio
methods, are much longer than the mean-time-to-failure of high-performance computing platforms. To run to completion, therefore, these applications must tolerate hardware failures.In this paper, we focus on the stopping failure model in which a faulty process hangs and stops responding to the rest of the system. We argue that tolerating such faults is best done by an approach called application-level coordinated non-blocking checkpointing, and that existing fault-tolerance protocols in the literature are not suitable for implementing this approach.We then present a suitable protocol, which is implemented by a co-ordination layer that sits between the application program and the MPI library. We show how this protocol can be used with a precompiler that instruments C/MPI programs to save application and MPI library state. An advantage of our approach is that it is independent of the MPI implementation. We present experimental results that argue that the overhead of using our system can be small.
CC--MPI
Authors: Karwande Amit , Yuan Xin , Lowenthal David K.
Published: November 2005

Compiled communication
has recently been proposed to improve communication performance for clusters of workstations. The idea of compiled communication is to apply more aggressive optimizations to communications whose information is known at compile time. Existing MPI libraries do not support compiled communication. In this paper, we present an MPI prototype,
CC--MPI
, that supports compiled communication on Ethernet switched clusters. The unique feature of
CC--MPI
is that it allows the user to manage network resources such as multicast groups directly and to optimize communications based on the availability of the communication information.
CC--MPI
optimizes one--to--all, one--to--many, all--to--all, and many--to--many collective communication routines using the compiled communication technique. We describe the techniques used in
CC--MPI
and report its performance. The results show that communication performance of Ethernet switched clusters can be significantly improved through compiled communication.
Optimizing data aggregation for cluster-based internet services
Authors: Chu Lingkun , Tang Hong , Yang Tao , Shen Kai
Published: November 2005

Large-scale cluster-based Internet services often host partitioned datasets to provide incremental scalability. The aggregation of results produced from multiple partitions is a fundamental building block for the delivery of these services. This paper presents the design and implementation of a programming primitive -- Data Aggregation Call (DAC) -- to exploit partition parallelism for cluster-based Internet services. A DAC request specifies a local processing operator and a global reduction operator, and it aggregates the local processing results from participating nodes through the global reduction operator. Applications may allow a DAC request to return partial aggregation results as a tradeoff between quality and availability. Our architecture design aims at improving interactive responses with sustained throughput for typical cluster environments where platform heterogeneity and software/hardware failures are common. At the cluster level, our load-adaptive reduction tree construction algorithm balances processing and aggregation load across servers while exploiting partition parallelism. Inside each node, we employ an event-driven thread pool design that prevents slow nodes from adversely affecting system throughput under highly concurrent workload. We further devise a staged timeout scheme that eagerly prunes slow or unresponsive servers from the reduction tree to meet soft deadlines. We have used the DAC primitive to implement several applications: a search engine document retriever, a parallel protein sequence matcher, and an online parallel facial recognizer. Our experimental and simulation results validate the effectiveness of the proposed optimization techniques for reducing response time, improving throughput, and gracefully handling server unresponsiveness. We also demonstrate the ease-of use of the DAC primitive and the scalability of our architecture design.
The design and implementation of a parallel array operator for the arbitrary remapping of data
Authors: Deitz Steven J. , Chamberlain Bradford L. , Choi Sung-Eun , Snyder Lawrence
Published: November 2005

Gather and scatter are data redistribution functions of long-standing importance to high performance computing. In this paper, we present a highly-general array operator with powerful gather and scatter capabilities unmatched by other array languages. We discuss an efficient parallel implementation, introducing three new optimizations---schedule compression, dead array reuse, and direct communication---that reduce the costs associated with the operator's wide applicability. In our implementation of this operator in ZPL, we demonstrate performance comparable to the hand-coded Fortran + MPI versions of the NAS FT and CG benchmarks.
Efficient on-the-fly data race detection in multithreaded C++ programs
Authors: Pozniansky Eli , Schuster Assaf
Published: November 2005

Data race detection is highly essential for debugging multithreaded programs and assuring their correctness. Nevertheless, there is no single universal technique capable of handling the task efficiently, since the data race detection problem is computationally hard in the general case. Thus, to approximate the possible races in a program, all currently available tools take different ``short-cuts'', such as using strong assumptions on the program structure or applying various heuristics. When applied to some general case program, however, they usually result in excessive false alarms or in a large number of undetected races.Another major drawback of many currently available tools is that they are restricted, for performance reasons, to detection units of fixed size. Thus, they all suffer from the same problem---choosing a small unit might result in missing some of the data races, while choosing a large one might lead to false detection.In this paper we present a novel testing tool, called MultiRace, which combines improved versions of Djit and Lockset---two very powerful on-the-fly algorithms for dynamic detection of apparent data races. Both extended algorithms detect races in multithreaded programs that may execute on weak consistency systems, and may use two-way as well as global synchronization primitives.By employing novel technologies, MultiRace adjusts its detection to the native granularity of objects and variables in the program under examination. In order to monitor all accesses to each of the shared locations, MultiRace instruments the C++ source code of the program. It lets the user fine-tune the detection process, but otherwise is completely automatic and transparent.This paper describes the algorithms employed in MultiRace, discusses some of its implementation issues, and proposes several optimizations to it. The paper shows that the overheads imposed by MultiRace are often much smaller (orders of magnitude) than those obtained by other existing dynamic techniques.
Compactly representing parallel program executions
Authors: Goel Ankit , Roychoudhury Abhik , Mitra Tulika
Published: November 2005

Collecting a program's execution profile is important for many reasons: code optimization, memory layout, program debugging and program comprehension. Path based execution profiles are more detailed than count based execution profiles, since they present the
order
of execution of the various blocks in a program: modules, procedures, basic blocks etc. Recently, online string compression techniques have been employed for collecting compact representations of sequential program executions. In this paper, we show how a similar approach can be taken for shared memory parallel programs. Our compaction scheme yields one to two orders of magnitude compression compared to the uncompressed parallel program trace on some of the SPLASH benchmarks. Our compressed execution traces contain detailed information about synchronization and control/data flow which can be exploited for post-mortem analysis. In particular, information in our compact execution traces are useful for accurate data race detection (detecting unsynchronized shared variable accesses that occurred in the execution).
Java bytecode verification for secure information flow
Authors: Avvenuti Marco , Bernardeschi Cinzia , De Francesco Nicoletta
Published: November 2005

Security of Java programs is important as they can be executed in different platforms. This paper addresses the problem of secure information flow for Java bytecode. In information flow analysis one wishes to check if high security data can ever propagate to low security observers. We propose a static analysis similar to the type-level abstract interpretation used for standard bytecode verification. Instead of types, our technique works with secrecy levels assigned to classes, methods' parameters and returned values, and handles implicit information flows. A verification tool based on the proposed technique is under development. Using the tool, programs downloaded from untrusted hosts can be checked locally prior to executing them.
The ART of compiler construction projects
Authors: Aycock John
Published: November 2005

Student projects in compiler construction courses are often limited to the implementation of toy languages, making the project's scope manageable but also restricting the number of interesting input programs. ART (Array Removal Transformation) is a language whose compiler translates array-based ART programs into array-less toy language programs which use only simple (non-aggregate) types. This allows algorithms to be expressed in toy languages that would not otherwise be feasible.ART's translation process creates large input files to stress-test student compilers, which are often not subjected to such testing.
Beyond AOP
Authors: Lopes Cristina Videira , Dourish Paul , Lorenz David H. , Lieberherr Karl
Published: November 2005

Software understanding for documentation, maintenance or evolution is one of the longest-standing problems in Computer Science. The use of "high-level" programming paradigms and object-oriented languages helps, but fundamentally remains far from solving the problem. Most programming languages and systems have fallen prey to the assumption that they are supposed to capture idealized models of computation inspired by deceptively simple metaphors such as objects and mathematical functions. Aspect oriented programming languages have made a significant breakthrough by noticing that, in many situations, humans think and describe in crosscutting terms. In this paper we suggest that the next breakthrough would require looking even closer to the way humans have been thinking and describing complex systems for thousand of years using natural languages. While natural languages themselves are not appropriate for programming, they contain a number of elements that make descriptions concise, effective and understandable. In particular, natural languages referentiality is a key factor in supporting powerful program organizations that can be easier understood by humans.
Graphical specification of object oriented systems
Authors: Bear Stephen , Allen Phillip , Coleman Derek , Hayes Fiona
Published: November 2005

The graphical notation
Objectcharts,
introduced in this paper, allows a developer to precisely specify the behaviour of object classes and to reason about the behaviour of particular configurations of objects.

Objectcharts combine object oriented analysis and design techniques and Harel's statecharts to give a diagrammatic specification technique for object oriented systems.
Actors as a special case of concurrent constraint (logic) programming
Authors: Kahn K. , Saraswat Vijay A.
Published: November 2005

Saraswat recently introduced the framework of concurrent constraint programming [14]. The essence of the framework is that computations consist of concurrent agents interacting by communicating constraints. Several concurrent constraint programming languages have been defined. They differ in the kinds of constraints that can be used as well as the kinds of operations on constraints which are available. In this paper we introduce a very simple concurrent constraint language we call Lucy, designed to closely mimic the actor model of computation. Agents can communicate only by the posting of constraints upon bags (un-ordered collections possibly with duplicate elements). This very impoverished concurrent constraint language is a syntactic subset of Janus, a concurrent constraint language which closely resembles concurrent logic programming languages such as Guarded Horn Clauses [21], Strand [5], Parlog [2] and Flat Concurrent Prolog [13]. By identifying the subset of Janus which is an actor language, we elucidate the relationship between actors and concurrent logic programming (and its generalization as concurrent constraint programming). Lucy is best not thought of as a unification of logic and constraint programming with actor and object-oriented programming, but as the
missing link
between these programming language genera.
Beyond schema evolution to database reorganization
Authors: Lerner Barbara Staudt , Habermann A. Nico
Published: November 2005

While the contents of databases can be easily changed, their organization is typically extremely rigid. Some databases relax the rigidity of database organization somewhat by supporting simple changes to individual schemas. As described in this paper, OTGen supports not only more complex schema changes, but also database reorganization. A database administrator uses a declarative notation to describe mappings between objects created with old versions of schemas and their corresponding representations using new versions. OTGen generates a transformer that applies the mappings to update the database to the new definitions, thus facilitating improvements in performance, functionality, and usability of the database.
1
Kaleidoscope: mixing objects, constraints, and imperative programming
Authors: Freeman-Benson Bjorn N.
Published: November 2005

Kaleidoscope is an object-oriented language being designed to integrate the traditional
imperative
object-oriented paradigm with the less traditional
declarative
constraint paradigm. Imperative state changes provide sequencing while declarative constraints provide object relations. A
variables as streams
semantics enables the declarative-imperative integration. A running example is used to illustrate the language concepts—a reimplementation of the MacDraw II dashed-lines dialog box. The example is in three parts: the input channel, using imperative code to sequence through modes; the output channel, using constraints to update the display; and the internal relations, using constraints to maintain the data objects' consistency requirements. The last sections of the paper discuss
views
as a natural result of combining objects with constraints, as well as related and future work.
Message pattern specifications: a new technique for handling errors in parallel object oriented systems
Authors: Purchase Jan A. , Winder Russel L.
Published: November 2005

As object oriented techniques enable the fabrication of ever more sophisticated systems, the need grows for a mechanism to ensure the consistent and 'correct' behaviour of each object at run-time. We describe a new, in-source specification mechanism, Message Pattern Specifications (MPS), to directly satisfy this need in a succinct, orthogonal and disciplined manner. Targeted for use in parallel object oriented systems, MPS allows programmers to enunciate the 'legal' patterns of run-time behaviour in which their objects may engage. Furthermore, it supports the definition of methods for object recovery or graceful failure in case these specifications are violated during execution.
Structured analysis and object oriented analysis
Authors: de Champeaux Dennis , Constantine Larry , Jacobson Ivar , Mellor Stephen , Ward Paul , Yourdon Edward
Published: November 2005

The object-oriented paradigm still faces an open challenge: Delivering huge software systems routinely and cost effectively. To quote Ed Yourdon: “A system composed of 100,000 lines of C++ is not be sneezed at, but we don't have that much trouble developing 100,000 lines of COBOL today. The real test of OOP will come when systems of 1 to 10 million lines of code are developed.”

Although the object-oriented community has an opening flirtation with exploratory programming and rapid prototyping by exploiting reuse via inheritance, there is for now, in my opinion, no hope that huge systems can be developed without giving due attention to what a target system is supposed to do. Which should produce an (electronic) (graphical) (Pseudo-formal) document, the requirements, that a customer can initially sign off. We believe as well that for huge systems a programming language independent design activity, that bridges the requirements and the actual programming effort, is mandatory. It goes without saying that we do not suggest that these activities constitute a waterfall sequence.

Consequently, the object-oriented community needs to address the question whether well established analysis techniques, like Structured Analysis, Jackson's JSD, etc. can be reused for object-oriented system development or whether a dedicated object-oriented analysis (and design) method is called for.

The panel members have been asked to consider the following of question: What is the relationship between Structured Analysis (SA) and Object Oriented Analysis (OOA)?

More specifically:

Can SA be used effectively to produce the requirements for a system that will be designed and implemented in an OO fashion?

If not, is it possible to adjust SA, what needs to be added? If SA cannot be used at all, what is the key obstacle?

In case SA and OOA have different applicability ranges, how do we circumscribe — positively and negatively - these ranges? Any overlap?

We appreciate that the organizing committee of this conference has selected this crucial topic.
Strong typing of object-oriented languages revisited
Authors: Madsen Ole Lehrmann , Magnusson Boris , Mølier-Pedersen Birger
Published: November 2005

This paper is concerned with the relation between
subtyping
and
subclassing
and their influence on programming language design. Traditionally subclassing as introduced by Simula has also been used for defining a hierarchical type system. The type system of a language can be characterized as
strong
or
weak
and the type checking mechanism as
static
or
dynamic
. Parameterized classes in combination with a hierarchical type-system is an example of a language construct that is known to create complicated type checking situations. In this paper these situations are analyzed and several different solutions are found. It is argued that an approach with a combination of static and dynamic type checking gives a reasonable balance also here. It is also concluded that this approach makes it possible to base the type system on the class/subclass mechanism.
COOL: kernel support for object-oriented environments
Authors: Habert Sabine , Mosseri Laurence
Published: November 2005

The Chorus Object-Oriented Layer (COOL) is an extension of the facilities provided by the Chorus distributed operating system with additional functionality for the support of object-oriented environments. This functionality is realized by a layer built on top of the Chorus V3 Nucleus, which extends the Chorus interface with generic functions for object management: creation, deletion, storage, remote invocation and migration. One major goal of this approach was to explore the feasibility of general object management at the kernel level, with support of multiple object models at a higher level. We present the implementation of COOL and a first evaluation of this approach with a C++ environment using the COOL mechanisms.
Generalized typestate checking using set interfaces and pluggable analyses
Authors: Lam Patrick , Kuncak Viktor , Rinard Martin
Published: November 2005

We present a generalization of standard typestate systems in which the typestate of each object is determined by its membership in a collection of abstract typestate sets. This generalization supports typestates that model participation in abstract data types, composite typestates that correspond to membership in multiple sets, and hierarchical typestates. Because membership in typestate sets corresponds directly to participation in data structures, our typestate system characterizes global sharing patterns.In our approach, each module encapsulates a data structure and uses membership in abstract sets to characterize how objects participate in its data structure. Each analysis verifies that the implementation of the module 1) preserves important internal data structure representation invariants and 2) conforms to a specification that uses formulas in a set algebra to characterize the effects of operations on the data structure. The analyses use the common set abstraction to 1) characterize how objects participate in multiple data structures and to 2) enable the inter-analysis communication required to verify properties that depend on multiple modules analyzed by different analyses.
Symbolic transfer function-based approaches to certified compilation
Authors: Rival Xavier
Published: November 2005

We present a framework for the certification of compilation and of compiled programs. Our approach uses a symbolic transfer functions-based representation of programs, so as to check that source and compiled programs present similar behaviors. This checking can be done either for a concrete semantic interpretation (Translation Validation) or for an abstract semantic interpretation (Invariant Translation) of the symbolic transfer functions. We propose to design a checking procedure at the concrete level in order to validate both the transformation and the translation of abstract invariants. The use of symbolic transfer functions makes possible a better treatment of compiler optimizations and is adapted to the checking of precise invariants at the assembly level. The approach proved successful in the implementation point of view, since it rendered the translation of very precise invariants on very large assembly programs feasible.
Semantic types
Authors: Vouillon Jerome , Melliès Paul-André
Published: November 2005

We present a generalization of the ideal model for recursive polymorphic types. Types are defined as sets of terms instead of sets of elements of a semantic domain. Our proof of the existence of types (computed by fixpoint of a typing operator) does not rely on metric properties, but on the fact that the identity is the limit of a sequence of projection terms. This establishes a connection with the work of Pitts on relational properties of domains. This also suggests that ideals are better understood as closed sets of terms defined by orthogonality with respect to a set of contexts.
Polymorphic typed defunctionalization
Authors: Pottier François , Gauthier Nadji
Published: November 2005

Defunctionalization
is a program transformation that aims to turn a higher-order functional program into a first-order one, that is, to eliminate the use of functions as first-class values. Its purpose is thus identical to that of
closure conversion
. It differs from closure conversion, however, by storing a
tag
, instead of a code pointer, within every closure. Defunctionalization has been used both as a reasoning tool and as a compilation technique.Defunctionalization is commonly defined and studied in the setting of a simply-typed λ-calculus, where it is shown that semantics and well-typedness are preserved. It has been observed that, in the setting of a polymorphic type system, such as ML or System F, defunctionalization is not type-preserving. In this paper, we show that extending System F with
guarded algebraic data types
allows recovering type preservation. This result allows adding defunctionalization to the toolbox of type-preserving compiler writers.
Free theorems in the presence of
seq
Authors: Johann Patricia , Voigtländer Janis
Published: November 2005

Parametric polymorphism constrains the behavior of pure functional programs in a way that allows the derivation of interesting theorems about them solely from their types, i.e., virtually for free. Unfortunately, the standard parametricity theorem fails for nonstrict languages supporting a polymorphic strict evaluation primitive like Haskell's
seq
. Contrary to the folklore surrounding
seq
and parametricity, we show that not even quantifying only over strict and bottom-reflecting relations in the $\forall$-clause of the underlying logical relation --- and thus restricting the choice of functions with which such relations are instantiated to obtain free theorems to strict and total ones --- is sufficient to recover from this failure. By addressing the subtle issues that arise when propagating up the type hierarchy restrictions imposed on a logical relation in order to accommodate the strictness primitive, we provide a parametricity theorem for the subset of Haskell corresponding to a Girard-Reynolds-style calculus with fixpoints, algebraic datatypes, and
seq
. A crucial ingredient of our approach is the use of an asymmetric logical relation, which leads to "inequational" versions of free theorems enriched by preconditions guaranteeing their validity in the described setting. Besides the potential to obtain corresponding preconditions for standard equational free theorems by combining some new inequational ones, the latter also have value in their own right, as is exemplified with a careful analysis of
seq
's impact on familiar program transformations.
Channel dependent types for higher-order mobile processes
Authors: Yoshida Nobuko
Published: November 2005

This paper introduces a new expressive theory of types for the higher-order π-calculus and demonstrates its applicability via two security analyses for higher-order code mobility. The new theory significantly improves our previous one presented in [55] by the use of
channel dependent/existential types
. New dependent types control dynamic change of process accessibility via channel passing, while existential types guarantee safe scope-extrusion in higher-order process passing. This solves an open issue in [55], leading to significant enlargement of original typability. The resulting typing system is coherently integrated with the linear/affine typing disciplines as well as state, concurrency and distribution [53, 5, 56, 22], allowing precise analysis of software behaviour with higher-order mobility. As illustration of the usage of the typed calculus, two basic security concerns for mobile computation, secrecy for data confidentiality and rôle-based access control for authorised resources, are analysed in a uniform type-based framework, leading to the noninterference theorem and authority-error freedom in the presence of higher-order code mobility.