Amit's Research Projects

I'm working towards a Ph.D. in Computer Science at Stanford University. This page is intended to be school-related, while my other home page has more about my personal life and my non-school-related activities (such as writing computer games).

Address

Gates 4B
Computer Science Department
Stanford University
Stanford, CA 94305-9045, USA

Advisor

My advisor is John Mitchell, who studies programming languages and computer security. For several years I was a teaching assistant for his course, Introduction to Programming Languages.

Projects

Objects in ML

The biggest project I'm working on is Obstacl, an attempt to add object-oriented features to ML, while keeping in mind the needs of programmers, and at the same time keeping in mind the flavor of ML.

By studying design patterns and general program design issues, we found that we could express many common patterns with just two (fairly simple) language features. These language features turned out to be interesting on their own, and you can read about one of them (mixins) in a paper I've made available on the web (see below).

It turns out that ML (and other high level languages) have features that can be used as building blocks for objects. Encapsulation and dynamic lookup (polymorphism) are already present in ML, and inheritance and subtyping are not too difficult to add. We were able to add to the language object-related constructs that did not intrude on the functionality provided by existing features. As a result the added features (classes and objects) are simpler than those in many other languages. For example, our classes do not provide functionality associated with modules, because ML already has modules. Our objects do not have to provide new semantics for dynamic lookup because ML already supports it.

In addition to the practical aspects of using a language for programming, I worked with Viviana Bono and Vitaly Shmatikov on an extension of lambda calculus that could express the basic constructs in Obstacl.

I've also investigated the implementation issues involved, and designed run-time data structures for classes and objects that balance small size overheads, small time overheads, and modularity. Unlike C++, our classes can be linked together using inheritance at link time, so they can be put into dynamically linked modules and updated in ways that would break C++ class updates. (For example, we can add new private fields to a base class, and derived classes do not have to be recompiled.)

Object Calculi

Many times when proposing a language feature, it is worth analyzing it formally. The formal analysis often brings up dark corners that may lead to problems. Alternatively, it may be clean and beautiful---evidence that the feature is nice in theory. For our ML objects, we have written some calculi to analyze the features we want to add to ML. During the analysis, we discovered that these features could be added to other languages as well---by boiling down the extensions to the absolute core, we saw that they were not dependent on ML, even though ML made them easier to implement. In particular, mixins may be a welcome alternative to multiple inheritance in many new object-oriented languages, not only in Obstacl.

The main result of our calculi papers is that when we consider classes to be basic features, rather than simulated using objects, and when we consider imperative object languages, rather than functional object languages, we get a much simpler system. The object calculus community probably is not interested in this work but we considered it important to preserve and analyze the style of programming used in real programs, instead of a different style of programming valued in the programming language community.

We also included forms of modularity that programmers generally want in larger systems. For example, a subclass does not have to be recompiled if only private fields in the superclass are changed. Clients do not have to be recompiled if only protected methods are changed or if new methods are added. Also, we include modular object creation (using constructors) instead of requiring the user to initialize all the fields after an object is created. Many of these goals are taken for granted in the programming community, but not always in the language community, so we included them in our calculus to ensure that the simplicity of our system was not the result of leaving our important modularity issues.

Mixins are a powerful program-structuring tool. Imagine a scenario in which you have a Stream interface, a File class implementing that interface, and an EncryptedFile subclassing from File. Now suppose you want to encrypt a network stream instead. What would you do? You could restructure your program so that File and Encryption are unrelated classes, but there's an alternative: mixins. You can change the class from EncryptedFile extends File to [For Any stream class S]: Encrypted extends S. Now EncryptedFile is simply Encrypted @ File. (I would use something other than @ but for web pages, @ seemed simplest.) You can also make an encrypted network stream with Encrypted @ Socket. You can simulate many useful forms of multiple inheritance by simply applying more than one mixin: Encrypt @ Compress @ UUEncode @ PGPSign @ File is a class that encrypts, compresses, uuencodes, and then signs data that is being written into a file. (If you are a Unix hacker, you may find this similar to combining filters at the command line through pipes.) In addition, you can do some things that are hard to do with multiple inheritance, like apply a mixin more than once: Encrypt @ Encrypt @ File is a class of doubly-encrypted files! (Note however that doubly encrypted files typically aren't any more secure; it's just a nice example of what you can do with mixins.) With mixins it's easy to control the order and number of times mixins are applied. The paper listed above explains the semantics of mixins and the issues with type checking them. We also have a nice way to compile them (just once, unlike C++ templates), which probably won't appear in print until I write my thesis.

Web Proxy

For some time I worked on a web proxy that modified Java bytecode as it was sent from the web server to the web browser. The modified applet was restricted from certain activities, such as opening too many windows on the screen at once. These hostile applets are not doing anything that violates the type system or security checks made by the virtual machine, but instead they are using annoying or misleading behavior to potentially learn secure information or cause damage to the user's machine.

Insik Shin added a user interface applet to control the behavior of the proxy. In addition, he used the proxy to modify Java bytecode so that it would bring up a window that let the user control (i.e., abort) annoying behavior. For example, the proxy modifies any applet that plays sounds so that along with each sound, there is a small pop-up window that lets the user stop or restart the sound.

The web proxy is part of the Pleiades Project.

As of January 1999, my Python proxy is no longer being used for research purposes. My proxy was being used as the prototype for a new proxy (written in Java), which will be used for research on mobile code. Jun Zhai wrote a proxy core, with support for multiple users and more advanced Java monitoring. Vijay Ganesh worked on a framework for Java filtering. I am still working on the Python version to improve it for personal use. Version 3 is far more modular, and somewhat more reliable. Version 3.5 supports more general web page transformation (for example, turning Slashdot from green on white to blue on gray, or rearranging table elements on Excite's page), more interfaces (curses and Gtk), and DNS pre-fetching (scanning a page for hostnames and performing DNS lookup on them before the browser needs it). In February 2000, I started working on version 4, which supports HTTP/1.1 (persistent connections, chunking, compressed HTML). I hope to add caching, pre-fetching, history (including searching pages you've visited recently), and more HTML modifications, such as highlighting words, rearranging tables, and installing style sheets to improve readability.

Java Bytecode Verifier

I was also involved in a project to "compile" type rules for Java bytecode into a Java bytecode verifier. See Stephen Freund's home page for some details about the type rules. I am not actively working on the project at this time.

Papers

Essays

I've learned so much while at Stanford, and I hope to write some of it down. I've started a list but I haven't gotten very far:

Something I'd like to do is write down how the Internet has transformed my life. I can't imagine life without it anymore.


Last modified 19:49 Fri 07 Dec 2001 , Amit Patel