The Intel i386 architecture and implementation options for Oberon on it

The design of programming languages has a long tradition at ETH Zürich. With the development of the extensible operating system Oberon [1] [2] for the personal work-station Ceres, a new programming language for its implementation came into being and was called Oberon as well. Building on the solid grounds of Modula-2, the programming language Oberon [3] [4] adds features to support object-oriented programming while dropping some of the less important constructs of its predecessor. Although the Oberon system and the language have been ported to several widely-used commercial platforms [5], a version for IBM PCs is still missing. To encourage the development of Oberon for PCs, we discuss the architecture of the Intel i386 [6], the requirements of Oberon, and different implementation options for Oberon on this processor.     

Type Theory and Language Constructs for Objects with States

In current class-based Object-Oriented Programming Languages (OOPLs), object types include only static features. How to add object dynamic behaviors modeled by Harel's statecharts into object types is a challenging task. We propose adding states and state transitions, which are largely unstated in object type theory, into object type definitions and typing rules. We argue that dynamic behaviors of objects should be part of object type definitions. We propose our type theory, the τ-calculus, which refines Abadi and Cardelli's ζ-calculus, in modeling objects with their dynamic behaviors. In our proposed type theory, we also explain that a subtyping relation between object types should imply the inclusion of their dynamic behaviors. By adding states and state transitions into object types, we propose modifying programming language constructs for state tracking.     

Using independence to enable parallelism on multicore computers

A simple programming abstraction based on the notion of independence is introduced as a means for mapping the independence inherent in an algorithm explicitly into its programmed solution. This enables a compiler and runtime system to exploit the independence and achieve efficient parallelism of execution on multicore processors. The constructs needed to express mutual independence among statements are proposed and their implementation in iOberon, an extension of the Active Oberon programming language, is defined. The programming language extensions, runtime support, and performance measurements are described in detail. We believe that this concept of specifying local disjoint program fragments can be applied to other programming languages. Copyright © 2010 John Wiley & Sons, Ltd.     

结合面向对象和函数式语言的概念

考虑了结合面向对象和函数式程序风范的问题.与这一方向的大多数方法相比,这种结合方法有下面两个优点：首先,结合了在广泛流行的几种主语言中非常有名的一些重要概念.换言之,没有引入新的语言概念并试图以新的概念为基础解释众所周知的语言概念.其次,这种结合具有下面的性质：如果整个语言以传统方式使用则不受个别的语言概念的影响,这样,只有在使用一个语言概念的时候才需要关注它.具体地说,提出了一个具有简明操作语言的用于函数式面向对象程序设计的核心语言,它具有如上所述的性质.这个核心语言结合了Eiffel, Java, ML和Haskell语言中的下列核心语言概念：对象,类,多重继承,方法重定义,动态绑定,静态类型安全性,二元方法,代数数据类型,高阶函数,ML-多态性.     

The Oberon System family

Oberon simultaneously refers to a moduar, extensible operating system and an object-oriented programming language developed for its implementation. Although the original Oberon System had been conceived as the native operating system for a custom-built workstation, furhter implementations for several commercial platforms were developed later and are described here. All of these implementations are based on an efficient, retargetable Oberon compiler, and each provides a complete Oberon environment and the original library interface. This paper describes the structure of the compiler, summarizes the experience gained in adapting it for various CISC and RISC processors, and presents some empirical performance data. It also sheds light on the task of grafting an operating environment onto a variety of existing operating systems.     

Static use-based object confinement

The confinement of object references is a significant security concern for modern programming languages. We define a language that serves as a uniform model for a variety of confined object reference systems. A use-based approach to confinement is adopted, which we argue is more expressive than previous communication-based approaches. We then develop a readable, expressive type system for static analysis of the language, along with a type safety result demonstrating that run-time checks can be eliminated. The language and type system thus serve as a reliable, declarative, and efficient foundation for secure capability-based programming and object confinement .     

Coverage and invariability by structural functions

Based on some of the results and definitions provided in the article System linkage: Structural functions and hierarchies (Lloret et al. “System linkage: structural functions and hierarchies”, Cybern. Syst. Int. J., 29, pp. 35–46, 1998) and adding new definitions that are in keeping with the spirit of the same article, new results have been obtained that explore the utility of the structural input–output function (also transferable to the other structural functions) and that expand on studies conducted to date on variables (cells).

Our approach is based principally on the application of graph theory to the study of relationships between variables (cells) using specific set theory concepts, introducing new definitions and adapting continuous function properties to our discrete environment. More specifically, we present two new concepts—coverage between sets and the invariant set—analysing their inter-relatedness from the perspective of structural functions, i.e. from the point of view of influences in the system. To date these concepts have been handled from a continuous point of view, and so the discrete approach described here will lay the foundations for new developments in this direction.

