Introduction

Underneath the Java hype, there is substance: a language that is relatively easy to learn and use, that provides a modicum of portability and a general-purpose GUI library, and that lets one attach interactive programs to web pages [AG96,GJS96].

One of the strengths of Java is that it is a relatively simple design. Arguably, it is too simple on at least two counts, as it omits two widely useful programming language features.

• Parametric polymorphism : the ability to parameterize classes over types, similar to (but safer than) templates in C++.
• Higher-order functions : the ability to treat functions as values.

There are also some features which, while not general purpose, are convenient for certain applications.

• Algebraic data types : a convenient way of representing trees with support for pattern matching, providing advantages similar to the well-known `Composition' and `Visitor' design patterns.
• Tail calls : don't grow the stack when the last operation in one methods is to call another method; this enables one to replace iteration by recursion, and makes it easy to simulate finite-state machines.

Pizza is a superset of Java that includes these four features. Pizza contains Java as a subset, interworks smoothly with Java, and compiles into the Java Virtual Machine (JVM): so it runs wherever Java runs, including web browsers. Pizza is freely available from the Pizza website.

http://www.cs.bell-labs.com/~wadler/pizza

The Pizza compiler can be used to translate Pizza into Java or to generate Java Virtual Machine code directly.

The Java designers themselves have accepted the arguments that higher-order functions and parametric polymorphism are a good thing. The new Java 1.1 release includes inner classes , which provide similar functionality to higher-order functions. And there is a mailing list moderated by Sun to discuss ways of adding parametric types to Java, and the Pizza designers are engaged in dialogue with the Java designers about how to smoothly extend Java to include parametric polymorphism. Pizza was originally designed based on Java 1.0; the new version supports full Java 1.1 (including inner classes) and also supports higher-order functions directly. The higher-order functions are slightly less flexible than inner classes, but are easier to use and have a more efficient implementation.

Pizza features are defined by translation into Java. The Pizza compiler also produces JVM output directly, for convenience. However, the Java language and the JVM support pretty much exactly the same abstractions, so little is lost by translating Pizza into Java and thence into the JVM rather than compiling to the JVM directly.

The Pizza compiler is itself implemented in Pizza, and was written by Martin Odersky. Since Pizza contains Java as a subset, it can be used as a replacement for a Java compiler. It accepts files with either the pizza or java extension, and in the latter case accepts only legal Java, disabling the Pizza extensions. Further, it takes less time to compile Java programs than Sun's own javac compiler.