Publications

• Yu David Liu, Scott Smith. Pedigree Types. To appear in International Workshop on Aliasing, Confinement and Ownership in Object-Oriented Programming (IWACO). Paphos, Cyprus. July 2008.

Abstract   Pedigree Types are an intuitive ownership type system requiring minimal programmer annotations. Reusing the vocabulary of human genealogy, Pedigree Types programmers can qualify any object reference with a pedigree -- a child, sibling, parent, grandparent, etc -- to indicate what relationship the object being referred to has with the referant on the standard ownership tree, following the owners-as-dominators convention. Such a qualifier serves as a heap shape constraint that must hold at run time and is enforced statically. Pedigree child captures the intention of encapsulation, i.e. ownership: the modified object reference is ensured not to escape the boundary of its parent. Among existing ownership type systems, Pedigree Types are closest to Universe Types. The former can be viewed as extending the latter with a more general form of pedigree modifiers, so that the relationship between any pair of objects on the aforementioned ownership tree can be named and -- more importantly -- inferred. We use a constraint-based type system which is proved sound via subject reduction. Other technical originalities include a polymorphic treatment of pedigrees not explicitly specified by programmers, and use of linear diophantine equations in type constraints to enforce the hierarchy.

• Yu David Liu, Xiaoqi Lu, Scott Smith. Coqa: Concurrent Objects with Quantized Atomicity. In Proceedings of the 2008 International Conference on Compiler Construction (CC'08). Budapest, Hungary. March 2008.

Abstract   This paper introduces a new language model, Coqa, for deeply embedding concurrent programming into objects. Every program written in our language has built-in the desirable behaviors of atomicity, mutual exclusion, and race freedom. Such a design inverts the default mode of e.g. Java, where programmers may write programs highly vulnerable to surprising runtime errors if they do not take advantage of synchronized blocks and other advanced concurrency features. Coqa takes advantage of basic object-oriented notions to express important concurrent programming primitives, resulting in a powerful but concise model that includes thread creation, shared object access and open nesting. A key property of our model is the notion of quantized atomicity: all concurrent program executions can be viewed as being divided into quantum regions of atomic execution, greatly reducing the number of interleavings to consider. The language design draws from different schools of concurrent language design, especially Actors, and constructs a unified design close to mainstream object-oriented programming practice. We justify our approach both from a theoretical basis by showing that a formal representation, CoqaKernel, has provable quantized atomicity properties, and by implementing CoqaJava, a Java extension incorporating all of the Coqa features.

• Yu David Liu, Scott Smith. A Formal Framework for Component Deployment. In Proceedings of the 21st Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA'06). Portland, Oregon, USA, October 2006.

Abstract   Software deployment is a complex process, and industrial-strength frameworks such as .NET, Java, and CORBA all provide explicit support for component deployment. However, these frameworks are not built around fundamental principles as much as they are engineering efforts closely tied to particulars of the respective systems. Here we aim to elucidate the fundamental principles of software deployment, in a platform-independent manner. Issues that need to be addressed include deployment unit design, when, where and how to wire components together, versioning, version dependencies, and hot-deployment of components. We define the application buildbox as the place where software is developed and deployed, and define a formal Labeled Transition System (LTS) on the buildbox with transitions for deployment operations that include build, install, ship, and update. We establish formal properties of the LTS, including the fact that if a component is shipped with a certain version dependency, then at run time that dependency must be satisfied with a compatible version. Our treatment of deployment is both platform- and vendor-independent, and we show how it models the core mechanisms of the industrial-strength deployment frameworks.

• Yu David Liu, Scott Smith. Interaction-Based Programming with Classages. In Proceedings of the 20th Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA'05). San Diego, California, USA, October 2005.

Abstract   This paper presents Classages, a novel interaction-centric object-oriented language. Classes and objects in Classages are fully encapsulated, with explicit interfaces for all interactions they might be involved in. The design of Classages touches upon a wide range of language design topics, including encapsulation, object relationship representation, and object confinement. An encoding of Java's OO model in Classages is provided, showing how standard paradigms are supported. A prototype Classages compiler is described.

• Yu David Liu, Scott Smith. Modules with Interfaces for Dynamic Linking and Communication. In Proceedings of the 18th European Conference on Object-Oriented Programming (ECOOP'04). Oslo, Norway, June 2004.

Abstract  Module systems are well known as a means for giving clear interfaces for the static linking of code. This paper shows how adding explicit interfaces to modules for 1) dynamic linking and 2) cross-computation communication can increase the declarative nature of modules, and build a stronger foundation for language-based security and version control. We term these new modules Assemblages. We additionally develop a sound constraint-based type system particularly suited to a module system supporting bounded type parametricity, cross-module type recursion, and polymorphic type binding during dynamic linking and cross-computation communication.

• Yu David Liu, Scott Smith, Andreas Terzis, A High-level Language for Sensor Networks.Technical Report of The Johns Hopkins University. Baltimore, Maryland, USA June 2004.

Abstract In this paper we describe Ensemble, a proposed language framework for sensor network programming. Our goal is to provide a programming framework to scientists and engineers that will allow them to directly code sensor network applications, without the need for expertise in low-level device programming. The key concepts in Ensemble are high-level communication protocol connectors, and the ability for systems programmers to define new communication protocols as metaprotocol extensions.

• Yu David Liu, Ran Rinat, Scott Smith. Component Assemblies and Component Runtimes. Technical Report of The Johns Hopkins University. Baltimore, Maryland, USA March 2003.

Abstract This paper proposes a component programming language that supports an integrated notion of both compile-time and run-time component. The centerpiece of this paper is the static, compile time notion of assembly, complementing our previous work on the dynamic, runtime notion of cell. An assembly is a declarative, stateless piece of code that facilitates code combination. It offers explicit typed interfaces to outsiders, called linkers, which can be used to link smaller assemblies into bigger, compound assemblies. Each assembly may in turn be loaded at run-time, producing a cell in the runtime environment. A cell is a dynamic, stateful component that interacts with other cells via explicit runtime interfaces. Thus, the static assemblies and the dynamic cells are fully integrated. 

• Yu David Liu, Scott Smith. A Component Security Infrastructure. Foundation of Computer Security Workshop. Copenhagen, Denmark, July 2002.

Abstract  This paper defines a security infrastructure for access control at the component level of programming language design. Distributed components are an ideal place to define and enforce significant security policies, because components are large entities that often define the political boundaries of computation. Also, rather than building a security infrastructure from scratch, we build on a standard one, the SDSI/SPKI security infrastructure.

• Older Publications in Chinese.