Although the development of the concepts may, a priori, appear to very theoretical, they are, in fact, much more practical than would appear to be the case. A result such as the fact that A covers B, for example, can be interpreted in terms of the latter set being formed of direct influences from elements in the former set in relation to one or more than one relationships. Analogously, the invariant set concept may be interpreted as the set maintaining its structure and status, remaining constant with respect to any possible relationships.     

Aspects as Modular Language Extensions

Extensible programming languages and their compilers use highly modular specifications of languages and language extensions that allow a variety of different language feature sets to be easily imported into the programming environment by the programmer. Our model of extensible languages is based on higher-order attribute grammars and an extension called “forwarding” that mimics a simple rewriting process. It is designed so that no additional attribute definitions need to be written when combining a language with language extensions. Thus, programmers can remain unaware of the underlying attribute grammars when building customized languages by importing various extensions. In this paper we show how aspects and the aspect weaving process from Aspect-Oriented Programming can be specified as a modular language extension and imported into a base language specified in an extensible programming language framework.     

From modula to oberon

The programming language Oberon is the result of a concentrated effort to increase the power of Modula-2 and simultaneously to reduce its complexity. Several features were eliminated, and a few were added in order to increase the expressive power and flexibility of the language. This paper describes and motivates the changes. The language is defined in a concise report¹.     

Static extensivity analysis for λ-definable functions over lattices

We employ a static analysis to examine the extensivity (∀x:x≤f(x)) of functions defined over lattices in a λ-calculus augmented with lattice operations. The need for such a verification procedure has arisen in our work on a generator system (called Zoo) of static program-analyzers. The input to Zoo is a static analysis specification that consists of lattice definitions and function definitions over the lattices. Once the extensivity of the functions is ascertained, the generated analyzer is guaranteed to terminate when the lattices have finite-heights. The extensivity analysis consists of a sound syntax-driven deductive rules whose satisfiability check is done by a constraint solving procedure. Hyunjun Eo: He is a Ph.D. candidate of Computer Science Dept. at KAIST (Korea Advanced Institute of Science and Technology). He received his B.S. and M.S. in Computer Science from KAIST in 1996 and 1998, respectively. For 1998–2003, he was a research assistant of the National Creative Research Initiative Center for Research On Program Analysis System. His research interest has been on static program analysis, program logics, and higher-order and typed languages. He is currently working on developing a tool for automatic generation of program analyzers. Kwangkeun Yi, Ph.D.: His research interest has been on semantic-based program analysis and systems application of language technologies. After his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories, where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995–2003, he was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since Fall 2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University. Kwang-Moo Choe, Ph.D.: He is a professor of Computer Science at Korea Advanced Institute of Science and Technology. He received his B.S. from Seoul National University in 1976, and his M.S. and Ph.D. from Korea Advanced Institute of Science and Technology in 1978 and 1984, respectively. For 1985–1986, he was a technical staff of AT&T Bell Labs at Murray Hill. His research interest is formal language theory, parallel evaluation of logic programs, and optimizing compilers.     

Programming Environment for Phase-Reconfigurable Parallel Programming on SuperNode

This paper presents a programming environment called C_—NET that we have developed for the reconfigurable SuperNode multiprocessor. It shows how one can take advantage of the environment to implement phase-reconfigurable programs. In the first stage a computing model is designed in relation with the capabilities of the hardware. Next, the entire programming environment is built upon this model. It is organized around a kernel language which has been extended in three separate directions so as to provide three specialized languages: PPL (phase programming language) for the development of phase-reconfigurable programs, GCL (graph-construction language) for the construction of processor graphs on which the phases are to be executed, and CPL (component programming language) for coding the software components that are to be executed on the processors within the phases. The second part of the paper provides an illustration of C_—NET. First, two implementations of the conjugate gradient algorithm within C_—NET are carried out: a phase-reconfigurable implementation and a fixed-topology one. Both have been developed on a 32-node machine. Next, a time model is built for both implementations. The time estimates yielded by the models are checked against time measurements issued from program runs. The time models are proved valid and are subsequently used for extrapolation purposes. The speed-up that could be achieved by executing the conjugate gradient algorithm on larger machines (up to 1024) is discussed ultimately.     

Object query optimization through detecting independent subqueries

The problem of query optimization in object-oriented databases is addressed. We follow the Stack-Based Approach to query languages, which employs the naming-scoping-binding paradigm of programming languages rather than traditional database concepts such as relational/object algebras or calculi. The classical environment stack is a semantic basis for definitions of object query operators, such as selection, projection/navigation, dependent join, and quantifiers. We describe a general object data model and define a formalized OQL-like query language SBQL. Optimization by rewriting concerns queries containing so-called independent subqueries. It consists in detecting them and then factoring outside loops implied by query operators. The idea is based on the formal static analysis of scoping rules and binding names occurring in a query. It is more general than the classical pushing selections/projections before joins.     

Basic constructs of the SIM operating system

