Lambda the Ultimate

"The reason I came over to Utrecht, if you must know the truth, is because I could not understand what was going on in current Categorial Grammar. I had this stack of papers...... and I just couldn't get through them on my own. Coming here I realized the benefit of immersing yourself in a particular culture. I volunteered to teach this material, amongst a group of people many of whom knew it better than me. I think I've come to the point where I'm up to the state-of-the-art level of knowledge." Bob Carpenter Ta! Interview

Does anyone know the history and reasons behind this consistency of approach at Utrecht (and the Netherlands in general) to linguistics (natural languages) and programming languages? (involving algebra and logic that is)

There is a similarity in their approach to And also note the applicability of a lot of this algebraic-functional approach to parsing to computational linguistics and natural language. Anyone

Note that the implementation of parser combinators (and any code with a functional smell) in Java will become much more attractive with the addition of parameterized types/generics to the Java language.

The conclusion of this paper mentions the problem of the weak type-system of Java, which forces the parser combinators to work just on java.lang.Objects. The parameterized types allows you to parameterize a function (which is represented as a class) with its argument and result. This makes functional like code in Java quite attractive (although still disgusting verbose of course).

However, I assume there is not a lot of performance gain in Java, because generics are not available in Java Bytecode and information on the parameters is not available at runtime. In C# and .NET this will be much better. I'm looking forward to a parser combinator library that exploits generics in Java or C#.

Unfortunately I'm not aware of any historical reasons why there is so much work in functional programming going on at the University of Utrecht. I'm a student over there, and indeed there is a high interest in functional programming in Utrecht. Our one and only course on parsing and grammars is even based on parser combinators in Haskell ;-) .

I am not sure I follow. Are you talking time or space efficiency?

Compiling by erasure can make generic code be as efficient as type specific code. Or do you have something else in mind.

I was wondering about that myself. I would guess it is mostly beacuse of the impact of a few scholars, but I'd love to hear some inside information...

If the casts have a serious impact on the performance of the parser combinators, I think the performance of this approach could be better in a future .NET version, with generics in the IL and .NET CLR. Maybe a JVM could remove unnecassary casts.

For example, in Ada I can have a Stack package which is parameterized over all item types. When I instantiate the package for integers, I get a package that is identical to an integer specific version of the stack package. This works no matter what the machine code is.

Obviously, if the casts are required because the client code uses Object to interface with your code, you are out of luck.

In general I must agree with you of course :) .

Quel dommage.

I was wondering what were the motivations for choosing this approach. Does anyone know?

Unfortunately I cannot figure out exactly why they've chosen the current solution. To me there seems to be some conflicts between te jsr 14 goals and the current public draft that is available for this jsr 14. The goals seem more ambitious to me. Most decisions are based on the huge amount of legacy code for the Java Platform or problems related to modification of the JVM. Therefore I think it was a huge mistake not to include .NET generics in the first release of .NET.

public draft of jsr 14: The proposed extension is designed to be fully backwards compatible with the current language, making the transition from non-generic to generic programming very easy. In particular, one can retrofit existing library classes with generic interfaces without changing their code.

In essence this means that you can use existing libraries as if they where parameterized. Although I understand the goals, I think this sucks. A class is parameterized or a class is not parameterized. The result of this goal is illustrated by the early access compiler that is available: you have to compile against 'stubs' for the Java Collections. These classes do not contain an implementation. At runtime the current, not parameterized, classes can be used. Of course this is great at the moment because you can use generics without requiring a new JVM, but is it worth it?

Some goals of the JSR:

G4) Simplicity. Keep it simple for users, but not necessarily for implementors: It's okay to place a larger burden upon VM and compiler implementors (within reason) if that will make generics more natural and easy to use.

Well, that sounds good to me. Now hope that they will bring this into practice.

G7) First class generics. Types involving parameters should be first-class types. This goal consists of several subsidiary goals: a) Instantiated parameterized types (e.g., List) should be first-class types.<br/> b) Type parameters (e.g., T) should be first-class types. (A consequence of this is that List is a first class type).<br/> By "first-class" we mean that these new sorts of type expressions can be used in exactly the same ways as existing type expressions. In particular, it should be possible to cast a value expression to one of these sorts of types, and to test whether an object is an instance of such a type.

I doubt whether this goal is completely satisfied by the current proposal. If the types are really first class, I would expect to be able to create a new instance of this type or pass the class to some method, which is not possible.

public draft: To facilitate interfacing with non-generic legacy code, it is also possible to use as a type the erasure of a parameterized class without its parameters. Such a type is called a raw type. Variables of a raw type can be assigned from values of any of the type's parametric instances. For instance, it is possible to assign a Vector<String> to a Vector. The reverse assignment from Vector to Vector<String> is unsafe from the standpoint of the generic semantics (since the vector might have had a different element type), but is still permitted in order to enable interfacing with legacy code. In this case, a compiler will issue a warning message that the assignment is deprecated.

Maybe great from the practical point of view: interaction with legacy code is possible, but imho this really sucks from a formal point of view.

NextGen is somewhat better. There are rumours that Java generics will be extended to NextGen in a future more complete revision of the Java Platform. I doubt whether this two fase introduction of generics is a good idea.

NextGen paper: NextGen is a more ambitious extension of Java, based on the same source language as GJ, developed by Cartwright and Steele that overcomes the limitations of GJ by introducing a separate Java class for each distinct instantiation of a generic type; all generic type information is preserved by the compiler and is available at run-time. Hence, type dependent operations are fully supported by NextGen. On the other hand, NextGen retains essentially the same level of compatibility with legacy code as GJ. For these reasons, we believe that NextGen could serve as the basis for an important step forward in the evolution of the Java programming language.

A few more links that might be interesting: Java Generics report.

There is also a presentation on generics for .NET that compares the approach chosen by .NET with the various proposals for Java. You can find some links at my overview of .NET resources. There is also a link to a paper.

(sorry for the long message ;) )