Walid Taha - US grants

Techniques such as program generation, partial evaluation, just-in-time compilation, and run-time code generation respond to the need for general purpose programs which do not pay unnecessary
run-time overheads. The thesis of this project is that a uniform, principled, high-level, and practical view of these diverse techniques is possible through multi-stage programming, a novel paradigm for the development of maintainable, high-performance software. The key idea in multi-stage programming is the use of simple, high-level annotations to allow the programmer to break down the cost of a computation into distinct stages.

The goal of this proposal is to demonstrate that the theoretical machinery that has been developed for multi-stage programming can be put to work. This project will involve the development of compilers
of multi-stage programming languages, addressing both practical and theoretical problems that arise in the development of such systems, and using these compilers in interesting applications ranging from dynamic programming algorithms and rewriting systems to implementations of domain specific programming languages.

CCR-0215394
GC: A merger of the workshops on Generative and Component-based Software Engineering (GCSE) and on the Semantics, Applications and Implementation of Program Generation (SAIG)
Walid M. Taha, Yale University, P.I.

This document requests funding in the amount of $9K for a pilot joint event of two previously independent workshops called GCSE and SAIG. Both GCSE and SAIG are forums for publishing research generative techniques. GCSE focuses on generative techniques from the software engineering point of view, and SAIG from the formal and programming languages point of view. The pilot joint event, called the First ACM SIGPLAN Conference on Generators and Components (GC'02) will be held in October 2002, in Pittsburgh, PA. The event will replace GCSE and SAIG this year. If this experiment is successful, the result will be a regular, three-day joint conference bringing the two communities in one consolidated forum.

Taha, Walid
CCR-0205542
"ITR: A Framework for Rapid Development of Reliable Robotics Software"

Robots are entering daily life. Commercially available systems are
delivering medication to patients in hospitals, mowing lawns, vacuuming
floors, and finding wide applications in the entertainment industry. In the future, they will play a more substantial role in areas such as space exploration, health care, and search and rescue. But as
these applications grow, so does the complexity of these robots, making
the reliability of their software and the productivity of their
programmers a priority. It is not clear that current techniques for
programming robots are sufficient for building systems that are orders of magnitude more complex than the ones available today. The vast majority of programming methods in current use focus on high-level planning and task and behavioral aspects. By contrast, there are no widely-accepted specialized software processes or programming languages for the integrated development of robotics applications.

This project explores the impact of state-of-the-art programming languages techniques in a small-scale robotics setting. The project applies domain-specific languages methods and automatic program generation techniques. The framework exploits core technologies such as multi-stage programming with simple, high-level annotations
to avoid unnecessary runtime overheads yet provide a natural and algorithmic approach to program generation, where generation occurs in a first stage, and the execution of the synthesized program occurs in a second stage. Because (even when the final goal is embedded software) the first stage does not need to be resource-bounded, conventional programming techniques can be used.

The challenge, then, becomes ensuring that the generated programs are suitable for execution on an embedded platform. Multi-stage languages already provide significant safety guarantees. For example, a program generator written in such a language not only is type-safe in the traditional sense, but we are guaranteed that any generated program will also be type safe. This provides a noteworthy degree of assurance about the quality of the generated code. But like most traditional high-level programming techniques, multi-stage programming was designed to satisfy functional requirements rather than operational ones, and existing multi-stage languages do not provide any guarantees about the behavior of programs in the presence of bounded resources. The focus of this project is ways to address this problem by strengthening
``traditional'' multi-stage type systems using a number of state-of-the-art techniques from type theory and functional reactive programming (FRP) to create resource-aware multi-stage programming. Linear and alias types (in conjunction with dependent typing) will be used to ensure space-boundedness, new typing techniques are used to ensure time-boundedness, and signals and behaviors from FRP allow for a natural style of reactive programming.

Some of the most exciting cyber technologies on the research horizon involve sophisticated digital systems that interact with the physical world. Examples include remote surgery, physical manipulation of nano-structures, autonomous (ground and air) vehicular travel, and space and terrestrial exploration. Because such applications interact directly with the physical world, it is imperative their physical safety be assured. This project is developing a comprehensive formal framework for producing controllers for cyber-physical systems, with machine checkable proofs of their physical safety. The project brings together ideas from control theory, language design, program verification, program generation, software engineering, and real-time and embedded systems to build a framework that can be applied to challenging applications. The framework promotes an efficient, rigorous engineering process for producing embedded controllers, incorporating explicit models not only of the controller itself, but also of the physical context in which it operates, the required stability conditions, the platform on which it will run, and the associated real-time constraints. The results of the project are being demonstrated and evaluated in the context of a tele-surgery application. This application is currently being developed at the Mechatronics and Haptic Interfaces Lab in the Mechanical Engineering Department at Rice University.

Proposal Number 0747431
TITLE CAREER: Multi-stage Programming for Object-Oriented Languages

PI Walid Taha, Rice University

Over the past decade, multi-stage programming (MSP) has emerged as a unifying approach that captures the disciplined essence program generation. Early work on MSP focused on purely functional languages. The goal of this proposal is to put what we know about MSP to work in the context of mainstream languages such as Java and C#. This will be achieved by means of carefully designed, minimal extensions that provide an expressive, statically checked mechanism for effectively eliminating the interpretive overhead.

The project will design an object-oriented language that provides statically checked support for the writing of program generators. The language, called The Java Program Mint (Mint) will support:

1. Staging constructs that are statically checked before expansion/generation,

2. Indexed types, to enable further optimizations that are particularly synergistic with staging, and

3. Disciplined, statically typed compile-time computation.

The design of Mint will be evaluated by establishing formal safety and expressivity results, and the implementation will be evaluated by building demonstration applications. The novel features of Mint will have the most impact on applications that use reflection and that constitute domain-specific language (DSL) extensions, such as serializers, JavaBeans customization facilities, and synchronization libraries.

In many important situations, analytically predicting the behavior of physical systems is not possible. For example, the three dimensional nature of physical systems makes it provably impossible to express closed-form analytical solutions for even the simplest systems. This has made experimentation the primary modality for designing new cyber-physical systems (CPS). Since physical prototyping and experiments are typically costly and hard to conduct, "virtual experiments" in the form of modeling and simulation can dramatically accelerate innovation in CPS. Unfortunately, major technical challenges often impede the effectiveness of modeling and simulation. This project develops foundations and tools for overcoming these challenges. The project focuses on robotics as an important, archetypical class of CPS, and consists of four key tasks: 1) Compiling and analyzing a benchmark suite for modeling and simulating robots, 2) Developing a meta-theory for relating cyber-physical models, as well as tools and a test bed for robot modeling and simulation, 3) Validating the research results of the project using two state-of-the-art robot platforms that incorporate novel control technologies and will require novel programming techniques to fully realize their potential 4) Developing course materials incorporating the project's research results and test bed.

With the aim of accelerating innovation in a wide range of domains including stroke rehabilitation and prosthetic limbs, the project is developing new control concepts and modeling and simulation technologies for robotics. In addition to new mathematical foundations, models, and validation methods, the project will also develop software tools and systematic methods for using them. The project trains four doctoral students; develops a new course on modeling and simulation for cyber-physical systems that balances both control and programming concepts; and includes an outreach component to the public and to minority-serving K-12 programs.