The basic constructs of SIMPOS (Sequential Inference Machine Programming and Operating System) are explained. SIMPOS is an operating system for a super-personal computer (SIM), based on logic programming language (a modified Prolog, called KL0). Our design principle is simplicity both in concept and structure. The entire system will be constructed using these basic constructs.     

Type Checking for JavaScript

JavaScript is a powerful imperative object based language made popular by its use in web pages. It supports flexible program development by allowing dynamic addition of members to objects. Code is dynamically typed: a runtime access to a non-existing member causes an error.We suggest a static type system for JavaScript that will detect such type errors. Therefore, programmers can benefit from the flexible programming style offered by JavaScript and from the safety offered by a static type system.We demonstrate our type system with a formalism of JavaScript, JS₀. Our types are structural. Members of an object type are classified into definite and potential. A potential member becomes definite upon assignment. We outline a proof that our type system is sound.     

An approach to genuine dynamic linking

This paper describes a new approach to dynamic link/unlink editing. The basis of this approach is a library of link editing functions that can add compiled object code to or remove such code from a process any time during its execution. Loading modules, searching libraries, resolving external references, and allocating storage for global and static data structures are all performed at run time. This approach provides the efficiency of native machine code execution along with the flexibility to modify a program during its execution, thereby making many new applications possible. This paper also describes three sample applications of these dynamic link editing functions: program customization, incremental program development, and support for debugging and testing. A prototype of this approach is implemented under UNIX as a library package called dld for the C programming language and is available for VAX, Sun 3 and SPARCstation machines.     

Extending Java to dynamic object behaviors

Class inheritance and dynamic binding are the key features of object-oriented programming and they permit designing and developing complex systems. However, standard class inheritance is essentially static and cannot be directly employed for modeling dynamic object behaviors. In this paper we propose a linguistic extension of Java, called Dec-Java, that is partially inspired by the decorator design pattern. This extension permits easily separating the basic features of objects (that are likely not to change during the application) from their behaviors (that, instead, can be composed dynamically at run-time). Thus, Dec-Java enables a dynamic extension and specialization of object responsibilities.     

Object-oriented Tree Traversal with JJForester

We want to use the advanced language processing technology available in the asf+sdf Meta-Environment in combination with general purpose programming languages. In particular, we want to combine the syntax definition formalism sdf and the associated components that support generalized LR parsing, with the object-oriented language Java. To this end, we implemented JJForester, a tool that generates class structures from sdf grammar definitions. The generated class structures implement a number of design patterns to facilitate construction and traversal of parse trees represented by object structures. In a detailed case study, we demonstrate how program analyses and transformations can be constructed with JJForester.     

An Extensible Encoding of Object-oriented Data Models in hol

We present an extensible encoding of object-oriented data models into higher-order logic (hol). Our encoding is supported by a datatype package that leverages the use of the shallow embedding technique to object-oriented specification and programming languages. The package incrementally compiles an object-oriented data model, i. e., a class model, to a theory containing object-universes, constructors, accessor functions, coercions (casts) between static types (and providing a foundation for the notion of dynamic types), characteristic sets, and co-inductive class invariants. The package is conservative, i. e., all properties are derived entirely from constant definitions, including the constraints over object structures. As an application, we use the package for an object-oriented core-language called imp++, for which we formally prove the correctness of a Hoare logic with respect to a denotational semantics.     

Circular attribute grammars with remote attribute references and their evaluators

Attribute grammars (AGs) are a suitable formalism for the development of language processing systems. However, for languages including unrestricted labeled jumps, such as “goto” in C, the optimizers in compilers are difficult to write in AGs. This is due to two problems that few previous researchers could deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposescircular remote attribute grammars (CRAGs), an extension of AGs that allows (1) direct relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2) circular dependencies, under certain conditions including those that arise from remote references. This extension gives AG programmers a natural means of describing language processors and programming environments for languages that include any type of jump structure. We also show a method of constructing an efficient evaluator for CRAGs called amostly static evaluator. The performance of the proposed evaluator has been measured and compared with dynamic and static evaluators. Akira Sasaki: He is a research fellow of the Advanced Clinical Research Center in the Institute of Medical Science at the University of Tokyo. He received his BSc and MSc from Tokyo Institute of Technology, Japan, in 1994 and 1996, respectively. His research interests include programming languages, programming language processors and programming environments, especially compiler compilers, attribute grammars and systematic debugging. He is a member of the Japan Society for Software Science and Technology. Masataka Sassa, D.Sc.: He is Professor of Computer Science at Tokyo Institute of Technology. He received his BSc, MSc and DSc from the University of Tokyo, Japan, in 1970, 1972 and 1978, respectively. His research interests include programming languages, programming language processors and programming environments, currently he is focusing on compiler optimization, compiler infrastructure, attribute grammars and systematic debugging. He is a member of the ACM, IEEE Computer Society, Japan Society for Software Science and Technology, and Information Processing Society of Japan.